Optimal Underdamped Langevin MCMC Method

Moreover, we prove a lower bound of gradient complexity as \Omega(N d \frac{1}{3}N \frac{2}{3}/\varepsilon \frac{2}{3}), which indicates that our method is optimal in dependence of N, \varepsilon, and d . In particular, we apply our method to sample the strongly-log-concave distribution and obtain gradient complexity better than all existing gradient based sampling algorithms. Experimental results on both synthetic and real-world data show that our new method consistently outperforms the existing ULD approaches.