Riemannian Langevin Algorithm for Solving Semidefinite Programs
Speaker:
Mufan Li, University of Toronto
Date and Time:
Friday, April 23, 2021 - 2:00pm to 2:15pm
Location:
Online
Abstract:
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.