Timezone: »

 
Spotlight
Stochastic Runge-Kutta Accelerates Langevin Monte Carlo and Beyond
Xuechen (Chen) Li · Denny Wu · Lester Mackey · Murat Erdogdu

Tue Dec 10 05:25 PM -- 05:30 PM (PST) @ West Ballroom C
in Track 4 Session 2 »
Sampling with Markov chain Monte Carlo methods typically amounts to discretizing some continuous-time dynamics with numerical integration. In this paper, we establish the convergence rate of sampling algorithms obtained by discretizing smooth It\^o diffusions exhibiting fast $2$-Wasserstein contraction, based on local deviation properties of the integration scheme. In particular, we study a sampling algorithm constructed by discretizing the overdamped Langevin diffusion with the method of stochastic Runge-Kutta. For strongly convex potentials that are smooth up to a certain order, its iterates converge to the target distribution in $2$-Wasserstein distance in $\tilde{\mathcal{O}}(d\epsilon^{-2/3})$ iterations. This improves upon the best-known rate for strongly log-concave sampling based on the overdamped Langevin equation using only the gradient oracle without adjustment. Additionally, we extend our analysis of stochastic Runge-Kutta methods to uniformly dissipative diffusions with possibly non-convex potentials and show they achieve better rates compared to the Euler-Maruyama scheme on the dependence on tolerance $\epsilon$. Numerical studies show that these algorithms lead to better stability and lower asymptotic errors.
[ Paper]  [ Slides]  [ Slides] 

Author Information

Xuechen (Chen) Li (UToronto, Google)
Denny Wu (University of Toronto & Vector Institute)
Lester Mackey (Microsoft Research)
Murat Erdogdu (University of Toronto)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors