Double Randomized Underdamped Langevin with Dimension-Independent Convergence Guarantee

This paper focuses on the high-dimensional sampling of log-concave distributions with composite structures: p ∗ (d x ) ∝ exp( − g ( x ) − f ( x ))d x . We develop a double randomization technique, which leads to a fast underdamped Langevin algorithm with a dimension-independent convergence guarantee. We prove that the algorithm enjoys an overall (cid:101) O (cid:16) (tr( H )) 1 / 3 ϵ 2 / 3 (cid:17) iteration complexity to reach an ϵ -tolerated sample whose distribution p admits W 2 ( p, p ∗ ) ≤ ϵ . Here, H is an upper bound of the Hessian matrices for f and does not explicitly depend on dimension d . For the posterior sampling over linear models with normalized data, we show a clear superiority of convergence rate which is dimension-free and outperforms the previous best-known results by a d 1 / 3 factor. The analysis to achieve a faster convergence rate brings new insights into high-dimensional sampling.