Source-linked AI summary
SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient
Lam M. Nguyen, Jie Liu, Katya Scheinberg, Martin Takáč
TL;DR
Large finite-sum optimization problems make full-gradient methods expensive, while stochastic methods can converge slowly or require delicate tuning. The paper proposes SARAH and SARAH+ with recursive stochastic-gradient updates, proving linear convergence under strong convexity and for SARAH’s inner loop. Experiments demonstrate the algorithms’ efficiency.
Problem
Large finite-sum problems require methods that avoid repeatedly computing costly full gradients while improving on stochastic optimization behavior.
Method
SARAH and SARAH+ use recursive stochastic-gradient estimates, combine stochastic and occasional exact gradient information, and avoid storing n past gradients.
Results
SARAH has sublinear convergence for smooth convex functions, linear convergence for strongly convex functions and inner loops, and computational complexity O((n + κ) log(1/ε)) under the stated strongly convex settings.
Takeaways & Limitations
SARAH provides a theoretically and numerically more stable alternative to SVRG, with a practical stopping criterion for its inner loops.
Takeaways & Limitations
The theoretical analysis requires convexity and, for several results, stronger assumptions including μ-strong convexity or related assumption combinations.
Abstract
from arXiv · showhide
In this paper, we propose a StochAstic Recursive grAdient algoritHm (SARAH), as well as its practical variant SARAH+, as a novel approach to the finite-sum minimization problems. Different from the vanilla SGD and other modern stochastic methods such as SVRG, S2GD, SAG and SAGA, SARAH admits a simple recursive framework for updating stochastic gradient estimates; when comparing to SAG/SAGA, SARAH does not require a storage of past gradients. The linear convergence rate of SARAH is proven under strong convexity assumption. We also prove a linear convergence rate (in the strongly convex case) for an inner loop of SARAH, the property that SVRG does not possess. Numerical experiments demonstrate the efficiency of our algorithm.
1. Introduction
The paper targets large finite-sum optimization problems where full-gradient methods are costly and SGD converges more slowly. It introduces SARAH to combine variance reduction, fixed learning rates, and reduced gradient storage while retaining strong-convexity guarantees.
- Motivation: Large n makes repeatedly computing full gradients impractical for otherwise smooth, convex objectives.GD can achieve linear convergence under strong convexity, but each iteration requires the full gradient.
- Motivation: SGD reduces per-iteration cost by up to n times but has sublinear convergence in the strongly convex case and requires sensitive learning-rate selection.Its practical convergence depends strongly on choosing the diminishing sequence {ηt}.
- Related methods: Variance-reduced methods such as SAG/SAGA, SVRG, and S2GD use the finite-sum structure, fixed learning rates, and faster convergence than SGD.The paper positions SARAH among methods that combine deterministic and stochastic optimization aspects.
- Contributions: SARAH combines past stochastic-gradient information with occasional exact gradients without storing n past stochastic gradients.Its design aims to improve on properties of SAGA and SVRG.
- Contributions: SARAH has sublinear convergence for general convex functions and linear convergence for strongly convex functions, with a constant learning rate.The paper also analyzes the learning rate and inner-loop length.
2. Stochastic Recursive Gradient Algorithm
SARAH uses an outer loop with a full gradient and an inner loop that recursively updates a stochastic gradient estimate. Its inner-loop steps use accumulated stochastic information rather than independent stochastic-gradient directions.
- Algorithm: The key SARAH operation recursively updates the stochastic gradient estimate before updating the iterate.The method is presented as a stochastic recursive gradient algorithm.
- Algorithm: The algorithm samples indices uniformly, updates wt+1 = wt −ηvt, and randomly selects an inner-loop iterate as the next outer-loop point.The inner loop runs for a prescribed size m.
- Estimator: Unlike SVRG, SARAH’s stochastic gradient estimate is not unbiased at each step, although its total expectation equals the expected gradient at the iterate.This distinguishes SARAH from both SVRG-type unbiased estimators and SAG/SAGA.
- Algorithm: Each outer iteration computes one full gradient, while the inner loop uses stochastic gradients and a fixed learning rate.This structure is shared with SVRG at the outer-loop level.
- Inner loop: SARAH’s inner-loop direction adds and subtracts component gradients from the previous direction, requiring two stochastic-gradient evaluations per inner iteration.The total work per outer iteration is described as O(n+m).
3. Theoretical Analysis
Under smoothness, convexity, and strong-convexity assumptions, SARAH achieves sublinear convergence for general convex problems and linear convergence for strongly convex problems. Its recursive inner-loop estimates converge linearly, with stronger guarantees than SVRG in the strongly convex setting and improved theoretical rates in outer iterations.
- Assumptions: SARAH assumes L-smooth component functions and analyzes general convex, aggregate strongly convex, and componentwise strongly convex cases.The componentwise strong-convexity assumption implies aggregate strong convexity, but not conversely.
- Inner-loop behavior: Unlike SVRG, SARAH’s stochastic-step variance decreases as inner iterations increase, approaching zero without additional outer loops.The contrast is illustrated on a two-dimensional quadratic example and in regularized logistic regression experiments.
- General convex case: Under general convexity, SARAH has sublinear convergence in a single inner loop and total complexity O(n + 1/ε^2) for an ε-accurate solution.The result applies under smoothness and convexity assumptions.
- Outer-loop convergence: With multiple outer iterations, SARAH achieves total complexity O((n + 1/ε) log(1/ε)) under general convexity and O((n + κ) log(1/ε)) in the strongly convex case.The strongly convex guarantee uses η = 1/(2L), m = 4.5κ, and T = ⌈log(∥∇P(w̃0)∥^2/ε) / log(9/7)⌉.
- Comparison with SVRG: SARAH permits η < 1/L versus SVRG’s η < 1/(4L), and its outer-iteration convergence rate is always smaller with the same m and η.Theoretical plots also show a significantly larger optimal learning rate and improved convergence rates for SARAH.
4. A Practical Variant
SARAH+ adaptively selects the inner-loop size using gradient-norm reduction, reducing sensitivity to manual m choices while retaining SARAH’s recursive behavior.
- Adaptive inner-loop control: SARAH+ adaptively chooses the inner-loop size m using a stopping criterion based on ||v_t||^2, with a maximum-step safeguard.The method sets the next outer-loop iterate to the last inner-loop iterate rather than a randomly selected intermediate one.
- Adaptive inner-loop control: The inner loop samples indices and updates v_t recursively from a stochastic gradient difference plus the previous estimate.Each iterate uses w_{t+1} = w_t − ηv_t.
- Practical behavior: SARAH+ can terminate early, avoids unnecessarily careful m choices, and reduces to gradient descent when γ = 1.With γ = 1, the while loop does not proceed.
- Practical behavior: For rcv1 and news20, γ = 1/8 appeared optimal, while performance remained robust across datasets and nearby γ choices.Larger γ values triggered insufficient inner-loop reduction, whereas smaller values added steps without substantial progress.
- Practical behavior: Unlike SVRG, SARAH+ inherits SARAH’s consistent expected decrease of ||v_t||^2 during inner loops, enabling adaptive termination.SVRG’s corresponding norm may exhibit side fluctuations.
5. Numerical Experiments
Experiments compare SARAH and SARAH+ with modern first-order methods on regularized logistic regression datasets, emphasizing convergence, tuning, and inner-loop sensitivity.
- Experimental setup: SARAH and SARAH+ were evaluated against SVRG, SAG, SGD+, and FISTA on covtype, ijcnn1, news20, and rcv1.The experiments used predefined or randomly split training and testing sets, with 70% training and 30% testing for covtype and news20.
- Convergence results: Across four datasets, SARAH quickly caught up to or surpassed competing methods, showing a faster decrease rate overall.It was sometimes comparable to or slightly worse than other methods at the beginning.
- Convergence results: On ijcnn1 and news20, SARAH and SVRG consistently surpassed the other methods.On covtype and rcv1, SARAH, SVRG, and SAG were comparable, with some advantage for SARAH on covtype.
- Parameter sensitivity: SARAH’s optimal learning rates varied less across datasets and approximated its theoretical upper bound of 1/L.The study reports that this made the ideal learning rate easier to find empirically.
- Parameter sensitivity: With improper inner-loop sizes, SARAH and SVRG loss residuals could increase from 10^-15 to 10^-3 on covtype and ijcnn1.The reported increases occurred within 40 effective passes on covtype and 17 effective passes on ijcnn1.
6. Conclusion
The paper proposes SARAH, a variance-reducing stochastic recursive gradient algorithm, and establishes convergence and practical stopping results for it.
- SARAH combines properties of existing methods including SAGA and SVRG.
- For smooth convex functions, SARAH has a sublinear convergence rate.
- For strongly convex problems, SARAH achieves linear convergence and computational complexity comparable to SVRG and SAG.
- SARAH’s convergence rate constant is smaller than SVRG’s, and its stability is supported theoretically and numerically.
- The linear convergence of SARAH’s inner loops motivates SARAH+, which uses a simple stopping criterion.
A. Technical Results
The technical results establish supporting lemmas for convex and strongly convex smooth functions and derive parameter choices for SARAH’s convergence analysis.
- A cited lemma assumes that f is convex and L-smooth for arbitrary w and w′.
- Equation (16) does not require convexity of f.
- A cited lemma assumes that f is µ-strongly convex and L-smooth for arbitrary w and w′.
- With η = 1/(θL), θ > 1, and fixed σ_m, the analysis considers an optimal choice of m.
- The proof tracks the information in F_j, including iterates w_0, . . ., w_j and gradient estimates v_0, . . ., v_{j−1}.
B.4. Proof of Lemma 6
The proof of Lemma 6 optimizes the inner-loop length and parameter θ by expressing the convergence rate in terms of θ and differentiating the resulting complexity.
- With η = 1/(θL) and κ = L/µ, the proof rewrites the convergence rate α_m in terms of θ.
- The optimal θ is obtained by setting the derivative of m(θ) to zero while holding σ_m fixed.
- The proof then substitutes the optimal θ into m(θ) to obtain the optimal m.
- The recursive argument uses strong convexity, smoothness, η < 2/L, and η ≤ 2/(µ + L).
B.8. Proof of Corollary 2
The corollary sets parameters to reach ε-accuracy and derives the resulting logarithmic dependence on the target accuracy.
- For an ε-accuracy solution, the analysis chooses Δ = ε/4, α = 1/2, and η = 2/(3L).
- Achieving ε-accuracy requires δ = O(ε), equivalently m = O(1/ε).
- The sufficient condition is E[∥∇P(ŵ_s)∥^2] ≤ ε.
- The total complexity is O((n + (1/ε)) log(1/ε)).
B.9. Proof of Corollary 3
The corollary selects SARAH parameters through Theorem 4 and bounds the expected final gradient norm by ε after T iterations. Counting gradient evaluations then yields the total computational complexity.
- Parameter selection: Choosing θ∗ = 2 gives m∗ = 4.5κ −1, motivating η = 1/(2L) and m = 4.5κ for SARAH.These parameter choices allow σ_m to be evaluated using the theorem's contraction analysis.
- Iteration bound: Theorem 4 specifies an iteration count T for running SARAH until the expected gradient norm reaches the target tolerance.The iteration count is expressed using the initial gradient norm and ε.
- Convergence guarantee: E[∥∇P(˜w_T)∥2] < (7/9)^T∥∇P(˜w_0)∥2 ≤ ε, establishing the required accuracy after T iterations.The contraction factor is bounded by 7/9 under the selected parameters.
- Computational complexity: The total complexity is derived by treating the number of gradient evaluations as the main computational cost.The passage introduces the gradient-evaluation accounting used for the final complexity expression.