Nonasymptotic convergence analysis for the unadjusted Langevin algorithm

DOI10.1214/16-AAP1238MaRDI QIDQ2403136zbMATH OpenOpenAlexFDO

Authors Alain Durmus, Eric Moulines

Publication date 15 September 2017

Published in The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1507.05021

zbMATH Keywords

Euler discretizationLangevin diffusionLangevin stochastic differential equationMarkov chain Monte CarloMetropolis adjusted Langevin algorithmrate of convergencetotal variation distance

Mathematics Subject Classification ID

Ordinary differential equations and systems with randomness (34F05) Stochastic ordinary differential equations (aspects of stochastic analysis) (60H10) Computational methods for stochastic equations (aspects of stochastic analysis) (60H35) Monte Carlo methods (65C05) Numerical solutions to stochastic differential and integral equations (65C30) Numerical analysis or methods applied to Markov chains (65C40)

Abstract: In this paper, we study a method to sample from a target distribution $pi$ over $mathbb{R}^d$ having a positive density with respect to the Lebesgue measure, known up to a normalisation factor. This method is based on the Euler discretization of the overdamped Langevin stochastic differential equation associated with $pi$. For both constant and decreasing step sizes in the Euler discretization, we obtain non-asymptotic bounds for the convergence to the target distribution $pi$ in total variation distance. A particular attention is paid to the dependency on the dimension $d$, to demonstrate the applicability of this method in the high dimensional setting. These bounds improve and extend the results of (Dalalyan 2014).

Recommendations

• High-dimensional Bayesian inference via the unadjusted Langevin algorithm
• Higher order Langevin Monte Carlo algorithm
• Analysis of Langevin Monte Carlo via convex optimization
• Unadjusted Langevin algorithm with multiplicative noise: total variation and Wasserstein bounds
• Improved bounds for discretization of Langevin diffusions: near-optimal rates without convexity

Cited in

(only showing first 100 items - show all)

