Faster Convergence of Stochastic Gradient Langevin Dynamics for Non-Log-Concave Sampling
Difan Zou, Pan Xu, Quanquan Gu
Abstract
We provide a new convergence analysis of stochastic gradient Langevin dynamics (SGLD) for sampling from a class of distributions that can be non-log-concave. At the core of our approach is a novel conductance analysis of SGLD using an auxiliary time-reversible Markov Chain. Under certain conditions on the target distribution, we prove that $\tilde O(d^4\epsilon^{-2})$ stochastic gradient evaluations suffice to guarantee $\epsilon$-sampling error in terms of the total variation distance, where $d$ is the problem dimension. This improves existing results on the convergence rate of SGLD [Raginsky et al., 2017, Xu et al., 2018]. We further show that provided an additional Hessian Lipschitz condition on the log-density function, SGLD is guaranteed to achieve $\epsilon$-sampling error within $\tilde O(d^{15/4}\epsilon^{-3/2})$ stochastic gradient evaluations. Our proof technique provides a new way to study the convergence of Langevin based algorithms, and sheds some light on the design of fast stochastic gradient based sampling algorithms.
BibTeX
@InProceedings{pmlr-v161-zou21a,
title = {Faster Convergence of Stochastic Gradient Langevin Dynamics for Non-Log-Concave Sampling},
author = {Zou, Difan and Xu, Pan and Gu, Quanquan},
booktitle = {Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence},
pages = {1152--1162},
year = {2021},
editor = {de Campos, Cassio and Maathuis, Marloes H.},
volume = {161},
series = {Proceedings of Machine Learning Research},
month = {27--30 Jul},
publisher = {PMLR},
pdf = {https://proceedings.mlr.press/v161/zou21a/zou21a.pdf},
url = {https://proceedings.mlr.press/v161/zou21a.html},
abstract = {We provide a new convergence analysis of stochastic gradient Langevin dynamics (SGLD) for sampling from a class of distributions that can be non-log-concave. At the core of our approach is a novel conductance analysis of SGLD using an auxiliary time-reversible Markov Chain. Under certain conditions on the target distribution, we prove that $\tilde O(d^4\epsilon^{-2})$ stochastic gradient evaluations suffice to guarantee $\epsilon$-sampling error in terms of the total variation distance, where $d$ is the problem dimension. This improves existing results on the convergence rate of SGLD [Raginsky et al., 2017, Xu et al., 2018]. We further show that provided an additional Hessian Lipschitz condition on the log-density function, SGLD is guaranteed to achieve $\epsilon$-sampling error within $\tilde O(d^{15/4}\epsilon^{-3/2})$ stochastic gradient evaluations. Our proof technique provides a new way to study the convergence of Langevin based algorithms, and sheds some light on the design of fast stochastic gradient based sampling algorithms.}
}