Langevin Monte Carlo without smoothness

Niladri Chatterji, Jelena Diakonikolas, Michael I. Jordan, Peter Bartlett
Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, PMLR 108:1716-1726, 2020.

Abstract

Langevin Monte Carlo (LMC) is an iterative algorithm used to generate samples from a distribution that is known only up to a normalizing constant. The nonasymptotic dependence of its mixing time on the dimension and target accuracy is understood mainly in the setting of smooth (gradient-Lipschitz) log-densities, a serious limitation for applications in machine learning. In this paper, we remove this limitation, providing polynomial-time convergence guarantees for a variant of LMC in the setting of nonsmooth log-concave distributions. At a high level, our results follow by leveraging the implicit smoothing of the log-density that comes from a small Gaussian perturbation that we add to the iterates of the algorithm and controlling the bias and variance that are induced by this perturbation.

Cite this Paper

BibTeX
@InProceedings{pmlr-v108-chatterji20a, title = {Langevin Monte Carlo without smoothness}, author = {Chatterji, Niladri and Diakonikolas, Jelena and Jordan, Michael I. and Bartlett, Peter}, booktitle = {Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics}, pages = {1716--1726}, year = {2020}, editor = {Chiappa, Silvia and Calandra, Roberto}, volume = {108}, series = {Proceedings of Machine Learning Research}, month = {26--28 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v108/chatterji20a/chatterji20a.pdf}, url = {https://proceedings.mlr.press/v108/chatterji20a.html}, abstract = {Langevin Monte Carlo (LMC) is an iterative algorithm used to generate samples from a distribution that is known only up to a normalizing constant. The nonasymptotic dependence of its mixing time on the dimension and target accuracy is understood mainly in the setting of smooth (gradient-Lipschitz) log-densities, a serious limitation for applications in machine learning. In this paper, we remove this limitation, providing polynomial-time convergence guarantees for a variant of LMC in the setting of nonsmooth log-concave distributions. At a high level, our results follow by leveraging the implicit smoothing of the log-density that comes from a small Gaussian perturbation that we add to the iterates of the algorithm and controlling the bias and variance that are induced by this perturbation.} }
Endnote
%0 Conference Paper %T Langevin Monte Carlo without smoothness %A Niladri Chatterji %A Jelena Diakonikolas %A Michael I. Jordan %A Peter Bartlett %B Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2020 %E Silvia Chiappa %E Roberto Calandra %F pmlr-v108-chatterji20a %I PMLR %P 1716--1726 %U https://proceedings.mlr.press/v108/chatterji20a.html %V 108 %X Langevin Monte Carlo (LMC) is an iterative algorithm used to generate samples from a distribution that is known only up to a normalizing constant. The nonasymptotic dependence of its mixing time on the dimension and target accuracy is understood mainly in the setting of smooth (gradient-Lipschitz) log-densities, a serious limitation for applications in machine learning. In this paper, we remove this limitation, providing polynomial-time convergence guarantees for a variant of LMC in the setting of nonsmooth log-concave distributions. At a high level, our results follow by leveraging the implicit smoothing of the log-density that comes from a small Gaussian perturbation that we add to the iterates of the algorithm and controlling the bias and variance that are induced by this perturbation.
APA
Chatterji, N., Diakonikolas, J., Jordan, M.I. & Bartlett, P.. (2020). Langevin Monte Carlo without smoothness. Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 108:1716-1726 Available from https://proceedings.mlr.press/v108/chatterji20a.html.

Related Material