aims at extending SGD by using the Langevin algorithm to construct the approximate gradient.

The Underdamped Langevin Algorithm {#sec:langevin}
==================================

In this section we provide some background knowledge of the underdamped Langevin algorithm, and derive a few important results that are crucial to the convergence of SAGD. At a high level, the underdamped Langevin algorithm is an approach to obtaining approximate samples from a target distribution $\pi(\xi)$. In many cases, we can only compute $\pi(\xi)$ up to some normalizing constant, *i.e.*, we have access to $V(\xi)\coloneqq-\log(\pi(\xi))+C$, where $C$ is free of $\xi$. Then the *underdamped Langevin diffusion* is defined by the following stochastic differential equation (SDE) for $W(t)=(\xi^{\mathrm{T}}(t),\rho^{\mathrm{T}}(t))^{\mathrm{T}}\in\mathbb{R}^{2r}$ with $\xi(t),\rho(t)\in\mathbb{R}^{r}$, $$\begin{aligned}
\mathrm{d}\xi(t) & =\rho(t)\mathrm{d}t,\label{eq:sde_xi}\\
\mathrm{d}\rho(t) & =-\gamma\rho(t)\mathrm{d}t-\nabla V(\xi(t))\mathrm{d}t+\sqrt{2\gamma}\mathrm{d}B(t),\label{eq:sde_rho}\\
\xi(0) & =\xi_{0},\ \rho(0)=\rho_{0},\ t\ge0,\nonumber \end{aligned}$$ where $\gamma>0$ is a fixed constant but can be chosen arbitrarily, and $B(t)$ is an $r$-dimensional Brownian motion. Under mild conditions, Proposition 6.1 of @pavliotis2014stochastic shows that the invariant distribution of $W(t)$ is unique, with the density function $$\pi_{W}(\xi,\rho)\propto\exp\{-V(\xi)-\Vert\rho\Vert^{2}/2\}\propto\pi(\xi)\cdot\exp(-\Vert\rho\Vert^{2}/2),$$ where $\rho$ is an auxiliary variable, and our main interest is in $\xi$. The form of $\pi_{W}(\xi,\rho)$ indicates that $\xi$ and $\rho$ are independent with $\xi\sim\pi(\xi)$ and $\rho\sim N(0,I_{r})$. That is, if we can solve the SDE 