When is the Convergence Time of Langevin Algorithms Dimension Independent? A Composite Optimization Viewpoint
arXiv:2110.01827
Abstract
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.
References in corpus (11)
- Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization
- Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes
- User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient
- Log-concave sampling: Metropolis-Hastings algorithms are fast
- Non-asymptotic convergence analysis for the Unadjusted Langevin Algorithm
- Convergence of Langevin MCMC in KL-divergence
- Rapid Mixing of Hamiltonian Monte Carlo on Strongly Log-Concave Distributions
- Is There an Analog of Nesterov Acceleration for MCMC?
- The Randomized Midpoint Method for Log-Concave Sampling
- Algorithmic Theory of ODEs and Sampling from Well-conditioned Logconcave Densities
- An Efficient Sampling Algorithm for Non-smooth Composite Potentials