PaperlayerView exact revision on arXiv

Source-linked AI summary

The Convergence of Sparsified Gradient Methods

Dan Alistarh, Torsten Hoefler, Mikael Johansson, Sarit Khirirat, Nikola Konstantinov, Cédric Renggli

arXiv:1809.10505v1cs.LGcs.DCstat.ML

TL;DR

Gradient sparsification offered substantial communication savings but lacked theoretical justification. The paper analyzes TopK SGD with local error correction and proves convergence for convex and nonconvex smooth objectives under analytic assumptions. The results show that sparsification can converge relatively quickly, while accuracy and convergence depend on conditions such as gradient variance and sparsity level.

  • Problem

    Gradient sparsification had strong practical communication benefits but lacked theoretical justification for data-parallel SGD.

  • Method

    The paper analyzes magnitude-based TopK gradient sparsification with local error accumulation for convex and nonconvex smooth objectives.

  • Results

    TopK converges similarly to sequential SGD when K is a constant fraction of n, while 0.1%—1% sparsity causes a noticeable convergence slowdown.

  • Takeaways & Limitations

    Magnitude selection implicitly bounds update staleness, giving sparsification a theoretical foundation and supporting its use as a communication-reduction method under the stated conditions.

  • Takeaways & Limitations

    The analysis requires restrictive conditions, including K = cn with c > 1/2 in the nonconvex case and assumptions about gradient behavior.

Abstract

from arXiv · show

Distributed training of massive machine learning models, in particular deep neural networks, via Stochastic Gradient Descent (SGD) is becoming commonplace. Several families of communication-reduction methods, such as quantization, large-batch methods, and gradient sparsification, have been proposed. To date, gradient sparsification methods - where each node sorts gradients by magnitude, and only communicates a subset of the components, accumulating the rest locally - are known to yield some of the largest practical gains. Such methods can reduce the amount of communication per step by up to three orders of magnitude, while preserving model accuracy. Yet, this family of methods currently has no theoretical justification. This is the question we address in this paper. We prove that, under analytic assumptions, sparsifying gradients by magnitude with local error correction provides convergence guarantees, for both convex and non-convex smooth objectives, for data-parallel SGD. The main insight is that sparsification methods implicitly maintain bounds on the maximum impact of stale updates, thanks to selection by magnitude. Our analysis and empirical validation also reveal that these methods do require analytical conditions to converge well, justifying existing heuristics.

1 Introduction

Distributed data-parallel SGD faces communication bottlenecks, motivating lossless, quantization-based, and sparsification-based approaches. This paper analyzes TopK sparsification, showing convergence guarantees under analytic assumptions while identifying conditions behind its practical performance.

  • 200 MB of gradients may need all-to-all communication every few milliseconds when training AlexNet, making communication a potential system bottleneck.
  • Communication-reduction methods include lossless approaches, quantization, and sparsification that broadcasts only important gradient components while accumulating the rest locally.
  • 600× communication reduction per node has been reported empirically for sparsification without loss of accuracy in large-scale neural networks.
  • The paper proves convergence guarantees for gradient sparsification on both convex and nonconvex smooth objectives, with bounds on convergence rates.
  • TopK SGD truncates each node’s error-corrected local gradient to its K largest-magnitude components, exchanges those components, and applies the resulting updates.
  • Sparsification resembles asynchronous SGD because updates can be delayed, but small updates may theoretically remain unapplied indefinitely.

2 Preliminaries

The preliminaries formalize data-parallel SGD and the objective classes studied. Convergence is expressed through rate supermartingales, which track progress and yield bounds on failure to reach a defined success region.

  • The paper assumes a bounded second moment for the average of P independent stochastic gradients at arbitrary parameter values.
  • The analysis covers c-strongly convex and L-smooth nonconvex objectives, targeting parameters within squared distance ϵ of the optimum.
  • A rate supermartingale is a nonnegative process depending on time and current and previous iterates that intuitively measures distance from convergence.
  • The supermartingale condition requires the expected process value after an SGD update not to exceed its current value.
  • Convergence analysis bounds the probability that the stochastic algorithm has not entered the success region by time T.

3 The TopK SGD Algorithm

