PaperlayerView exact revision on arXiv

Source-linked AI summary

Katyusha: The First Direct Acceleration of Stochastic Gradient Methods

Zeyuan Allen-Zhu

arXiv:1603.05953v6math.OCcs.DScs.LGstat.ML

TL;DR

Stochastic gradient methods lack the acceleration of full-gradient methods, while momentum can accumulate stochastic estimation errors. The paper introduces Katyusha, a direct primal-only method using negative momentum, and reports optimal accelerated rates together with parallel linear speedup for convex finite-sum optimization.

  • Problem

    Stochastic gradient methods generally lack the accelerated convergence known for full-gradient methods, and naive momentum can accumulate errors from inaccurate stochastic gradients.

  • Method

    Katyusha is a direct, primal-only stochastic gradient method that adds a negative-momentum magnet to a variance-reduction-based accelerated scheme.

  • Results

    Katyusha gives optimal accelerated convergence rates for the covered convex cases and achieves linear parallel speedup for mini-batches up to √n.

  • Takeaways & Limitations

    Katyusha momentum yields stochastic methods that are reported as simple, practical, and parallelizable while matching theoretical lower bounds for many problem classes.

  • Takeaways & Limitations

    The strongest stated results focus on convex finite-sum objectives, and the revised mini-batch generalizations Katyusha2 and Katyusha2ns lack a clean worst-case speedup statement.

Abstract

from arXiv · show

Nesterov's momentum trick is famously known for accelerating gradient descent, and has been proven useful in building fast iterative algorithms. However, in the stochastic setting, counterexamples exist and prevent Nesterov's momentum from providing similar acceleration, even if the underlying problem is convex and finite-sum. We introduce $\mathtt{Katyusha}$, a direct, primal-only stochastic gradient method to fix this issue. In convex finite-sum stochastic optimization, $\mathtt{Katyusha}$ has an optimal accelerated convergence rate, and enjoys an optimal parallel linear speedup in the mini-batch setting. The main ingredient is $\textit{Katyusha momentum}$, a novel "negative momentum" on top of Nesterov's momentum. It can be incorporated into a variance-reduction based algorithm and speed it up, both in terms of $\textit{sequential and parallel}$ performance. Since variance reduction has been successfully applied to a growing list of practical problems, our paper suggests that in each of such cases, one could potentially try to give Katyusha a hug.

1 Introduction

Stochastic gradient methods lack the straightforward acceleration available to full-gradient methods because momentum can accumulate estimator errors. Katyusha addresses this gap with negative momentum, achieving optimal acceleration and parallel linear speedup for convex finite-sum optimization.

  • Motivation: Naive momentum is dangerous with stochastic gradients because inaccurate estimators can be carried into future updates, causing error accumulation and preventing accelerated convergence in general.Experiments report that momentum-based stochastic methods can fail to achieve accelerated rates, become unstable, and lack supporting theory.
  • Results: Katyusha achieves optimal accelerated convergence rates for the covered convex cases and a parallel speedup factor b when distributed to b ≤ √n machines, ignoring communication overhead.Its mini-batch complexity also accounts for non-uniform smoothness, and the paper reports optimal ε ∝ n/T^2 behavior in a non-strongly convex setting.
  • Motivation: Stochastic gradient methods use inexpensive random-example gradients, but standard SGD cannot converge faster than 1/ε even for strongly convex, smooth objectives.Computing ∇f_i(x) is usually n times faster than computing the full gradient ∇f(x).
  • Motivation: Existing variance-reduction methods improve convergence, yet their iteration complexities retain linear dependence on κ instead of the optimal √κ dependence.Catalyst partially addresses the gap but adds a log κ factor and has further optimality, practicality, parallelism, and generality limitations.
  • Contribution: Katyusha is a direct, primal-only accelerated stochastic gradient method designed to obtain optimal rates without reductions.The method targets convex finite-sum objectives with a convex proximal term and smooth component functions.
  • High-Level Idea: Katyusha momentum combines Nesterov-style momentum with a negative-momentum magnet that attracts the next iterate toward a snapshot point.The update uses three sequences and a convex combination of y_k, z_k, and the snapshot x̃; the suggested parameters include τ_2 = 0.5 and τ_1 = min{√(nσ/L), 0.5}.

