On Biased Compression for Distributed Learning

Aleksandr BeznosikovSamuel HorváthPeter RichtárikMher Safaryan

article2023JMLR231 citations

Establishes the first theoretical framework proving linear convergence for biased gradient compression operators in single-node and distributed optimization, showing both theoretically and empirically why biased methods like Top- $k$ sparsification consistently outperform unbiased alternatives when combined with error feedback.

Listen

Distributed machine learning has become essential for training modern large-scale neural networks across central clusters and decentralized edge devices. In these distributed setups, exchanging full model updates between worker nodes and central servers creates a massive communication bottleneck that slows training timelines and consumes expensive network bandwidth. While communication compression reduces the volume of transmitted data, practitioners frequently rely on biased compression methods—such as greedy coordinate selection—which demonstrate superior empirical performance compared to unbiased alternatives. However, biased compression historically lacked rigorous theoretical foundations, and naive implementations across multiple workers frequently fail to converge or diverge entirely.

The main objective of the article is to establish a comprehensive theoretical and algorithmic foundation for biased compression operators in both single-node and multi-node distributed optimization. Specifically, the article formalizes mathematical classifications for biased compressors, proves their convergence properties, explains why biased operators systematically outperform unbiased ones, and provides algorithmic solutions that guarantee convergence across distributed networks.

To achieve this, the article introduces three parametric classes of biased compression operators and mathematically establishes their equivalence, scaling, and composition properties. The authors then analyze the convergence rates of compressed gradient descent on smooth, strongly convex objectives. To explain empirical advantages, the article performs analytical and numerical evaluations comparing biased greedy sparsification against unbiased random sparsification under synthetic and empirical gradient distributions. Finally, the authors construct explicit mathematical counterexamples showing how standard distributed gradient descent fails with biased compressors, and subsequently analyze a distributed stochastic gradient descent framework equipped with an error-feedback memory mechanism across various stepsize and weighting schedules, validating the results on deep learning vision architectures and large-scale language models.

The investigation yields several critical findings. First, when biased compression is applied naively to distributed gradient descent without error correction, the algorithm can diverge exponentially fast or stall completely due to accumulated local drift. Second, implementing an error-feedback mechanism fully resolves this failure, delivering the first proven linear convergence rates for distributed stochastic gradient descent with biased compression under smooth and strongly convex conditions when full local gradients and over-parameterized models are used. Third, theoretical and empirical analyses reveal that greedy biased compressors capture three to forty times more gradient energy than unbiased random compressors, achieving exponentially lower variance for a given communication budget. Fourth, combining greedy selection with natural dithering creates an exceptionally effective hybrid compression operator that achieves the lowest compression error parameter across evaluated methods.

These findings have direct operational implications for high-performance computing and federated learning infrastructures. They prove that engineering teams do not need to accept the higher variance and slower convergence of unbiased compression merely for theoretical safety. By pairing biased compressors with error feedback, distributed training pipelines can drastically cut communication volume and round durations without sacrificing model quality or training stability. In transformer pretraining experiments, this strategy reduced communication round times from approximately 9.6 seconds to roughly 1.0 second per round with negligible impact on downstream benchmark accuracy, offering significant reductions in cloud compute and energy costs.

Organizations training distributed models should adopt biased compression schemes paired strictly with error-feedback mechanisms rather than uncompressed or pure unbiased communication baselines. For bandwidth-constrained networks, practitioners should deploy hybrid operators that combine greedy coordinate selection with natural dithering, tuning the retention parameter to match available network capacity. Future engineering efforts should explore deploying these error-compensated techniques across heterogeneous edge topologies and non-convex training workloads, validating performance on emerging model architectures.

The theoretical guarantees presented in the article are derived primarily under assumptions of smoothness and strong convexity, with stochastic gradient errors bounded by variance conditions. While empirical validations on deep convolutional networks and transformer language models confirm these benefits in non-convex settings, practitioners should exercise measured caution when applying these methods to highly non-convex or unstable loss landscapes without preliminary tuning. Overall confidence in the fundamental conclusions remains high due to the alignment between formal proofs, exact counterexamples, and consistent multi-model experimental results.

Institute of Science and Technology Austria King Abdullah University of Science and Technology Mohamed bin Zayed University of Artificial Intelligence Moscow Institute of Physics and Technology Skolkovo Institute of Science and Technology biased compression distributed learning gradient compression

arXiv: 2002.12410

Paper: QSGD: Communication-Efficient SGD via Gradient Quantization and Encoding, Dan Alistarh et al. (2016). This paper establishes foundational theoretical convergence guarantees for gradient quantization in distributed SGD, providing the primary unbiased compression baseline against which biased compressors are analyzed.
Paper: signSGD: compressed optimisation for non-convex problems, Jeremy Bernstein et al. (2018). This work introduces sign-based distributed gradient compression, providing a prominent empirical example of a biased compression operator whose theoretical convergence properties motivate the source paper.
Paper: Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training, Yujun Lin et al. (2018). This study demonstrates practical high-ratio gradient sparsification and error accumulation mechanisms in distributed deep learning, establishing the empirical utility of biased compression with error compensation.
Paper: Federated Learning: Strategies for Improving Communication Efficiency, Jakub Konečný et al. (2016). This paper introduces fundamental sketching and update-compression techniques to reduce uplink bandwidth in distributed and federated optimization.

No sufficiently relevant recommendations were found.

Cover for On Biased Compression for Distributed Learning

Abstract

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 (δL exp [− μK / δL] + (C+δD) / (Kμ)), where δ ≥ 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

Keywords

