PaperlayerView exact revision on arXiv

Source-linked AI summary

Qsparse-local-SGD: Distributed SGD with Quantization, Sparsification, and Local Computations

Debraj Basu, Deepesh Data, Can Karakus, Suhas Diggavi

arXiv:1906.02367v2stat.MLcs.DCcs.LGmath.OC

TL;DR

Distributed learning can be communication-bound when workers exchange full-precision gradients for large models over bandwidth-limited networks. Qsparse-local-SGD combines aggressive sparsification, quantization, local computation, and error compensation in synchronous and asynchronous implementations. The method is reported to match vanilla distributed SGD’s convergence rate for important operator classes while achieving substantial reductions in transmitted bits.

  • Problem

    Full-precision gradient exchange creates a communication bottleneck for large-scale distributed learning over bandwidth-limited networks.

  • Method

    Qsparse-local-SGD combines aggressive sparsification, quantization, local computations, and error compensation, with synchronous and asynchronous distributed implementations.

  • Results

    Qsparse-local-SGD converges at the same rate as distributed vanilla SGD for important sparsifiers and quantizers and reaches target accuracies with about 15-20× fewer transmitted bits than the state of the art.

  • Takeaways & Limitations

    Error compensation allows compressed distributed updates to retain vanilla-SGD convergence rates while reducing communication for ImageNet and MNIST experiments.

  • Takeaways & Limitations

    With fixed γ and H, compression and local-computation errors keep memory bounded by O(η2), so reducing it asymptotically requires occasional learning-rate reductions.

Abstract

from arXiv · show

Communication bottleneck has been identified as a significant issue in distributed optimization of large-scale learning models. Recently, several approaches to mitigate this problem have been proposed, including different forms of gradient compression or computing local models and mixing them iteratively. In this paper, we propose \emph{Qsparse-local-SGD} algorithm, which combines aggressive sparsification with quantization and local computation along with error compensation, by keeping track of the difference between the true and compressed gradients. We propose both synchronous and asynchronous implementations of \emph{Qsparse-local-SGD}. We analyze convergence for \emph{Qsparse-local-SGD} in the \emph{distributed} setting for smooth non-convex and convex objective functions. We demonstrate that \emph{Qsparse-local-SGD} converges at the same rate as vanilla distributed SGD for many important classes of sparsifiers and quantizers. We use \emph{Qsparse-local-SGD} to train ResNet-50 on ImageNet and show that it results in significant savings over the state-of-the-art, in the number of bits transmitted to reach target accuracy.

1 Introduction

The paper targets communication bottlenecks in distributed learning by combining gradient compression with local computation and error compensation, then analyzes and evaluates the resulting Qsparse-local-SGD algorithm.

  • 1 Introduction: Full-precision gradient exchange becomes a bottleneck when high-dimensional models train over bandwidth-limited or unreliable networks.A BERT-scale model with about 340 million parameters requires over 1.3GB per full-precision exchange.
  • 1 Introduction: Existing approaches reduce communication through gradient quantization, Topk-style sparsification with error compensation, or less frequent model averaging after local updates.These approaches respectively reduce precision, transmit selected components, or postpone synchronization.
  • 1 Introduction: Qsparse-local-SGD combines aggressive sparsification, quantization, local computations, and error compensation, with synchronous and asynchronous distributed implementations.The method tracks differences between true and compressed gradients and supports arbitrary-time gradient updates in the asynchronous model.
  • 1 Introduction: The paper analyzes Qsparse-local-SGD for smooth non-convex and convex objectives and reports convergence comparable to distributed vanilla SGD for important sparsifier and quantizer classes.The stated theoretical results cover synchronous and asynchronous settings, including distributed mini-batch and local-iteration effects.
  • 1 Introduction: On ImageNet ResNet-50 and MNIST softmax classification, the method reaches target accuracies with about 15-20× fewer transmitted bits than the state of the art.The paper reports significant communication savings while retaining equivalent state-of-the-art performance.

2 Communication Efficient Operators

