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

Markov chain Monte Carlorate of convergencetotal variation distanceEuler discretizationLangevin diffusionMetropolis adjusted Langevin algorithmLangevin stochastic differential equation

Mathematics Subject Classification ID

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

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)

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

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)