TopK SGD maintains a shared model view while each node error-corrects and communicates only its largest-magnitude gradient components. The analysis also isolates overlap and local-gradient variability assumptions needed for distributed updates to track the intended process.

  • 3 The TopK SGD Algorithm: Each node adds its accumulated local error to the current gradient, selects its top K absolute-magnitude components, broadcasts them, and applies the peers’ average update.
  • 3 The TopK SGD Algorithm: The shared parameter view vt remains consistent across nodes because every node applies the same averaged received update.
  • 3 The TopK SGD Algorithm: The auxiliary variable xt tracks all generated gradients without truncation, allowing the analysis to bound its difference from the shared view vt.
  • 3 The TopK SGD Algorithm: TopK convergence is established for both the auxiliary aggregate xt and the shared parameter view vt, with slightly different rates.
  • 3.1 An Analytic Assumption.: Opposite-signed large local gradients can cancel globally, causing locally selected components to differ from the top K components of the summed gradient.
  • 3.1 An Analytic Assumption.: The analysis assumes such overlaps lose only a small amount of information per iteration and interprets this condition as controlling local-gradient variability.

4 Analysis in the Convex Case

The convex-case analysis transfers sequential SGD convergence guarantees to TopK sparsification by bounding the discrepancy between sparse and full-gradient updates. Under a rate-supermartingale framework and stated assumptions, the resulting convergence slowdown depends on sparsity and is reduced by more nodes.

  • Convex-case proof strategy: The analysis bounds the difference between the iterates and between TopK and full-gradient updates under Assumption 1.These bounds support the subsequent convergence proof for the sparsified process.
  • Convergence bound: Theorem 1 gives a finite-horizon convergence probability bound when the sequential-SGD rate supermartingale is H-Lipschitz and αHMC′ < 1.The theorem applies for any T ≤ B.
  • Convex-case proof strategy: The proof constructs a rate supermartingale for the sparsified iterate by using the sequential-SGD martingale and the bound on the iterate discrepancy.The sequential process uses the average of P stochastic gradients as its update.
  • Convergence bound: Compared with sequential SGD, TopK incurs a slowdown of α2√ϵMC′ in the convergence rate.The comparison is stated directly for the TopK convergence rate.
  • Convergence bound: The slowdown is linear in n/K and ξ/P, so increasing the number of nodes dampens the effect of ξ.This identifies how sparsity and distributed averaging enter the bound.

5 Analysis for the Non-Convex Case

For non-convex smooth objectives, the analysis uses decreasing learning rates and bounds the model-view gap to establish ergodic convergence for TopK under suitable choices of the learning-rate sequence and K.

  • Assumptions and convergence notion: The non-convex analysis assumes an L-smooth objective and uses ergodic convergence as its convergence notion.The target is convergence to a point where gradients are 0.
  • Proof strategy: The proof controls the expected objective value by leveraging the bound on the gap between the real model x_t and observed view v_t.This gap connects the sparsified process to the objective analyzed by the proof.
  • Convergence bound: Theorem 2 establishes a general convergence bound for TopK when the learning-rate sequence and K satisfy the stated condition for every t > 0.The theorem applies to functions satisfying the assumptions of the non-convex section.
  • Convergence bound: The effect of ξ in the non-convex bound is dampened by P, and the required inequality holds whenever K = cn for a constant c > 1.The passage explicitly links this condition to the sparsity parameter K.
  • Convergence bound: When K = cn with c > 1/2, a constant learning rate depending on T can also ensure ergodic convergence.The complete derivation is deferred to Appendix B.

6 Discussion and Experimental Validation

The experiments examine how gradient shape and sparsity affect TopK convergence, while comparisons relate its behavior to asynchronous SGD and stochastic quantization. They support the theoretical prediction of slower convergence under extreme sparsity and better behavior when gradients are concentrated in top components.

  • Gradient shape: Empirical validation confirms that gradient norm is concentrated toward the top elements, making the worst-case uniform-gradient bound potentially loose.The analysis states C′ = O(n/K) in the convex case when P is constant, but notes that practical gradient distributions are not uniformly spread.
  • Gradient shape: Figure 2 measures the relative norm discarded by TopK as K varies across datasets and tasks.The quantity examined is ∥˜G − TopK(˜G)∥/∥˜G∥.
  • Convergence versus K: Figure 3 examines convergence as K varies across datasets and tasks, validating that TopK convergence can be similar to sequential SGD when K is a constant fraction of n.In that regime, convergence is governed by the Lipschitz constant of W and the second-moment bound M.
  • Comparison with SGD variants: O(√n/K) maximum-delay behavior relates TopK's convergence rate to asynchronous SGD with bounded staleness.Dense asynchronous updates with maximum delay τ have slowdown Θ(τ√n), while TopK behaves as though τ = O(√n/K).
  • Comparison with SGD variants: Large sparsity of 0.1%—1% produces a noticeable convergence slowdown, as predicted by the theory.For K = √n, the worst-case slowdown is O(√n), matching stochastic quantization's worst-case order.
  • Comparison with SGD variants: TopK has a superior convergence rate to stochastic quantization or sparsification methods at the same communication budget per node in the experiments.The comparison is made against QSGD and related stochastic methods.

