Katyusha Direct Negative-Momentum Acceleration for Stochastic Variance-Reduced Optimization

Katyusha Direct Negative-Momentum Acceleration for Stochastic Variance-Reduced Optimization is a direct, primal-only accelerated stochastic gradient method introduced by Allen-Zhu (2017, 2018) for composite convex finite-sum minimization min_{x in R^d} {F(x) = (1/n) sum_{i=1}^n f_i(x) + psi(x)}, where each f_i is convex and L-smooth and psi is sigma-strongly convex. Whereas naive Nesterov momentum on stochastic gradients accumulates variance errors, Katyusha (Algorithm 1) couples three iterate sequences (x_k, y_k, z_k) with a periodic SVRG snapshot x_tilde^s (updated every m = 2n iterations as an exponentially weighted average x_tilde^{s+1} = (sum_{j=0}^{m-1} (1 + alpha*sigma)^j)^{-1} sum_{j=0}^{m-1} (1 + alpha*sigma)^j y_{sm+j+1}) via the convex combination x_{k+1} = tau_1 z_k + tau_2 x_tilde^s + (1 - tau_1 - tau_2) y_k. Here tau_1 = min{sqrt(m*sigma/(3L)), 1/2} is the classical Nesterov linear-coupling momentum weight, alpha = 1/(3*tau_1*L) is the mirror step size, and tau_2 = 1/2 is the Katyusha 'negative momentum' weight, which acts as a retracting magnet toward the snapshot x_tilde^s so that the inner-product error <grad f(x_{k+1}), x_tilde^s - x_{k+1}> in the tight SVRG variance bound E[||grad_tilde_{k+1} - grad f(x_{k+1})||^2] <= 2L(f(x_tilde^s) - f(x_{k+1}) - <grad f(x_{k+1}), x_tilde^s - x_{k+1}>) (Lemma 2.4) is algebraically canceled in the linear-coupling step (Lemmas 2.6-2.7). Theorem 2.1 proves that Katyusha achieves an epsilon-additive minimizer in an optimal O((n + sqrt(n*L/sigma)) log((F(x_0) - F(x^*))/epsilon)) stochastic gradient iterations without outer-inner Catalyst reductions or Fenchel dual conjugates.