biased compression distributed learning gradient compression communication compression unbiased compression operators biased random sparsification operator stochastic gradient descent gradient quantization convex optimization

1. Introduction
1.1 Distributed optimization
1.2 Contributions
1.3 Related work
1.4 Basic notation and definitions
2. Biased Compressors
2.1 Three classes of biased compressors
2.2 Examples of biased compressors: old and new
3. Gradient Descent with Biased Compression
3.1 Complexity theory
3.2 B3 and B2 are better than B1
4. Superiority of Biased Compressors Under Statistical Assumptions
4.1 Topk vs Randk
4.2 New compressor: Topk combined with dithering
5. Distributed Setting
5.1 Distributed CGD with unbiased compressors
5.2 Failure of DCGD with biased compressors
5.3 Error Feedback
5.4 Complexity theory
6. Experiments
6.1 Lower empirical variance induced by biased compressors during deep network training
6.2 Error-feedback is needed in distributed training with biased compression
6.3 Topk mixed with natural dithering saves in communication significantly
6.4 Theoretical behavior predicts the actual performance in practice
6.5 Transformer training
Appendix
Appendix A. Basic Facts and Inequalities
A.1 Strong convexity
A.2 Smoothness
A.3 Useful inequalities
A.4 Facts from order statistics
Appendix B. Proofs for Section 2.2
B.1 Proof of Lemma 8: Unbiased Random Sparsification
B.2 Proof of Lemma 9: Biased Random Sparsification
B.3 Proof of Lemma 10: Adaptive Random Sparsification
B.4 Proof of Lemma 11: Topk sparsification
B.5 Proof of Lemma 12: General Unbiased Rounding
B.6 Proof of Lemma 13: General Biased Rounding
B.7 Proof of Lemma 15: General Exponential Dithering
B.8 Proof of Lemma 16: Topk Combined with Exponential Dithering
Appendix C. Proofs for Section 3
C.1 Analysis for C ∈ B1 (α, β)
C.2 Analysis for C ∈ B2 (γ, β)
C.3 Analysis for C ∈ B3 (δ)
Appendix D. Proofs for Section 4
D.1 Proof of Theorem 21 (Convergence guarantees for Algorithm 1)
References

Knowls

Knowl 1 — Distributed SGD with Biased Compression and Error Feedback
algorithm
The distributed SGD algorithm with error feedback resolves convergence failures of naive distributed compressed gradient descent when using biased compression operators $\mathcal{C}_i^k \in \mathbb{B}^3(\delta)$ .
Input: Number of workers $n$ , total communication rounds $K$ , stepsize schedule $\{\eta^k\}_{k=0}^K$ , averaging weights $\{w^k\}_{k=0}^K$ , local biased compression operators $\{\mathcal{C}_i^k\}_{i=1}^n \subset \mathbb{B}^3(\delta)$ , initial model vector $x^0 \in \mathbb{R}^d$
Initialization: Set local error memory buffers $e_i^0 = 0 \in \mathbb{R}^d$ for all $i \in \{1, \dots, n\}$
for $k = 0, 1, \dots, K$ do
    Server broadcasts current iterate $x^k$ to all $n$ workers
    for each worker $i \in \{1, \dots, n\}$ in parallel do
        Compute stochastic gradient $g_i^k = \nabla f_i(x^k) + \xi_i^k$
        Compute compressed message $\tilde{g}_i^k = \mathcal{C}_i^k(e_i^k + \eta^k g_i^k)$
        Update local error buffer $e_i^{k+1} = e_i^k + \eta^k g_i^k - \tilde{g}_i^k$
        Transmit $\tilde{g}_i^k$ to the server
    Server aggregates received messages: $x^{k+1} = x^k - \frac{1}{n} \sum_{i=1}^n \tilde{g}_i^k$
Compute $W^K = \sum_{k=0}^K w^k$
Output: Ergodic average iterate $\bar{x}^K = \frac{1}{W^K} \sum_{k=0}^K w^k x^k$
Each worker $i$ stores an error memory $e_i^k \in \mathbb{R}^d$ that tracks accumulated compression residuals, ensuring that discarded gradient information is fed back into subsequent communication rounds rather than lost.
Knowl 2 — Convergence Guarantees for Distributed SGD with Biased Compression and Error Feedback
theoretical result
Consider the distributed optimization problem $\min_{x \in \mathbb{R}^d} f(x) := \frac{1}{n} \sum_{i=1}^n f_i(x)$ , where each local objective $f_i: \mathbb{R}^d \to \mathbb{R}$ is $L$ -smooth and $\mu$ -strongly convex with optimal value $f^* = f(x^*)$ . Assume the stochastic gradient noise $\xi_i^k$ satisfies $\mathbb{E}[\xi_i^k] = 0$ and $\mathbb{E}[\|\xi_i^k\|_2^2] \le B \|\nabla f_i(x^k)\|_2^2 + C$ for constants $B, C \ge 0$ , and define the gradient variance at the optimum by $D := \frac{1}{n} \sum_{i=1}^n \|\nabla f_i(x^*)\|_2^2$ . Let all workers employ compression operators $\mathcal{C}_i^k \in \mathbb{B}^3(\delta)$ with $\delta \ge 1$ .

Define the constants:

$A_1 := \frac{L^2(2\delta+B)^2}{\mu} \|x^0 - x^*\|_2^2, \qquad A_2 := \frac{C(1 + 1/n) + D(2B/n + 3\delta)}{\mu}$

$A_3 := L(2\delta + B)\|x^0 - x^*\|_2^2, \qquad A_4 := \frac{28L(2\delta+B)}{\mu}$

$A_5 := \sqrt{C(1 + 1/n) + D(2B/n + 3\delta)} \|x^0 - x^*\|_2, \qquad \kappa := \frac{56(2\delta+B)L}{\mu}$

The ergodic iterate $\bar{x}^K = \frac{1}{\sum_{k=0}^K w^k} \sum_{k=0}^K w^k x^k$ produced by Distributed SGD with Error Feedback satisfies the following bounds across three stepsize and weighting schedules:
1. Harmonic stepsizes and linear weights: Setting $\eta^k = \frac{4}{\mu(\kappa+k)}$ and $w^k = \kappa + k$ yields
$\mathbb{E}[f(\bar{x}^K)] - f^* = \mathcal{O}\left( \frac{A_1}{K^2} + \frac{A_2}{K} \right).$
1. Constant stepsize and exponential weights: Setting $\eta^k = \eta \le \frac{1}{14(2\delta+B)L}$ and $w^k = (1 - \mu\eta/2)^{-(k+1)}$ yields
$\mathbb{E}[f(\bar{x}^K)] - f^* = \tilde{\mathcal{O}}\left( A_3 \exp\left(-\frac{K}{A_4}\right) + \frac{A_2}{K} \right).$

In the deterministic, over-parameterized regime where $C = 0$ (full gradients) and $D = 0$ (all $\nabla f_i(x^*) = 0$ ), this achieves a linear convergence rate of $\mathcal{O}\left(\delta \frac{L}{\mu} \log \frac{1}{\epsilon}\right)$ .
1. Constant stepsize and uniform weights: Setting $\eta^k = \eta \le \frac{1}{14(2\delta+B)L}$ and $w^k = 1$ yields
$\mathbb{E}[f(\bar{x}^K)] - f^* = \mathcal{O}\left( \frac{A_3}{K} + \frac{A_5}{\sqrt{K}} \right).$
Knowl 3 — Divergence and Failure of Distributed Gradient Descent with Biased Compression
theoretical result
A naive extension of compressed gradient descent to distributed optimization without an error feedback mechanism—defined by $x^{k+1} = x^k - \frac{\eta}{n} \sum_{i=1}^n \mathcal{C}_i(\nabla f_i(x^k))$ —can diverge exponentially fast or stall indefinitely when $\mathcal{C}_i$ are biased compression operators.
1. Exponential Divergence with Top- $1$ Sparsification: Consider $n = d = 3$ and quadratic loss functions $f_1(x) = \langle a, x \rangle^2 + \frac{1}{4}\|x\|_2^2$ , $f_2(x) = \langle b, x \rangle^2 + \frac{1}{4}\|x\|_2^2$ , and $f_3(x) = \langle c, x \rangle^2 + \frac{1}{4}\|x\|_2^2$ , where $a = (-3,2,2)$ , $b = (2,-3,2)$ , and $c = (2,2,-3)$ . Starting at $x^0 = (t, t, t)$ for any $t > 0$ , applying the deterministic Top- $1$ compressor yields
$x^k = \left(1 + \frac{11\eta}{6}\right)^k x^0,$

which diverges exponentially to $+\infty$ for any stepsize $\eta > 0$ . This generalises to Top- $d_1$ sparsification whenever $d_1 < d/2$ .
1. Stalling at Suboptimal Points: Let $\mathcal{C}: \mathbb{R}^d \to \mathbb{R}^d$ be any deterministic mapping for which there exist vectors $v_1, \dots, v_m \in \mathbb{R}^d$ such that $\sum_{i=1}^m v_i \ne 0$ but $\sum_{i=1}^m \mathcal{C}(v_i) = 0$ . For the strongly convex objectives $f_i(x) = \langle v_i, x \rangle + \frac{1}{2}\|x\|_2^2$ across $m$ workers, the true unique minimizer is $x^* = -\frac{1}{m}\sum_{i=1}^m v_i \ne 0$ . Initialized at $x^0 = 0$ , naive distributed compressed gradient descent produces $x^k = x^0 = 0$ for all $k \ge 1$ , remaining permanently stuck away from $x^*$ .
Knowl 4 — Three Parametric Classes of Biased Compression Operators and Their Equivalence
definition
Let $\mathcal{C}: \mathbb{R}^d \to \mathbb{R}^d$ be a (possibly randomized) compression operator. Three parametric classes characterize biased compressors:
1. Class $\mathbb{B}^1(\alpha, \beta)$ : For $\alpha, \beta > 0$ , $\mathcal{C} \in \mathbb{B}^1(\alpha, \beta)$ if for all $x \in \mathbb{R}^d$ ,
$\alpha \|x\|_2^2 \le \mathbb{E}\left[\|\mathcal{C}(x)\|_2^2\right] \le \beta \langle \mathbb{E}[\mathcal{C}(x)], x \rangle.$

This implies $\beta^2 \ge \alpha$ and $\mathbb{E}[\|\mathcal{C}(x)\|_2^2] \le \beta^2 \|x\|_2^2$ .
1. Class $\mathbb{B}^2(\gamma, \beta)$ : For $\gamma, \beta > 0$ , $\mathcal{C} \in \mathbb{B}^2(\gamma, \beta)$ if for all $x \in \mathbb{R}^d$ ,
$\max\left\{ \gamma \|x\|_2^2, \frac{1}{\beta} \mathbb{E}\left[\|\mathcal{C}(x)\|_2^2\right] \right\} \le \langle \mathbb{E}[\mathcal{C}(x)], x \rangle.$

This implies $\beta \ge \gamma$ .
1. Class $\mathbb{B}^3(\delta)$ : For $\delta \ge 1$ , $\mathcal{C} \in \mathbb{B}^3(\delta)$ if for all $x \in \mathbb{R}^d$ ,
$\mathbb{E}\left[\|\mathcal{C}(x) - x\|_2^2\right] \le \left(1 - \frac{1}{\delta}\right) \|x\|_2^2.$

Equivalence relations under scaling (with parameter $\lambda > 0$ ):
- If $\mathcal{C} \in \mathbb{B}^1(\alpha, \beta)$ , then $\lambda \mathcal{C} \in \mathbb{B}^1(\lambda^2\alpha, \lambda\beta)$ , $\mathcal{C} \in \mathbb{B}^2(\alpha/\beta, \beta)$ , and $\frac{1}{\beta}\mathcal{C} \in \mathbb{B}^3(\beta^2/\alpha)$ .
- If $\mathcal{C} \in \mathbb{B}^2(\gamma, \beta)$ , then $\lambda \mathcal{C} \in \mathbb{B}^2(\lambda\gamma, \lambda\beta)$ , $\mathcal{C} \in \mathbb{B}^1(\gamma^2, \beta)$ , and $\frac{1}{\beta}\mathcal{C} \in \mathbb{B}^3(\beta/\gamma)$ .
- If $\mathcal{C} \in \mathbb{B}^3(\delta)$ , then $\mathcal{C} \in \mathbb{B}^2\left(\frac{1}{2\delta}, 2\right) \subseteq \mathbb{B}^1\left(\frac{1}{4\delta^2}, 2\right)$ .
While the classes contain the same operators up to rescaling, parameterizing via $\mathbb{B}^2$ or $\mathbb{B}^3$ yields strictly tighter convergence bounds for compressed gradient descent than $\mathbb{B}^1$ (by a factor of $\beta/\gamma \ge 1$ or $16\delta$ , respectively).
Knowl 5 — Linear Convergence of Compressed Gradient Descent in Single-Node Optimization
theoretical result
Let $f: \mathbb{R}^d \to \mathbb{R}$ be $L$ -smooth and $\mu$ -strongly convex with minimizer $x^*$ . Consider single-node Compressed Gradient Descent (CGD):

$x^{k+1} = x^k - \eta \mathcal{C}^k(\nabla f(x^k)),$

where $\mathcal{C}^k$ is a compression operator and $\mathcal{E}_k := \mathbb{E}[f(x^k)] - f(x^*)$ . Under the three biased compressor classes:
1. For $\mathcal{C} \in \mathbb{B}^1(\alpha, \beta)$ : If $0 \le \eta \le \frac{2}{\beta L}$ , then $\mathcal{E}_k \le \left(1 - \frac{\alpha}{\beta} \eta \mu (2 - \eta \beta L)\right) \mathcal{E}_{k-1}$ . Setting $\eta = \frac{1}{\beta L}$ gives
$\mathcal{E}_k \le \left(1 - \frac{\alpha}{\beta^2}\frac{\mu}{L}\right)^k \mathcal{E}_0, \qquad \text{iteration complexity: } \mathcal{O}\left(\frac{\beta^2}{\alpha} \frac{L}{\mu} \log \frac{1}{\epsilon}\right).$
1. For $\mathcal{C} \in \mathbb{B}^2(\gamma, \beta)$ : If $0 \le \eta \le \frac{2}{\beta L}$ , then $\mathcal{E}_k \le \left(1 - \gamma \eta \mu (2 - \eta \beta L)\right) \mathcal{E}_{k-1}$ . Setting $\eta = \frac{1}{\beta L}$ gives
$\mathcal{E}_k \le \left(1 - \frac{\gamma}{\beta}\frac{\mu}{L}\right)^k \mathcal{E}_0, \qquad \text{iteration complexity: } \mathcal{O}\left(\frac{\beta}{\gamma} \frac{L}{\mu} \log \frac{1}{\epsilon}\right).$
1. For $\mathcal{C} \in \mathbb{B}^3(\delta)$ : If $0 \le \eta \le \frac{1}{L}$ , then $\mathcal{E}_k \le \left(1 - \frac{1}{\delta}\eta\mu\right) \mathcal{E}_{k-1}$ . Setting $\eta = \frac{1}{L}$ gives
$\mathcal{E}_k \le \left(1 - \frac{1}{\delta}\frac{\mu}{L}\right)^k \mathcal{E}_0, \qquad \text{iteration complexity: } \mathcal{O}\left(\delta \frac{L}{\mu} \log \frac{1}{\epsilon}\right).$

For the uncompressed identity operator $\mathcal{C}(x) = x$ , $\alpha = \beta = \gamma = \delta = 1$ , recovering the standard gradient descent rate $\mathcal{O}(\frac{L}{\mu} \log \frac{1}{\epsilon})$ .
Knowl 6 — Error Variance and Energy Savings Advantage of Top-k over Rand-k Sparsifiers
theoretical result
Let $x \in \mathbb{R}^d$ be a vector with i.i.d. coordinates. Define the unbiased Rand- $k$ sparsifier by $\mathcal{C}_{rnd}^k(x) = \frac{d}{k} \sum_{i \in S} x_i e_i$ (where $S \subset [d]$ is a uniform random subset of size $k$ ) and the biased Top- $k$ sparsifier by $\mathcal{C}_{top}^k(x) = \sum_{i=d-k+1}^d x_{(i)} e_{(i)}$ (retaining the $k$ largest coordinates by magnitude $|x_{(1)}| \le \dots \le |x_{(d)}|$ ).

The error variances are $\omega_{rnd}^k(x) := \mathbb{E}_S[\|\frac{k}{d}\mathcal{C}_{rnd}^k(x) - x\|_2^2] = (1 - k/d)\|x\|_2^2$ and $\omega_{top}^k(x) := \|\mathcal{C}_{top}^k(x) - x\|_2^2 = \sum_{i=1}^{d-k} x_{(i)}^2$ . The energy savings are $s_{rnd}^k(x) := \|x\|_2^2 - \omega_{rnd}^k(x) = \frac{k}{d}\|x\|_2^2$ and $s_{top}^k(x) := \|x\|_2^2 - \omega_{top}^k(x) = \sum_{i=d-k+1}^d x_{(i)}^2$ .
1. Uniform Distribution over $[0, 1]$ :
$\frac{\mathbb{E}[\omega_{top}^k(x)]}{\mathbb{E}[\omega_{rnd}^k(x)]} = \left(1 - \frac{k}{d+1}\right)\left(1 - \frac{k}{d+2}\right), \qquad \frac{\mathbb{E}[s_{top}^1(x)]}{\mathbb{E}[s_{rnd}^1(x)]} = \frac{3d}{d+2}$

Top- $k$ achieves an expected error variance roughly $(1 - k/d)^2$ times smaller than Rand- $k$ .
1. Standard Exponential Distribution ( $ext{PDF } \phi(t) = e^{-t}, t \ge 0$ ):
$\frac{\mathbb{E}[s_{top}^1(x)]}{\mathbb{E}[s_{rnd}^1(x)]} = \frac{1}{2} \sum_{i=1}^d \frac{1}{i^2} + \frac{1}{2} \left(\sum_{i=1}^d \frac{1}{i}\right)^2 = \mathcal{O}(\log^2 d)$

Top- $1$ preserves $\mathcal{O}(\log^2 d)$ times more energy than Rand- $1$ .
1. Gaussian Distribution $\mathcal{N}(\mu, \sigma^2)$ : For $k=3$ and $k=5$ across dimensions $d = 10^2$ to $10^5$ , Top- $k$ saves $3\times$ to $40\times$ more information in expectation than Rand- $k$ . Under a fixed bit budget $b$ , greedy Top- $k$ achieves exponentially lower normalized variance (empirical scaling $\approx 0.86^{b/d}$ ) compared to the linear decay ( $1 - \frac{b/d}{32}$ ) of Rand- $k$ .
Knowl 7 — Top-k Sparsification Combined with Exponential Dithering
model/method
The composite compression operator $\mathcal{C}(x) := \mathcal{C}_{dith}(\mathcal{C}_{top}(x))$ combines greedy Top- $k$ sparsification with general exponential dithering:
1. Top- $k$ Sparsification $\mathcal{C}_{top}(x)$ : Selects the $k$ components of $x \in \mathbb{R}^d$ having the largest absolute magnitudes, setting all other coordinates to 0.
2. General Exponential Dithering $\mathcal{C}_{dith}(v)$ : For base $b > 1$ , $s$ exponential levels $0 < b^{1-s} < b^{2-s} < \dots < b^{-1} < 1$ , and norm parameter $p \ge 1$ , the operator scales $v$ as
$\mathcal{C}_{dith}(v) := \|v\|_p \operatorname{sign}(v) \odot \xi\left( \frac{|v|}{\|v\|_p} \right),$

where $\xi(t)$ for $t \in [b^{-u-1}, b^{-u}]$ randomly rounds $t$ to $b^{-u-1}$ or $b^{-u}$ with probabilities proportional to $b^{-u} - t$ and $t - b^{-u-1}$ , respectively. $\mathcal{C}_{dith} \in \mathbb{U}(\zeta_b)$ where

$\zeta_b = \frac{1}{4}\left(b + \frac{1}{b} + 2\right) + d^{1/r} b^{1-s} \min\left(1, d^{1/r} b^{1-s}\right), \qquad r = \min(p, 2).$

The resulting composite operator $\mathcal{C}$ belongs to the biased classes $\mathbb{B}^1(k/d, \zeta_b)$ , $\mathbb{B}^2(k/d, \zeta_b)$ , and $\mathbb{B}^3\left(\frac{d}{k}\zeta_b\right)$ . When configured with natural dithering ( $b = 2$ ), it belongs to $\mathbb{B}^3\left(\frac{9d}{8k}\right)$ and attains the lowest compression variance parameter $\delta$ among known operators for any communication budget.

Knowl 8 — Theoretical Parameters of Standard and Novel Compression Operators

data/table

The following table lists compression operators $\mathcal{C}: \mathbb{R}^d \to \mathbb{R}^d$ , their unbiasedness status, and their respective membership parameters in the classes $\mathbb{B}^1(\alpha, \beta)$ , $\mathbb{B}^2(\gamma, \beta)$ , $\mathbb{B}^3(\delta)$ , and $\mathbb{U}(\zeta)$ :