7 Conclusions

The paper provides a theoretical foundation for TopK sparsification and connects it to prior empirical evidence across large-scale learning tasks. The approach may also extend to sparsification combined with quantization or approximate quantiles.

  • Conclusions: The paper provides the first theoretical analysis of TopK sparsification-based communication reduction.It supplies a theoretical foundation for empirical results reported across speech, translation, and image-classification tasks.
  • Conclusions: The general analytical approach is proposed as extensible to sparsification combined with reduced-precision quantization and approximate quantiles.The paper does not repeat prior scalability experiments because those practical results were already extensively validated.

A Analysis for the Convex Case

The convex-case analysis develops auxiliary notation and lemmas to relate the TopK update process to full-gradient updates. The proof proceeds through recursive relations and bounds on their discrepancy.

  • Auxiliary lemmas: Lemma 1 establishes a recursive relation for the processes x_t and v_t.The proof then iterates the relation downwards to obtain the stated result.
  • Update comparison: The analysis bounds the difference between updates produced by TopK and those produced by full gradients.This bound is introduced after applying the preceding recursive result.
  • Auxiliary lemmas: Lemma 2 derives an expectation-based bound using the result from Lemma 1.The expectation is taken with respect to the gradients at time t.

A.1 The Main Result

The analysis uses rate supermartingales and a corrected process to bound TopK's probability of not reaching the success region. Under the stated assumptions, the bound applies to convex SGD.

  • Theorem 1: Theorem 1 bounds the probability that sequential SGD has not entered the success region by time T when W is an H-Lipschitz rate supermartingale and αHMC′ < 1.The bound is Pr[FT] ≤ E[W0(v0)](1 − αHMC′)^T.
  • Proof strategy: The proof defines Vt by subtracting αHMCt from Wt and retaining the stopped value after success.This construction supports the supermartingale argument for the TopK process.
  • Proof strategy: For TopK, the inequality also holds after success, so Vt is a supermartingale throughout the process.The argument then establishes nonnegativity and transfers the rate bound to TopK.
  • Supporting result: A sequential-SGD rate supermartingale with infinite horizon and H-Lipschitz constant H = 2√ϵ supplies the required comparison process.The process is defined differently before and after entering the success region.
  • Corollary: The convex-case corollary applies this construction to Algorithm 1 under the listed assumptions and a specified learning rate α.Its probability statement concerns avoiding the success region through time T.

B Analysis for the Non-Convex Case

For smooth non-convex objectives, the analysis controls the discrepancy between the real model and the worker view, then derives convergence with suitable learning rates and K.

  • Setup: The non-convex analysis assumes an L-Lipschitz gradient and bounded expected second moments of stochastic gradients.It uses decreasing step sizes αt and targets ergodic convergence to a local minimum.
  • Convergence target: The non-convex result settles for the weaker convergence notion of gradient norms tending to zero in expectation.This is the standard non-convex convergence target described in the analysis.
  • Analysis: The strategy bounds the difference between xt and vt to control the expected evolution of f(vt).This yields a bound on the sum of gradient norms and supports convergence toward zero in expectation.
  • Theorem 2: Theorem 2 applies to TopK when the learning-rate sequence and K satisfy the stated condition for every time t.The theorem then gives a finite-time bound after T steps.
  • Proof strategy: The derivation uses gradient Lipschitzness to relate ∥∇f(vt)∥² to ∥∇f(xt)∥² and the view error ∥vt − xt∥².The resulting inequality is summed over time and normalized by the cumulative learning rates.
  • Parameter choices: Choosing αt = t^-θ with θ > 0 and K = cn for c > 1 can make the required series converge asymptotically.The passage also states that a fixed learning rate can be used in another admissible case.

C Experimental Details

The experiments evaluate the algorithm on image classification, logistic regression, and synthetic linear regression using a distributed sparse-gradient communication layer.

  • Datasets and models: The evaluation covers classification and linear regression tasks, including ResNet110 on CIFAR-10 and logistic regression on RCV1.A synthetic dataset is used for linear regression.
  • Infrastructure: SparCML aggregates sparse gradients across multiple compute nodes through an MPI-based communication layer.The framework is designed for distributed optimization with low communication overhead.
  • Experimental setup: For image classification, the experiments use standard batch sizes and default CNTK 2.0 hyperparameters as the full-accuracy convergence baseline.The image-classification experiments run on four nodes, with additional hyperparameter tuning described in the implementation setup.
Loading 1809.10505v1…