PaperlayerView exact revision on arXiv

Source-linked AI summary

Communication-Efficient Distributed Blockwise Momentum SGD with Error-Feedback

Shuai Zheng, Ziyue Huang, James T. Kwok

arXiv:1905.10936v2cs.LGcs.DCmath.OCstat.ML

TL;DR

Communication costs constrain the scalability of distributed machine learning, while signSGD's convergence relies on assumptions that may fail in practice. The paper develops two-way error-feedback compression with blockwise quantization and analyzes distributed SGD with momentum. Its methods retain the convergence rates and test accuracy of full-precision SGD/SGDM, with nearly 32x lower communication cost.

  • Problem

    Communication overhead limits the scalability of distributed machine learning, and signSGD's convergence depends on assumptions that can be violated in practice.

    Source: §1 · p. 1

  • Method

    The paper extends error-feedback to distributed parameter-server SGD, compressing gradients in both directions and using blockwise 1-bit quantization with an average ℓ1-norm scaling factor.

    Source: §1 · p. 2

  • Results

    The proposed methods match full-precision distributed SGD/SGDM in convergence rate and test accuracy, while achieving nearly 32x lower communication cost.

    Source: §1 · p. 2, §5 · p. 9

  • Takeaways & Limitations

    Blockwise error-feedback compression provides a communication-efficient alternative that preserves the reported convergence rates and test accuracy of distributed SGD/SGDM.

    Source: §1 · p. 2, §5 · p. 9

    The convergence analysis assumes the objective is lower-bounded and L-smooth.

    Source: §3.1 · p. 4

Abstract

from arXiv · show

Communication overhead is a major bottleneck hampering the scalability of distributed machine learning systems. Recently, there has been a surge of interest in using gradient compression to improve the communication efficiency of distributed neural network training. Using 1-bit quantization, signSGD with majority vote achieves a 32x reduction on communication cost. However, its convergence is based on unrealistic assumptions and can diverge in practice. In this paper, we propose a general distributed compressed SGD with Nesterov's momentum. We consider two-way compression, which compresses the gradients both to and from workers. Convergence analysis on nonconvex problems for general gradient compressors is provided. By partitioning the gradient into blocks, a blockwise compressor is introduced such that each gradient block is compressed and transmitted in 1-bit format with a scaling factor, leading to a nearly 32x reduction on communication. Experimental results show that the proposed method converges as fast as full-precision distributed momentum SGD and achieves the same testing accuracy. In particular, on distributed ResNet training with 7 workers on the ImageNet, the proposed algorithm achieves the same testing accuracy as momentum SGD using full-precision gradients, but with $46\%$ less wall clock time.

1 Introduction

Distributed training can be limited by gradient and parameter communication costs. The paper proposes two-way error-feedback compression with a blockwise compressor and studies convergence for distributed SGD variants.

1 Introduction

  • Distributed synchronous SGD and its momentum variant aggregate worker-computed mini-batch gradients at a server, but communication can limit scalability.Each iteration transfers 64Md bits between workers and server for gradient/parameter dimension d and M workers.Source: §1 · p. 1
  • Prior approaches include sparsification and quantization; signSGD's convergence relies on large mini-batches and unimodal symmetric gradient noise, and it can diverge when these assumptions fail.Error-feedback methods instead retain compression residuals for later correction, while some alternatives use all-to-all communication.Source: §1 · pp. 1–2
  • Two-way compression sends gradients in both directions, and blockwise 1-bit quantization with an average ℓ1-norm scaling factor yields nearly 32x lower communication cost.The approach is used in dist-EF-SGD and its Nesterov-momentum variant, dist-EF-SGDM.Source: §1 · p. 2
  • Dist-EF-SGD is analyzed for a class of compressors including sign and top-k, with general, constant, decreasing, and increasing stepsize schedules.The paper states these guarantees do not rely on the assumptions it characterizes as unrealistic for signSGD.Source: §1 · p. 2
  • The proposed methods achieve the same test accuracy as SGD/SGDM and avoid the much worse accuracies reported for signSGD and signum.The conclusion also reports convergence rates matching full-precision distributed SGD/SGDM on nonconvex objectives.Source: §1 · p. 2

2 Related Work: SGD with Error-Feedback

Error-feedback retains the part of a gradient not used in the current update and adds that residual to the next iteration. This correction lets EF-SGD recover the same convergence rate as SGD.

2 Related Work: SGD with Error-Feedback

  • The paper frames its objective as minimizing expected risk F(x)=Eξ[f(x,ξ)], which directly measures generalization error.Taking the expectation over a training set reduces expected risk to empirical risk.Source: §2 · p. 3
  • EF-SGD adds the accumulated residual to the current stochastic gradient before compression, then stores the difference between the corrected gradient and compressed update.The method described here considers a single machine.Source: §2 · p. 3
  • An δ-approximate compressor bounds its squared compression error by (1−δ) times the input's squared ℓ2 norm.Scaled sign and top-k operators are examples; randomized compressors may satisfy the condition in expectation.Source: §2 · p. 3
  • EF-SGD achieves the same O(1/T) rate as SGD, using an error-corrected iterate whose recurrence resembles SGD's.That resemblance supports bounding the gradient difference between corrected and actual iterates.Source: §2 · p. 3