Compression Operator $\mathcal{C}$	Unbiased?	$\alpha$	$\beta$	$\gamma$	$\delta$	$\zeta$
Unbiased random sparsification (Rand- $k$ )	✓	–	–	–	–	$d/k$
Biased random sparsification ( $q := \min_i p_i$ )	✗	$q$	1	$q$	$1/q$	–
Adaptive random sparsification ( $p_i = \|x_i\|/\\|x\\|_1$ )	✗	$1/d$	1	$1/d$	$d$	–
Top- $k$ sparsification	✗	$k/d$	1	$k/d$	$d/k$	–
General unbiased rounding	✓	–	–	–	–	$\frac{1}{4}\sup_k \left(\frac{a_k}{a_{k+1}} + \frac{a_{k+1}}{a_k} + 2\right)$
Unbiased exponential rounding ( $a_k = b^k$ )	✓	–	–	–	–	$\frac{1}{4}(b + 1/b + 2)$
Biased exponential rounding ( $a_k = b^k$ )	✗	$\left(\frac{2}{b+1}\right)^2$	$\frac{2b}{b+1}$	$\frac{2}{b+1}$	$\frac{(b+1)^2}{4b}$	–
Natural compression ( $b = 2$ )	✓	–	–	–	–	$9/8$
General exponential dithering	✓	–	–	–	–	$\zeta_b$
Natural dithering ( $b = 2$ )	✓	–	–	–	–	$\zeta_2$
Top- $k$ + exponential dithering	✗	$k/d$	$\zeta_b$	$k/d$	$\frac{d}{k}\zeta_b$	–

Here, $d$ is dimension, $k \in [d]$ is sparsity, $b > 1$ is the geometric quantization base, and $\zeta_b = \frac{1}{4}(b + 1/b + 2) + d^{1/r} b^{1-s} \min(1, d^{1/r} b^{1-s})$ with $r = \min(p, 2)$ for $s$ exponential levels.

Knowl 9 — Scaling Transformation from Unbiased to Biased Compressors
theoretical result
Let $\mathcal{C} \in \mathbb{U}(\zeta)$ be an unbiased compression operator with second moment bounded by $\mathbb{E}[\|\mathcal{C}(x)\|_2^2] \le \zeta \|x\|_2^2$ for all $x \in \mathbb{R}^d$ , where $\zeta \ge 1$ . For any positive scaling factor $\lambda > 0$ , the scaled operator $\lambda \mathcal{C}$ belongs to all three biased compressor classes with the following parameters:
1. Class $\mathbb{B}^1$ : For any $\lambda > 0$ ,
$\lambda \mathcal{C} \in \mathbb{B}^1\left(\lambda^2, \lambda \zeta\right).$
1. Class $\mathbb{B}^2$ : For any $\lambda > 0$ ,
$\lambda \mathcal{C} \in \mathbb{B}^2\left(\lambda, \lambda \zeta\right).$
1. Class $\mathbb{B}^3$ : For any $\lambda \in \left(0, \frac{2}{\zeta}\right)$ ,
$\lambda \mathcal{C} \in \mathbb{B}^3\left(\frac{1}{\lambda(2 - \zeta \lambda)}\right).$

Choosing $\lambda = 1/\zeta$ optimizes the parameter for $\mathbb{B}^3$ , yielding $\frac{1}{\zeta}\mathcal{C} \in \mathbb{B}^3(\zeta)$ .

Knowl 10 — Empirical Efficiency of Biased Compression in Distributed Transformer Training

empirical result

In distributed training of the ALBERT-large transformer model (18 million parameters) on Bookcorpus and Wikipedia datasets using the LAMB optimizer across 10 Tesla T4 GPUs, biased compression combined with error feedback demonstrates superior communication efficiency and downstream task accuracy compared to unbiased compressors:

Setup	Avg time (s)	CoLA	MNLI	MRPC	QNLI	QQP	RTE	SST2	STS-B
Without compression	9.62 $\pm$ 0.03	46.2	81.1	82.5	87.9	88.0	66.3	85.1	88.0
Natural compression	4.05 $\pm$ 0.05	48.3	81.0	87.5	87.8	84.4	63.2	87.8	86.9
Power compression (rank $r=8$ )	1.04 $\pm$ 0.04	42.4	80.3	85.1	88.2	85.3	46.3	88.0	87.4

Biased Power compression ( $r=8$ ) reduces communication time per round by approximately $9.25\times$ compared to uncompressed training and $3.89\times$ compared to unbiased natural compression ( $4\times$ factor reduction), while retaining competitive downstream evaluation accuracy across GLUE benchmark tasks (e.g., 88.2 on QNLI vs. 87.9 uncompressed, and 88.0 on SST2 vs. 85.1 uncompressed).

Coverage note — None omitted; all primary contributions—including the three compressor classes, single-node and distributed convergence theorems, counterexamples, statistical comparisons, operator table, composite dithering compressor, and empirical transformer benchmark results—are captured.

References

