Riemannian Langevin Algorithm for Solving Semidefinite Programs
This provides a theoretical guarantee for solving SDPs via non-convex optimization, which is incremental as it builds on existing Langevin and Burer-Monteiro methods.
The authors tackled non-convex optimization on manifolds by proposing a Riemannian Langevin algorithm, showing it achieves ε accuracy with high probability in approximately ε^{-5} iterations for solving semidefinite programs and the Max-Cut problem.
We propose a Langevin diffusion-based algorithm for non-convex optimization and sampling on a product manifold of spheres. Under a logarithmic Sobolev inequality, we establish a guarantee for finite iteration convergence to the Gibbs distribution in terms of Kullback--Leibler divergence. We show that with an appropriate temperature choice, the suboptimality gap to the global minimum is guaranteed to be arbitrarily small with high probability. As an application, we consider the Burer--Monteiro approach for solving a semidefinite program (SDP) with diagonal constraints, and analyze the proposed Langevin algorithm for optimizing the non-convex objective. In particular, we establish a logarithmic Sobolev inequality for the Burer--Monteiro problem when there are no spurious local minima, but under the presence saddle points. Combining the results, we then provide a global optimality guarantee for the SDP and the Max-Cut problem. More precisely, we show that the Langevin algorithm achieves $ε$ accuracy with high probability in $\widetildeΩ( ε^{-5} )$ iterations.