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

Yu Cao (Courant Institute of Mathematical Sciences, New York University, New York, N.Y., U.S.A.; and Department of Mathematics, Duke University, Durham, North Carolina, U.S.A.)

Jianfeng Lu (Departments of Mathematics, Physics, and Chemistry, Duke University, Durham, North Carolina, U.S.A.)

Lihan Wang (Department of Mathematics, Duke University, Durham, North Carolina, U.S.A.)

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