Riemannian Langevin Algorithm for Solving Semidefinite Programs
We propose a Langevin Markov chain Monte Carlo (MCMC) algorithm for sampling and non-convex optimization on a product manifold of spheres. Under a logarithmic Sobolev inequality, we establish a quantitative convergence bound 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. Furthermore, we establish a logarithmic Sobolev inequality for potential functions without spurious local minima, but under the presence saddle points. For an application, we provide a global optimality guarantee for solving the Burer-Monteiro relaxation of semidefinite programs.