SGD convergence rates can be transferred: one Lyapunov calculation on a diffusion, then carried back window by window

Convergence-rate analysis for stochastic gradient algorithms can be recast as a Lyapunov calculation on a continuous diffusion, then carried back to the discrete iterates. Such rates previously came either from bespoke discrete-time proofs for each algorithm or from diffusion approximations accurate only on a finite horizon. For strongly convex stochastic gradient descent the transfer recovers the classical rates of the direct discrete-time analysis of Moulines and Bach (2011), and for stochastic Heavy Ball it recovers the familiar geometric transient together with a neighbourhood.

The construction restarts the continuous comparator at each fixed diffusion-time window and compares only the Lyapunov observable weakly. Strong process-level diffusion approximations require the whole trajectory to stay close over a growing time horizon, so approximation error accumulates. Each window's local weak error enters the estimate at order and is attenuated by the contraction over later windows, so no single diffusion approximation must stay accurate over a growing horizon.

The transfer method addresses convergence-rate analysis for stochastic approximation and stochastic gradient algorithms, for readers familiar with stochastic approximation or continuous-time analysis. It yields finite-time bounds: the SDE supplies contraction and forcing, while the discrete algorithm contributes an additional forcing term from the fixed-window weak comparison. The author states that the same proof template applies, once its moment and regularity conditions are verified, to monotone Robbins–Monro schemes, contractive fixed-point recursions, and stable linear stochastic approximation, and explicitly lists more general Lyapunov dissipation inequalities, higher-order stochastic modified equations, path-space and hitting-time quantities, Markovian noise, adaptive clocks, and two-timescale recursions as directions requiring extensions of the theorem rather than new applications alone.

The author notes that the global Lipschitz condition is a convenient sufficient condition rather than a minimal one, and that polynomially growing coefficients can be handled under nonexplosion and sufficiently strong fixed-window polynomial moment bounds. The all-iteration conclusion also requires a global moment stability condition, for which the author gives a sufficient condition via a Foster–Lyapunov inequality for the associated SDE, using a power-lifting trick when a higher moment is needed. Constant steps give convergence to a neighbourhood rather than to zero, and the author states that this constant-step conclusion is used only in the first-order setting and makes no claim when the comparison has a persistent multiplicative defect.