2 Katyusha in the Strongly Convex Setting

Katyusha combines variance-reduced stochastic gradients with Nesterov-style updates and a novel negative momentum that compensates for stochastic-estimator error. Its analysis establishes accelerated convergence while retaining sparse-iteration efficiency.

  • Algorithm design: Katyusha uses epochs, weighted snapshot averages, and SVRG-style gradient estimators within a proximal accelerated method.A full gradient is computed once per epoch, while stochastic corrections use a randomly selected component gradient.
  • Algorithm design: The novel Katyusha momentum is a constant weight τ2 for an added negative-momentum term on top of Nesterov parameters.The paper sets τ2 = 1/2, while any constant in (0, 1) works theoretically.
  • Main guarantee: For convex L-smooth components with σ-strongly convex regularization, Katyusha achieves an ε-additive error with an accelerated convergence guarantee.The theorem uses epoch length m = Θ(n); the supplied passages state the guarantee qualitatively but omit its complete displayed complexity.
  • Implementation: With sparse implementation, Katyusha’s amortized per-iteration complexity for ERM is O(d′), matching SGD when d′ is feature-vector sparsity.Deferred coordinate updates reduce overhead when stochastic gradients have at most d′ nonzero entries.
  • One-iteration analysis: The coupling lemmas connect expected objective decrease, estimator variance, proximal descent, and distances between iterates and the minimizer.The analysis combines proximal mirror descent, proximal gradient descent, and the special convex combination defining x_k+1.
  • One-iteration analysis: Katyusha’s variance analysis uses a tighter bound than standard objective-distance bounds and cancels an additional gradient inner-product term through Katyusha momentum.The tighter variance quantity is paired with the negative term introduced by the new momentum.

3 Corollaries on Non-Smooth or Non-SC Problems

The paper applies reductions to Katyusha to cover non-strongly-convex and nonsmooth objectives. It also establishes HOOD, a reusable objective-decrease property for strongly convex problems.

  • Reductions: Reductions translate Katyusha’s strongly convex result into algorithms for non-strongly-convex and/or nonsmooth objectives.The paper introduces AdaptReg, AdaptSmooth, and JointAdaptRegSmooth for these cases.
  • HOOD: Katyusha satisfies the HOOD property with T(L, σ) = O(... ) stochastic gradient iterations.HOOD requires a fixed objective decrease from every starting point within a stated iteration budget; the displayed complexity is truncated here.
  • HOOD: Existing accelerated stochastic methods either fail to satisfy HOOD or incur an additional log(L/σ) factor in their iteration bounds.This comparison is stated for methods preceding Katyusha, including simpler problem settings.
  • Corollaries: For non-strongly-convex smooth objectives, AdaptReg applied to Katyusha reaches ε error with a rate proportional to 1/√ε iterations.The equivalent error-versus-iterations form is ε proportional to 1/T^2.
  • Corollaries: AdaptSmooth and JointAdaptRegSmooth extend Katyusha to strongly convex nonsmooth and simultaneously non-strongly-convex nonsmooth settings.The supplied passages state corresponding ε-error guarantees but omit their complete displayed complexities.

4 Katyusha in the Non-Strongly Convex Setting

Katyushans is a direct accelerated solver for the non-strongly-convex case, avoiding reductions such as restarting. Its convergence is compared favorably with a direct non-accelerated solver.

  • Method: Katyushans is a direct accelerated method for non-strongly-convex Problem (1.1).The method is introduced specifically for this setting rather than obtained through the reduction framework.
  • Method: Its epoch-dependent parameters decrease across epochs, while τ1 and τ2 remain constant within each epoch.The parameter schedule changes τ1 and α with epoch index s and uses variance-reduced full-gradient snapshots.
  • Comparison: Katyushans is reported to be a factor S faster than non-accelerated methods such as SAGA, where S = T/n.The comparison is expressed using total stochastic iterations T and epoch-related quantity S.
  • Caveat: The direct theorem’s displayed complexity can be improved through more sophisticated choices of τ1 or epoch length, but the paper omits them to keep proofs and notation simpler.The authors report satisfactory practical performance despite this presentation choice.

