论文标题
Riemannian Langevin算法用于求解半决赛程序
Riemannian Langevin Algorithm for Solving Semidefinite Programs
论文作者
论文摘要
我们提出了一种基于langevin扩散的算法，以在球体的产物歧管上进行非凸优化和采样。在对数Sobolev不平等的情况下，我们根据Kullback-Leibler Divergence建立了有限的迭代迭代收敛到Gibbs分布的保证。我们表明，有了适当的温度选择，可以保证，次级最小值的次数差距很小，概率很高。 作为一种应用，我们考虑使用具有对角约束的半决赛程序（SDP）的burer- monteiro方法，并分析提出的langevin算法以优化非convex目标。特别是，我们为Burer建立了对数Sobolev的不平等现象 - 当没有虚假的当地最小值时，但在存在鞍点的情况下。结合结果，我们为SDP和最大切割问题提供了全局最佳保证。更确切地说，我们表明，langevin算法在$ \widetildeΩ（ε^{ - 5}）$迭代中实现了$ε$精度。
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.
