Source-linked AI summary
Error Feedback Fixes SignSGD and other Gradient Compression Schemes
Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian U. Stich, Martin Jaggi
TL;DR
Biased sign compression can prevent convergence and harm generalization, motivating a method that preserves communication savings without discarding correction information. The paper adds error-feedback to compressed updates, proves SGD-like convergence for arbitrary compressors, and reports improved convergence and generalization.
Problem
Biased sign compression can cause non-convergence and poor generalization, even though it is used to reduce communication in distributed training.
Method
Error-feedback rescales the signed corrected gradient and stores compression residuals for addition to the next update.
Results
EF-SGD with arbitrary compression achieves the same convergence rate as SGD, while EF-SIGNSGD approaches the max-margin solution and improves over SIGNSGD experimentally.
Takeaways & Limitations
Error-feedback mitigates the adverse convergence and generalization effects of biased compression while retaining gradient communication savings.
Takeaways & Limitations
The asymptotic EF-SGD rate is presented as 2 times slower than SGD in the paper’s simple analysis, though the authors state tighter analysis can fix this.
Abstract
from arXiv · showhide
Sign-based algorithms (e.g. signSGD) have been proposed as a biased gradient compression technique to alleviate the communication bottleneck in training large neural networks across multiple workers. We show simple convex counter-examples where signSGD does not converge to the optimum. Further, even when it does converge, signSGD may generalize poorly when compared with SGD. These issues arise because of the biased nature of the sign compression operator. We then show that using error-feedback, i.e. incorporating the error made by the compression operator into the next step, overcomes these issues. We prove that our algorithm EF-SGD with arbitrary compression operator achieves the same rate of convergence as SGD without any additional assumptions. Thus EF-SGD achieves gradient compression for free. Our experiments thoroughly substantiate the theory and show that error-feedback improves both convergence and generalization. Code can be found at \url{https://github.com/epfml/error-feedback-SGD}.
1 Introduction
The paper identifies convergence and generalization failures in biased sign-based compression, then introduces error-feedback to recover SGD-like behavior while retaining communication savings.
- Motivation: Sign-based updates can lose gradient magnitude and direction, causing non-convergence in general.The paper presents convex counterexamples and links the failures to information discarded by the sign operator.
- Error-feedback: EF-SIGNSGD rescales the signed corrected vector and feeds accumulated compression error into the next gradient step.The corrected direction is p_t = γg_t + e_t, and compression uses (∥p_t∥_1/d) sign(p_t).
- Theory: Error-feedback extends beyond SIGNSGD: arbitrary gradient compression schemes achieve the same non-convex smooth convergence rate as SGD.The result is presented as gradient compression without an additional convergence-rate cost.
- Generalization: EF-SIGNSGD approaches the span of past gradients and converges to the max-margin solution in over-parameterized least-squares.This gives a theoretical basis for its expected generalization advantage over SIGNSGD.
- Experiments: On CIFAR10 and CIFAR100 with ResNet and VGG, EF-SIGNSGD significantly outperforms SIGNSGD, matches SGD on train and test datasets, and reduces communication by ∼64×.The experiments evaluate both convergence-related performance and generalization-related performance.
2 Significance and Related Work
The related work connects sign methods to adaptive optimization and gradient compression, emphasizing their relevance to both convergence analysis and communication-efficient distributed training.
- Adaptive methods: SIGNSGD with momentum is described as behaviorally identical to ADAM, making sign-method convergence relevant to understanding adaptive optimization.The connection is used to motivate studying SIGNSGD and SIGNSGDM.
- Gradient compression: Gradient communication becomes a bottleneck as model sizes and distributed training scale increase.Compression is presented as a way to alleviate this bottleneck and better use parallel hardware.
- Error-feedback: Prior practical compressed-training methods commonly use some form of error-feedback.The paper cites 1-bit SGD, Strom, and Lin et al. as examples.
- Error-feedback: Earlier theory analyzed error-feedback for strongly convex problems, while this paper positions its convergence results as extending analysis to non-convex and weakly convex cases.The related-work discussion distinguishes these settings from the paper’s broader scope.
- Generalization: The generalization discussion places SIGNSGD and ADAM within broader work on over-parameterized deep networks and their ability to fit arbitrary data.This connects optimizer behavior to ongoing research on why highly expressive networks generalize.
3 Counterexamples for SignSGD
The section gives convex counterexamples showing that SIGNSGD can fail to converge, including under adaptive step sizes and smooth stochastic gradients. The failures arise because sign-based updates discard gradient magnitude or a persistent direction.
- Failure under standard assumptions: SIGNSGD can fail to converge under standard assumptions, despite convergence results under smoothness with Gaussian noise or extremely large batches.The section contrasts benign conditions with counterexamples under more standard settings.
- Failure under standard assumptions: With a fixed step size, SIGNSGD does not converge even for simple one-dimensional linear functions.
- Failure under standard assumptions: Even adaptive step sizes cannot ensure convergence: in a non-smooth convex problem, SIGNSGD remains constrained to a line and never improves the initial objective.Starting from x0 = (1, 1)⊤, the iterates satisfy x1 + x2 = 2 and f(xt) ≥ f(x0).
- Failure under standard assumptions: The same obstruction extends to smooth functions with stochastic gradients, where SIGNSGD remains on x1 + x2 = 2 and f(xt) ≥ f(x0) almost surely.
- Generalization of the counterexample: In arbitrary dimensions, batch-size-1 SIGNSGD does not converge almost surely when all sampled feature signs align with a common sign vector, even with adaptive step sizes and random initialization.The stated conditions include a unique optimum and stochastic gradients sampled uniformly from the component losses.
4 Convergence of Compressed Methods
The paper analyzes error-feedback for general compressed gradients, showing bounded residual error and convergence guarantees under standard assumptions. For smooth non-convex objectives, compression affects only higher-order terms asymptotically, while non-smooth rates retain direct dependence on compression quality.
- Error-feedback framework: Error-feedback augments compressed SGD with residual errors, transmitting omitted gradient information later as a delayed gradient method.The update forms a corrected direction from the stochastic gradient and accumulated error before compression.
- Smooth non-convex convergence: Under smoothness and stochastic-gradient moment assumptions, EF-SGD converges for any δ-approximate compressor.The analysis bounds the residual error and states a non-convex convergence theorem under Assumptions A, B, and C.
- Smooth non-convex convergence: After T ≥ O(1/δ^2) iterations, EF-SGD catches up with full SGD because compression appears only in the higher-order O(1/T) term.The paper states that this is usually reached within the first few epochs.
- Non-smooth convergence: Error-feedback also ensures convergence for convex non-smooth functions, although compression quality δ appears directly in the leading convergence term.Unlike the smooth case, the analysis cannot approximate gradients at delayed and current iterates as equal.
- EF-SIGNSGD implications: For EF-SIGNSGD, the relevant compression quality is the density of the error-corrected gradient gt + et, which can exceed the density of the stochastic gradient alone.The paper notes that dense deep-learning gradients yield larger density values, with Figure 2 reporting a minimum above 0.13 for φ(gt+et).
5 Generalization of SignSGD
The paper links poor sign-based generalization to iterates leaving the gradient span, while error-feedback keeps iterates close to that span and restores SGD-like behavior.
- SGD iterates lie in the linear span of gradients, and converging to zero loss there yields the minimum-norm, maximum-margin solution.
- Biased compressors such as SIGNSGD can leave the gradient span, which may explain their poorer generalization.
- Error-feedback iterates remain close to the gradient span, with the distance shrinking as the step-size decreases.
- In simulations, SIGNSGD and SIGNSGDM retain high span distance and test loss above 0.8, whereas EF-SIGNSGD's span distance and test loss go to 0.
6 Experiments
Experiments compare sign-based methods, momentum, and error-feedback on CIFAR models across batch sizes. EF-SIGNSGD consistently outperforms sign-based alternatives and closely matches SGDM on test performance.
- Experimental setup: Experiments compare SGDM, scaled SIGNSGD, SIGNSGDM, and EF-SIGNSGD on CIFAR-10 and CIFAR-100 models.
- Results: EF-SIGNSGD consistently and significantly outperforms other sign-based methods on CIFAR-100 Resnet18 across batch sizes, closely matching SGDM.
- Results: EF-SIGNSGD matches or exceeds SGDM on training performance and is much closer to SGD than other sign methods on test performance.
- Results: SIGNSGD performance worsens as batch size decreases and becomes extremely unstable at batch-size 8.
- Results: SIGNSGDM performs poorly on some datasets and smaller batch sizes, including a 6.6% accuracy drop at batch-size 8.
7 Conclusion
The paper concludes that naive biased compression can harm convergence and generalization, whereas error-feedback mitigates these effects and preserves SGD's asymptotic convergence rate.
- Biased compressors can cause poor generalization and even non-convergence when used naively.
- Error-feedback mitigates these adverse effects, giving compressed EF-SGD the same convergence rate as original SGD.
A Additional Experiments
Additional experiments show that sign methods can be faster on a sparse-noise toy problem, contrasting with the paper's real-world training results, and report the learning-rate tuning setup.
- A.1 Convergence under sparse noise: In the toy problem, SIGNSGD and scaled SIGNSGD are faster than both SGD and EF-SIGNSGD.
- A.1 Convergence under sparse noise: The toy experiment was repeated 100 times, with solid lines showing means and shaded regions showing one standard deviation.
- A.1 Convergence under sparse noise: The toy result contrasts directly with real-world experiments where EF-SIGNSGD is faster during training than SGD and SIGNSGD.
- A.2 Experimental details: The CIFAR experiments use data augmentation, VGG19 for CIFAR-10, and Resnet18 for CIFAR-100.
- A.3 Learning rate tuning: Initial learning rates are tuned on batch-size 128, then scaled down for batch-sizes 32 and 8.
A.4 Experiments with Resnet
The Resnet experiments report complete loss results and compare generalization gaps across batch sizes on CIFAR-100. EF-SIGNSGD has a smaller gap that decreases as batch size decreases.
- The experiments report complete results, including losses, for Resnet.
- EF-SIGNSGD has a much smaller generalization gap than the sign-based methods, and its gap decreases as batch size decreases.
- The generalization gaps of SIGNSGDM and SIGNSGD increase as batch size decreases.
A.5 Experiments with VGG
The VGG experiments compare losses, accuracies, and generalization gaps across batch sizes on CIFAR-10. EF-SIGNSGD consistently outperforms other sign-based methods in the reported comparisons.
- The VGG experiments report complete results, including losses.
- EF-SIGNSGD consistently and significantly outperforms the other sign-based methods and is faster than SGDM in the reported Resnet18 comparison.
- EF-SIGNSGD has a much smaller generalization gap that decreases with decreasing batch size, whereas SIGNSGDM and SIGNSGD show increasing gaps.
- On VGG19, SIGNSGDM performs better on the train dataset than in the corresponding comparison, while the test-dataset comparison includes SIGNSGDM and another method.
A.6 Data generation process (Section 5.2)
The data-generation process fixes the sample and dimension sizes, constructs binary labels and a structured data matrix, then splits the data equally into train and test sets.
- The process fixes n = 200 data points and d = 6n dimensions.
- Each target label is uniformly assigned one of the values −1 or 1.
- The data matrix entries are filled according to a coordinate rule depending on the label and data-point index.
- The data and labels are randomly and equally split, producing 100 training and 100 test points, each with dimension 1200.
- The appendix section fills out proofs of claims, lemmas, and theorems from the main paper.
B.1 Proof of counter-example (Theorem I)
The proof analyzes SIGNSGD iterates and error-feedback sequences to establish convergence behavior and compare EF-SIGNSGD with SGD under smooth and non-smooth settings.
- SIGNSGD iterates move only along the signed-gradient direction, so convergence requires a suitable scalar step relation.
- In dimensions d ≥ 2, the required solution set has measure zero, so SIGNSGD fails to converge to x⋆ almost surely.
- Error-feedback analysis bounds the error sequence through a recurrence using the δ-approximate compressor and Young’s inequality.
- The proof treats the actual iterates as an approximation to ˜x_t = x_t − e_t, whose recurrence follows the stochastic-gradient updates.
- As T approaches infinity, EF-SIGNSGD has asymptotic convergence exactly the same as SGD.
- For non-smooth convex analysis, the convergence-rate dependence on compression quality δ is unavoidable, unlike the smooth case.