5 Katyusha in the Mini-Batch Setting

Katyusha1 extends Katyusha to mini-batches and non-uniform smoothness, changing epoch lengths, sampling, and step-size parameters. The resulting method exhibits a mini-batch/full-batch phase transition and parallel speedup.

  • Extension: Katyusha1 jointly handles mini-batch computation and non-uniform component smoothness.The extension changes the algorithm and provides a theorem for arbitrary mini-batch size b.
  • Algorithmic changes: The method sets epoch length m = ⌈n/b⌉ and uses b sampled gradients per iteration, enabling distributed computation on up to b processors.Sampling is from a smoothness-proportional distribution in the non-uniform case.
  • Parallel speedup: For b ≤ √n, Katyusha1 preserves total work and achieves parallel speedup factor b, ignoring communication overhead.The paper describes this as linear speedup and states that total work remains unchanged over the relevant range.
  • Comparison: In contrast, mini-batch SVRG has no parallel speedup in the stated comparison, while Catalyst increases total work by a factor of b.The paper contrasts these methods with Katyusha1’s linear speedup.
  • Comparison: Katyusha1 can achieve the same iteration complexity as Nesterov while using b = (nL/L)1/2 stochastic gradients per iteration on average.This can reduce total work when L is much larger than L.
  • Phase transition: Katyusha1’s phase transition occurs at b0 = (nL/L)1/2, separating mini-batch and full-batch regimes.The mini-batch phase is defined by b ≤ b0; larger b enters the full-batch phase.
  • Full-batch phase: When b > b0, total work scales essentially linearly with b and matches Nesterov’s method at b = n.At b = n, the iteration complexity matches Nesterov’s accelerated gradient method and does not depend on the possibly larger L.

6 Katyusha in the Non-Euclidean Norm Setting

Katyusha extends to non-Euclidean norms by replacing Euclidean smoothness and proximal updates with norm- and Bregman-divergence-based variants. The resulting algorithms retain stated convergence guarantees, while mini-batch speedup lacks a clean worst-case characterization.

  • Katyusha and Katyushans extend naturally to smoothness defined with respect to a non-Euclidean norm.
  • The extension assumes each f_i is convex and L_i-smooth under the chosen norm, with a corresponding Bregman divergence.
  • The non-Euclidean algorithms sample i proportional to L_i and replace the proximal arg min with its norm-specific variant.
  • Katyusha2 supports generalized strong convexity through Bregman divergence, while Katyusha2ns removes the strong-convexity requirement.
  • Arbitrary norms prevent the usual mini-batch variance reduction argument, so the paper does not give a clean worst-case speedup statement in that setting.

7 Empirical Evaluations

Experiments on ridge and Lasso regression compare Katyusha with variance-reduced and accelerated competitors across six datasets. Katyusha is generally competitive or better, with its advantage most visible for small regularizer weights and high-accuracy optimization.

  • The study evaluates ridge and Lasso regression on six datasets using automatically tuned algorithms, with mini-batch size 1.The compared methods include SVRG, Katyusha, Katyushans, SAGA, Catalyst, APCG, and APCG+AdaptReg.
  • Katyusha fixes τ2 = 1/2 in experiments, while τ1 controls Nesterov momentum and τ2 controls Katyusha momentum.
  • Without Katyusha momentum, some tasks lose accelerated convergence even though careful tuning can sometimes make the older heuristic faster.
  • Small regularizer weights expose Katyusha’s advantage over SVRG and SAGA, whereas performance is relatively similar for large weights.
  • Katyusha almost always matches or outperforms its competitors, with SVRG the only notable reported exception.Katyusha can recover SVRG when both momentum parameters are set to zero.
  • Catalyst is outperformed by SVRG in several high-accuracy plots, while APCG performs poorly on all reported Lasso tasks.

8 Conclusion

