Contents Online
Communications in Mathematical Sciences
Volume 19 (2021)
Number 7
Complexity of randomized algorithms for underdamped Langevin dynamics
Pages: 1827 – 1853
DOI: https://dx.doi.org/10.4310/CMS.2021.v19.n7.a4
Authors
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 (\sqrt{d}N^{-3/2)}$, for solving a family of $d$‑dimensional underdamped Langevin dynamics, by any randomized algorithm with only $N$ queries to $\nabla U$, 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$.
Keywords
underdamped Langevin dynamics, randomized algorithms, information-based complexity, order optimal, randomized midpoint method
2010 Mathematics Subject Classification
65C20, 65C50
Received 18 July 2020
Accepted 23 March 2021
Published 7 September 2021