• Convergence of realization-based statistics to model-based statistics for the LU unconditional simulation algorithm: some numerical tests
• Rapid mixing of geodesic walks on manifolds with positive curvature
• Explicit contraction rates for a class of degenerate and infinite-dimensional diffusions
• Using perturbed underdamped Langevin dynamics to efficiently sample from probability distributions
• Normalizing constants of log-concave densities
• Fourier transform MCMC, heavy-tailed distributions, and geometric ergodicity
• Is there an analog of Nesterov acceleration for gradient-based MCMC?
• Approximation of heavy-tailed distributions via stable-driven SDEs
• A duality formula and a particle Gibbs sampler for continuous time Feynman-Kac measures on path spaces
• Efficient stochastic optimisation by unadjusted Langevin Monte Carlo. Application to maximum marginal likelihood and empirical Bayesian estimation
• Sampling from non-smooth distributions through Langevin diffusion
• Randomized Hamiltonian Monte Carlo as scaling limit of the bouncy particle sampler and dimension-free convergence rates
• Unadjusted Langevin algorithm for sampling a mixture of weakly smooth potentials
• Approximations of piecewise deterministic Markov processes and their convergence properties
• Nonparametric Bayesian inference for reversible multidimensional diffusions
• Variance reduction for additive functionals of Markov chains via martingale representations
• Approximation to stochastic variance reduced gradient Langevin dynamics by stochastic delay differential equations
• Central limit theorem and self-normalized Cramér-type moderate deviation for Euler-Maruyama scheme
• Oracle lower bounds for stochastic gradient sampling algorithms
• Improved bounds for discretization of Langevin diffusions: near-optimal rates without convexity
• Stochastic zeroth-order discretizations of Langevin diffusions for Bayesian inference
• Stochastic gradient Hamiltonian Monte Carlo for non-convex learning
• Constrained ensemble Langevin Monte Carlo
• Ergodicity of the infinite swapping algorithm at low temperature
• On sampling from a log-concave density using kinetic Langevin diffusions
• Geometric ergodicity in a weighted Sobolev space
• Variance reduction for Markov chains with application to MCMC
• Bridging the gap between constant step size stochastic gradient descent and Markov chains
• On stochastic gradient Langevin dynamics with dependent data streams in the logconcave case
• High-dimensional MCMC with a standard splitting scheme for the underdamped Langevin diffusion
• Mixing of Hamiltonian Monte Carlo on strongly log-concave distributions: continuous dynamics
• The tamed unadjusted Langevin algorithm
• User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient
• Recursive computation of invariant distributions of Feller processes
• Non-asymptotic guarantees for sampling by stochastic gradient descent
• High-dimensional Bayesian inference via the unadjusted Langevin algorithm
• Higher order Langevin Monte Carlo algorithm
• Recursive computation of the invariant distributions of Feller processes: revisited examples and new applications
• PAC-Bayesian risk bounds for group-analysis sparse regression by exponential weighting
• Quantitative contraction rates for Markov chains on general state spaces
• Nonasymptotic bounds for sampling algorithms without log-concavity
• Optimising portfolio diversification and dimensionality
• Nonasymptotic estimates for stochastic gradient Langevin dynamics under local conditions in nonconvex optimization
• Accelerating Proximal Markov Chain Monte Carlo by Using an Explicit Stabilized Method
• Convergence of Langevin MCMC in KL-divergence
• Scaling Limit of the Stein Variational Gradient Descent: The Mean Field Regime
• Analysis of multiscale integrators for multiple attractors and irreversible Langevin samplers
• Quantitative Harris-type theorems for diffusions and McKean-Vlasov processes
• Efficient Bayesian computation by proximal Markov chain Monte Carlo: when Langevin meets Moreau
• Nonasymptotic mixing of the MALA algorithm
• New particle representations for ergodic McKean-Vlasov SDEs
• On stationary-point hitting time and ergodicity of stochastic gradient Langevin dynamics
• Maximum entropy methods for texture synthesis: theory and practice
• A proximal Markov chain Monte Carlo method for Bayesian inference in imaging inverse problems: when Langevin meets Moreau
• scientific article; zbMATH DE number 7626754 (Why is no real title available?)
• scientific article; zbMATH DE number 7626757 (Why is no real title available?)
• Particle dual averaging: optimization of mean field neural network with global convergence rate analysis*
• Markov Chain Importance Sampling—A Highly Efficient Estimator for MCMC
• Asymptotically Exact Data Augmentation: Models, Properties, and Algorithms
• Bayesian Imaging Using Plug & Play Priors: When Langevin Meets Tweedie
• Kinetic walks for sampling
• Maximum likelihood estimation of regularization parameters in high-dimensional inverse problems: an empirical Bayesian approach. II: Theoretical analysis
• scientific article; zbMATH DE number 7415079 (Why is no real title available?)
• Replica exchange for non-convex optimization
• On Stochastic Gradient Langevin Dynamics with Dependent Data Streams: The Fully Nonconvex Case
• Analysis of Langevin Monte Carlo via convex optimization
• Laplacian smoothing stochastic gradient Markov chain Monte Carlo
• Stochastic gradient Markov chain Monte Carlo
• Statistical Finite Elements via Langevin Dynamics
• ALMOND: Adaptive Latent Modeling and Optimization via Neural Networks and Langevin Diffusion
• Birth–death dynamics for sampling: global convergence, approximations and their asymptotics
• Global Optimization via Schrödinger–Föllmer Diffusion
• Phase transitions for support recovery under local differential privacy
• Convergence of Langevin-simulated annealing algorithms with multiplicative noise. II: Total variation
• Discretization of the ergodic functional central limit theorem
• Convergence of Position-Dependent MALA with Application to Conditional Simulation in GLMMs
• Unadjusted Langevin algorithm with multiplicative noise: total variation and Wasserstein bounds
• Complexity results for MCMC derived from quantitative bounds
• Swarm gradient dynamics for global optimization: the mean-field limit case
• Distributed event-triggered unadjusted Langevin algorithm for Bayesian learning
• Unbiased Estimation Using Underdamped Langevin Dynamics
• Markov chain stochastic DCA and applications in deep learning with PDEs regularization
• The Split Gibbs Sampler Revisited: Improvements to Its Algorithmic Structure and Augmented Target Distribution
• A fresh Take on ‘Barker Dynamics’ for MCMC
• Convergence of the Kiefer–Wolfowitz algorithm in the presence of discontinuities
• Taming Neural Networks with TUSLA: Nonconvex Learning via Adaptive Stochastic Gradient Langevin Algorithms
• Multi-index antithetic stochastic gradient algorithm
• The forward-backward envelope for sampling with the overdamped Langevin algorithm
• Lévy Langevin Monte Carlo
• A Bayesian learning model of hedge fund performance
• Contraction and convergence rates for discretized kinetic Langevin dynamics
• Diffusion approximations and control variates for MCMC
• Hybrid unadjusted Langevin methods for high-dimensional latent variable models
• Variable-step Euler-Maruyama approximations of regime-switching jump diffusion processes
• NF-ULA: normalizing flow-based unadjusted Langevin algorithm for imaging inverse problems
• Bayesian Robustness: A Nonasymptotic Viewpoint
• Swing contract pricing: with and without neural networks
• A diffusion process perspective on posterior contraction rates for parameters
• Accelerated Bayesian imaging by relaxed proximal-point Langevin sampling
• Mixing of Metropolis-adjusted Markov chains via couplings: the high acceptance regime

This page was built for publication: Nonasymptotic convergence analysis for the unadjusted Langevin algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2403136)