Poster
Optimal Underdamped Langevin MCMC Method
Zhengmian Hu · Feihu Huang · Heng Huang
Virtual
Keywords: [ Generative Model ]
Abstract:
In the paper, we study the underdamped Langevin diffusion (ULD) with strongly-convex potential consisting of finite summation of N smooth components, and propose an efficient discretization method, which requires O(N+d13N23/ε23) gradient evaluations to achieve ε-error (in √E‖⋅‖22 distance) for approximating d-dimensional ULD. Moreover, we prove a lower bound of gradient complexity as Ω(N+d13N23/ε23), which indicates that our method is optimal in dependence of N, ε, 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.
Chat is not available.