mlsanityData to 7 Oct 2026

When is the Convergence Time of Langevin Algorithms Dimension Independent? A Composite Optimization Viewpoint

arXiv 2110.01827 ↗First posted 5 Oct 2021cs.LG math.OCcited by 12

Not on the map. Why?

Abstract (arXiv)

There has been a surge of works bridging MCMC sampling and optimization, with a specific focus on translating non-asymptotic convergence guarantees for optimization problems into the analysis of Langevin algorithms in MCMC sampling. A conspicuous distinction between the convergence analysis of Langevin sampling and that of optimization is that all known convergence rates for Langevin algorithms depend on the dimensionality of the problem, whereas the convergence rates for optimization are dimension-free for convex problems. Whether a dimension independent convergence rate can be achieved by Langevin algorithm is thus a long-standing open problem. This paper provides an affirmative answer to this problem for large classes of either Lipschitz or smooth convex problems with normal priors. By viewing Langevin algorithm as composite optimization, we develop a new analysis technique that leads to dimension independent convergence rates for such problems.

Key facts. Cited by 12 papers in the map (data through 7 Oct 2026). Builds on 22 of its 55 references that are in the map. First posted on arXiv 5 Oct 2021.

Builds on

22 of 55 references.

References · 22

  1. 2014Theoretical guarantees for approximate sampling from smooth and log-concave densitiescited by 206
  2. 2015Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithmcited by 195
  3. 2016High-dimensional Bayesian inference via the Unadjusted Langevin Algorithmcited by 144
  4. 2017Underdamped Langevin MCMC: A non-asymptotic analysiscited by 131
  5. 2018Analysis of Langevin Monte Carlo via convex optimizationcited by 126
  6. 2018Sampling as optimization in the space of measures: The Langevin dynamics as a composite optimization problemcited by 123
  7. 2018Log-concave sampling: Metropolis-Hastings algorithms are fastcited by 117
  8. 2017User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradientcited by 116
  9. 2017Convergence of Langevin MCMC in KL-divergencecited by 86
  10. 2019The Randomized Midpoint Method for Log-Concave Samplingcited by 77
  11. 2018Sampling Can Be Faster Than Optimizationcited by 68
  12. 2018Sharp convergence rates for Langevin dynamics in the nonconvex settingcited by 67
10 more
  1. 2018On sampling from a log-concave density using kinetic Langevin diffusionscited by 61
  2. 2017Stochastic Methods for Composite and Weakly Convex Optimization Problemscited by 48
  3. 2018Coupling and Convergence for Hamiltonian Monte Carlocited by 36
  4. 2019High-Order Langevin Diffusion Yields an Accelerated MCMC Algorithmcited by 36
  5. 2019Langevin Monte Carlo without smoothnesscited by 27
  6. 2018On the Theory of Variance Reduction for Stochastic Gradient Monte Carlocited by 19
  7. 2019Is There an Analog of Nesterov Acceleration for MCMC?cited by 19
  8. 2019An Efficient Sampling Algorithm for Non-smooth Composite Potentialscited by 19
  9. 2017Rapid Mixing of Hamiltonian Monte Carlo on Strongly Log-Concave Distributionscited by 12
  10. 2018Algorithmic Theory of ODEs and Sampling from Well-conditioned Logconcave Densitiescited by 7

Built on by

Cited by year

Citing papers per year: 2021: 1; 2022: 4; 2023: 6; 2024: 1.

12 papers.

  1. 2023Reverse Diffusion Monte Carlocited by 41
  2. 2021A Proximal Algorithm for Sampling from Non-smooth Potentialscited by 23
  3. 2023On the Convergence of Black-Box Variational Inferencecited by 22
  4. 2022A Proximal Algorithm for Samplingcited by 21
  5. 2022Dimension Independent Generalization of DP-SGD for Overparameterized Smooth Convex Optimizationcited by 9
  6. 2023Initialization Matters: Privacy-Utility Analysis of Overparameterized Neural Networkscited by 9
  7. 2022Statistical and Computational Trade-offs in Variational Inference: A Case Study in Inferential Model Selectioncited by 7
  8. 2023A Simple Proof of the Mixing of Metropolis-Adjusted Langevin Algorithm under Smoothness and Isoperimetrycited by 7
  9. 2022A Proximal Algorithm for Sampling from Non-convex Potentialscited by 2
  10. 2023CORE: Common Random Reconstruction for Distributed Optimization with Provable Low Communication Complexitycited by 1
  11. 2023The surrogate Gibbs-posterior of a corrected stochastic MALA: Towards uncertainty quantification for neural networkscited by 0
  12. 2024An Improved Analysis of Langevin Algorithms with Prior Diffusion for Non-Log-Concave Samplingcited by 0