PaperlayerView exact revision on arXiv

Source-linked AI summary

On Variance Reduction in Stochastic Gradient Descent and its Asynchronous Variants

Sashank J. Reddi, Ahmed Hefny, Suvrit Sra, Barnabás Póczos, Alex Smola

arXiv:1506.06840v2cs.LGstat.ML

TL;DR

Asynchronous extensions of variance-reduced SGD are needed for large-scale parallel and distributed optimization, but had not been developed for these methods. The paper provides a unifying VR framework and asynchronous algorithms with provable convergence, including SVRG- and SAGA-like variants. In sparse settings, the approach achieves near-linear speedups and shows strong empirical performance in an asynchronous SVRG-like implementation.

  • Problem

    Large-scale optimization requires asynchronous parallel or distributed processing, but synchronous finite-sum variance-reduction algorithms lacked corresponding asynchronous extensions.

  • Method

    The paper develops a formal framework for variance reduction and asynchronous parallel VR algorithms within it, including variants of SVRG, SAGA, and S2GD.

  • Results

    Strong empirical speedups were observed for an asynchronous SVRG-like specialization, while the proposed methods provably converge at a linear rate for smooth strongly convex finite-sum problems.

  • Takeaways & Limitations

    In sparse machine-learning settings, the framework supports asynchronous variance-reduction algorithms whose speedups scale near linearly with processor count.

  • Takeaways & Limitations

    The analysis assumes a consistent read model and leaves the inconsistent-read analysis for future work.

Abstract

from arXiv · show

We study optimization algorithms based on variance reduction for stochastic gradient descent (SGD). Remarkable recent progress has been made in this direction through development of algorithms like SAG, SVRG, SAGA. These algorithms have been shown to outperform SGD, both theoretically and empirically. However, asynchronous versions of these algorithms---a crucial requirement for modern large-scale applications---have not been studied. We bridge this gap by presenting a unifying framework for many variance reduction techniques. Subsequently, we propose an asynchronous algorithm grounded in our framework, and prove its fast convergence. An important consequence of our general approach is that it yields asynchronous versions of variance reduction algorithms such as SVRG and SAGA as a byproduct. Our method achieves near linear speedup in sparse settings common to machine learning. We demonstrate the empirical performance of our method through a concrete realization of asynchronous SVRG.

1 Introduction

Variance-reduced stochastic methods improve convergence over SGD, but their asynchronous extensions are needed for large-scale parallel and distributed settings. The paper develops a framework and asynchronous methods that cover several established VR algorithms and achieve near-linear sparse-data speedups.

  • 1 Introduction: Variance-reduced stochastic algorithms reduce stochastic-gradient variance through problem structure and space-time tradeoffs, enabling linear convergence under strong convexity.These methods have better expected convergence rates than SGD in theory and practice.
  • 1 Introduction: Asynchronous variants are a key open question because large-scale problems require parallel or distributed processing.The paper focuses on extending synchronous finite-sum VR algorithms to asynchronous settings.
  • 1 Introduction: The proposed asynchronous parallel stochastic gradient methods provably converge at a linear rate for smooth strongly convex finite-sum problems.They are inspired by the SVRG, S2GD, SAG, and SAGA family.
  • 1 Introduction: The paper introduces a formal framework unifying VR methods such as SAGA and SVRG while expressing their algorithmic and practical tradeoffs.The framework also supports development of asynchronous parallel variants.
  • 1 Introduction: Under sparse-data settings common in machine learning, the parallel algorithms attain speedups that scale near linearly with processor count.A concrete asynchronous SVRG-like specialization shows strong empirical speedups agreeing with the theory.
  • 1 Introduction: The work relates its primal VR methods to SAG, SAGA, SVRG, and S2GD, alongside dual approaches such as SDCA and Finito.It also distinguishes the parallel asynchronous setting from distributed asynchronous SGD and related coordinate-descent methods.

2 A General Framework for VR Stochastic Methods