The paper develops quantization and sparsification operators for communication-efficient distributed optimization, including compositions whose compression properties support the proposed algorithms.

  • 2. Communication Efficient Operators: Quantization maps gradient components to finitely many levels, while sparsification retains selected components such as Topk or randomly chosen Randk entries.Quantizers may be deterministic or randomized; Topk selects the k largest-magnitude components.
  • 2.1 Quantization: Randomized quantizers preserve unbiasedness while controlling the expected squared norm through a dimension- and level-dependent parameter βd,s.The definition requires E[Qs(x)] = x and E[∥Qs(x)∥2] ≤ (1 + βd,s)∥x∥2.
  • 2.2 Sparsification: Topk and Randk satisfy a compression property with coefficient γ = k/d, and piecewise operators inherit the minimum coefficient across coordinate blocks.This permits different compression operators for different coordinates or neural-network layers.
  • 2.3 Composition of Quantization and Sparsification: Composing quantizers with explicit sparsifiers yields a compression operator under conditions on the quantizer and sparsity level.For QsCompk, the unscaled composition is covered when βk,s < 1, with γ = (1 − βk,s)k/d.
  • 2.3 Composition of Quantization and Sparsification: The quantizer-sparsifier operating regime remains constrained by second-moment growth from stochastic quantization, although piecewise compression alleviates this limitation to some extent.The restriction is expressed through the requirement βk,s < 1 for the composed operator.
  • 2.3 Composition of Quantization and Sparsification: Piecewise composition can permit a coarser quantizer than whole-vector composition, improving communication efficiency in layerwise applications.The paper notes this can expand the operating regime for quantization and sparsification.

3 Distributed Synchronous Operation

The synchronous algorithm lets workers perform local updates between synchronizations, then send compressed, error-compensated progress for global aggregation. Under stated smoothness and bounded-moment assumptions, its convergence analysis covers non-convex and strongly convex objectives, with compression preserving vanilla-SGD rates under synchronization conditions.

  • Synchronous operation: Workers maintain local parameter vectors and synchronize with the master at shared indices in I_T.At synchronization, workers send compressed, error-compensated updates based on net progress since the previous synchronization.
  • Synchronous operation: The master aggregates workers’ updates, updates the global parameter vector, and broadcasts the new model to all workers.Workers then reset their local parameter vectors to the global model.
  • Error compensation: Error compensation stores compression errors in worker memory, enabling future updates to recover convergence rates matching vanilla SGD.The controlled operators combine current updates with previously accumulated compression errors.
  • Error compensation: With a decaying learning rate, local memory contracts to zero as O(η_t)^2, so net compression error is eventually compensated.This result holds under bounded synchronization gaps and suitable conditions involving the compression coefficient.
  • Memory behavior: For fixed learning rates, worker memory remains bounded by O(η^2), rather than asymptotically vanishing unless the learning rate is reduced during training.The fixed-rate bound is improved by directly analyzing the fixed-rate case.
  • Convergence results: The synchronous convergence analysis covers smooth non-convex and strongly convex objectives, with compression not affecting the first-order term under the stated conditions.The results use compressed operators including the paper’s composed quantization-and-sparsification operators.
  • Convergence results: Unlike prior local-computation methods, the approach combines quantization and sparsification with local computation, creating additional technical challenges in the analysis.The paper highlights this combination as a distinction from work considering local computation alone.

4 Distributed Asynchronous Operation

