PaperlayerView exact revision on arXiv

Source-linked AI summary

Minimizing Finite Sums with the Stochastic Average Gradient

Mark Schmidt, Nicolas Le Roux, Francis Bach

arXiv:1309.2388v2math.OCcs.LGstat.COstat.ML

TL;DR

Large finite-sum optimization problems need the low iteration cost of stochastic gradients without sacrificing the faster convergence of full gradients. The paper proposes SAG, which stores recent component gradients while computing one new gradient per iteration; it attains O(1/k) convergence for convex objectives and linear convergence for strongly-convex objectives, with numerical evidence of strong performance. Its guarantees and comparisons depend on finite-data smooth-convex structure and problem-specific conditioning assumptions.

  • Problem

    Large finite-sum problems require methods that remain affordable when n is very large, while standard SG methods have slower convergence rates than FG methods.

  • Method

    SAG randomly selects one component per iteration and stores the most recent gradient for each component, combining this memory into an SG-cost update.

  • Results

    SAG achieves O(1/k) convergence for convex objectives and linear convergence for strongly-convex objectives, while retaining iteration cost independent of n and often outperforming SG and FG methods empirically.

  • Takeaways & Limitations

    SAG is useful for finite-data problems where only a few passes through the dataset are affordable and can be preferable to SG for finding the ERM.

  • Takeaways & Limitations

    The analysis does not explain why empirical risk minimizers often achieve better true-risk performance, and rate comparisons depend on the Lipschitz assumptions used for SAG versus FG.

Abstract

from arXiv · show

We propose the stochastic average gradient (SAG) method for optimizing the sum of a finite number of smooth convex functions. Like stochastic gradient (SG) methods, the SAG method's iteration cost is independent of the number of terms in the sum. However, by incorporating a memory of previous gradient values the SAG method achieves a faster convergence rate than black-box SG methods. The convergence rate is improved from O(1/k^{1/2}) to O(1/k) in general, and when the sum is strongly-convex the convergence rate is improved from the sub-linear O(1/k) to a linear convergence rate of the form O(p^k) for p \textless{} 1. Further, in many cases the convergence rate of the new method is also faster than black-box deterministic gradient methods, in terms of the number of gradient evaluations. Numerical experiments indicate that the new algorithm often dramatically outperforms existing SG and deterministic gradient methods, and that the performance may be further improved through the use of non-uniform sampling strategies.

1 Introduction

Finite-sum optimization balances full-gradient methods’ convergence against stochastic methods’ low per-iteration cost. SAG uses finite-data structure and stored gradients to preserve SG iteration cost while attaining FG-like rates, often outperforming both in effective data passes.

  • Large-scale finite-sum problems arise in applications such as least-squares and logistic regression, where computing a full gradient becomes costly as n grows.
  • FG methods have sublinear convergence for convex objectives and linear convergence for strongly-convex objectives, but each iteration costs O(n).The linear rate is geometric, with error reduced by a fixed fraction per iteration.
  • SG methods have iteration cost independent of n because each iteration samples and differentiates one function, but their expected convergence rates are slower and sublinear.The sampled gradient is an unbiased estimate of the full gradient.
  • SAG stores the most recent gradient for each function, combining gradients across the sum while computing only one new gradient per iteration.This preserves SG-like iteration cost while incorporating information from every function.
  • With constant step size, SAG achieves O(1/k) convergence for convex objectives and linear convergence for strongly-convex objectives.The paper also reports that SAG can be faster than standard FG methods in effective passes through the data.
  • For empirical-risk minimization, SAG is preferable to SG methods for finding the ERM, although the analysis does not explain why ERMs may perform better on true risk.
  • Numerical comparisons indicate that SAG may be useful when only a few passes through the dataset are affordable, while implementation can reduce memory from O(np) to O(n) for common linear models.
  • The paper extends earlier work with a general convex-case rate and a faster large-step-size analysis that can make SAG nearly n times as fast as standard gradient methods on ill-conditioned problems.The stronger analysis uses a generalized Lyapunov function.

2 Related Work

The related work contrasts SAG with stochastic, accelerated, hybrid, incremental, and averaging methods that seek faster convergence or lower iteration costs. It positions SAG as distinct through its gradient-memory update and convergence guarantees under broader conditions.

  • Momentum: Momentum methods geometrically weight previous gradients, whereas SAG averages the most recent evaluation of each component gradient.Momentum can improve practical performance but is not known to yield faster convergence rates.
  • Gradient Averaging: Gradient averaging with a constant step size can improve convergence-rate constants but does not improve SG methods' sublinear rates.The approach averages all previous gradients, unlike SAG's most-recent-gradient selection.
  • Iterate Averaging: Iterate averaging can achieve Newton-like SG asymptotic efficiency and make convergence more robust to the exact step-size sequence.These properties are reported for suitable step sizes and averaged iterates rather than averaged gradients.
  • Related Alternatives: Prior stochastic variants of full-gradient acceleration, hybrid schemes, and IAG methods offer narrower guarantees or additional parameter and stability limitations.Examples include cyclic IAG analyses limited to strongly-convex quadratics and hybrid weighting described as numerically unstable.
  • Subsequent Work: Subsequent research extended faster stochastic rates to constrained and non-smooth problems, memory-free methods, Newton-like variants, and other algorithms.These developments are surveyed as later work following the original SAG contribution.

3 Convergence Analysis

Under convex, differentiable, Lipschitz-gradient assumptions, the analysis establishes O(1/k) convergence for convex objectives and linear convergence for strongly-convex objectives. The results also characterize initialization, step-size, conditioning, local adaptivity, and comparisons with other first-order methods.

  • Assumptions: Under standard assumptions, each f_i is convex and differentiable with an L-Lipschitz continuous gradient, and a minimizer x* exists.The framework allows the regular convex case and assumes strong convexity only when deriving the corresponding specialized result.
  • Main convergence result: With constant step size α_k = 1/16L, SAG achieves an O(1/k) convergence rate for convex objectives and a linear rate for strongly-convex objectives.The theorem provides bounds for different initializations and uses a Lyapunov function that dominates expected sub-optimality.
  • Main convergence result: The results apply to the average iterate and, with a proof adjustment, to any iterate whose function value is no greater than the average value through iteration k.Thus, the guarantee also covers the best iterate.
  • Initialization and n-dependence: An SG-based initialization changes the rates' dependence on n to O(√n/k) in the convex case and O(ρ^k/n) in the strongly-convex case.These improve on the O(n/k) and O(ρ^k) dependencies implied directly by the theorem, although the experiments use an early-iteration SAG variant instead.
  • Adaptivity and robustness: The fixed step size adapts to local strong convexity, potentially yielding local linear convergence even when the objective is not globally strongly-convex.This contrasts with SG step-size sequences that typically depend on global constants and do not adapt to local strong convexity.
  • Comparisons by conditioning: For ill-conditioned problems with n ≤ 2L/µ, n does not appear in SAG's rate, while n iterations in the well-conditioned setting reduce error by at least exp(−1/8).The analysis also reports that n iterations of SAG can be faster than the lower bound for FG methods, but cautions that the comparison uses different Lipschitz constants.

4 Implementation Details

The implementation details reduce SAG’s storage and iteration costs by exploiting gradient structure and sparse data, while also modifying normalization, regularization, initialization, and sampling strategies for practical performance.

  • Structured gradients: O(n) storage replaces O(np) storage for linearly parameterized models by storing one scalar per example instead of each full gradient.The reduction uses the fixed structure of gradients in these models.
  • Just-in-time parameter updates: Sparse gradients enable just-in-time updates whose iteration cost is proportional to the sampled example’s nonzeros rather than all p variables.The method avoids explicitly storing the full parameter vector after every iteration and updates only coordinates needed by the sampled sparse vector.
  • Initialization and normalization: Normalizing by m, the number of examples seen at least once, avoids overly small early steps caused by zero-initialized gradient memory and improved experimental performance.The modified method outperformed both basic SAG and an SG/SAG hybrid in the reported experiments.
  • Regularization and warm starts: For regularized objectives, SAG can use the exact regularizer gradient while approximating only the finite-sum loss gradients, with sparse implementations preserving reduced storage and efficient updates.Representing x as κz makes scalar regularization updates constant-time; warm-starting related regularized problems may further improve performance.
  • Step-size selection: 1/L steps always converged and often outperformed the analytically suggested 1/16L step in experiments, despite lacking a formal analysis for that choice.The experiments also considered 2/(L + nµ) in strongly-convex settings.
  • Non-uniform sampling: Non-uniform sampling based on Lipschitz constants can improve the convergence bound in some constructions, but direct Lipschitz-proportional sampling does not converge in general.The paper suggests interpolating between Lipschitz and uniform sampling by duplicating each function Li + c times.

