The Anytime Convergence of Stochastic Gradient Descent with Momentum: From a Continuous-Time Perspective

We study the stochastic optimization problem from a continuous-time perspective, with a focus on the Stochastic Gradient Descent with Momentum (SGDM) method. We show that the trajectory of SGDM, despite its stochastic nature, converges in L2-norm to a deterministic second-order Ordinary Differential Equation (ODE) as the stepsize goes to zero. The connection between the ODE and the algorithm results in a useful development for the discrete-time convergence analysis. More specifically, we develop, through the construction of a suitable Lyapunov function, convergence results for the ODE, which are then translated to the corresponding convergence results for the discrete-time case. This approach yields a novel anytime convergence guarantee for stochastic gradient methods. In particular, we prove that the sequence xk , governed by running SGDM on a smooth convex function f, satisfies beginalign* mathbbPleft(f (xk) - f^* ≤ Cleft(1+logfrac1βright)fraclog k√k,;for all kright)≥ 1-βquad for any β>0, endalign* where f^*=minx∈ℝn f(x), and C is a constant. Rather than at a single step, this result captures the convergence behavior across the entire trajectory of the algorithm.