Harnessing Structure in Discrete and Non-convex optimization with applications in online learning, multi-agent systems, and phase retrieval