Complexity of randomized algorithms for underdamped Langevin dynamics

03/22/2020
by   Yu Cao, et al.
0

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 Ω(√(d) N^-3/2), for solving a family of d-dimensional underdamped Langevin dynamics, by any randomized algorithm with only N queries to ∇ 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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset