Source-linked AI summary
On Biased Compression for Distributed Learning
Aleksandr Beznosikov, Samuel Horváth, Peter Richtárik, Mher Safaryan
TL;DR
Communication is a bottleneck in distributed learning, while biased compression remains theoretically underexplored. This paper studies biased compressors in gradient methods and shows convergence guarantees, including linear convergence and error-feedback results for distributed methods.
Problem
Biased compressors can outperform unbiased ones in practice, but their theoretical behavior, including when and why they outperform, is poorly understood.
Method
The paper analyzes three classes of biased compression operators in compressed gradient descent and distributed stochastic gradient descent, including error-feedback mechanisms.
Results
Biased compressors achieve linear convergence guarantees in single-node and distributed settings, while error feedback provides convergence guarantees for distributed methods using biased compression.
Takeaways & Limitations
The analysis extends understanding of biased compression and connects theoretical predictions with lower empirical gradient variance during deep-network training.
Takeaways & Limitations
DCGD can diverge at an exponential rate when biased compression operators are used, as shown for the Top-1 compressor.
Abstract
from arXiv · showhide
In the last few years, various communication compression techniques have emerged as an indispensable tool helping to alleviate the communication bottleneck in distributed learning. However, despite the fact biased compressors often show superior performance in practice when compared to the much more studied and understood unbiased compressors, very little is known about them. In this work we study three classes of biased compression operators, two of which are new, and their performance when applied to (stochastic) gradient descent and distributed (stochastic) gradient descent. We show for the first time that biased compressors can lead to linear convergence rates both in the single node and distributed settings. We prove that distributed compressed SGD method, employed with error feedback mechanism, enjoys the ergodic rate $O\left( δL \exp \left[-\frac{μK}{δL}\right] + \frac{(C + δD)}{Kμ}\right)$, where $δ\ge 1$ is a compression parameter which grows when more compression is applied, $L$ and $μ$ are the smoothness and strong convexity constants, $C$ captures stochastic gradient noise ($C=0$ if full gradients are computed on each node) and $D$ captures the variance of the gradients at the optimum ($D=0$ for over-parameterized models). Further, via a theoretical study of several synthetic and empirical distributions of communicated gradients, we shed light on why and by how much biased compressors outperform their unbiased variants. Finally, we propose several new biased compressors with promising theoretical guarantees and practical performance.
1 Introduction
The paper studies biased communication compression for distributed learning, addressing limited theory despite practical evidence that biased compressors can outperform unbiased ones. It develops new compressor classes, analyzes compressed gradient methods, and establishes convergence results for single-node and distributed settings.
- 1 Introduction: Communication is typically the bottleneck when training large models on distributed data and parameters.The setting includes federated networks and centralized clusters.
- 1.2 Contributions: The paper addresses limited theoretical understanding of biased compression, including when and why it can outperform unbiased compression.It studies this question under synthetic and empirical assumptions on communicated gradient entries.
- 1.2 Contributions: Three parametric classes, B1(α, β), B2(γ, β), and B3(δ), are studied, with the first two introduced as new classes.The paper also relates these classes to unbiased compression and studies scaling and compositions.
- 1.2 Contributions: The paper compiles new and known biased and unbiased compressors and summarizes them in Table 3.This operator catalog complements the theoretical analysis of the three classes.
- 1.2 Contributions: Compressed gradient descent is analyzed for all three biased-compression classes under smoothness and strong convexity in the single-node case.The results generalize existing unbiased-operator results and recover the standard gradient-descent rate.
- 1.2 Contributions: Distributed SGD with error feedback is shown to converge for biased compressors, while naive distributed gradient descent with biased compression may diverge.The paper presents three convergence rates for different learning schedules and iterate-averaging schemes.
2 Biased Compressors
The paper introduces three classes of biased compressors, including two new classes, and characterizes their relationships, scaling behavior, and memberships. It also catalogs established and newly composed operators within these classes.
- Three biased compressor classes, B1(α, β), B2(γ, β), and B3(δ), are introduced, with the first two presented as new classes.
- The three classes describe the same collection of operators after reparameterization and possible scaling, but their parameterizations differ.
- Unbiased compressors can be converted into the biased classes through positive scaling, establishing a relationship between the U(ζ) and B-class formulations.
- Examples of biased compressors: The paper studies biased rounding, unbiased rounding, exponential dithering, natural compression, and a new Top-k–exponential-dithering composition.
- Examples of biased compressors: Top-k sparsification belongs to B1 and B3, while Rand-k is an unbiased compressor with a corresponding U-class guarantee.
- Examples of biased compressors: For exponential rounding, B3 yields the best iteration complexity among the class-based parameterizations considered.
3 Gradient Descent with Biased Compression
This section analyzes compressed gradient descent for smooth, strongly convex objectives using potentially biased compressors from the three proposed classes. The results establish convergence guarantees and compare the classes’ resulting iteration complexities.
- Compressed gradient descent applies a compressor C_k to each gradient before the stepsize update on an L-smooth, μ-strongly convex objective.
- The paper establishes three complexity theorems, one for each biased-compressor class, under bounded stepsizes.
- The identity compressor belongs to all three biased classes and recovers the standard gradient-descent rate.
- Time-varying parameters: Time-varying compression parameters can be accommodated, with time-varying stepsizes required for the B1 and B2 cases.
- Comparing parameterizations: For B3 compressors, converting through B1 can produce a bound worse than the direct B3 result by a factor of 16δ.
- Comparing parameterizations: The analysis therefore favors parameterizing compressors as members of B2 or B3 rather than B1 for compressed gradient descent.
4 Superiority of Biased Compressors Under Statistical Assumptions
The paper compares biased and unbiased compressors by expected gradient-information preservation under synthetic and practical coordinate distributions. Across these settings, Top-k sparsification and its composition with dithering show strong compression-performance trade-offs.
- Evaluation setup: The comparison evaluates expected approximation error and energy savings when gradient coordinates are modeled using synthetic or empirical distributions.
- Top-k versus Rand-k: Top-3 and Top-5 sparsifiers save 3×–40× more information in expectation than random sparsifiers, with the factor increasing with dimension.
- Top-k versus Rand-k: Figure 1 compares Top-k and Rand-k using normalized variance and average encoding bits per coordinate for Gaussian vectors with d = 104.
- Top-k versus Rand-k: For practical quadratic and logistic-regression gradient distributions, Top-5 achieves 3–5× better energy savings than Rand-5.
- Top-k combined with dithering: The paper proposes composing Top-k sparsification with exponential dithering, including natural dithering as the base-2 case.
- Top-k combined with dithering: The Top-k–natural-dithering composition attains the lowest empirically observed compression parameter δ among the compared compressors.
- Top-k combined with dithering: Figure 3 compares compressors by compression parameter δ and average encoding bits per coordinate, including parameter-free compressors with fixed communication budgets.
5 Distributed Setting
In distributed learning with biased compression, naive distributed compressed gradient descent can fail, while error feedback enables convergence under stated smoothness, strong convexity, and compressor assumptions.
- Failure of DCGD with biased compressors: Biased compression can make DCGD diverge exponentially fast or remain stuck at its initial point instead of reaching x⋆.The counterexamples include Top-1 compression and deterministic mappings satisfying the stated condition.
- Error Feedback: Error feedback corrects compressed-message errors across communication rounds and supports distributed stochastic gradients.Each node adds its error-feedback memory to the next message, compresses it, and stores the compression difference for later correction.
- Convergence guarantees: Algorithm 1 assumes L-smooth, µ-strongly convex local losses and compressors in B3(δ), then provides convergence rates under three stepsize and weighting regimes.The regimes use O(k) stepsizes and weights, constant stepsizes with exponentially changing weights, or constant stepsizes with equal weights.
- Convergence guarantees: All three schedules are sublinear in general, while the second schedule guarantees linear convergence when C = D = 0.C = 0 can hold with full local gradients, and D = 0 is associated with over-parameterized models.
- Convergence guarantees: With full local gradients and over-parameterization, distributed SGD with error feedback converges at the same linear rate as single-node CGD.The paper identifies this as the first regime guaranteeing linear convergence for a distributed first-order method with biased compression.
6 Experiments
The experiments compare biased and unbiased compression across deep-learning, regression, and synthetic quadratic settings. They report lower empirical variance, improved convergence, and communication savings for selected biased compressors, while emphasizing error feedback for biased methods.
- 6.1 Lower empirical variance induced by biased compressors during deep network training: Figure 6 compares empirical gradient variance for unbiased and biased compressors with matched communication complexity.The experiments use ResNet18, GoogleNet, and VGG19 on CIFAR10, comparing deterministic compression with Cnat and Top-k with Rand-k.
- 6.2 Error feedback for biased compression: Rand-5 performs significantly worse than Top-5 in the reported compression comparison.
- 6.3 Top-k mixed with natural dithering saves in communication significantly: Adding natural dithering after Top-k significantly reduces communication with almost no effect on convergence or generalization.The comparison trains VGG11 on CIFAR10 using Top-k, Rand-k, natural dithering, Top-k with natural dithering, and plain SGD.
- 6.4 Theoretical behavior predicts the actual performance in practice: Theoretical and practical convergence gaps for Top-5 and Rand-5 are compared on quadratics with different condition numbers and on Boston and Diabetes regression datasets.The synthetic quadratic experiment varies condition numbers through randomly generated matrices, while the regression experiment uses normalized Boston and Diabetes data.
- 6.4 Theoretical behavior predicts the actual performance in practice: Biased compression with less empirical variance leads to better practical convergence, and the observed gap nearly matches the theoretical improvement.
- 6.5 Transformer training: ALBERT-large experiments evaluate training loss and downstream GLUE scores while including communication-round and compression/decompression time in communication cost.The model has 18M parameters with layer sharing and is trained on BookCorpus and Wikipedia; Figure 9 reports training objective values.
B.5 Proof of Lemma 12: General Unbiased Rounding
This proof analyzes unbiased rounding coordinatewise through scalar second-moment and variance bounds. It contrasts the resulting parameter with bounds for biased rounding-related classes.
- Unbiasedness: The unbiasedness proof reduces coordinatewise rounding compression to scalar inputs x = t > 0.
- Second-moment bound: The proof computes a second-moment bound for the scalar rounding variable and transfers it to the compressor.
- Variance analysis: The variance maximum occurs at the harmonic mean of adjacent quantization levels, which lies between those levels.
- Parameter bound: The resulting parameter ζ is derived for general unbiased rounding.
- Norm control: Norm inequalities involving p and r = min(p, 2) are used to bound the compressor's second moment.
B.8 Proof of Lemma 16: Top-k Combined with Exponential Dithering
This proof uses the unbiasedness and second-moment properties of exponential dithering to derive parameters for the Top-k combined compressor. It then applies the resulting bound to the B3 class.
- Dithering properties: The proof begins from the unbiasedness of the general dithering operator C_dith.
- Dithering properties: A lemma on exponential dithering is used to derive the relevant second-moment bound.
- Parameter identification: The compressor parameters satisfy β = ζb and γ = k under the stated derivations.
- Parameter identification: The derivations combine the preceding bounds to establish the required expectation inequality.
- B3 characterization: Applying Theorem 6 yields δ = β for the B3(δ) characterization.
C.1 Analysis for C ∈B1(α, β)
The analysis establishes convergence bounds for compressed gradient descent with compressors in B1(α, β), using smoothness, strong convexity, and a stepsize restriction. Equivalent proof routes yield the same bound.
- Assumptions and stepsize: For C ∈ B1(α, β), the analysis assumes an L-smooth objective and restricts the stepsize to 0 ≤ η ≤ 2/(βL).
- Proof mechanism: An alternative derivation leads to the same bound as the primary proof approach.
- Proof mechanism: The proof combines the B1 compressor lemma with a strong-convexity inequality involving f(x_k) − f(x⋆).
C.3 Analysis for C ∈B3(δ)
The analysis establishes a smoothness-based lemma for compressors in B3(δ), then combines it with strong convexity under a stepsize restriction.
- ηL ≤ 1 completes the smoothness-based lemma for C ∈ B3(δ).
- The proof applies the lemma with x = xk and g = ∇f(xk) after invoking strong convexity.
Appendix D. Proofs for Section 4
The appendix derives distributional identities and variance comparisons for coordinate compressors, then develops auxiliary lemmas for distributed SGD analysis under smoothness, convexity, and stepsize conditions.
- Distributional analysis: Top-k has roughly (1 − k/d)^2 times less variance than Rand-k on average under the uniform distribution.
- Distributional analysis: The exponential-distribution analysis computes the expected saving using the mean and variance of the standard exponential distribution.
- Distributional analysis: The transformed variables y1, …, yd are independent and follow the standard exponential distribution.
- Distributed SGD: The distributed-SGD analysis assumes each fi is L-smooth and μ-strongly convex, implying the aggregate f has both properties.
- Distributed SGD: The auxiliary lemmas impose upper bounds on ηk and conditions on the squared-stepsize sequence for subsequent convergence analysis.
Proof
The proof of Theorem 21 combines a distributed-SGD recurrence with weighted-sum lemmas, using different stepsize schedules and a bound involving δ, B, and L.
- The analysis uses weighted summation and telescoping identities to derive the theorem's bound.
- The proof treats decreasing, constant, and 2δ-slow-decreasing stepsize regimes through the cited auxiliary lemmas.
- Theorem 21 applies Lemma 27 because 1/[14(2δ+B)L] ≤ 1/[4L(1+2B/n)].
- ηk = 4/[μ(κ + k)] satisfies the required stepsize bound after choosing κ = 1 + μ/[56(2δ+B)L].
- The proof uses Lemmas 29, 30, and 31 to handle three stepsize cases.