How Well Do Local Algorithms Solve Semidefinite Programs?

Zhou Fan, Andrea Montanari

Several probabilistic models from high-dimensional statistics and machine learning reveal an intriguing --and yet poorly understood-- dichotomy. Either simple local algorithms succ…