Variance Reduced Stochastic Gradient Descent with Neighbors

Thomas Hofmann; Aurelien Lucchi; Simon Lacoste-Julien; Brian McWilliams

Source-linked AI summary

Variance Reduced Stochastic Gradient Descent with Neighbors

Thomas Hofmann, Aurelien Lucchi, Simon Lacoste-Julien, Brian McWilliams

arXiv:1506.03662v4Jun 11, 2015cs.LGmath.OCstat.ML

TL;DR

The paper addresses the slow transient convergence of SGD and the overhead of existing variance-reduction methods. It unifies their analysis as memorization algorithms and proposes neighborhood-based correction sharing, finding consistent early-phase speed-ups while approximate corrections limit asymptotic accuracy.

Problem
SGD converges slowly, while existing variance-reduction methods require full-gradient computations or per-data-point correction memory, delaying practical speed-ups.
Method
The paper analyzes memorization algorithms and proposes ϵN-SAGA, which approximates per-data-point gradients by sharing stochastic-gradient information among neighboring training points.
Results
The analysis quantifies step-size, gradient-freshness, and correction-error effects, while experiments show consistent speed-ups during the initial phase of regularized risk minimization.
Takeaways & Limitations
Neighborhood-based approximate corrections can trade computation for solution accuracy and may support variance reduction in streaming settings where each data point is seen once.
Takeaways & Limitations
At fixed ϵ, ϵN-SAGA cannot drive suboptimality to zero and instead levels off at an ϵ-determined point, so accurate convergence may require switching to SAGA.

Abstract

from arXiv · show

Stochastic Gradient Descent (SGD) is a workhorse in machine learning, yet its slow convergence can be a computational bottleneck. Variance reduction techniques such as SAG, SVRG and SAGA have been proposed to overcome this weakness, achieving linear convergence. However, these methods are either based on computations of full gradients at pivot points, or on keeping per data point corrections in memory. Therefore speed-ups relative to SGD may need a minimal number of epochs in order to materialize. This paper investigates algorithms that can exploit neighborhood structure in the training data to share and re-use information about past stochastic gradients across data points, which offers advantages in the transient optimization phase. As a side-product we provide a unified convergence analysis for a family of variance reduction algorithms, which we call memorization algorithms. We provide experimental results supporting our theory.

1 Introduction

The paper studies convex empirical-risk optimization, where full-gradient methods become costly on massive datasets and SGD trades this cost for slower convergence. It builds on variance-reduction methods that exploit finite-sum structure to obtain geometric convergence with constant step sizes.

Optimization setting: Full-gradient steepest descent is prohibitive for massive datasets because it repeatedly computes f′(w), whereas SGD uses stochastic gradients.Each fi has L-Lipschitz-continuous gradients, and SGD samples an index uniformly to reduce per-update computation.
Variance reduction: The finite-sum structure enables faster convergence in expectation than SGD’s standard O(1/t) rate for strongly convex functions.Variance-reduction corrections can support linear convergence with geometric rates and constant learning rates.
Paper contributions: The paper defines memorization algorithms as a family of variance-reducing SGD methods that includes SAGA and SVRG as special cases.It also develops a unifying analysis technique for this family.
Paper contributions: The analysis establishes geometric rates for all step sizes γ < 1/(4L), including a universal µ-independent choice, and gives a µ-adaptive convergence proof for SVRG.The paper further studies correction freshness and proposes neighborhood-based corrections for learning with few epochs.

2 Memorization Algorithms

Memorization algorithms reuse past stochastic-gradient information through correction terms, unifying SAGA and SVRG while enabling geometric convergence analysis. The analysis characterizes how update frequency, step size, conditioning, and data size affect convergence rates.