The paper concludes that Katyusha momentum supplies accelerated convergence for stochastic finite-sum optimization while preserving practical and parallelizable algorithms. It positions the technique as a way to extend acceleration beyond settings where classical momentum is reliable.

  • Katyusha momentum yields accelerated convergence rates in the stochastic setting.
  • For many problem classes, these rates are the first reported to match theoretical lower bounds.
  • The resulting algorithms are described as simple, practical, and parallelizable.
  • The paper frames Katyusha momentum as an additional design element layered on classical Nesterov momentum.
  • The conclusion focuses on convex finite-sum settings, while nonconvex and online stochastic optimization are discussed as separate research settings.
  • The broader discussion distinguishes stochastic gradient methods from coordinate descent, whose acceleration is described as significantly easier to design.

B Experiment Details

The appendix documents datasets, tuning procedures, and implementation choices for the empirical comparisons. It uses LibSVM datasets and automated parameter selection to support consistent evaluation across methods.

  • The experiments use six LibSVM datasets: adult, web, covtype, mnist, rcv1, and sensit.The datasets vary in sample counts and feature dimensions.
  • Learning rates are selected from {10^-k, 2 × 10^-k, 5 × 10^-k}, while APCG regularizer weights use {10^-k}.
  • The tuning procedure is fully automated to provide a fair and strong comparison.
  • For accelerated methods, the reported learning-rate factor multiplies the theory-predicted parameter, including τ1 for Katyusha and Katyushans.
  • Catalyst additionally uses a stopping rule based on reducing the inner-loop duality gap to roughly one fourth of the previous epoch’s gap.

C.1 Proof of Theorem 4.1

The proof establishes Theorem 4.1 by applying the preceding lemmas across iterations and epochs, conditioning on epoch-wise randomness, and telescoping the resulting inequalities.

  • C.1 Proof of Theorem 4.1: The parameter choices satisfy the presumptions of Lemma 2.6, allowing the proof to invoke the lemma through defined objective gaps.The proof defines D_k and eD_s using objective differences from F(x∗).
  • C.1 Proof of Theorem 4.1: The iteration inequalities are summed over each epoch and combined using convexity of F.The argument relates the epoch-level quantity eD_s to sums of the iteration-level quantities D_k.
  • C.1 Proof of Theorem 4.1: The proof conditions on all randomness before the current epoch, so only the current epoch contributes randomness to the inequality.This conditioning supports the epoch-by-epoch expectation argument.
  • C.1 Proof of Theorem 4.1: A base case is established for s = 0, after which the inequalities are telescoped over epochs s = 0, 1, . . . , S −1.The final step scales the left-hand side by 2τ_1,S−1^2 m before concluding.

D.1 One-Iteration Analysis

The one-iteration analysis bounds Katyusha’s stochastic update by combining variance control, proximal mirror descent, convexity, smoothness, and the coupling of y_k, z_k, and the snapshot point.

  • D.1 One-Iteration Analysis: The analysis fixes y_k, z_k, and x_k+1, leaving the random index i as the sole randomness in one iteration.The snapshot point is abbreviated by ex in the subsection, and expectations are taken over the stochastic choice.
  • D.1 One-Iteration Analysis: The y_k+1 bound uses its definition, smoothness of f, and Young’s inequality before taking expectation.The analysis also uses the identity for the variance of a random vector and the first inequality in the proof.
  • D.1 One-Iteration Analysis: The variance upper bound accounts for the absence of a mini-batch and replaces the uniform smoothness parameter with the non-uniform setting’s L.The supporting inequality uses each convex, L_i-smooth component f_i.
  • D.1 One-Iteration Analysis: A lemma identical to Lemma 2.5 is reused without repeating its proof.This keeps the one-iteration derivation focused on the additional coupling and variance steps.
  • D.1 One-Iteration Analysis: The coupling step uses x_k+1 as a convex combination of y_k, z_k, and ex, with τ_1 constrained by α and L.It combines proximal mirror descent with the variance and gradient-related lemmas.
  • D.1 One-Iteration Analysis: The second coupling step converts objective gaps into distances to the minimizer by applying convexity to the first coupling inequality.The resulting relation involves F(y_k) − F(x∗), F(y_k+1) − F(x∗), F(ex) − F(x∗), and distances involving z_k and z_k+1.

D.2 Proof of Theorem 5.4

