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^∗(dx) ∝ exp(−g(x) − f(x)dx. 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 (equation presented)iteration complexity to reach an ϵ-tolerated sample whose distribution p admits W₂(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.