论文标题
引导不足的Langevin动力学的随机算法的复杂性
Complexity of randomized algorithms for underdamped Langevin dynamics
论文作者
论文摘要
我们建立了随机算法的信息复杂性下限，以模拟阻尼不足的Langevin动力学。 More specifically, we prove that the worst $L^2$ strong error is of order $Ω(\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, 分别。我们建立的下限与Shen和Lee [NIPS 2019]最近提出的随机中点方法的上限匹配，这两个参数$ n $和$ d $。
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 $Ω(\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$.