1.Saurabh Agarwal, Hongyi Wang, Kangwook Lee, Shivaram Venkataraman, and Dimitris Papailiopoulos. Accordion: Adaptive gradient communication via critical learning regime identification. arXiv preprint arXiv:2010.16248, 2020.
2.Ahmad Ajalloeian and Sebastian U. Stich. On the Convergence of SGD with Biased Gradients. arXiv preprint arXiv:2008.00051, 2021.
3.Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. QSGD: Communication-efficient sgd via gradient quantization and encoding. In Advances in Neural Information Processing Systems, pages 1709–1720, 2017.
4.Dan Alistarh, Torsten Hoefler, Mikael Johansson, Sarit Khirirat, Nikola Konstantinov, and Cédric Renggli. The convergence of sparsified gradient methods. In Advances in Neural Information Processing Systems, pages 5977–5987, 2018.
5.Zeyuan Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 1200–1205. ACM, 2017.
6.Barry C. Arnold, N. Balakrishnan, and H. N. Nagaraja. A First Course in order Statistics. John Wiley and Sons Inc., 1992.
7.Amir Beck and Marc Teboulle. A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM Journal on Imaging Sciences, 2(1):183–202, 2009.
8.Tom B. Brown et al. Language models are few-shot learners. arXiv preprint arXiv:2005.14165, 2020.
9.Jean-Baptiste Cordonnier. Convex optimization using sparsified stochastic gradient descent with memory. Technical report, École Polytechnique Fédérale de Lausanne, 2018.
10.Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805, 2018.
11.Ilyas Fatkhullin, Igor Sokolov, Eduard Gorbunov, Zhize Li, and Peter Richtárik. EF21 with Bells & Whistles: Practical Algorithmic Extensions of Modern Error Feedback. arXiv preprint arXiv:2110.03294, 2021.
12.Eduard Gorbunov, Filip Hanzely, and Peter Richtárik. A unified theory of SGD: Variance reduction, sampling, quantization and coordinate descent. In The 23rd International Conference on Artificial Intelligence and Statistics, 2020a.
13.Eduard Gorbunov, Dmitry Kovalev, Dmitry Makarenko, and Peter Richtárik. Linearly converging error compensated SGD. In 34th Conference on Neural Information Processing Systems, 2020b.
14.Samuel Horváth and Peter Richtárik. A better alternative to error feedback for communication-efficient distributed learning. In International Conference on Learning Representations, 2021. URL https://openreview.net/forum?id=vYVI1CHPaQg.
15.Samuel Horváth, Chen-Yu Ho, Ľudovít Horváth, Atal Narayan Sahu, Marco Canini, and Peter Richtárik. Natural compression for distributed deep learning. arXiv preprint arXiv:1905.10988, 2019a.
16.Samuel Horváth, Dmitry Kovalev, Konstantin Mishchenko, Sebastian Stich, and Peter Richtárik. Stochastic distributed learning with gradient quantization and variance reduction. arXiv preprint arXiv:1904.05115, 2019b.
17.Peter Kairouz and et al. Advances and open problems in federated learning. arXiv preprint arXiv:1912.04977, 2019.
18.Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank J. Reddi, Sebastian U. Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for on-device federated learning. ArXiv, abs/1910.06378, 2019a.
19.Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian U Stich, and Martin Jaggi. Error feedback fixes SignSGD and other gradient compression schemes. arXiv preprint arXiv:1901.09847, 2019b.
20.Ahmed Khaled, Konstantin Mishchenko, and Peter Richtárik. Tighter theory for local SGD on identical and heterogeneous data. In The 23rd International Conference on Artificial Intelligence and Statistics (AISTATS 2020), 2020a.
21.Ahmed Khaled, Othmane Sebbouh, Nicolas Loizou, Robert M Gower, and Peter Richtárik. Unified analysis of stochastic gradient methods for composite convex and smooth optimization. arXiv preprint arXiv:2006.11573, 2020b.
22.Jakub Konečný, H. Brendan McMahan, Felix Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: strategies for improving communication efficiency. In NIPS Private Multi-Party Machine Learning Workshop, 2016.
23.Zhen-Zhong Lan, Mingda Chen, Sebastian Goodman, Kevin Gimpel, Piyush Sharma, and Radu Soricut. Albert: A lite bert for self-supervised learning of language representations. In International Conference on Learning Representations, 2020.
24.Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: challenges, methods, and future directions. arXiv preprint arXiv:1908.07873, 2019.
25.Zhize Li and Peter Richtárik. A unified analysis of stochastic gradient methods for nonconvex federated optimization. arXiv preprint arXiv:2006.07013, 2020.
26.Hyeontaek Lim, David G Andersen, and Michael Kaminsky. 3lc: Lightweight and effective traffic compression for distributed machine learning. arXiv preprint arXiv:1802.07389, 2018.
27.Yujun Lin, Song Han, Huizi Mao, Yu Wang, and William J. Dally. Deep gradient compression: Reducing the communication bandwidth for distributed training. CoRR, abs/1712.01887, 2017a. URL http://arxiv.org/abs/1712.01887.
28.Yujun Lin, Song Han, Huizi Mao, Yu Wang, and William J Dally. Deep gradient compression: Reducing the communication bandwidth for distributed training. arXiv preprint arXiv:1712.01887, 2017b.
29.Yujun Lin, Song Han, Huizi Mao, Yu Wang, and Bill Dally. Deep gradient compression: Reducing the communication bandwidth for distributed training. In ICLR 2018 - International Conference on Learning Representations, 2018.
30.H Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera y Arcas. Communication-efficient learning of deep networks from decentralized data. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS), 2017.
31.Konstantin Mishchenko, Eduard Gorbunov, Martin Takáč, and Peter Richtárik. Distributed learning with compressed gradient differences. arXiv preprint arXiv:1901.09269, 2019.
32.Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87. Springer Science & Business Media, 2013.
33.Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. dAlché Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 8024–8035. Curran Associates, Inc., 2019.
34.Peter Richtárik and Martin Takáč. Parallel coordinate descent methods for big data optimization. Mathematical Programming, 156(1-2):433–484, 2016.
35.Peter Richtárik, Igor Sokolov, and Ilyas Fatkhullin. EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback. In 35nd Conference on Neural Information Processing Systems, 2021.
36.Mher Safaryan and Peter Richtárik. Stochastic sign descent methods: New algorithms and better theory. In Proceedings of the 38th International Conference on Machine Learning (ICML), 2021.
37.Amedeo Sapio, Marco Canini, Chen-Yu Ho, Jacob Nelson, Panos Kalnis, Changhoon Kim, Arvind Krishnamurthy, Masoud Moshref, Dan R. K. Ports, and Peter Richtárik. Scaling distributed machine learning with in-network aggregation. arXiv preprint arXiv:1903.06701, 2019.
38.Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and application to data-parallel distributed training of speech dnns. In Interspeech 2014, September 2014.
39.Sebastian U. Stich and Sai Praneeth Karimireddy. The error-feedback framework: Better rates for SGD with delayed gradients and compressed communication. arXiv preprint arXiv:1909.05350, 2019.
40.Sebastian U Stich, Jean-Baptiste Cordonnier, and Martin Jaggi. Sparsified sgd with memory. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems 31, pages 4447–4458. Curran Associates, Inc., 2018. URL http://papers.nips.cc/paper/7697-sparsified-sgd-with-memory.pdf.
41.Haobo Sun, Yingxia Shao, Jiawei Jiang, Bin Cui, Kai Lei, Yu Xu, and Jiang Wang. Sparse gradient compression for distributed SGD. In Guoliang Li, Jun Yang, Joao Gama, Juggapong Natwichai, and Yongxin Tong, editors, Database Systems for Advanced Applications, pages 139–155, Cham, 2019. Springer International Publishing. ISBN 978-3-030-18579-4.
42.Sharan Vaswani, Francis Bach, and Mark Schmidt. Fast and faster convergence of SGD for over-parameterized models and an accelerated perceptron. In 22nd International Conference on Artificial Intelligence and Statistics, volume 89 of PMLR, pages 1195–1204, 2019.
43.Thijs Vogels, Sai Praneeth Karimireddy, and Martin Jaggi. PowerSGD: Practical low-rank gradient compression for distributed optimization. In Advances in Neural Information Processing Systems 32 (NeurIPS), 2019.
44.Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R Bowman. Glue: A multi-task benchmark and analysis platform for natural language understanding. arXiv preprint arXiv:1804.07461, 2018.
45.Wei Wen, Cong Xu, Feng Yan, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Terngrad: Ternary gradients to reduce communication in distributed deep learning. In Advances in Neural Information Processing Systems, pages 1509–1519, 2017.
46.Jiaxiang Wu, Weidong Huang, Junzhou Huang, and Tong Zhang. Error compensated quantized SGD and its applications to large-scale distributed optimization. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 5325–5333, Stockholmsmässan, Stockholm Sweden, 10–15 Jul 2018. PMLR.
47.Hantian Zhang, Jerry Li, Kaan Kara, Dan Alistarh, Ji Liu, and Ce Zhang. ZipML: Training linear models with end-to-end low precision, and a little bit of deep learning. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 4035–4043, International Convention Centre, Sydney, Australia, 06–11 Aug 2017. PMLR.
48.Shen-Yi Zhao, Yinpeng Xie, Hao Gao, and Wu-Jun Li. Global momentum compression for sparse communication in distributed SGD. arXiv preprint arXiv:1905.12948, 2019.
49.Yukun Zhu, Ryan Kiros, Rich Zemel, Ruslan Salakhutdinov, Raquel Urtasun, Antonio Torralba, and Sanja Fidler. Aligning books and movies: Towards story-like visual explanations by watching movies and reading books. In Proceedings of the IEEE international conference on computer vision, pages 19–27, 2015.

