Langevin Monte Carlo without smoothness

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.

arXiv commentUpdated to match the AISTATS 2020 camera ready version. Some example applications added and typos corrected

References in corpus (11)

• Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes
• User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient
• Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis
• Underdamped Langevin MCMC: A non-asymptotic analysis
• Log-concave sampling: Metropolis-Hastings algorithms are fast
• Convergence of Langevin MCMC in KL-divergence
• Uncertainty quantification for radio interferometric imaging: I. proximal MCMC methods
• Rapid Mixing of Hamiltonian Monte Carlo on Strongly Log-Concave Distributions
• Dimensionally Tight Bounds for Second-Order Hamiltonian Monte Carlo
• Sparse Bayesian mass-mapping with uncertainties: local credible intervals
• A Moreau-Yosida approximation scheme for a class of high-dimensional posterior distributions

Cited by in corpus (8)

• On the Convergence of Langevin Monte Carlo: The Interplay between Tail Growth and Smoothness
• Primal Dual Interpretation of the Proximal Stochastic Gradient Langevin Algorithm
• Convergence of Stein Variational Gradient Descent under a Weaker Smoothness Condition
• Black-box sampling for weakly smooth Langevin Monte Carlo using p-generalized Gaussian smoothing
• A Proximal Algorithm for Sampling from Non-smooth Potentials
• Fast Convergence of Langevin Dynamics on Manifold: Geodesics meet Log-Sobolev
• Penalized Langevin dynamics with vanishing penalty for smooth and log-concave targets
• Langevin Monte Carlo for strongly log-concave distributions: Randomized midpoint revisited