3 Distributed Blockwise Momentum SGD with Error-Feedback

The section develops distributed error-feedback SGD with compression in both communication directions, then extends it with blockwise compression and Nesterov momentum. Its analysis establishes convergence guarantees and identifies the trade-offs among compression, worker count, and momentum.

3.1 Distributed SGD with Error-Feedback

  • Worker and server error-feedback compress gradients in both directions; changing stepsizes require rescaling local residuals by η_{t−1}/η_t and omitting stepsize multiplication before compression.With an identity compressor, dist-EF-SGD reduces to full-precision distributed SGD, but it does not reduce to single-worker EF-SGD.Source: §3.1 · p. 3
  • After T ≥ O(1/δ^2) iterations, dist-EF-SGD matches full-precision distributed synchronous SGD’s convergence rate, with O(1/(MT)) convergence without signSGD’s large-batch and noise assumptions.The analysis also contrasts the two-way compression bound with the single-machine, one-way EF-SGD bound.Source: §3.1 · pp. 4–5
  • Decreasing, increasing, or hybrid stepsize schedules are allowed; the paper identifies this as the first such result for distributed compressed SGD on nonconvex problems.An increasing warm-up followed by a decreasing schedule is given as an example.Source: §3.1 · p. 5

3.2 Blockwise Compressor

  • The blockwise compressor partitions the input into B blocks and quantizes each block’s signs using its own mean-absolute-value scaling factor; its approximation parameter is at least min_b 1/d_b.The resulting dist-EF-blockSGD is a special case of dist-EF-SGD, so its convergence results apply with δ replaced by φ(v).Source: §3.2 · p. 6
  • For same-sized blocks with constant within-block magnitudes, the blockwise compressor can have a much larger approximation parameter than the standard compressor; ResNet-20 estimates show φ(v) substantially larger than the non-block value.The proposed blockwise compressor also adds 64MB bits per iteration for scaling factors, while reducing communication nearly 32x versus full-precision distributed SGD.Source: §3.2 · p. 6

3.3 Nesterov’s Momentum

  • dist-EF-blockSGDM adds local Nesterov momentum to the error-feedback procedure while retaining the same communication cost as dist-EF-blockSGD.The error-corrected iterate is similar to a Nesterov accelerated-gradient iterate, except its momentum is computed from the original iterates.Source: §3.3 · p. 7
  • A larger momentum parameter reduces the initial-condition term but worsens both the variance term and the gradient-compression error term in the convergence bound.The theorem assumes a constant stepsize and η ≤ (1−μ)^2/(2L).Source: §3.3 · p. 7

4 Experiments

The experiments compare blockwise error-feedback SGD variants with full-precision methods and sign-based methods on CIFAR-100 and ImageNet. On ImageNet with 7 workers, dist-EF-blockSGDM reaches SGDM’s highest accuracy in about 13 hours versus 24 hours, a 46% speedup.

4.1 Multi-GPU Experiment on CIFAR-100

  • On CIFAR-100, dist-EF-blockSGD converges as fast as SGD with slightly better accuracy, while signSGD performs poorly and signum remains much worse than dist-EF-blockSGDM.BlockSGD is robust to mini-batch size, whereas signSGD degrades with smaller batches; momentum accelerates SGD and blockSGD for batch sizes 16 or 32, particularly before epoch 100.Source: §4.1 · p. 8

4.2 Distributed Training on ImageNet

  • 46% speedup: with 7 ImageNet workers, dist-EF-blockSGDM reaches SGDM’s highest accuracy in about 13 hours versus 24 hours, with 76.77% versus 76.27% accuracy.With 15 workers, the improvement is smaller; the authors attribute this to a heavier parameter-server burden.Source: §4.2 · p. 9, Figure 3 · p. 9
  • On ImageNet, SGDM and dist-EF-blockSGDM have comparable accuracy, while signum is inferior and about 4% worse in test accuracy.The comparison uses 50-layer ResNet training with 7 or 15 workers; the figure reports testing accuracy against epochs and wall-clock time.Source: §4.2 · pp. 8–9, Figure 3 · p. 9
  • ImageNet computation costs are comparable across methods, but signum and dist-EF-blockSGDM have lower communication costs than SGDM.Their communication costs are comparable with 7 workers; with 15, signum is lower, which the authors speculate may reflect separate transmission of sign vectors and scaling factors.Source: §4.2 · p. 9

5 Conclusion

The paper concludes that blockwise distributed SGD with error feedback and momentum can reduce gradient transmission to 1-bit blocks while matching full-precision methods’ convergence rates and test accuracy. In the stated experiments, signSGD and signum achieve much worse accuracy.

