# Global Convergence of Langevin Dynamics Based Algorithms for Nonconvex Optimization

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

## Key facts

- Cited by 97 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Jul 2017.

## Built on by (most cited first, 30 of 97)

- [Constrained Synthesis with Projected Diffusion Models](https://mlsanity.com/paper/2402.03559/) (2024)
- [Towards a Theory of Non-Log-Concave Sampling: First-Order Stationarity Guarantees for Langevin Monte Carlo](https://mlsanity.com/paper/2202.05214/) (2022)
- [Simultaneous Multi-Robot Motion Planning with Projected Diffusion Models](https://mlsanity.com/paper/2502.03607/) (2025)
- [Stable Neural Stochastic Differential Equations in Analyzing Irregular Time Series Data](https://mlsanity.com/paper/2402.14989/) (2024)
- [Alignment of Diffusion Models: Fundamentals, Challenges, and Future](https://mlsanity.com/paper/2409.07253/) (2024)
- [Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlo](https://mlsanity.com/paper/2305.18246/) (2023)
- [Time-independent Generalization Bounds for SGLD in Non-convex Settings](https://mlsanity.com/paper/2111.12876/) (2021)
- [Langevin Monte Carlo for Contextual Bandits](https://mlsanity.com/paper/2206.11254/) (2022)
- [Training-Free Constrained Generation With Stable Diffusion Models](https://mlsanity.com/paper/2502.05625/) (2025)
- [Guiding Energy-based Models via Contrastive Latent Variables](https://mlsanity.com/paper/2303.03023/) (2023)
- [Constrained Discrete Diffusion](https://mlsanity.com/paper/2503.09790/) (2025)
- [Improved Convergence Rate of Stochastic Gradient Langevin Dynamics with Variance Reduction and its Application to Optimization](https://mlsanity.com/paper/2203.16217/) (2022)
- [Generalization Bounds for Noisy Iterative Algorithms Using Properties of Additive Noise Channels](https://mlsanity.com/paper/2102.02976/) (2021)
- [Fisher information lower bounds for sampling](https://mlsanity.com/paper/2210.02482/) (2022)
- [Time-Independent Information-Theoretic Generalization Bounds for SGLD](https://mlsanity.com/paper/2311.01046/) (2023)
- [More Efficient Randomized Exploration for Reinforcement Learning via Approximate Sampling](https://mlsanity.com/paper/2406.12241/) (2024)
- [Polygonal Unadjusted Langevin Algorithms: Creating stable and efficient adaptive algorithms for neural networks](https://mlsanity.com/paper/2105.13937/) (2021)
- [Score-Guided Intermediate Layer Optimization: Fast Langevin Mixing for Inverse Problems](https://mlsanity.com/paper/2206.09104/) (2022)
- [Convergence and concentration properties of constant step-size SGD through Markov chains](https://mlsanity.com/paper/2306.11497/) (2023)
- [Non-asymptotic estimates for TUSLA algorithm for non-convex learning with applications to neural networks with ReLU activation function](https://mlsanity.com/paper/2107.08649/) (2021)
- [Accelerating Approximate Thompson Sampling with Underdamped Langevin Monte Carlo](https://mlsanity.com/paper/2401.11665/) (2024)
- [Neuro-Symbolic Generative Diffusion Models for Physically Grounded, Robust, and Safe Generation](https://mlsanity.com/paper/2506.01121/) (2025)
- [Interacting Contour Stochastic Gradient Langevin Dynamics](https://mlsanity.com/paper/2202.09867/) (2022)
- [Energy-based Hopfield Boosting for Out-of-Distribution Detection](https://mlsanity.com/paper/2405.08766/) (2024)
- [Stochastic Gradient Langevin Dynamics with Variance Reduction](https://mlsanity.com/paper/2102.06759/) (2021)
- [Stochastic Anderson Mixing for Nonconvex Stochastic Optimization](https://mlsanity.com/paper/2110.01543/) (2021)
- [Non-reversible Parallel Tempering for Deep Posterior Approximation](https://mlsanity.com/paper/2211.10837/) (2022)
- [Hardness of Learning Fixed Parities with Neural Networks](https://mlsanity.com/paper/2501.00817/) (2025)
- [Parallel Stochastic Gradient-Based Planning for World Models](https://mlsanity.com/paper/2602.00475/) (2026)
- [Constrained Langevin Algorithms with L-mixing External Random Variables](https://mlsanity.com/paper/2205.14192/) (2022)

## Abstract (arXiv)

We present a unified framework to analyze the global convergence of Langevin dynamics based algorithms for nonconvex finite-sum optimization with n component functions. At the core of our analysis is a direct analysis of the ergodicity of the numerical approximations to Langevin dynamics, which leads to faster convergence rates. Specifically, we show that gradient Langevin dynamics (GLD) and stochastic gradient Langevin dynamics (SGLD) converge to the almost minimizer within tilde Obig(nd/(λε) big) and tilde Obig(d7/(λ5ε5) big) stochastic gradient evaluations respectively, where d is the problem dimension, and λ is the spectral gap of the Markov chain generated by GLD. Both results improve upon the best known gradient complexity results (Raginsky et al., 2017). Furthermore, for the first time we prove the global convergence guarantee for variance reduced stochastic gradient Langevin dynamics (SVRG-LD) to the almost minimizer within tilde Obig(√nd5/(λ4ε5/2)big) stochastic gradient evaluations, which outperforms the gradient complexities of GLD and SGLD in a wide regime. Our theoretical analyses shed some light on using Langevin dynamics based algorithms for nonconvex optimization with provable guarantees.