The asynchronous algorithm allows workers to synchronize at different times while maintaining a bounded delay between updates. Its convergence analysis covers smooth non-convex and strongly convex objectives and identifies conditions under which compressed updates match distributed vanilla-SGD rates.

  • Asynchronous operation: All workers’ local iterates evolve at the same global-clock rate, although their updates may occur after different numbers of local iterations.This differs from straggler-oriented asynchronous methods based on delayed individual gradient steps.
  • Asynchronous operation: The asynchronous analysis assumes each worker’s synchronization-gap maximum is bounded by H.This provides a uniform bound on the maximum delay in each worker’s update times.
  • Asynchronous operation: Workers synchronize with the master at locally determined times, and arbitrary subsets, including a single worker, may send updates.The master aggregates received updates, updates the global model, and sends it only to participating workers.
  • Convergence results: Theorems cover smooth non-convex and strongly convex objectives for arbitrary compression operators with compression coefficient γ.The result includes the composed operators used by Qsparse-local-SGD.
  • Convergence results: The asynchronous fixed-learning-rate analysis provides non-asymptotic guarantees in which compression does not affect the dominant convergence terms.The paper describes this effect as compression coming “for free.”
  • Asynchronous analysis: Asynchrony requires additional bounds on deviations between local, virtual, and true sequences because workers can update the global model between other workers’ synchronizations.The paper notes that these bounds can be weaker than in the synchronous setting.
  • Convergence results: For decaying learning rates, the asynchronous method attains vanilla-SGD convergence rates when H satisfies separate non-convex and strongly convex bounds.The stated bounds are H = O(√γT 1/8/(bR)3/8) for smooth non-convex objectives and H = O(√γ(T/(bR))1/4) for strongly convex objectives.
  • Practical flexibility: The method permits trade-offs among batch size, synchronization period H, Topk sparsity, and quantizer configuration to mitigate communication bottlenecks.The paper reports numerical experiments demonstrating savings in transmitted bits.

5 Experimental Results

Experiments evaluate Qsparse operators and Qsparse-local-SGD across non-convex and convex objectives, with comparisons against compressed, sparsified, local, and vanilla SGD baselines. The results show near-preserved convergence alongside substantial communication savings, including up to over 1000× fewer bits in reported settings.

  • Non-convex experiments: ResNet-50 experiments use ImageNet, 8 NVIDIA Tesla V100 GPUs, and 25,610,216 model parameters.Training uses five warmup epochs, piecewise learning-rate decay, and batch size 256 per GPU.
  • Non-convex experiments: QTopk-SGD and SignTopk-SGD show almost no convergence-rate penalty versus vanilla SGD when error compensation is enabled.QTopk uses a 4 bit quantizer, while SignTopk uses a 1 bit sign quantizer with Topk sparsification.
  • Non-convex experiments: 6 to 8 times fewer communicated bits are achieved on average by adding local iterations to Qsparse methods while retaining comparable convergence rates.The comparison covers vanilla SGD, Topk, Sign compositions, QSGD with error accumulation, and Qsparse operators.
  • Non-convex experiments: Around 1/16 as many bits as Topk-SGD and over 1000× fewer bits than vanilla SGD are needed for the same loss or top-1 accuracy.The comparison combines sign or stochastic quantization, aggressive sparsification, and infrequent communication; memory-based error compensation also addresses quantization error.
  • Convex experiments: Convergence is not significantly affected when local iterations increase from 1 to 8, although QTopk is more sensitive to local computation with coarser quantizers.The sensitivity is less prominent with a 4 bit quantizer than with a coarser quantizer.

6 Conclusion

Qsparse-local-SGD combines quantization, aggressive sparsification, local computation, and error compensation, with analyses covering synchronous and asynchronous convex and non-convex settings. The paper reports vanilla distributed SGD convergence rates and communication-efficient training, while momentum analysis remains future work.

  • Qsparse-local-SGD composes unbiased or biased quantization, aggressive sparsification, local computations, and error compensation.Error compensation tracks the difference between true and compressed gradients.
  • The algorithm is analyzed for synchronous and asynchronous distributed optimization with convex and non-convex objectives.
  • Qsparse-local-SGD achieves the same convergence rate as distributed vanilla SGD in the analyzed settings.Without compression, the framework also subsumes or generalizes several local-SGD results with similar convergence rates.
  • Momentum acceleration is used in the numerical experiments, but its analysis is left for future research.The paper also reports preliminary evidence for momentum applied to blocks of updates, although this is not the main focus.
  • Figure 7 compares the scheme with ef-signSGD and TopK-SGD for asynchronous operation in a convex setting.

A.1 Proof of Lemma 1

