Complexity of randomized algorithms for underdamped Langevin dynamics

DOI10.4310/CMS.2021.V19.N7.A4MaRDI QIDQ2057047zbMATH OpenOpenAlexFDO

Authors Yu Cao, Lihan Wang, Jianfeng Lu

Publication date 8 December 2021

Published in Communications in Mathematical Sciences (Search for Journal in Brave)

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

zbMATH Keywords

information-based complexityorder optimalrandomized algorithmsrandomized midpoint methodunderdamped Langevin dynamics

Mathematics Subject Classification ID

Stochastic ordinary differential equations (aspects of stochastic analysis) (60H10) Probabilistic models, generic numerical methods in probability and statistics (65C20) Numerical solutions to stochastic differential and integral equations (65C30) Stochastic methods (Fokker-Planck, Langevin, etc.) applied to problems in time-dependent statistical mechanics (82C31)

Abstract: We establish an information complexity lower bound of randomized algorithms for simulating underdamped Langevin dynamics. More specifically, we prove that the worst $L^2$ strong error is of order $Omega(sqrtd,N^{-3/2})$, for solving a family of $d$-dimensional underdamped Langevin dynamics, by any randomized algorithm with only $N$ queries to $ablaU$, the driving Brownian motion and its weighted integration, respectively. The lower bound we establish matches the upper bound for the randomized midpoint method recently proposed by Shen and Lee [NIPS 2019], in terms of both parameters $N$ and $d$.

Recommendations

• The randomized complexity of initial value problems
• High-dimensional MCMC with a standard splitting scheme for the underdamped Langevin diffusion
• Using perturbed underdamped Langevin dynamics to efficiently sample from probability distributions
• Complexity bounds for Markov chain Monte Carlo algorithms via diffusion limits
• Logarithmic Sobolev inequalities and Langevin algorithms inRⁿ

Cited in

(16)

• Stochastic zeroth-order discretizations of Langevin diffusions for Bayesian inference
• Performance analysis of LVQ algorithms: a statistical physics approach
• Computational Complexity Analysis for Monte Carlo Approximations of Classically Scaled Population Processes
• scientific article; zbMATH DE number 7626757 (Why is no real title available?)
• Unbiased Estimation Using Underdamped Langevin Dynamics
• Contraction rate estimates of stochastic gradient kinetic Langevin integrators
• Convergence of random splitting method for the Allen-Cahn equation in a background flow
• Analysis of Langevin Monte Carlo from Poincaré to log-Sobolev
• Randomized Runge-Kutta-Nyström methods for unadjusted Hamiltonian and kinetic Langevin Monte Carlo
• Resolving the mixing time of the Langevin algorithm to its stationary distribution for log-concave sampling
• Unadjusted Hamiltonian MCMC with stratified Monte Carlo time integration
• Query lower bounds for log-concave sampling
• Faster high-accuracy log-concave sampling via algorithmic warm starts
• Random ordinate method for mitigating the ray effect in radiative transport equation simulations
• GIST: Gibbs self-tuning for locally adaptive Hamiltonian Monte Carlo
• Reflection coupling for unadjusted generalized Hamiltonian Monte Carlo in the nonconvex stochastic gradient case

This page was built for publication: Complexity of randomized algorithms for underdamped Langevin dynamics

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