Variance-reduced updates: Memorization algorithms use variance-correction terms whose unbiasedness and vanishing variance depend on corrections approaching each component gradient at the optimum.The memory-update rule distinguishes the algorithms in this family.
SAGA: SAGA stores one stochastic-gradient correction per data point and reuses the sampled gradient to update both the iterate and its memory.The correction is centered by the average memory to preserve unbiasedness.
q-SAGA: q-SAGA updates q memory variables per iteration, reducing average correction age from n to n/q at the cost of additional gradient computations.
Uniform memorization: Uniform q-memorization algorithms update memory locations with equal probability q/n, encompassing q-SAGA and a randomized SVRG variant.N-SAGA instead selects neighborhood memories uniformly subject to the required update-count condition.
Approximate corrections: The ideal correction case would achieve rate 1 − µ/(2L), while approximate corrections require bounds that account for their additional error.The analysis assumes an unconstrained regime with f′(w∗) = 0.
Convergence analysis: The Lyapunov analysis yields geometric convergence for every step size γ = a/(4L) with a < 1, at a guaranteed rate of at least 1 − ρ(γ).The contraction proof uses a Lyapunov function that tracks both distance to the optimum and memory-error bounds.
Step-size choice: Step sizes near 1/(4L) have similar rates to the optimum over most of the admissible range, but underestimating the optimal step size can slow convergence by γ/γ∗.
Rate regimes: The guaranteed rate is bounded by µ/(4L) when the condition number dominates n and by q/n in the large-data regime.Increasing q improves the rate proportionally when q ≤ nµ/(4L), while q has little influence in the ill-conditioned regime.

3 Sharing Gradient Memory

Sharing gradient memory replaces exact per-point corrections with neighborhood-based approximations, trading computation and freshness against approximation error. The resulting method can retain geometric convergence toward a neighborhood and empirically accelerates early optimization.

Sharing gradient memory: Neighborhood sharing avoids extra gradient computations relative to q-SAGA or N-SAGA but introduces approximation bias, creating a freshness-versus-accuracy trade-off.
Approximation trade-off: Approximate memorization preserves unbiased update directions but loses asymptotically vanishing variance, yielding geometric convergence only to a δ-ball around the optimum.
Approximation analysis: Approximation errors are multiplied by γ², so smaller learning rates can control extra variance while preserving useful convergence behavior.
Approximation analysis: For µ ∼ 1/√n, approximate methods converge toward a √ϵ-ball at a rate similar to the exact method; for µ ∼ n^-1, the rate slows to ρ ∼ n^-2.
Shared updates: The shared-memory update keeps the current stochastic-gradient direction while replacing stored corrections with neighbor-based approximations.For generalized linear models, storing scalar quantities can reduce memory while retaining the correct data direction.
Neighborhood construction: Neighborhood errors depend on data-point distances and, for classification, matching labels; nearest-neighbor constructions can therefore define the sharing graph.Finding neighborhoods introduces computational overhead.
ϵ-N-SAGA: Dynamic neighborhood pruning directly controls the target approximation error and interpolates between aggressive sharing and exact N-SAGA as ϵ varies.The limit ϵ → 0 recovers N-SAGA, while ϵ → ϵmax recovers the more aggressive variant.

4 Experimental Results

Experiments compare memorization variants on three datasets using gradient-evaluation and stochastic-update budgets. εN-SAGA delivers early speed-ups by approximating shared corrections, but fixed approximation error limits asymptotic accuracy.

Experimental setup: Experiments compare SAGA, εN-SAGA, q-SAGA, and SGD on three datasets, using both gradient evaluations and datapoint evaluations as progress measures.The study uses q = 20 for q-SAGA and εN-SAGA, with results averaged over five i.i.d. runs.
SAGA vs. SGD: Constant-step-size SGD is faster initially than SAGA but later reaches a noisy neighborhood of the optimum, while SAGA’s advantage emerges after several epochs.The comparison uses the same constant step size for both methods.
SAGA vs. q-SAGA: q-SAGA consistently outperforms plain SAGA when performance is counted by stochastic update steps.The paper treats q-SAGA as a reference for potential speed-ups rather than as a practically relevant algorithm.
εN-SAGA results: With sufficiently small ε, εN-SAGA performs similarly to q-SAGA over 2–10 epochs while tracing between the SAGA and q-SAGA curves.The reported speed-ups occur on all three datasets for µ = 0.1 and µ = 0.001.
Asymptotics: Fixed-ε εN-SAGA eventually levels off instead of driving suboptimality to zero, with cross-over against SAGA typically after 5–15 epochs.The paper recommends choosing ε for a target accuracy or switching to SAGA for accurate convergence.

