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

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 the Langevin algorithm is thus a long-standing open problem. This paper provides an affirmative answer to this problem for the case of either Lipschitz or smooth convex functions 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.

Automated summary

There has been a growing body of research on bridging MCMC sampling and optimization, focusing on adapting convergence analysis techniques from optimization to the Langevin algorithms in MCMC sampling. This paper provides a positive answer to the long-standing question of whether dimension independent convergence rates can be achieved by the Langevin algorithm for Lipschitz or smooth convex functions with normal priors. By treating the Langevin algorithm as composite optimization, a new analysis technique is developed, leading to dimension independent convergence rates for such problems.