The paper formalizes a general variance-reduction framework in which schedule updates determine several stochastic gradient methods, then uses it to construct HSAG and analyze convergence. The framework exposes trade-offs among storage, computation, update frequency, and convergence while supporting asynchronous extensions.

  • The framework targets smooth, strongly convex finite-sum objectives with L-Lipschitz gradients and strong-convexity parameter λ.
  • Algorithm 1 maintains auxiliary parameters whose schedule updates determine the method, while the associated gradient estimate provides variance reduction.Different schedule choices instantiate incremental methods such as SAG, SVRG, and SAGA, as well as gradient descent.
  • SVRG updates its schedule every m iterations, whereas SAGA and SAG update one stored component at each iteration; SAG consequently uses a biased gradient estimate.Gradient descent updates all stored components each iteration.
  • Storage and computation trade off across methods: SVRG uses O(d) storage with a full-gradient cost O(nd) per epoch, while SAG and SAGA use O(nd) storage and O(d) per iteration.Gradient descent uses O(d) storage but incurs O(nd) computation each iteration.
  • HSAG combines SVRG- and SAGA-style schedules over an index subset S, interpolating between SAGA when S=[n] and SVRG when S=∅ with s_i=m.Smaller S and larger schedule frequencies reduce storage but typically slow convergence.
  • The general framework provides a common platform for analyzing asynchronous variants and deriving new algorithms through schedule design.Its convergence analysis for HSAG assumes unbiased gradient estimates and therefore excludes SAG; the stated theorem and corollary yield an expected linear rate under their conditions.

3 Asynchronous Stochastic Variance Reduction

The paper develops asynchronous variance-reduced stochastic methods under a bounded-staleness model, focusing on sparse data and providing convergence guarantees for asynchronous SVRG and the general HSAG framework. Its analysis yields near-linear speedup in suitable sparse regimes, while relying on a consistent-read assumption and limited synchronization.

  • Asynchronous model: Each processor asynchronously reads the parameter and schedule iterates, computes a stochastic update, updates the parameter, and runs a schedule update.The model allows x and A to have different timestamps, with delays bounded by τ.
  • Asynchronous model: The analysis assumes bounded staleness and synchronization after every epoch, with t − D(t) ≤ τ, t − D′(t) ≤ τ, and D(t) ≥ km for t ≥ km.The paper characterizes τ as capturing the degree of parallelism and argues that once-per-epoch synchronization is not a strong assumption.
  • Sparsity: For sparse data, convergence depends on Δ, the average feature frequency, with the analysis targeting settings where Δ ≪ 1.The asynchronous analysis uses Δ to quantify how often features appear in the data matrix.
  • Asynchronous SVRG: Asynchronous SVRG achieves a similar convergence rate to synchronous SVRG with epoch size m = O(n + Δ^1/2τ n) under the indicative regime L/λ = n.The step size is normalized by max{1, Δ^1/2τ} to obtain this guarantee.
  • Asynchronous SVRG: When Δ = o(1/n), near-linear speedup is possible for τ = o(n^1/2), while the theoretical speedup is 1/Δ^1/2 when Δ^1/2τ > 1.These conclusions follow from the asynchronous SVRG convergence analysis.
  • General framework: The general asynchronous HSAG analysis establishes convergence under stated parameter conditions, while specializing the framework to SAGA can yield per-iteration guarantees and avoid extra epoch synchronization.The paper presents the general result for epoch-based analysis but notes stronger SAGA-specific analyses are possible.

4 Experiments

The experiments evaluate asynchronous variance-reduced and SGD methods for l2-regularized logistic regression, emphasizing runtime, speedup, and sparse-data implementation. Lock-Free SVRG shows strong performance relative to asynchronous SGD baselines.

  • Experimental setup: The experiments study binary classification with l2-regularized logistic regression and set λ = 1/n, producing a high condition number.The algorithms are evaluated on datasets from the LIBSVM website.
  • Implementation: The implementation uses a just-in-time update scheme because standard SVRG updates become dense despite sparse gradients.The appendix provides the implementation details for preserving sparsity efficiently.
  • Algorithms: The evaluated methods are Lock-Free SVRG, Locked SVRG, Lock-Free SGD with constant step size, and Lock-Free SGD with decaying step size.The SGD variants are called CSGD and DSGD, respectively, with dataset-specific step-size tuning.
  • Runtime comparison: Figure 4 plots training-loss residual f(x) −f(x∗) against runtime on rcv1, real-sim, news20, and url using 10 cores.The comparison includes Lock-Free SVRG, DSGD, and CSGD.
  • Speedup: The asynchronous experiments achieve significant speedups across datasets, with Lock-Free SVRG exceeding locking-based speedups and rcv1 showing the lowest speedup.The speedup is measured to reach f(x) −f(x∗) < 10−10; rcv1 is described as nonsparse and therefore unfavorable for the method.
  • Results: Lock-Free SVRG outperforms both DSGD and CSGD, while DSGD outperforms CSGD across the reported cases.The observed gains are qualitatively similar to those reported for synchronous versions.