5 Conclusion

The paper unifies convergence analysis for memorization algorithms and uses it to motivate εN-SAGA, which shares approximate gradient corrections across neighboring data points. Experiments show consistent initial speed-ups, while approximation errors constrain eventual solution accuracy.

Analysis: The paper presents a unified analysis of variance-reduced SGD methods under the name memorization algorithms.The analysis covers safe step sizes, geometric rates, and the role of stochastic-gradient freshness.
Analysis: The analysis identifies trade-offs between small O(1/n) and large O(1/4L) step sizes across different regimes.It also examines how freshness of gradients evaluated at past iterates affects convergence.
Approximation errors: Approximation errors in variance corrections can be tolerated depending on how µ scales with n, but small µ may require much smaller step sizes for convergence to a small region.The paper frames this as a quantified effect on convergence behavior.
εN-SAGA: εN-SAGA exploits similarities between training points by sharing approximate per-data-point gradients through a neighborhood system.The construction is presented as a modification of SAGA and as a possible route to variance reduction when each point is seen once.
Conclusion: Experiments achieve consistent speed-ups during the initial phase of regularized risk minimization, trading computation against solution accuracy.The conclusion characterizes approximate correction terms as promising for this trade-off.

A Appendix

The appendix develops a Lyapunov-based convergence analysis for uniform q-memorization algorithms, deriving geometric rates under step-size conditions and examining approximate corrections. It also characterizes optimal rates and the effects of correction error.

Convergence analysis: The analysis combines iterate progress and memory-state progress in a Lyapunov function to establish contraction for uniform q-memorization algorithms.The proof tracks both w → w+ and α → α+ in a combined potential.
Convergence rates: For step size γ = a/(4L) with a < 1, uniform q-memorization algorithms converge at a geometric rate governed by ρ(γ).For γ below the threshold γ∗(K), the rate is ρ = µγ; at the optimized threshold, the rate is maximized.
Optimal parameters: The optimal step size γ∗(K) maximizes the guaranteed rate ρ∗(K), with distinct asymptotic expressions in well-conditioned and ill-conditioned regimes.The corollary gives the optimized rate as a function of K and distinguishes the two conditioning cases.
Approximate corrections: Average ε-accurate correction updates yield a rate ρ = min{µ^2, µγ̃} under the stated step-size restriction.The theory notes that exceeding γ̃ increases correction error while reducing the guaranteed rate.
Approximate corrections: Patch-up bounds using a different approximation condition require a stricter normalized step-size restriction and produce a slightly smaller rate expression.The corresponding theorem requires a < 2/3 rather than a < 1.

A.1 Implementation details

The implementation constructs neighborhoods from distances between data points and uses a growing-n initialization heuristic for q-memorization methods. The nearest-neighbor graph is simple but can be asymmetric and costly if built naively.

Neighborhood construction: Neighborhoods are constructed by making the q nearest points to each datapoint its parents in a directed graph.This guarantees that every point has exactly q parents, while its set of children need not have size q.
Neighborhood construction: The resulting neighborhoods can be asymmetric because membership is defined through directed parent-child relationships.A symmetric alternative based on a distance threshold is also described.
Neighborhood construction: The symmetric distance-threshold construction did not improve performance in practice and violated the uniform q-memorization property.The threshold is chosen so that q is approximately 20.
Initialization: During the first pass, the growing-n heuristic introduces datapoints one by one and normalizes averages by the number of distinct points seen so far.The same initialization heuristic is used for all q-memorization algorithms.
Computational cost: Naively computing all pairwise distances for neighborhood construction costs O(n^2), although hashing and randomized partition trees offer more efficient alternatives.The paper identifies these data structures as possible implementation improvements.