5 Experimental Results

Experiments compare SAG with full-gradient, stochastic-gradient, coordinate, mini-batch, step-size, and sampling strategies. SAG generally combines strong early performance with continued progress, while practical outcomes depend on step size, problem dimensions, and sampling choices.

  • Comparison to FG and SG Methods: SG methods perform best when only one pass through the data is affordable, whereas full-gradient methods are recommended when several hundred passes are feasible.SAG is positioned between these extremes, when more than one pass is possible but extensive passes are not affordable.
  • Comparison to FG and SG Methods: SAG starts substantially better than full-gradient methods and continues improving after the first few passes, outperforming SG methods later.On most datasets, sophisticated full-gradient methods did not catch up after 50 passes through the data.
  • Comparison to Coordinate Optimization Methods: Lipschitz coordinate sampling greatly improves PCD when p > n, but has little effect when n > p.The comparison distinguishes uniform and Lipschitz sampling across the top and bottom versus middle rows of Figure 2.
  • Step-Size Strategies: The step size αk = 1/L performs extremely well for p > n and better than the other tested choices on all but one remaining dataset.The choice αk = 2/(L + nµ) performs similarly or slightly better except on one dataset, where it performs poorly.
  • Step-Size Strategies: Line search performs as well as or better than constant step-size strategies and similarly to selecting the best step size in hindsight.By contrast, αk = 1/2nL performs poorly, while αk = 1/16L is consistently reasonable.
  • Comparison to FG and SG Methods: SAG substantially outperforms cyclic IAG because random sampling permits step sizes 100 to 10000 times larger, yielding better performance by several orders of magnitude.The authors attribute this difference to larger SAG step sizes that would cause IAG iterations to diverge.
  • Mini-Batches: Mini-batches trade higher iteration cost for faster convergence, and experiments used batches up to 500 without performance loss despite a conservative theoretical bound.Larger mini-batches require larger step sizes to achieve fast convergence.
  • Mini-Batches: For a quantum mini-batch of 20000, the tested reciprocal step sizes were 4.4 · 10^-4, 5.5 · 10^-2, and 3.7 · 10^-1 for Lmax, Lmean, and LHessian.For covertype, the corresponding values were 2.1 · 10^-5, 6.2 · 10^-2, and 4.1 · 10^-1.

6 Discussion

The discussion compares SAG with related stochastic, coordinate, surrogate, and mixed-optimization methods. These alternatives share some convergence benefits, but differ in memory, parameter, regularization, or data-pass requirements.

  • Related developments: The discussion notes that improved-rate stochastic methods became an active research area after the conference version of this work.The literature review is explicitly stated to be current only through January 2015.
  • SDCA: SDCA has SAG-like iteration cost and convergence properties, but its rates depend on the regularization parameter λ rather than the strong-convexity constant µ.SAG can be faster when µ is substantially larger than λ or when iterates enter a more strongly convex local region.
  • MISO: MISO achieves O(1/k) convex and linear strongly-convex rates, but stores both n gradients and n previous iterates.Its reported linear rate is substantially slower than SAG’s Theorem 1 rate, and some larger step sizes can diverge when µ is insufficiently large.
  • SVRG: SVRG alternates full-gradient evaluations with stochastic updates, reducing memory to one stored iterate but requiring two gradient evaluations per iteration and full data passes.It also requires two interacting parameters and cannot be applied directly to general convex problems without modification.
  • Practical considerations: SAG may also offer practical advantages for termination criteria and step-size selection beyond its faster convergence rate.The discussion identifies a natural termination criterion suggested by the SAG iterations.

A.1 Full Gradient Methods

This section compares primal and dual full-gradient methods through their convergence rates and conditioning. The preferable formulation depends on the problem’s dimensional structure, while some cases show no primal-dual rate difference.

  • Primal full-gradient methods: A larger full-gradient step size of 2/(L_g + µ_g) gives a faster primal rate than step size 1/L_g.The speed improvement depends on how much smaller m_σ is than M_σ.
  • Dual full-gradient methods: A larger dual full-gradient step size of 2/(L_d + µ_d) gives a faster dual rate than step size 1/L_d.The section separately reports rates for applying accelerated full-gradient methods to the primal and dual.
  • Primal-dual choice: Primal-versus-dual efficiency depends on m_σ and m′_σ: primal methods are preferred for independent columns, while dual methods are preferred for independent rows.A dual-objective rate does not necessarily imply the same rate for the primal objective.
  • Primal-dual choice: When A is invertible or has neither independent columns nor independent rows, the primal and dual rates are identical.These cases correspond to m_σ = m′_σ or m_σ = m′_σ = 0, respectively.

A.2 Coordinate-Descent Methods

Coordinate descent can exploit dimensions and conditioning that make full-gradient methods inefficient. Its relative advantage depends on whether primal or dual coordinates better match the problem structure.

  • Primal coordinate descent: One full-gradient iteration costs O(np), equivalent to p coordinate-descent iterations when coordinate selection costs O(1).Uniformly random coordinate selection yields the stated comparison rate for p iterations.
  • Primal coordinate descent: Coordinate descent can outperform full-gradient methods when M_j << M_σ, such as when the number of variables p greatly exceeds examples n.It can also beat accelerated full gradient when the conditioning difference is sufficiently large.
  • Dual coordinate descent: For the cost of one full-gradient iteration, n dual coordinate-descent iterations can be performed, with dual efficiency depending on M_i relative to M_σ.The dual coordinate method is faster than dual full gradient when M_i << M_σ.
  • Dual coordinate descent: The SDCA analysis expresses convergence in the duality gap, matching the corresponding dual rate when m′_σ has the stated relationship.This connects dual coordinate descent comparisons to a primal-relevant duality-gap guarantee.

A.3 Stochastic Average Gradient

SAG can use the computational budget of one full-gradient iteration to perform n stochastic-average-gradient iterations. Its rate is often competitive, but eventually stops improving with larger n.

  • SAG comparison: For the O(np) cost of one full-gradient iteration, n SAG iterations can be performed using step size 1/(16L_g/µ_g).The resulting rate is most similar to dual coordinate descent, with a constant factor of 16 and dependence on the primal strong-convexity constant.
  • SAG comparison: SAG can be faster because its rate replaces the term nλ in the denominator with λ.This comparison is made against the corresponding dual coordinate-descent rate.
  • Rate behavior: SAG’s rate improves as n grows and as the condition number L_g/µ_g decreases, but no further improvement occurs beyond n = 2L_g/µ_g.The section presents this saturation as a distinctive feature of the SAG rate.
  • Rate behavior: SAG is characterized as a robust choice that is generally among the best methods, although it may not be preferred for very well-conditioned problems.This conclusion follows the reported rate saturation and conditioning dependence.

Appendix B: Proof of the theorem

The appendix proves the theorem by analyzing SAG under smooth convex summands, using a Lyapunov function whose expected value decreases and controls the objective gap.

  • Assumptions: The proof assumes each f_i is convex with L-Lipschitz continuous gradients, while their sum g is μ-strongly convex with μ ≥ 0.The regular convex case μ = 0 is included, and a minimizer x* of g is assumed attained.
  • Algorithm and notation: The SAG recursion selects i_k uniformly from {1, . . . , n} and updates the stored gradient-related variables accordingly.The appendix introduces the recursion and associated notation before analyzing its conditional expectations.
  • Proof strategy: The analysis constructs a Lyapunov function L whose expected value decreases at a suitable rate and dominates g(x_k) − g(x*).The coefficients are left parameterized initially, with constraints tracked for later selection.
  • Auxiliary results: The proof also relies on a quadratic-form evolution lemma and an inverse formula for a structured matrix arising in the SAG analysis.These lemmas support the matrix-based Lyapunov calculations.
  • Proof strategy: The Lyapunov function is parameterized using matrices A = a1eeᵀ + a2I, B = be, and C = cI, together with additional scalar parameters.The target is an almost-sure decrease condition involving the algorithm parameter α and result parameters γ and δ.

B.3 Lyapunov upper bound

This section derives an upper bound on the expected Lyapunov change, then imposes convex constraints ensuring both its decrease and its domination of the objective gap.

  • Upper-bound derivation: Strong convexity and Lipschitz continuity are combined with the SAG recursion to bound terms involving g(x_k + deᵀy_k) and the stored-gradient state.Lemma 1 is used to take expectations over the relevant quadratic terms.
  • Upper-bound derivation: The proof expands the expected Lyapunov change into grouped terms, using strong convexity, Lipschitz continuity, and quadratic-form identities.Table 3 lists the terms, scalar factors, matrices, and source groups used in the simplification.
  • Upper-bound derivation: The resulting quadratic expression in x_{k−1} is required to be non-positive for all x_{k−1}, with coefficient conditions such as C1 ≤ 0 and C2 ≤ 0.Strong convexity reduces the requirement to an inequality involving C0 + μC1 + μ^2C2.
  • Feasibility constraints: The Lyapunov function dominates g(x_k) − g(x*) only when additional constraints on its coefficients and the result parameters are satisfied.These include positivity constraints B3 > 0 and B4 > 0 and further conditions involving a1, a2, c, d, h, γ, and μ.
  • Feasibility constraints: The coefficient constraints are convex in a1, a2, b, c, d, and h, so feasibility can be checked with a second-order cone program.The selected parameters are then verified symbolically as polynomials in 1/n, using Matlab computations for n > 1.

B.6 Verifying the result

The result verification reduces the parameter constraints to polynomial positivity checks after normalizing L and reparameterizing the relevant range of μ and n.

  • Parameter verification: The verification considers δ = 1/(8n) or μ/(16L), assumes L = 1 without loss of generality, and restricts μ to [0, 1].A term that does not affect validity is discarded during the verification.
  • Parameter verification: It suffices to verify the result at μ = 2/n because stronger convexity implies strong convexity for every smaller parameter and the final inequality does not involve μ.This reduces the range of cases that must be checked.

B.6.2 Ill-conditioned problems (µ ⩽2/n)

For ill-conditioned problems, the verification reparameterizes the constraints using x = 1/n and y = nμ/2, then exploits polynomial monotonicity to reduce the checks.

  • Reparameterization: The verification uses x = 1/n ∈ [0, 1/2] and y = nμ/2 ∈ [0, 1], so μ = 2y/n.This converts the two-parameter dependence into polynomial expressions in x and y.
  • Monotonicity reduction: B3 and B4 are non-negative and decreasing in y, while B6 + B7 is non-negative and increasing in y.These monotonicity properties identify endpoint values sufficient for subsequent positivity checks.
  • Monotonicity reduction: Because of the monotonicity of B3 and B4, their smallest values occur at y = 1; the squared B6 + B7 term can likewise be replaced using its upper bound at y = 1.The remaining constraints are then reduced to positivity checks for simpler polynomials.
  • Polynomial checks: Constraints 5–7 are affine in y, so checking positivity at y = 0 and y = 1 is sufficient.The higher-degree constraints require separate convexity and endpoint arguments when n ≥ 5.
  • Polynomial checks: For n ∈ {2, 3, 4}, positivity is checked directly in y because x is fixed for each remaining case.A Matlab script performs these additional finite-case checks.

B.7 Convergence Rate

The convergence analysis treats convex and strongly convex cases separately, using a Lyapunov-function argument to derive the rates and account for initialization.

  • In the strongly-convex case (δ > 0), the analysis establishes a linear convergence rate.
  • In the convex case (µ = 0 and δ = 0), convexity provides the key inequality used in the convergence argument.
  • 1 32n[g(xk−1) −g(x∗)] is bounded by the Lyapunov decrease L(θk−1) − E(L(θk)|Fk−1).
  • Summing the one-step inequality through iteration k yields the cumulative convergence bound.
  • Jensen’s inequality is used to complete the convergence-rate derivation.
  • Theorem 1’s results require computing the initial Lyapunov-function value for both initializations.

B.8.2 Initialization with average gradient

This initialization analysis starts from y0 and uses its relationship to the gradient difference to bound the Lyapunov function.

  • The initialization is defined by starting with y0.
  • Because y0 = f ′(x0) −eg′(x0), a cited Nesterov result bounds the norm appearing in the second term.
  • Substituting this bound into the Lyapunov function gives the resulting initialization estimate.
Loading 1309.2388v2…