User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient

Abstract

In this paper, we study the problem of sampling from a given probability density function that is known to be smooth and strongly log-concave. We analyze several methods of approximate sampling based on discretizations of the (highly overdamped) Langevin diffusion and establish guarantees on its error measured in the Wasserstein-2 distance. Our guarantees improve or extend the state-of-the-art results in three directions. First, we provide an upper bound on the error of the first-order Langevin Monte Carlo (LMC) algorithm with optimized varying step-size. This result has the advantage of being horizon free (we do not need to know in advance the target precision) and to improve by a logarithmic factor the corresponding result for the constant step-size. Second, we study the case where accurate evaluations of the gradient of the log-density are unavailable, but one can have access to approximations of the aforementioned gradient. In such a situation, we consider both deterministic and stochastic approximations of the gradient and provide an upper bound on the sampling error of the first-order LMC that quantifies the impact of the gradient evaluation inaccuracies. Third, we establish upper bounds for two versions of the second-order LMC, which leverage the Hessian of the log-density. We provide nonasymptotic guarantees on the sampling error of these second-order LMCs. These guarantees reveal that the second-order LMC algorithms improve on the first-order LMC in ill-conditioned settings.

Cited by in corpus (66)

• Sampling Can Be Faster Than Optimization
• Cyclical Stochastic Gradient MCMC for Bayesian Deep Learning
• Underdamped Langevin MCMC: A non-asymptotic analysis
• Maximum Mean Discrepancy Gradient Flow
• High-Order Langevin Diffusion Yields an Accelerated MCMC Algorithm
• Is There an Analog of Nesterov Acceleration for MCMC?
• Ensemble Kalman Sampler: mean-field limit and convergence analysis
• Global Convergence of Stochastic Gradient Hamiltonian Monte Carlo for Non-Convex Stochastic Optimization: Non-Asymptotic Performance Bounds and Momentum-Based Acceleration
• A Non-Asymptotic Analysis for Stein Variational Gradient Descent
• On the Theory of Variance Reduction for Stochastic Gradient Monte Carlo
• Sampling as optimization in the space of measures: The Langevin dynamics as a composite optimization problem
• Stochastic Runge-Kutta Accelerates Langevin Monte Carlo and Beyond
• Langevin Monte Carlo and JKO splitting
• Decentralized Stochastic Gradient Langevin Dynamics and Hamiltonian Monte Carlo
• Higher Order Langevin Monte Carlo Algorithm
• Fast mixing of Metropolized Hamiltonian Monte Carlo: Benefits of multi-step gradients
• Analysis of Langevin Monte Carlo via convex optimization
• On Last-Layer Algorithms for Classification: Decoupling Representation from Uncertainty Estimation
• Algorithmic Theory of ODEs and Sampling from Well-conditioned Logconcave Densities
• Nonasymptotic estimates for Stochastic Gradient Langevin Dynamics under local conditions in nonconvex optimization
• Bounding the error of discretized Langevin algorithms for non-strongly log-concave targets
• An Analysis of Constant Step Size SGD in the Non-convex Regime: Asymptotic Normality and Bias
• The reproducing Stein kernel approach for post-hoc corrected sampling
• Langevin Monte Carlo without smoothness
• Nonasymptotic analysis of Stochastic Gradient Hamiltonian Monte Carlo under local conditions for nonconvex optimization
• Estimating Convergence of Markov chains with L-Lag Couplings
• Simulated Tempering Langevin Monte Carlo II: An Improved Proof using Soft Markov Chain Decomposition
• On Stationary-Point Hitting Time and Ergodicity of Stochastic Gradient Langevin Dynamics
• Faster Convergence of Stochastic Gradient Langevin Dynamics for Non-Log-Concave Sampling
• From bilinear regression to inductive matrix completion: a quasi-Bayesian analysis
• Stochastic Proximal Langevin Algorithm: Potential Splitting and Nonasymptotic Rates
• Replica Exchange for Non-Convex Optimization
• Decentralized Langevin Dynamics
• On Thompson Sampling with Langevin Algorithms
• Stochastic Variance-Reduced Hamilton Monte Carlo Methods
• On stochastic gradient Langevin dynamics with dependent data streams in the logconcave case
• Projection Robust Wasserstein Distance and Riemannian Optimization
• Extended Stochastic Gradient MCMC for Large-Scale Bayesian Variable Selection
• Estimating Normalizing Constants for Log-Concave Distributions: Algorithms and Lower Bounds
• Stochastic Particle-Optimization Sampling and the Non-Asymptotic Convergence Theory
• Data-informed Deep Optimization
• Implicit Langevin Algorithms for Sampling From Log-concave Densities
• QLSD: Quantised Langevin stochastic dynamics for Bayesian federated learning
• Channel-Driven Monte Carlo Sampling for Bayesian Distributed Learning in Wireless Data Centers
• Stochastic Gradient Langevin Dynamics Algorithms with Adaptive Drifts
• Scalable Gaussian Process Inference with Finite-data Mean and Variance Guarantees
• Random Coordinate Underdamped Langevin Monte Carlo
• Structured Logconcave Sampling with a Restricted Gaussian Oracle
• Stochastic Gradient Langevin Dynamics with Variance Reduction
• Fast Convergence of Langevin Dynamics on Manifold: Geodesics meet Log-Sobolev
• A Decentralized Approach to Bayesian Learning
• A splitting Hamiltonian Monte Carlo method for efficient sampling
• Black-box sampling for weakly smooth Langevin Monte Carlo using p-generalized Gaussian smoothing
• A Langevinized Ensemble Kalman Filter for Large-Scale Static and Dynamic Learning
• Non-asymptotic estimates for TUSLA algorithm for non-convex learning with applications to neural networks with ReLU activation function
• When is the Convergence Time of Langevin Algorithms Dimension Independent? A Composite Optimization Viewpoint
• Targeted stochastic gradient Markov chain Monte Carlo for hidden Markov models with rare latent states
• On Transformations in Stochastic Gradient MCMC
• Dimension-free Information Concentration via Exp-Concavity
• Constrained Ensemble Langevin Monte Carlo
• Wasserstein distance estimates for the distributions of numerical approximations to ergodic stochastic differential equations
• An Adaptive Empirical Bayesian Method for Sparse Deep Learning
• Mirrored Langevin Dynamics
• Aggregated Gradient Langevin Dynamics
• Variance Reduction in Stochastic Particle-Optimization Sampling
• Variance reduction for Random Coordinate Descent-Langevin Monte Carlo