PaperlayerView exact revision on arXiv

Source-linked AI summary

Variance-Reduced Methods for Machine Learning

Robert M. Gower, Mark Schmidt, Francis Bach, Peter Richtarik

arXiv:2010.00892v1cs.LGmath.OCstat.ML

TL;DR

The paper reviews how to optimize machine-learning models on finite datasets when full-gradient computation is expensive and stochastic gradients are noisy. It synthesizes variance-reduction principles and developments, emphasizing methods that retain SGD-like update costs while achieving faster convergence. The review focuses mainly on convex optimization, while noting that VR methods have had little impact on deep neural-network training and may be ineffective there.

  • Problem

    Large datasets make full-gradient updates expensive, while stochastic methods can have unfavorable convergence behavior; understanding variance reduction matters for finite-data machine-learning optimization.

  • Method

    The paper reviews the principles and main developments of variance-reduced stochastic optimization methods, mainly for convex finite-sum problems.

  • Results

    Variance-reduced methods combine SGD-like update costs with fast convergence, and their total runtime can outperform gradient descent because GD iterations cost n times more.

  • Takeaways & Limitations

    VR methods are especially useful when multiple passes through finite training data are allowed, where they can improve convergence relative to classic SGD.

  • Takeaways & Limitations

    The review focuses mainly on convex and linear-model settings; VR methods have had little impact on deep neural-network training and may be ineffective there.

Abstract

from arXiv · show

Stochastic optimization lies at the heart of machine learning, and its cornerstone is stochastic gradient descent (SGD), a method introduced over 60 years ago. The last 8 years have seen an exciting new development: variance reduction (VR) for stochastic optimization methods. These VR methods excel in settings where more than one pass through the training data is allowed, achieving a faster convergence than SGD in theory as well as practice. These speedups underline the surge of interest in VR methods and the fast-growing body of work on this topic. This review covers the key principles and main developments behind VR methods for optimization with finite data sets and is aimed at non-expert readers. We focus mainly on the convex setting, and leave pointers to readers interested in extensions for minimizing non-convex functions.

1. Introduction

Machine learning fits models to large datasets by minimizing losses over data points, but full-gradient methods become costly as datasets grow. SGD reduces per-iteration cost, while variance-reduced methods retain cheap updates and achieve faster convergence.

  • Problem setting: Machine learning training can be expressed as minimizing an average loss over n data points and model parameters x.The framework covers linear least squares and other supervised models, including logistic regression with regularization.
  • Variance reduction: Variance-reduced stochastic methods are as cheap to update as SGD while achieving fast exponential convergence like full gradient descent.The review presents this combination as the central advantage of VR methods.
  • Problem setting: Large datasets make full-gradient methods expensive because gradient descent processes all n data points at every iteration.This cost can make GD prohibitive when n is large.
  • Stochastic gradient descent: SGD lowers per-iteration cost by using one randomly selected data-point gradient instead of the full gradient.Iterations are compared using epochs: GD performs one iteration per epoch, whereas SGD performs n iterations per epoch.
  • Stochastic gradient descent: In the reported logistic-regression comparison, SGD makes more initial progress than GD and accelerated GD when progress is measured by epochs.The comparison includes GD, accelerated GD, SGD, ADAM, SAG, and SVRG on the mushrooms dataset with n = 8,124 and d = 112.

B. The Issue with Variance.

Unbiased stochastic gradients can still fluctuate enough to prevent convergence with a constant stepsize. Classical remedies reduce this variance through decreasing stepsizes, mini-batches, or momentum, while VR methods make the gradient-estimate variance converge to zero.

  • The issue with variance: An unbiased stochastic gradient does not guarantee convergence of SGD iterates with a constant stepsize.In the illustrated logistic-regression example, SGD forms a point cloud around the solution rather than converging to it.
  • The issue with variance: The non-convergence occurs because stochastic gradients do not converge to zero, so constant-step SGD keeps moving.By contrast, GD naturally stops as the full gradient approaches zero at the optimum.
  • Classical remedies: Decreasing stepsizes can force stochastic updates to vanish, but tuning them risks stopping too early or wasting computation by stopping too late.This is the classic Robbins–Monro remedy for variance-induced non-convergence.
  • Classical remedies: Mini-batching reduces estimator variance in proportion to batch size, but its computational cost increases with the number of sampled gradients.Sampling with replacement gives variance inversely proportional to |B_k|.
  • Classical remedies: Momentum forms a weighted average of past stochastic gradients, reducing variance but failing to converge to the plain full-gradient average.Its emphasis on recently sampled gradients creates the mismatch with the full gradient.
  • Variance-reduced methods: Variance-reduced methods update an estimate g_k of the full gradient and require its variance to converge to zero, enabling constant-stepsize convergence under suitable assumptions.The review identifies this vanishing-variance condition as the defining VR property and links it to faster convergence in theory and practice.

E. First example of a VR method: SGD⋆.

SGD⋆ illustrates the defining variance-reduction property: its gradient-estimate variance vanishes near the optimum, yielding faster convergence under standard smoothness and convexity assumptions. The resulting bounds contrast VR methods’ fixed-fraction error reduction with classic SGD’s slower tolerance dependence.

  • SGD⋆ construction: SGD⋆ uses differences between gradients at xk and x⋆ to form an unbiased estimate of the full gradient.This construction assumes access to each ∇fi(x⋆), which is unrealistic but serves as an illustration of VR behavior.
  • SGD⋆ construction: As xk approaches x⋆, SGD⋆ satisfies the VR property because its gradient-estimate variance converges to zero.The paper identifies this vanishing-variance property as responsible for faster convergence under suitable assumptions.
  • Convergence assumptions: Under L-smoothness and strong convexity, VR methods converge linearly, whereas classic SGD obtains only a sublinear rate.The assumptions require Lipschitz-continuous gradients, strong convexity of f, and convexity of each fi.
  • Convergence assumptions: Strong convexity is a substantial scope condition, though L2-regularized logistic regression satisfies it and the paper discusses possible relaxations.For least squares, strong convexity requires the design matrix to have full row rank.
  • Complexity comparison: The standard complexity comparison gives GD O(κ log(1/ε)), SGD O(κmax(1/ε)), and VR O((κmax + n) log(1/ε)) iterations.VR iterations cost O(1), compared with O(n) for GD; total runtime therefore favors VR despite GD’s smaller iteration count.

2. Basic Variance-Reduced Methods

Basic variance-reduced methods estimate the full gradient by maintaining and averaging data-point gradient information while updating only a small portion per iteration. SAG established linear convergence with single-sample updates, motivating variants such as SAGA that retain similar performance with easier analysis.

  • Core idea: The first VR methods mimic the full gradient’s plain average by averaging estimates of the individual gradients.This design leads directly to the stochastic average gradient (SAG) method.
  • SAG: SAG maintains one stored gradient estimate per data point and updates the estimate associated with a randomly sampled index.Because only one stored vector changes, the running average can be updated without recomputing all n vectors.
  • SAG: The stored-gradient average approaches the full gradient as the individual stored estimates become accurate near a solution.The implementation stores one vector vj for each data point and updates the running aggregate incrementally.
  • SAG: SAG achieves linear convergence with iteration complexity O((κmax + n) log(1/ε)) using stepsize γ = O(1/Lmax).This result contrasts with classic SGD’s sublinear convergence under difficult-to-tune decreasing stepsizes.
  • SAG and SAGA: SAG’s single-gradient updates are computationally attractive, but its biased gradient estimate makes the convergence proof difficult.SAGA uses covariates to construct an unbiased variant with similar performance and easier analysis.

B. SAGA.

SAGA reduces stochastic-gradient variance by maintaining covariates based on previously evaluated component gradients, while avoiding the impractical reference-point choice of SGD⋆. It achieves a linear-convergence iteration complexity but may require substantial memory.

  • Covariates: The variance-reduction property holds when the covariates vi approach the component gradients ∇fi(xk) as iterations progress.The covariates can be chosen to reduce variance because they are otherwise unrestricted.
  • Covariates: SAGA chooses each covariate as the latest stored gradient ∇fi(¯xi), where ¯xi is the most recent evaluation point for fi.This produces an unbiased gradient estimate using per-function reference information.
  • Implementation: SAGA stores previously known component gradients rather than reference points, updating one randomly selected gradient per iteration.A dummy variable retains the old gradient needed to form the unbiased estimate.
  • Convergence: SAGA has iteration complexity O((κmax + n) log(1/ε)) with stepsize γ = O(1/Lmax), using a simpler proof than SAG.The method still needs auxiliary vectors vi ∈ Rd.
  • Memory: O(nd) storage can be infeasible when both the number of data points n and dimension d are large.The review notes that memory reduction is possible for common regularized linear models.
  • Comparison: When the auxiliary vectors fit in memory, SAG and SAGA tend to perform similarly; otherwise, SVRG offers the same convergence rate with O(d) memory.This positions SVRG as the alternative when SAGA’s memory requirement is too high.

C. SVRG.

SVRG reduces variance by comparing current stochastic gradients with gradients at a shared reference point whose full gradient is periodically recomputed. It matches SAG and SAGA’s iteration complexity with O(d) memory, but requires tuning and extra gradient evaluations.

  • Core method: SVRG stores a reference point ¯x and its full gradient, then computes the reference component gradient during each iteration instead of storing individual gradients.Using one shared reference point sets ¯xj = ¯x for all j.
  • Variance reduction: The closer ¯x is to xk, the smaller the variance of the gradient estimate.This variance bound is central to the convex-setting convergence analysis.
  • Algorithm structure: SVRG alternates outer-loop full-gradient evaluations with inner-loop updates using a fixed reference point, balancing update cost against variance reduction.The reference point is updated every t iterations to remain near the current iterate.
  • Trade-offs: SVRG requires O(d) memory, but its inner-loop length t must be tuned and it computes two gradients per iteration plus a full gradient at reference-point updates.These are the stated practical downsides of the method.
  • Convergence: SVRG has iteration complexity O((κmax + n) log(1/ε)), similar to SAG and SAGA.The cited result is attributed to Johnson and Zhang (2013).
  • Practical choices: In practice, SVRG often uses γ = O(1/Lmax) and inner-loop length t = n, although the theoretical setting imposes a more complex dependency among Lmax, µ, γ, and t.The review reports this as the setting used in Figure 1.
  • Variants: SVRG variants change the inner-loop sampling, allow alternative stepsizes, or approximate full-gradient evaluations with growing mini-batches.A continuous-update variant is reported to have advantages for nonconvex minimization.
  • Limitation: SAG and SVRG have stepsizes dependent on Lmax, which may be unknown for some problems.SDCA is introduced as an earlier VR method that addresses this setting through dual coordinate ascent.

D. SDCA and Variants.

SDCA obtains variance-reduced coordinate updates from a separable dual formulation, enabling efficient iterations and stepsize selection without Lmax. Its advantages are tied to convex conjugates, memory requirements, and assumptions specific to its formulation.

  • Coordinate variance reduction: Coordinate-wise derivatives have the VR property because ∇jf(x⋆) = 0, unlike individual data-point gradients that may remain nonzero at x⋆.Random coordinate derivatives can therefore provide favorable variance-reduced estimates.
  • Dual formulation: For finite-sum objectives, computing a coordinate-wise derivative can require a full data pass, but a dual formulation can exploit the problem’s structure.This makes coordinate updates practical in suitable models.
  • Dual structure: The L2-regularized linear-model dual has one real variable vi per training example, and each dual loss term is separable over its coordinate.This separability enables efficient coordinate ascent.
  • Convergence: SDCA coordinate ascent has iteration complexity O((κmax + n) log(1/ε)), similar to SAG, SAGA, and SVRG.Each iteration considers one training example and has cost independent of n.
  • Stepsizes: A one-dimensional line search can choose a stepsize that maximally increases the dual objective, achieving VR runtime without knowledge of Lmax or related quantities.The implementation tracks the sum ∑n_i=1 viai to handle the dual’s second term.
  • Limitations: SDCA requires convex conjugates rather than simply gradients, increasing implementation effort; dual-free variants remove this requirement but lose dual-objective stepsize tracking.The original method uses O(n + d) memory for the specified problem.
  • Limitations: For more general problems, SDCA can require O(nd) memory, and its analysis implicitly assumes µ = λ.When µ > λ, primal VR methods may significantly outperform SDCA.

3. Practical Considerations

Practical use of variance-reduced methods depends on choosing stepsizes, stopping rules, and memory-efficient implementations. The review emphasizes that common heuristics can work well, but several lack theoretical guarantees or require additional computation.

  • Stepsizes: Primal SAG, SAGA, and SVRG theory uses stepsizes γ = O(1/Lmax), although Lmax may be unknown and alternative stepsizes can perform better in practice.SDCA can use the dual objective to set its stepsize naturally.
  • Stepsizes: Armijo line search evaluates f(xk + γkgk) at several candidate stepsizes, making it prohibitively expensive because each evaluation requires a full data pass.A stochastic variant replaces the full function with a stochastic criterion.
  • Heuristics: The stochastic line-search implementation can work well with suitable trial stepsizes, but no theory exists for the method.The cited implementation uses c = 1/2 when the sampled gradient norm is not close to zero.
  • Heuristics: The Bottou trick samples typically 5% of the dataset and uses binary search to select a stepsize for one pass through that sample.It often works well in practice, but no theory is known for the method.
  • Stopping criteria: Termination tests are needed because worst-case iteration bounds depend on unknown constants and practical runs often require fewer iterations than the bounds indicate.Possible criteria include full-gradient norms for SVRG, approximate gradient norms for SAG/SAGA, and duality gaps for SDCA.
  • Memory: Although SVRG removes earlier VR methods’ memory requirement, SAG and SAGA often use fewer iterations, motivating memory reductions for linear models.The review identifies linear models as a setting where SAG/SAGA memory can be substantially reduced.

C. Reducing Memory Requirement.

The review describes memory-saving strategies for variance-reduced methods, including compressed gradient structures and sparse updates. It also notes that VR methods can be slower than SGD initially and motivates hybrid and adaptive approaches.

  • Memory-efficient gradient storage: Storing n scalar gradient components instead of full vectors reduces SAG/SAGA memory from O(nd) to O(n).The same structure can reduce SVRG inner-iteration gradient evaluations to one.
  • Sparse gradients: Sparse-gradient problems lose SGD’s nonzero-proportional cost under plain variance reduction, but just-in-time and randomized sparse updates address this limitation.The randomized SAGA update remains unbiased, and its added variance does not affect the convergence rate.
  • Dependence on dataset size: VR convergence rates depend on n, so VR methods can underperform SGD early when datasets are very large.In Figure 1, SGD remains competitive with two VR methods during the first 10 epochs.
  • Hybrid methods: Initializing SAG or SVRG with n SGD iterations improves the dependence on n in the constant factor without changing the convergence rate.This hybrid strategy requires setting an additional stepsize for the initial SGD iterations.
  • Adaptive improvements: Growing-mini-batch SVRG can provide both an n-dependent linear rate and an n-independent sublinear rate.Non-uniform sampling instead targets the Lipschitz-constant dependence by favoring examples with larger Li values.
  • Adaptive improvements: Non-uniform sampling improves VR rates by replacing dependence on κmax with dependence on the average of the Li values.The approach is established for SVRG, SDCA, and SAGA; adaptive probability updates and local Li estimates are related extensions.

C. Mini-batching.

Mini-batching, acceleration, proximal methods, and extensions beyond strong convexity broaden the settings in which variance reduction can be applied. These techniques can improve complexity, but their benefits depend on problem structure and computational costs.

  • Mini-batching: Mini-batch VR methods interpolate between full-gradient descent and single-sample VR complexity through a mini-batch smoothness constant L(b).L(n)=L and L(1)=Lmax, so larger batches can yield speedups when gradients are evaluated in parallel.
  • Mini-batching: Computing the mini-batch smoothness constant can negate mini-batch advantages, while replacing it with a simple upper bound may be overly conservative.For generalized linear models, estimating the relevant eigenvalue can cost O(d^2n).
  • Acceleration: Accelerated VR methods achieve the best known complexity O((√nκmax + n) log(1/ε)), rather than simply replacing κmax with √κmax.This complexity is especially favorable in ill-conditioned settings where κmax ≫ n.
  • Nonsmooth objectives: For nonsmooth individual losses such as SVM loss, SDCA has O(1/ε) convergence rather than O(log(1/ε)), but permits optimal stepsize selection.This provides no worst-case advantage over classic SGD in the stated setting.
  • Nonsmooth objectives: Proximal-gradient methods handle nonsmooth regularizers when their proximal operator is efficiently computable, including the L1 regularizer.The proximal framework retains O(κ log(1/ε)) iteration complexity under the stated assumptions.
  • Relaxed assumptions: Without strong convexity, VR methods achieve O(1/k), matching GD and improving on SGD’s O(1/√k) rate in the convex setting.Weaker conditions such as the PL and KL inequalities can still support linear convergence.

G. Non-convex Problems.

The review extends variance reduction beyond convex optimization to non-convex objectives, second-order methods, and combinations of algorithmic techniques. These extensions achieve strong complexity results in some settings while retaining substantial computational trade-offs.

  • Non-convex components: When individual fi are non-convex but their average is strongly convex, catalyst-based methods achieve O((n + n^3/4√Lmax/√µ) log(1/ε)) complexity.This complexity was later shown to match the lower bound for that setting.
  • Non-convex objectives: Accelerated SVRG extends guarantees to convex and bounded-non-convex objectives, with state-of-the-art complexities later shown to be optimal.The bounded-non-convexity setting allows strong convexity with a negative parameter −µ.
  • Non-convex objectives: When convexity of f is completely dropped, variance-reduced methods can find approximate stationary points under smoothness and lower-bound assumptions.The corresponding complexity was also accompanied by a matching lower bound.
  • Second-order methods: Second-order VR methods estimate inverse Hessians, balancing update accuracy against computational cost.Poor Hessian estimates can harm convergence, while expensive updates become unsuitable for large datasets.
  • Second-order methods: Second-order methods can be less sensitive to coordinate transformations and ill-conditioning than first-order methods.Most second-order VR methods use BFGS-style quasi-Newton updates.
  • Second-order methods: SVRG combined with SQN achieved proven linear convergence, but with worse complexity than O((κmax + n) log(1/ε)).Existing quasi-Newton VR variants were not known to have n-independent update costs and better global complexity than basic VR methods.
  • Second-order methods: Stochastic Newton methods such as SDNA can have n-independent cost and better convergence than SDCA, while minibatch Newton can achieve O((n/b) log(1/ε)) local convergence independent of the condition number.These results differ from the limitations described for quasi-Newton VR variants.
  • Combined extensions: The review emphasizes that mini-batching, acceleration, and proximal updates can be combined to address multiple problem features simultaneously.The literature has developed most such combinations.

A. Lemmas

The appendix develops auxiliary lemmas using convexity, smoothness, expectation, and finite-variance assumptions. These results support variance and gradient relationships used in the review’s convergence analysis.

  • Assumptions: The lemmas assume convex, Lmax-smooth component functions and uniform sampling of an index.These assumptions establish the setting for the subsequent gradient inequalities.
  • Proof strategy: Convexity and smoothness are combined to upper-bound a component-function expression by a gradient-difference term.The proof minimizes the right-hand side over an auxiliary point z.
  • Proof result: Substituting the minimizing point yields the term −1/(2Lmax)∥∇fi(x)−∇fi(x⋆)∥².This is the key inequality produced before taking expectation over the sampled index.
  • Proof result: Taking expectation uses E_i[fi(x)]=f(x) and E[∇fi(x⋆)]=0 to obtain the stated aggregate result.The expectation step converts component-level relations into a full-objective statement.
  • Assumptions: A separate auxiliary lemma assumes a finite-variance random vector X.This supplies a probabilistic condition for variance-related arguments.

B. Convergence Proof Illustrated via SGD⋆

The convergence proof for SGD⋆ follows the standard variance-reduced analysis: expand the update, take conditional expectations, use convexity, and bound the stochastic-gradient second moment. Under the stated assumptions and stepsize condition, the iterates converge linearly.

  • Proof setup: The proof begins by expanding the SGD⋆ update and then taking expectation conditioned on the current iterate.These are presented as the common initial steps in the convergence proofs for variance-reduced methods.
  • Proof setup: Convexity or strong convexity removes the inner-product term involving x_k − x⋆ and ∇f(x_k).The strong-convexity argument is used to relate this term to function progress.
  • Variance control: Bounding the second moment of g_k is the remaining key step in establishing the convergence rate.For plain SGD, a uniform variance bound B is often assumed, whereas variance reduction permits explicit control through the variance of g_k.
  • Convergence result: Under Assumptions 1.1 and 1.2 and γ ≤ 1/Lmax, SGD⋆ iterates converge linearly.The theorem states this result after the preceding proof steps and supporting lemmas.
  • Variance control: SGD⋆ is analyzed as a variance-reduced method because its proof explicitly controls the stochastic-gradient variance.The text identifies the shifted SGD method as variance-reduced based on this control.
Loading 2010.00892v1…