Nonasymptotic convergence analysis for the unadjusted Langevin algorithm

DOI10.1214/16-AAP1238zbMATH Open1377.65007arXiv1507.05021OpenAlexW4299557478MaRDI QIDQ2403136FDOQ2403136

Authors: Alain Durmus, Eric Moulines 

Publication date: 15 September 2017

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

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).

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

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

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)

Cited In (only showing first 100 items - show all)

• Non-asymptotic guarantees for sampling by stochastic gradient descent
• Nonparametric Bayesian inference for reversible multidimensional diffusions
• Statistical Finite Elements via Langevin Dynamics
• Convergence of realization-based statistics to model-based statistics for the LU unconditional simulation algorithm: some numerical tests
• Fourier transform MCMC, heavy-tailed distributions, and geometric ergodicity
• Title not available (Why is that?)
• Variance reduction for additive functionals of Markov chains via martingale representations
• Central limit theorem and self-normalized Cramér-type moderate deviation for Euler-Maruyama scheme
• Efficient Bayesian Computation by Proximal Markov Chain Monte Carlo: When Langevin Meets Moreau
• Title not available (Why is that?)
• Recursive computation of invariant distributions of Feller processes
• Stochastic Gradient Markov Chain Monte Carlo
• Normalizing constants of log-concave densities
• The tamed unadjusted Langevin algorithm
• Randomized Hamiltonian Monte Carlo as scaling limit of the bouncy particle sampler and dimension-free convergence rates
• Maximum Likelihood Estimation of Regularization Parameters in High-Dimensional Inverse Problems: An Empirical Bayesian Approach. Part II: Theoretical Analysis
• Approximation to stochastic variance reduced gradient Langevin dynamics by stochastic delay differential equations
• Stochastic gradient Hamiltonian Monte Carlo for non-convex learning
• Global Optimization via Schrödinger–Föllmer Diffusion
• Quantitative Harris-type theorems for diffusions and McKean–Vlasov processes
• 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
• Constrained ensemble Langevin Monte Carlo
• 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
• Title not available (Why is that?)
• Scaling Limit of the Stein Variational Gradient Descent: The Mean Field Regime
• 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
• Asymptotically Exact Data Augmentation: Models, Properties, and Algorithms
• Ergodicity of the infinite swapping algorithm at low temperature
• User-friendly guarantees for the Langevin Monte Carlo with inaccurate gradient
• The Split Gibbs Sampler Revisited: Improvements to Its Algorithmic Structure and Augmented Target Distribution
• Mixing of Hamiltonian Monte Carlo on strongly log-concave distributions: continuous dynamics
• Laplacian Smoothing Stochastic Gradient Markov Chain Monte Carlo
• Optimising portfolio diversification and dimensionality
• Analysis of Multiscale Integrators for Multiple Attractors and Irreversible Langevin Samplers
• Nonasymptotic bounds for sampling algorithms without log-concavity
• Efficient stochastic optimisation by unadjusted Langevin Monte Carlo. Application to maximum marginal likelihood and empirical Bayesian estimation
• Bridging the gap between constant step size stochastic gradient descent and Markov chains
• Explicit contraction rates for a class of degenerate and infinite-dimensional diffusions
• Kinetic walks for sampling
• Title not available (Why is that?)
• Recursive computation of the invariant distributions of Feller processes: revisited examples and new applications
• Geometric ergodicity in a weighted Sobolev space
• Sampling from non-smooth distributions through Langevin diffusion
• Complexity results for MCMC derived from quantitative bounds
• Unadjusted Langevin algorithm with multiplicative noise: total variation and Wasserstein bounds
• PAC-Bayesian risk bounds for group-analysis sparse regression by exponential weighting
• On sampling from a log-concave density using kinetic Langevin diffusions
• New particle representations for ergodic McKean-Vlasov SDEs
• Accelerating Proximal Markov Chain Monte Carlo by Using an Explicit Stabilized Method
• Unadjusted Langevin algorithm for sampling a mixture of weakly smooth potentials
• Rapid mixing of geodesic walks on manifolds with positive curvature
• Theoretical properties of quasi-stationary Monte Carlo methods
• Markov Chain Importance Sampling—A Highly Efficient Estimator for MCMC
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• 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
• Unbiased Estimation Using Underdamped Langevin Dynamics
• Markov chain stochastic DCA and applications in deep learning with PDEs regularization
• Convergence of Langevin-simulated annealing algorithms with multiplicative noise. II: Total variation
• Swing contract pricing: with and without neural networks
• A diffusion process perspective on posterior contraction rates for parameters
• A fresh Take on ‘Barker Dynamics’ for MCMC
• Convergence of the Kiefer–Wolfowitz algorithm in the presence of discontinuities
• Accelerated Bayesian imaging by relaxed proximal-point Langevin sampling
• ALMOND: Adaptive Latent Modeling and Optimization via Neural Networks and Langevin Diffusion
• Mixing of Metropolis-adjusted Markov chains via couplings: the high acceptance regime
• Birth–death dynamics for sampling: global convergence, approximations and their asymptotics
• Dimension-free mixing times of Gibbs samplers for Bayesian hierarchical models
• Multi-index antithetic stochastic gradient algorithm
• Consensus-based optimization methods converge globally
• Discretization of the ergodic functional central limit theorem
• Maximum Entropy Methods for Texture Synthesis: Theory and Practice
• Taming Neural Networks with TUSLA: Nonconvex Learning via Adaptive Stochastic Gradient Langevin Algorithms
• Approximation for the invariant measure with applications for jump processes (convergence in total variation distance)
• Phase transitions for support recovery under local differential privacy
• Kinetic Langevin MCMC sampling without gradient Lipschitz continuity -- the strongly convex case
• Proximal Langevin sampling with inexact proximal mapping
• Subgradient Langevin methods for sampling from nonsmooth potentials
• Riemannian Langevin algorithm for solving semidefinite programs
• Distributed event-triggered unadjusted Langevin algorithm for Bayesian learning
• A Proximal Markov Chain Monte Carlo Method for Bayesian Inference in Imaging Inverse Problems: When Langevin Meets Moreau
• 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
• The forward-backward envelope for sampling with the overdamped Langevin algorithm

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)