# Global Non-convex Optimization with Discretized Diffusions

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

## Key facts

- Cited by 44 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Oct 2018.

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

- [Towards a Theory of Non-Log-Concave Sampling: First-Order Stationarity Guarantees for Langevin Monte Carlo](https://mlsanity.com/paper/2202.05214/) (2022)
- [Towards a Complete Analysis of Langevin Monte Carlo: Beyond Poincar'e Inequality](https://mlsanity.com/paper/2303.03589/) (2023)
- [Improved Discretization Analysis for Underdamped Langevin Monte Carlo](https://mlsanity.com/paper/2302.08049/) (2023)
- [Resolving the Mixing Time of the Langevin Algorithm to its Stationary Distribution for Log-Concave Sampling](https://mlsanity.com/paper/2210.08448/) (2022)
- [A Finite-Particle Convergence Rate for Stein Variational Gradient Descent](https://mlsanity.com/paper/2211.09721/) (2022)
- [On Learnability via Gradient Method for Two-Layer ReLU Neural Networks in Teacher-Student Setting](https://mlsanity.com/paper/2106.06251/) (2021)
- [Algorithmic Stability of Heavy-Tailed SGD with General Loss Functions](https://mlsanity.com/paper/2301.11885/) (2023)
- [Controlling Moments with Kernel Stein Discrepancies](https://mlsanity.com/paper/2211.05408/) (2022)
- [Polygonal Unadjusted Langevin Algorithms: Creating stable and efficient adaptive algorithms for neural networks](https://mlsanity.com/paper/2105.13937/) (2021)
- [Generalization Bounds for Stochastic Gradient Descent via Localized varepsilon-Covers](https://mlsanity.com/paper/2209.08951/) (2022)
- [Excess Risk of Two-Layer ReLU Neural Networks in Teacher-Student Settings and its Superiority to Kernel Methods](https://mlsanity.com/paper/2205.14818/) (2022)
- [Langevin Monte Carlo for strongly log-concave distributions: Randomized midpoint revisited](https://mlsanity.com/paper/2306.08494/) (2023)
- [Interacting Contour Stochastic Gradient Langevin Dynamics](https://mlsanity.com/paper/2202.09867/) (2022)
- [Generalisation under gradient descent via deterministic PAC-Bayes](https://mlsanity.com/paper/2209.02525/) (2022)
- [Parallelized Midpoint Randomization for Langevin Monte Carlo](https://mlsanity.com/paper/2402.14434/) (2024)
- [Heavy-tailed Sampling via Transformed Unadjusted Langevin Algorithm](https://mlsanity.com/paper/2201.08349/) (2022)
- [Constrained Langevin Algorithms with L-mixing External Random Variables](https://mlsanity.com/paper/2205.14192/) (2022)
- [Stochastic Methods in Variational Inequalities: Ergodicity, Bias and Refinements](https://mlsanity.com/paper/2306.16502/) (2023)
- [A Separation in Heavy-Tailed Sampling: Gaussian vs. Stable Oracles for Proximal Samplers](https://mlsanity.com/paper/2405.16736/) (2024)
- [Probabilistic Inference and Learning with Stein's Method](https://mlsanity.com/paper/2603.07467/) (2026)
- [A Unifying and Canonical Description of Measure-Preserving Diffusions](https://mlsanity.com/paper/2105.02845/) (2021)
- [Non-Log-Concave and Nonsmooth Sampling via Langevin Monte Carlo Algorithms](https://mlsanity.com/paper/2305.15988/) (2023)
- [Langevin Quasi-Monte Carlo](https://mlsanity.com/paper/2309.12664/) (2023)
- [Unadjusted Langevin algorithm for sampling a mixture of weakly smooth potentials](https://mlsanity.com/paper/2112.09311/) (2021)
- [Generalization Bounds for Label Noise Stochastic Gradient Descent](https://mlsanity.com/paper/2311.00274/) (2023)
- [Privacy of SGD under Gaussian or Heavy-Tailed Noise: Guarantees without Gradient Clipping](https://mlsanity.com/paper/2403.02051/) (2024)
- [Global convergence of optimized adaptive importance samplers](https://mlsanity.com/paper/2201.00409/) (2022)
- [On Uniform Boundedness Properties of SGD and its Momentum Variants](https://mlsanity.com/paper/2201.10245/) (2022)
- [Weak Convergence of Approximate reflection coupling and its Application to Non-convex Optimization](https://mlsanity.com/paper/2205.11970/) (2022)
- [A Dynamical System View of Langevin-Based Non-Convex Sampling](https://mlsanity.com/paper/2210.13867/) (2022)

## Abstract (arXiv)

An Euler discretization of the Langevin diffusion is known to converge to the global minimizers of certain convex and non-convex optimization problems. We show that this property holds for any suitably smooth diffusion and that different diffusions are suitable for optimizing different classes of convex and non-convex functions. This allows us to design diffusions suitable for globally optimizing convex and non-convex functions not covered by the existing Langevin theory. Our non-asymptotic analysis delivers computable optimization and integration error bounds based on easily accessed properties of the objective and chosen diffusion. Central to our approach are new explicit Stein factor bounds on the solutions of Poisson equations. We complement these results with improved optimization guarantees for targets other than the standard Gibbs measure.