5 Conclusion

  • Blockwise error-feedback SGD with momentum transmits each gradient block using 1-bit quantization and its average ℓ1-norm.The methods are reported to have the same convergence rates as full-precision distributed SGD/SGDM for nonconvex objectives.Source: §5 · p. 9
  • The proposed methods achieve the same test accuracy as SGD/SGDM, while signSGD and signum achieve much worse accuracies.The conclusion also reports fast convergence for the proposed methods.Source: §5 · p. 9

A Experimental Setup

  • For synchronous experiments, weight decay is added to the update rather than compressed with the gradient; the momentum variant maintains an extra momentum for weight decay on each machine.The sign is mapped to {−1, 1} and uses 1 bit.Source: A Experimental Setup · p. 12

A.1 Setup: Multi-GPU Experiment on CIFAR-100

The CIFAR-100 and ImageNet experiments use separately specified training schedules and hyperparameters. For CIFAR-100, the error-feedback variants reuse stepsizes tuned for SGD or SGDM; ImageNet settings include worker-count-specific stepsizes.

A.1 Setup: Multi-GPU Experiment on CIFAR-100

  • For CIFAR-100, each algorithm runs 200 epochs, with stepsizes selected on a 5K-image validation set and reduced by 10 at epochs 100 and 150.Weight decay is fixed at 0.0005 and momentum at 0.9; error-feedback methods reuse the stepsizes tuned for SGD or SGDM.Source: §A.1 · p. 12, Table 2 · p. 12

A.2 Setup: Distributed Training on ImageNet

  • For ImageNet, SGDM and signum use code-base hyperparameters with momentum 0.9, weight decay 0.0001, and 128 examples per worker.The stated stepsizes are η = 0.1M for SGDM and η = 0.0001 on 7 workers or η = 0.0002 on 15 workers for signum.Source: §A.2 · p. 12
  • ImageNet dist-EF-blockSGDM uses momentum 0.9 and weight decay 0.0001, with η = 0.1 for 7 workers and η = 0.2 for 15 workers.The authors note that η = 0.1M is too large for dist-EF-blockSGDM, while SGDM with η = 0.1 performs worse than SGDM with η = 0.1M.Source: §A.2 · p. 12

B Proof of Lemmas 1 and 3

The proof establishes a recurrence and notes that Lemmas 1 and 3 follow by substituting the respective gradient and momentum-gradient expressions.

B Proof of Lemmas 1 and 3

C Proof of Theorem 1

The proof uses smoothness and variance bounds to derive an expected objective bound for compressed SGD. It assumes a step-size restriction and selects an index from the resulting bound.

C Proof of Theorem 1

  • The proof derives an expected objective bound using the smoothness of F and a mini-batch gradient variance bound.The variance step uses E[||x − E[x]||^2] = E[||x||^2] − ||E[x]||^2.Source: C Proof of Theorem 1 · pp. 13–14
  • Young’s inequality and smoothness are used to control terms in the bound, with ρ set to 1/2.Source: C Proof of Theorem 1 · p. 14
  • The derivation assumes η_t < 3/(2L) for every t before summing and dividing the bound across iterations.Source: C Proof of Theorem 1 · p. 14
  • The proof chooses an index o from {0, …, T−1} satisfying the derived bound, completing the argument.Source: C Proof of Theorem 1 · p. 14

D Proof of Corollary 1

The proof obtains a bound for full-precision distributed SGD by adapting the smoothness argument. For a constant step size, it averages the bound over T iterations.

D Proof of Corollary 1

E Proof of Corollary 2

The proof of Corollary 2 substitutes summed-term bounds into Theorem 1. It also gives a condition on T that ensures an upper bound on the step size.

E Proof of Corollary 2

G Proof of Theorem 2

Theorem 2’s proof analyzes a virtual iterate, bounds its expected objective change, and combines the resulting inequalities to obtain a gradient bound. The accompanying Corollary 3 proof imposes a condition on T to bound the step size.

G Proof of Theorem 2

  • The proof bounds accumulated compressor-related error terms using the compressor definition, Young’s inequality, and a geometric-series sum.Source: G Proof of Theorem 2 · pp. 18–20
  • The proof uses smoothness to bound the virtual iterate’s expected objective change and then combines intermediate inequalities to derive a bound.The combination invokes Jensen’s inequality, telescoping expectations over iterations, and a double-sum rearrangement.Source: G Proof of Theorem 2 · pp. 21–22
  • The derivation bounds a term involving the inner product of gradients and separately bounds a final term before combining the estimates.Source: G Proof of Theorem 2 · p. 21
  • The final gradient bound depends on the initial objective gap and the variance term, with parameters including momentum and ρ.Source: G Proof of Theorem 2 · p. 22

Proof of Corollary 3

Related papers

Loading 1905.10936v2…