5 Discussion & Future Work

The paper concludes that its framework supports provably convergent asynchronous variance-reduction methods, including asynchronous variants of several established algorithms. It identifies empirical schedule comparisons and space-time-accuracy tradeoffs as future work.

  • Discussion: The framework captures many variance-reduction techniques and provides a common platform for their convergence analysis.The paper also presents a simple hybrid variance-reduction method within the framework.
  • Discussion: The asynchronous framework yields variants of SVRG, SAGA, and S2GD with provable convergence guarantees.The paper states that these methods exploit data sparsity to obtain near-linear speedup in common machine-learning settings.
  • Future work: Future work includes empirical comparison of schedules and analysis of their space-time-accuracy tradeoffs in asynchronous variants.The authors specifically identify the effect of these tradeoffs on asynchronous methods as an open direction.

A Appendix

The appendix defines notation for Bregman divergence and expectations over sampled indices, and clarifies how epoch-end iterate replacement is represented in the analysis.

  • Notation: Df denotes the Bregman divergence for function f.The appendix notes that this divergence is defined below.
  • Notation: E[X] denotes expectation over indices {i1, . . . , it} when X depends on those indices through step t.The indicator function is denoted by 1.
  • Epoch iterates: At the end of an epoch, xkm+m is replaced by a randomly selected iterate from {xkm, . . . , xkm+m−1} with probabilities {p1, · · · , pm}.Within proofs, xkm continues to denote the iterate before this replacement.

Implementation Details

The implementation rewrites regularized objectives and maintains gradient components separately so asynchronous SVRG updates remain sparse and efficient.

  • Sparse reformulation: Directly updating the whole vector x is inefficient because the regularization term appears in every fi.The problem is therefore rewritten before implementation.
  • Sparse reformulation: Although the gradients are sparse, the SVRG update remains dense because it contains an averaged-gradient component.The implementation must separately manage this dense contribution.
  • Update maintenance: The method maintains the bracketed update terms separately: one receives sparse updates, while the other uses scalar additions from the maintained average gradient.This decomposition avoids recomputing the full update at every iteration.
  • Update maintenance: When ∇fit at xt is needed, the required components of xt are assembled on demand from the maintained terms.Thus each update can respect the data sparsity pattern.

Proof of Theorem 1

The proof establishes a recursive Lyapunov bound for HSAG using unbiased gradient estimates, convexity, and Bregman-divergence inequalities. With suitable parameters, the recursion contracts by a constant θ<1.

  • Gradient estimator: Unbiasedness gives E[v_t] = −∇f(x_t), enabling the expected-iterate recursion.The proof combines this property with convexity of f.
  • Lyapunov recurrence: The analysis tracks a Lyapunov quantity combining squared distance to x∗ with an auxiliary term G_t.The recurrence begins from E[R_{t+1}] = E[c∥x_{t+1}−x∗∥² + G_{t+1}].
  • Term bounds: The proof bounds the auxiliary terms T1 and T2 using strong convexity, Lemma 3, the definition of G_t, and parameter-dependent inequalities.These bounds are substituted into the Lyapunov recurrence before iterating it across an epoch.
  • Epoch contraction: The epoch analysis applies the recursive relationship for m iterations and then uses the randomized epoch-output rule to derive the next-epoch bound.The output iterate is sampled with probabilities proportional to {(1−1/κ)^(m−1), …, 1}.
  • Epoch contraction: The resulting contraction factor satisfies θ<1 when the algorithm parameters are chosen appropriately.This establishes the central contraction statement used by Theorem 1.