Citation

MLA

Beznosikov, A., et al. “On Biased Compression for Distributed Learning”. Journal of Machine Learning Research, vol. 24, no. 276, 2023, pp. 1–0, https://www.jmlr.org/papers/v24/21-1548.html.

APA

Beznosikov, A., Horváth, S., Richtárik, P., & Safaryan, M. (2023). On Biased Compression for Distributed Learning. Journal of Machine Learning Research, 24(276), 1–50. https://www.jmlr.org/papers/v24/21-1548.html

Chicago

Beznosikov, A., S. Horváth, P. Richtárik, and M. Safaryan. 2023. “On Biased Compression for Distributed Learning”. Journal of Machine Learning Research 24 (276): 1–50. https://www.jmlr.org/papers/v24/21-1548.html.

Harvard

Beznosikov, A. et al. (2023) “On Biased Compression for Distributed Learning”, Journal of Machine Learning Research, 24(276), pp. 1–50. Available at: https://www.jmlr.org/papers/v24/21-1548.html.

Vancouver

1. Beznosikov A, Horváth S, Richtárik P, Safaryan M (2023) On Biased Compression for Distributed Learning. Journal of Machine Learning Research 24:1–50

BibTeX

@article{JMLR:v24:21-1548,
  author  = {Aleksandr Beznosikov and Samuel HorvÃ¡th and Peter RichtÃ¡rik and Mher Safaryan},
  title   = {On Biased Compression for Distributed Learning},
  journal = {Journal of Machine Learning Research},
  year    = {2023},
  volume  = {24},
  number  = {276},
  pages   = {1--50},
  url     = {http://jmlr.org/papers/v24/21-1548.html}
}

Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

On Biased Compression for Distributed Learning

Abstract

Keywords

Table of Contents

Knowls

Knowl 1 — Distributed SGD with Biased Compression and Error Feedback

Knowl 2 — Convergence Guarantees for Distributed SGD with Biased Compression and Error Feedback

Knowl 3 — Divergence and Failure of Distributed Gradient Descent with Biased Compression

Knowl 4 — Three Parametric Classes of Biased Compression Operators and Their Equivalence

Knowl 5 — Linear Convergence of Compressed Gradient Descent in Single-Node Optimization

Knowl 6 — Error Variance and Energy Savings Advantage of Top-k over Rand-k Sparsifiers

Knowl 7 — Top-k Sparsification Combined with Exponential Dithering