STORM (Stochastic Recursive Momentum) for Single-Loop Adaptive Variance-Reduced Non-Convex SGD

STOchastic Recursive Momentum (STORM) is a single-loop, checkpoint-free, adaptive variance-reduced stochastic gradient descent algorithm for non-convex optimization min_{x in R^d} F(x) = E_{xi ~ D}[f(x, xi)], introduced by Cutkosky and Orabona (2019). At each iteration t >= 1, STORM updates the iterate via x_t = x_{t-1} - eta_{t-1} * d_{t-1}, draws a single sample (or mini-batch) xi_t ~ D, and updates its gradient estimator via the convex-combination recursive momentum rule d_t = nabla f(x_t, xi_t) + (1 - a_t) * (d_{t-1} - nabla f(x_{t-1}, xi_t)) (Eq. 2), equivalently written as corrected Heavy-Ball momentum d_t = a_t * nabla f(x_t, xi_t) + (1 - a_t) * d_{t-1} + (1 - a_t) * (nabla f(x_t, xi_t) - nabla f(x_{t-1}, xi_t)) (Eq. 1), with adaptive AdaGrad-style step size eta_t = k / (w + sum_{i=1}^t G_i^2)^{1/3} and momentum decay weight a_t = c * eta_{t-1}^2 where G_t = ||nabla f(x_t, xi_t)|| (Algorithm 1).