Nonasymptotic convergence analysis for the unadjusted Langevin algorithm

DOI10.1214/16-AAP1238MaRDI QIDQ2403136zbMATHOpenAlexFDO

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)

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

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)