# Riemannian Langevin Algorithm for Solving Semidefinite Programs

arXiv: https://arxiv.org/abs/2010.11176 · HTML: https://mlsanity.com/paper/2010.11176/

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Oct 2020.

## Built on by (most cited first, 22 of 22)

- [Faster high-accuracy log-concave sampling via algorithmic warm starts](https://mlsanity.com/paper/2302.10249/) (2023)
- [Spherical Sliced-Wasserstein](https://mlsanity.com/paper/2206.08780/) (2022)
- [Towards a Complete Analysis of Langevin Monte Carlo: Beyond Poincar'e Inequality](https://mlsanity.com/paper/2303.03589/) (2023)
- [Convergence of the Riemannian Langevin Algorithm](https://mlsanity.com/paper/2204.10818/) (2022)
- [Resolving the Mixing Time of the Langevin Algorithm to its Stationary Distribution for Log-Concave Sampling](https://mlsanity.com/paper/2210.08448/) (2022)
- [Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with Variance Reduction and its Application to Optimization](https://mlsanity.com/paper/2203.16217/) (2022)
- [Learning Multi-Index Models with Neural Networks via Mean-Field Langevin Dynamics](https://mlsanity.com/paper/2408.07254/) (2024)
- [Fast sampling from constrained spaces using the Metropolis-adjusted Mirror Langevin algorithm](https://mlsanity.com/paper/2312.08823/) (2023)
- [Fluctuation without dissipation: Microcanonical Langevin Monte Carlo](https://mlsanity.com/paper/2303.18221/) (2023)
- [Taming under isoperimetry](https://mlsanity.com/paper/2311.09003/) (2023)
- [Tamed Langevin sampling under weaker conditions](https://mlsanity.com/paper/2405.17693/) (2024)
- [Efficient Sampling on Riemannian Manifolds via Langevin MCMC](https://mlsanity.com/paper/2402.10357/) (2024)
- [Sampling and estimation on manifolds using the Langevin diffusion](https://mlsanity.com/paper/2312.14882/) (2023)
- [Mean-Square Analysis of Discretized Ito Diffusions for Heavy-tailed Sampling](https://mlsanity.com/paper/2303.00570/) (2023)
- [Non-Log-Concave and Nonsmooth Sampling via Langevin Monte Carlo Algorithms](https://mlsanity.com/paper/2305.15988/) (2023)
- [R'enyi-infinity constrained sampling with d3 membership queries](https://mlsanity.com/paper/2407.12967/) (2024)
- [Polynomial Convergence of Riemannian Diffusion Models](https://mlsanity.com/paper/2601.02499/) (2026)
- [Improved Algorithms for Differentially Private Language Model Alignment](https://mlsanity.com/paper/2505.08849/) (2025)
- [Higher Order Generalization Error for First Order Discretization of Langevin Diffusion](https://mlsanity.com/paper/2102.06229/) (2021)
- [Riemannian Langevin Monte Carlo schemes for sampling PSD matrices with fixed rank](https://mlsanity.com/paper/2309.04072/) (2023)
- [Langevin Multiplicative Weights Update with Applications in Polynomial Portfolio Management](https://mlsanity.com/paper/2502.19210/) (2025)
- [Functional Stochastic Localization](https://mlsanity.com/paper/2602.03999/) (2026)

## Abstract (arXiv)

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 widetildeOmega( ε-5 ) iterations.