The appendix establishes compression properties for composed quantization and sparsification operators, then bounds error-compensation memory under synchronization gaps and learning-rate schedules. These bounds support controlled memory evolution in the distributed method.

  • Composing a quantizer Qs with Topk or Randk yields a compression operator when βk,s < 1, with γ = (1 − βk,s)k/d.The expectation covers randomness from both the sparsifier and quantizer.
  • The scaled composition QsCompk is also characterized by γ = k/d(1+βk,s).
  • Error-compensation memory is bounded under uniformly bounded gradients and synchronization gaps of at most H.The proof uses induction and separately treats synchronization indices and intervening iterations.
  • The proof uses geometric-sum control of accumulated compression errors and the fact that local memory remains unchanged between synchronization indices.

B.3 Proof of Lemma 6

The proof of Lemma 6 relates the true and virtual distributed sequences through the workers’ average memory. This identity is then used alongside memory bounds to control sequence deviation.

  • The difference between the true and virtual sequence equals the average memory across workers.
  • The proof compares synchronization times and uses the nearest relevant synchronization indices to express the sequence difference.

B.6 Proof of Theorem 1

The proof of Theorem 1 uses smoothness, stochastic mini-batch sampling, and learning-rate restrictions to derive a convergence bound. It also introduces a random output iterate whose expected squared gradient is controlled over T iterations.

  • The proof starts from L-smoothness and uses Lipschitz continuity of local gradients to bound stochastic updates.
  • The analysis applies the inequality ∥u+v∥^2 ≤ 2∥u∥^2 + 2∥v∥^2 when taking expectations over the optimization process.
  • The intermediate bound holds for any learning-rate schedule, including fixed ηt = η ≤ 1/(2L).
  • The theorem samples an output parameter zT from iterates with probability 1/(RT) for each worker and time index.
  • The sampling rule implies E∥zT∥^2 = 1/(RT).

B.7 Proof of Theorem 2

The proof derives a weak convergence result for the non-convex setting by combining intermediate bounds and sampling a parameter iterate.

  • The proof aggregates per-worker and time-indexed terms using a telescopic sum over t = 0 to T −1.
  • The analysis establishes a weak convergence result for the generated iterates.
  • A parameter zT is sampled from the iterates to express the expected squared gradient norm through the weighting quantity PT.

B.8 Proof of Theorem 3

The proof analyzes convergence under strong convexity and smoothness, combining bounds on separate terms before applying weighted averaging of iterates.

  • The proof uses strong convexity and smoothness to bound separate terms in the main recurrence.
  • The bounds are combined under the step-size condition a ≥32L/µ, which implies ηt ≤1/4L.
  • For ηt = 8/µ(a+t) and wt = (a+t)^2, the proof forms a weighted sum of iterates before concluding Theorem 3.

C.1 Proof of Lemma 9

The lemma proofs bound deviations between local, virtual, and averaged sequences in asynchronous execution under bounded synchronization gaps.

  • A deviation bound is established for the local sequences generated by Algorithm 2 with a decaying learning rate.
  • The asynchronous analysis assumes each worker’s synchronization gap satisfies gap(I(r)T) ≤H.
  • The bounds use the compressor inequality E∥QCompk(u)∥2 ≤B∥u∥2, with B = (4 −2γ).
  • The proof introduces virtual sequences for every worker to handle asynchronous updates and compare them with the actual sequences.

D Omitted Details from Section 5

The non-convex experiments compare scaled and unscaled QTopk operators. With error compensation, compressed and infrequently communicated training can match vanilla SGD rates, while unscaled QTopk is preferred at higher local-iteration counts.

  • Figure 8 compares Qsparse-local-SGD with scaled and unscaled QTopk operators in the non-convex setting.
  • With error compensation, Qsparse-local-SGD recovers convergence rates matching vanilla SGD despite compression and infrequent communication.
  • For L = 0, 4, both composed operators require almost equal transmitted bits to reach a target loss or accuracy.
  • When L = 8, the unscaled QTopk operator performs better in transmitted bits than the scaled operator.
Loading 1906.02367v2…