General Mathematics

Stochastic Gradient Leimkuhler—Matthews Integrator with Second Order Discretization Error

Authors: Xuda Ye, Yuliang Wang, Guang Lin, Cindy Xiangrui Kong
Comments: 87 Pages.

Stochastic gradient Langevin dynamics (SGLD) has a discretization error of first order in the step size, even with the full gradient. We study the stochastic gradient Leimkuhler--Matthews (SGLM) integrator, which has the cost of SGLD and reuses each Gaussian vector in consecutive steps; its full-gradient form, the Leimkuhler--Matthews (LM) integrator, has a discretization error of second order for the invariant distribution. For a potential strongly convex outside a ball, we prove the bound $mathcal O(frac{1}{Nh} + Sigma^2 h^2 + h^4)$ on the mean square error (MSE) of time averages of SGLM over $N$ steps of size $h$, where $Sigma$ bounds the variance of the gradient noise, through a modified class that absorbs the non-Markovian part of the integrator. The bound separates the stochastic gradient error from the discretization error, so a larger batch reduces the error at a fixed step size. We also give the coefficient of $h$ in the numerical bias of SGLM explicitly, in terms of the covariance of the gradient noise and the solution of the Poisson equation; that of SGLD contains in addition the Hessian of the potential, which no batch size removes. Through Riesz representors, these coefficients determine the Wasserstein-1 errors of SGLM and SGLD to first order in $h$. For a strongly convex potential, the Wasserstein-1 error of SGLM is at most that of SGLD to first order in $h$ once the batch size reaches an explicit threshold.
Category: General Mathematics