The proof of Theorem 5.4 combines the one-iteration inequality across epochs, handles multiple parameter cases, and telescopes the resulting bounds using strong convexity and carefully chosen coefficients.

  • D.2 Proof of Theorem 5.4: The proof begins by defining D_k and eD_s and rewriting Lemma D.5 in terms of objective gaps.These quantities organize the iteration-level and snapshot-level terms for epoch-wise summation.
  • D.2 Proof of Theorem 5.4: The one-iteration inequality is summed over the m iterations of each epoch while conditioning on randomness from earlier epochs.The resulting weighted sum uses factors θ^j.
  • D.2 Proof of Theorem 5.4: The proof considers two cases and four subcases to select parameters such as L⋄, τ_1, τ_2, and α.One displayed case assumes L > L_m and sets L⋄ = L with a corresponding τ_2 choice.
  • D.2 Proof of Theorem 5.4: The parameter choices ensure inequalities linking τ_1, τ_2, θ, m, α, and σ, including bounds based on ασ ≤ 1 4m.These relations are used to derive the epoch-level inequality needed for telescoping.
  • D.2 Proof of Theorem 5.4: The epoch inequalities are telescoped over s = 0, 1, . . . , S −1 using the specified output point and strong convexity of F.Strong convexity supplies F(x0) − F(x∗) ≥ σ 2 ∥x0 − x∗∥2, while the output choice controls the final combination.
  • D.2 Proof of Theorem 5.4: In one parameter regime, the proof chooses τ_1 = 1 2m and α = 2m 3L, with α > 1 4σm.The accompanying coefficient bounds ensure the telescoped inequality applies in that regime.

E Appendix for Section 6

The appendix presents pseudocodes for Katyusha2 and Katyusha2ns, then analyzes one iteration; the final theorems follow as direct corollaries of that analysis.

  • E Appendix for Section 6: The section includes complete pseudocodes for Katyusha2 and Katyusha2ns before presenting their one-iteration analyses.The analyses follow the same general spirit as the earlier Section 2.1 treatment.
  • E Appendix for Section 6: The final proofs of Theorems 6.1 and 6.2 are direct corollaries of the one-iteration analyses.The appendix states that the remaining details were already given in Sections 2.2 and C.1.
  • E Appendix for Section 6: The pseudocode samples an index i randomly with probability L_i/nL.This sampling rule appears in the algorithmic steps for the appendix methods.
  • E Appendix for Section 6: The algorithm sets τ_1,s and α_s from the epoch index and L, and computes the snapshot gradient µ_s as ∇f(ex_s).The displayed pseudocode gives τ_1,s ← 2 s+4, α_s ← 1 9τ_1,sL, and µ_s ← ∇f(ex_s).

E.2 One-Iteration Analysis

This section develops the one-iteration analysis of Katyusha and its proximal, variance, and coupling lemmas. The analysis uses a convex combination of y_k, z_k, and the epoch reference point, with τ_2 fixed to 1/2.

  • The analysis treats y_k, z_k, and x_{k+1} as fixed, leaving only the stochastic gradient choice as random.The epoch reference is abbreviated as the snapshot point corresponding to the iteration’s epoch.
  • The proximal-gradient lemma uses smoothness, Young’s inequality, and expectation over the stochastic gradient estimator.Its bound includes a term involving the squared difference between the true and estimated gradients.
  • The proof combines proximal gradient descent, a variance upper bound, and proximal mirror descent.The variance bound follows from convex smoothness, while the mirror-descent lemma uses a general Bregman divergence and strong convexity.
  • The proximal mirror-descent step relies on the Bregman three-point equality and strong convexity of ψ.These ingredients produce the divergence and regularization terms needed for the coupling analysis.
  • The first coupling step uses x_{k+1}=τ_1z_k+τ_2x̃+(1−τ_1−τ_2)y_k with τ_1≤1/(9αL) and τ_2=1/2.The resulting inequality combines the proximal, variance, and smoothness bounds through the auxiliary point v.
  • A second coupling lemma follows under the same parameter choices, and its proof is analogous to the earlier coupling argument.The appendix explicitly treats this step as a direct reuse of the preceding analysis.
Loading 1603.05953v6…