Proof of Theorem 2

The proof of Theorem 2 controls asynchronous errors caused by delayed iterates and stale gradients. It combines termwise bounds across an epoch and uses synchronization to obtain the theorem’s inequality.

  • Error decomposition: The proof defines epoch-specific quantities for the delayed iterate D(t) and expands the objective into components used in the error analysis.The analysis introduces terms whose bounds are combined later.
  • Error bounds: The auxiliary terms T3, T4, and T5 are bounded using convexity, Lipschitz continuity, Cauchy–Schwarz, triangle inequality, AM-GM, and counting arguments.The bounds account for delayed gradients and the maximum delay τ.
  • Epoch aggregation: Adding the termwise inequalities over t=km to t=km+m−1 produces an epoch-level bound on the asynchronous error terms.The proof explicitly combines the bounds from Equations (A.7), (A.8), and (A.9).
  • Epoch aggregation: The analysis uses synchronization after every epoch together with telescoping and the definition of the epoch iterate to simplify the accumulated terms.Lemma 3 is then applied to obtain the remaining bound.

Proof of Theorem 3

The proof of Theorem 3 extends the delayed-gradient analysis to the HSAG setting by tracking changing stored gradients and bounded staleness. It derives a contraction inequality under the stated delay and parameter conditions.

  • Assumptions: For simplicity, the proof assumes D(t)=D′(t), while stating that the analysis extends straightforwardly when the indices differ.The objective is decomposed as f=g+h for the analysis.
  • Lyapunov analysis: The proof reuses the Lyapunov function and obtains E[u_t]=−∇f(x_D(t)) and E[v_t]=−∇f(x_t) from gradient unbiasedness.These identities support the expected-recursion analysis for delayed and current iterates.
  • Staleness control: The proof bounds the resulting terms using Jensen’s inequality, Lemma 3, Lipschitz continuity, counting arguments, and the delay bound τ.These estimates are substituted into the epoch recurrence for the auxiliary quantities.
  • Staleness control: At most τ stored-gradient coefficients α_i differ between D(t) and t because delay is bounded by τ and at most one α_i changes per iteration.Changed coefficients correspond to recent iterates between max{t−τ,km} and t.
  • Contraction: The theorem’s final condition states that θ_a<1 for parameters chosen according to the derived inequalities.The parameter dependence is summarized separately in the remarks section.
  • Contraction: The epoch recurrence is completed by substituting bounds on e_t and v_t, applying Bregman-divergence and strong-convexity inequalities, and using randomized epoch-output selection.The resulting factor θ_a is required to be below one.

Remarks about the parameters in Theorem 1 & Theorem 3

The parameter remarks show that the framework can achieve constant contraction and near-linear-in-n complexity in the high-condition-number regime. They also identify sparse-data conditions for the asynchronous result.

  • Theorem 1 parameters: O(n log(1/ϵ)) is the total computational complexity of HSAG when L/λ=n and m=O(n).Each epoch costs O(n), and O(log(1/ϵ)) epochs achieve ϵ accuracy in the objective function.
  • Theorem 1 parameters: θ=0.5 can be obtained with m=O(n) in the high-condition-number regime L/λ=n, where κ=Θ(n).The resulting contraction yields ϵ accuracy after O(log(1/ϵ)) epochs.
  • Theorem 3 parameters: The asynchronous analysis assumes ∆^1/2τ<1 and m>n>9τ for the sparse regime of interest.The alternative case ∆^1/2τ≥1 is stated to admit a similar analysis.
  • Theorem 3 parameters: θ_a=0.5 can be obtained with m=Θ(n) and κ=Θ(n) when L/λ=n.The paper notes that the constants are not optimized and may improve with more careful analysis.
  • Interpretation: The framework can yield sharper constants for specific asynchronous or synchronous SVRG and SAGA cases through specialized analyses or modifications.The remarks compare the general framework’s constants with sharper case-specific results.
Loading 1506.06840v2…