Source-linked AI summary
Don't Jump Through Hoops and Remove Those Loops: SVRG and Katyusha are Better Without the Outer Loop
Dmitry Kovalev, Samuel Horvath, Peter Richtarik
TL;DR
SVRG and Katyusha rely on outer loops that periodically compute full gradients, creating a structural target for simplification. The paper replaces those loops with probabilistic gradient updates, preserves their theoretical convergence properties, and reports substantially better practical behavior.
Problem
SVRG and Katyusha require outer loops with full-data gradient passes, while variance-reduced methods are not yet successful for production-grade neural-network training.
Method
The paper develops L-SVRG and L-Katyusha, replacing deterministic outer loops with per-iteration coin flips that trigger full-gradient recomputation with probability p.
Results
The loopless methods retain the theoretical convergence rates of SVRG and Katyusha and show superior practical behavior in numerical experiments.
Takeaways & Limitations
Removing the outer loop preserves the methods' theoretical advantages while making them easier to write down, comprehend, and analyze.
Takeaways & Limitations
Variance-reduced methods have not yet succeeded in training production-grade neural networks.
Abstract
from arXiv · showhide
The stochastic variance-reduced gradient method (SVRG) and its accelerated variant (Katyusha) have attracted enormous attention in the machine learning community in the last few years due to their superior theoretical properties and empirical behaviour on training supervised machine learning models via the empirical risk minimization paradigm. A key structural element in both of these methods is the inclusion of an outer loop at the beginning of which a full pass over the training data is made in order to compute the exact gradient, which is then used to construct a variance-reduced estimator of the gradient. In this work we design {\em loopless variants} of both of these methods. In particular, we remove the outer loop and replace its function by a coin flip performed in each iteration designed to trigger, with a small probability, the computation of the gradient. We prove that the new methods enjoy the same superior theoretical convergence properties as the original methods. However, we demonstrate through numerical experiments that our methods have substantially superior practical behavior.
1 Introduction
Variance-reduced methods target finite-sum supervised-learning problems by reducing stochastic-gradient variance, with SVRG and Katyusha combining full-gradient reference passes and stochastic updates. In strongly convex settings, they achieve faster theoretical rates than gradient descent and SGD.
- Finite-sum empirical risk minimization underlies supervised models including ridge regression, support vector machines, logistic regression, and neural networks.
- SVRG and Katyusha use an outer full-data pass to compute a reference gradient, then adjust stochastic gradients using the current and reference points.Their estimator is g_k = ∇f_i(x_k) − ∇f_i(w_k) + ∇f(w_k).
- The adjusted estimator remains unbiased, while its variance progressively decreases during optimization, producing faster convergence.
- O((n + L/µ) log 1/ϵ) is SVRG's iteration complexity, improving on gradient descent and SGD in the strongly convex regime.
- O((n + √(nL/µ)) log 1/ϵ) is Katyusha's accelerated rate, superior to SVRG when L/µ ≥ n.The supplied passage presents this rate as optimal in a precise sense.
2 Contributions
The paper removes SVRG and Katyusha’s problematic outer loops by using probabilistic gradient-refresh steps, while preserving fast convergence and improving practical behavior. The loopless analysis is simpler and identifies useful parameter regimes for the resulting methods.
- Motivation: Removing the outer loop avoids choosing an inner-loop length that depends on potentially unknown or inaccurate strong-convexity information.The paper identifies this parameter-selection issue as a source of difficulty in the original methods.
- Two loopless methods: L-SVRG and L-Katyusha replace the outer loop with a per-iteration coin flip that refreshes the full gradient with probability p.With probability 1 − p, the previous reference gradient is retained.
- Fast rates are preserved: The loopless methods preserve the same fast theoretical convergence rates as their original counterparts.For L-SVRG with η = 1/6L and p = 1/n, the complexity is O((n + L/µ) log 1/ϵ).
- Fast rates are preserved: L-SVRG achieves optimal complexity O((n + L/µ) log 1/ϵ) for a broad interval of refresh probabilities, including p ∈ [µ/L, 1/n] when L/µ ≫ n.This contrasts with standard SVRG, whose outer-loop size is approximately L/µ and is often difficult to choose when µ is unknown or estimated loosely.
- Simplified analysis: A single-iteration analysis establishes convergence for the loopless approach, replacing the elaborate inner-loop aggregation needed for the original methods.The resulting proofs are described as simpler and the complexity results as more insightful.
- Superior empirical behaviour: Extensive experiments on synthetic and real data find the loopless methods superior to their loopy variants, with L-SVRG robust across its theoretically predicted probability interval.The reported comparison states that even the worst L-SVRG case outperforms the best SVRG case.
3 Loopless SVRG (L-SVRG)
L-SVRG removes SVRG’s deterministic outer loop and replaces it with probabilistic full-gradient updates. Its analysis yields optimal complexity across a range of update probabilities, while adapting without requiring known µ.
- Algorithm: L-SVRG removes SVRG’s outer loop and updates the reference gradient probabilistically at each iteration.With probability p, it computes a full gradient and updates the reference point; otherwise, it keeps the previous reference gradient.
- Algorithm: The expected time between full-gradient passes is 1/p, so p controls the frequency of reference-point updates.
- Convergence analysis: The method’s analysis combines variance, distance, and function-suboptimality bounds through a Lyapunov-function recursion.The resulting proof uses several lemmas to establish contraction of the Lyapunov function.
- Convergence analysis: The step size need not depend on µ, while the resulting complexity still adapts to the strong-convexity parameter.
- Convergence analysis: L-SVRG attains optimal total complexity O((n + L/µ) log 1/ε) for p within a range proportional to 1/n and µ/L.This range is expressed as p ∈ [min{c/n, cµ/L}, max{c/n, cµ/L}], with c = Θ(1).
4 Loopless Katyusha (L-Katyusha)
L-Katyusha applies the loopless probabilistic-gradient-update idea to Katyusha. The resulting analysis preserves optimal-rate behavior while simplifying the treatment of the original double-loop method.
- Algorithm: L-Katyusha removes Katyusha’s outer loop and probabilistically updates the full-gradient reference point.The reference point is updated to the current iterate with probability p and otherwise remains unchanged.
- Algorithm: The algorithm uses Katyusha’s parameterized updates with probability p, stepsize η, and σ = µ/L.
- Convergence analysis: Its convergence analysis tracks function values and pointwise convergence through a Lyapunov function involving y_k, w_k, and z_k.Although x_k is absent from the Lyapunov function, its convergence follows from the algorithm definition and smoothness.
- Convergence analysis: The analysis establishes contraction of the Lyapunov function using bounds involving ησ, θ_1, θ_2, and p.
- Convergence analysis: For ill-conditioned problems, p = Θ(1/n) yields the optimal total complexity for L-Katyusha.The expected stochastic-gradient cost per iteration is O(1 + pn), and the resulting total complexity is optimal when p scales as 1/n.
5 Numerical Experiments
Experiments evaluate loopless and original methods on regularized logistic regression using synthetic and LIBSVM datasets. Across the reported comparisons, loopless methods match or outperform their loopy counterparts, sometimes substantially.
- Setup: The experiments use binary logistic regression with L2 regularization on four LIBSVM datasets: a9a, w8a, mushrooms, and phishing.
- Setup: L-SVRG and L-Katyusha are compared with their original methods rather than SAGA because SAGA’s memory requirements can preclude its use.
- Results: L-SVRG is always better than SVRG on the reported datasets and can be faster by several orders of magnitude.
- Results: L-Katyusha performs at least as well as Katyusha and is significantly faster in some cases.The parameters for all methods are selected according to their respective theoretical prescriptions.
- Results: Across choices of p in the theoretically predicted interval, L-SVRG is robust, and its worst case outperforms SVRG’s best case.
- Results: When all methods are plotted across datasets and regularizer weights, loopless methods are not worse and are sometimes significantly better.
Supplementary Material: SVRG and Katyusha are Better Without the Outer Loop
The supplementary material introduces auxiliary variance and vector inequalities used in the convergence analysis. These lemmas provide basic tools for the paper’s proofs.
- Auxiliary lemmas: Lemma A.1 decomposes the variance of a random vector relative to another vector.
- Auxiliary lemmas: The next auxiliary inequality follows from Jensen’s inequality applied to the squared norm.
- Auxiliary lemmas: Lemma A.2 states an inequality for arbitrary vectors a_1, a_2, ..., a_k.
B Proofs for Algorithm 1 (L-SVRG)
The proofs use the shorthand f* = f(x*) throughout.
- The proofs define f* as f(x*) for simplicity.
B.1 Proof of Lemma 3.1
The proof invokes the definition of x_{k+1} and the unbiasedness of g_k.
- The definition of x_{k+1} and unbiasedness of g_k provide the proof’s starting guarantee.
B.2 Proof of Lemma 3.2
The proof bounds the relevant quantity using a contraction term and an objective-gap term.
- Equation (8) bounds the expression using 4L(f(x_k) − f*) and p√2η^2D_k.
- The bound includes a contraction term (1 − p)D_k and an objective-gap term 8Lη^2(f(x_k) − f*).
B.4 Proof of Lemma 3.4
The proof combines earlier lemmas, variance bounds, definitions, and an η-dependent inequality to establish the desired result.
- The proof combines Lemmas 3.1 and 3.3.
- Using η ≤ 1/(6L) yields the desired inequality.
- The variance of g_k is upper-bounded starting from its definition.
- The proof begins one step by using the definition of z_{k+1}.
- Young’s inequality is used to justify the last inequality in one bound.
- The proof concludes after setting β = ηθ_1L/(1−ηθ_1).
- The argument uses the definition of w_{k+1} from Algorithm 2 and then the definition of W_k in (17).
C.5 Proof of Lemma 4.5
The proof combines previous lemmas to derive the target inequality, using convexity of f(x), the definition of W_k, and Lemma 4.4. The resulting bound concludes the proof of Lemma 4.5.
- The argument combines all previous lemmas to obtain the intermediate bound.
- Convexity of f(x) is used in the second inequality.
- The definition of W_k transforms the bound into an expression involving p(1 + θ_1)W_k.
- Lemma 4.4 adds the remaining W_k and θ_2(1 + θ_1)Y_k terms to the inequality.
- The final rearrangement yields the stated bound and concludes the proof.