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 is constrained by the communication cost of exchanging full-precision gradients. Qsparse-local-SGD combines sparsification, quantization, local computation, and error compensation, achieving vanilla distributed SGD’s convergence rate while substantially reducing transmitted bits.

  • Problem

    Exchanging full-precision gradients creates a communication bottleneck for large-scale distributed learning over bandwidth-limited networks.

    Source: §1 · pp. 1–2

  • Method

    Qsparse-local-SGD combines aggressive sparsification, quantization, local computation, and error compensation in synchronous and asynchronous distributed algorithms.

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

  • Results

    Qsparse-local-SGD matches vanilla distributed SGD’s convergence rate, using around 1/16 the bits of Topk-SGD and over 1000× fewer than vanilla SGD at comparable accuracy.

    Source: §5.1.2 · p. 21, §5.2.3 · p. 23, §6 · p. 25

  • Takeaways & Limitations

    The method provides a communication-efficient approach for distributed training while preserving convergence rates across the analyzed convex and non-convex settings.

    Source: §1 · p. 2, §6 · p. 25

    The numerical experiments use momentum acceleration, but analyzing momentum is left for future research.

    Source: §6 · p. 25

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 addresses communication bottlenecks in distributed optimization by combining quantization, aggressive sparsification, local computation, and error compensation in Qsparse-local-SGD. It provides synchronous and asynchronous algorithms, convergence analyses, and experiments showing substantial communication savings while retaining comparable performance.

1 Introduction

  • Communication is a bottleneck because exchanging full-precision gradients is costly for high-dimensional models over bandwidth-limited and potentially unreliable networks.For BERT, approximately 340 million parameters imply more than 1.3GB per full-precision exchange, motivating quantization, sparsification, and skipped communication rounds.Source: §1 · pp. 1–2

1.2 Contributions

  • Qsparse-local-SGD combines quantization, aggressive sparsification, local computations, and error compensation, with synchronous and asynchronous distributed implementations.The method tracks differences between true and compressed gradients and supports master-based distributed optimization, with minor modifications enabling peer-to-peer operation.Source: §1 · p. 2, §1.2 · p. 3
  • The method matches vanilla distributed SGD convergence rates for important sparsifiers and quantizers across smooth non-convex and convex objectives.The analyses cover synchronous and asynchronous settings, with non-convex convergence proportional to 1/√rate and convex convergence proportional to 1/T under diminishing learning rates.Source: §1 · p. 2, §1.2 · p. 3
  • Experiments on ImageNet ResNet-50 and MNIST softmax classification achieve target accuracies with about 15–20× fewer transmitted bits than state-of-the-art methods.The results report significant communication savings while retaining equivalent state-of-the-art performance.Source: §1 · p. 2, §1.2 · pp. 3–4

1.1 Related Work

  • The work extends prior compression and local-SGD analyses by proving distributed sparsification convergence without the earlier closeness assumption and composing quantization, sparsification, and local computation.The framework applies to compression operators satisfying a stated regularity condition, including stochastic and deterministic 1-bit sign quantizers.Source: §1.1 · pp. 2–3

1.3 Paper Organization

  • The paper develops quantizer–sparsifier regularity results, synchronous and asynchronous algorithms with convergence analyses, and experiments, while placing proof details in the appendices.Sections 2–5 respectively address regularity, synchronous theory, asynchronous theory, and experiments.Source: §1.3 · p. 4

2 Communication Efficient Operators

This section motivates communication-efficient distributed optimization through quantization and sparsification, then establishes that their compositions remain compression operators under useful conditions. It also shows that piecewise and appropriately scaled compositions can improve the attainable compression regime.

2 Communication Efficient Operators

  • Communication-efficient operators address bandwidth bottlenecks that limit full-precision distributed SGD for massive models or widely distributed data.The section introduces quantization, sparsification, and composed operators as lower-bandwidth alternatives intended to preserve convergence while accelerating training.Source: §2 · p. 4

2.1 Quantization

  • Quantization reduces gradient precision through deterministic or randomized finite-level mappings, including stochastic quantizers and the deterministic 1-bit Sign operator [BWAA18] [KRSJ19].Randomized quantizers preserve unbiasedness while controlling the second moment, whereas Sign maps each component to +1 or −1.Source: §2 · p. 4, §2.1 · pp. 4–5

2.2 Sparsification

  • Topk retains the largest k absolute components, Randk selects k uniformly, and both satisfy compression with γ = k/d [SCJ18].Different compression operators can also be assigned to different coordinate blocks or neural-network layers, with overall coefficient γmin.Source: §2.2 · p. 5

2.3 Composition of Quantization and Sparsification

  • Composing quantizers with Topk or Randk yields compression operators, while appropriate scaling removes the restriction βk,s < 1 and improves compression.The unscaled composition has coefficient γ = (1 − βk,s)k when βk,s < 1; the scaled version remains valid for all βk,s > 0.Source: §2.3 · pp. 6–7
  • Piecewise composition permits coarser per-layer quantization than applying one operator to the entire parameter vector, improving communication efficiency.For QSGD with Topk, per-block conditions can replace the global requirement βk,s = k/s^2 < 1, allowing coarser quantizers on smaller vectors.Source: §2.3 · p. 6

3 Distributed Synchronous Operation

This section develops synchronous Qsparse-local-SGD with periodic worker–master synchronization, local error-compensated memories, and convergence guarantees for non-convex and strongly convex objectives under fixed and decaying learning rates. It also completes and outlines theorem proofs using virtual sequences, convexity, smoothness, weighted averaging, and specified stepsize conditions.

3 Distributed Synchronous Operation

  • Each worker maintains a local parameter and memory; at synchronization indices, workers send compressed error-compensated net updates, the master aggregates them, and broadcasts the updated global model.All workers use the same synchronization set in the synchronous setting and reset their local parameters to the received global vector.Source: §3 · pp. 7–8

3.1 Assumptions

  • The convergence analysis assumes each local objective is L-smooth and stochastic gradients have a uniformly bounded second moment.The bounded-gradient assumption also imposes a variance bound, while relaxing uniformity for heterogeneous local gradients is left for future work.Source: §3.1 · p. 8

3.2 Error Compensation

  • Error compensation accumulates each iteration’s compression error in worker memory and feeds it into future updates, enabling convergence rates matching vanilla SGD under uniformly bounded gradients.The synchronization gap is measured as the maximum difference between consecutive synchronization indices.Source: §3.2 · p. 9, §3.1 · p. 9

3.2.1 Decaying Learning Rate

  • With a decaying learning rate η_t, worker memory contracts to zero as O(η_t)^2 when the synchronization gap is bounded and the schedule satisfies the stated condition involving H and γ.The resulting decay compensates for the net compression error accumulated across communication rounds.Source: §3.2.1 · p. 9

3.2.2 Fixed Learning Rate

  • With a fixed learning rate, worker memory remains bounded at O(η^2), and reducing it asymptotically to zero requires periodically decreasing the learning rate.A direct fixed-rate analysis improves the bound by saving a factor C 1−γ2, stated to be larger than 4.Source: §3.2.2 · pp. 9–10

3.3 Main Results

  • Theorem 1 provides a non-asymptotic fixed-rate smooth non-convex guarantee in which compression does not affect the first-order term, while convergence to a fixed point requires a piecewise learning-rate schedule.The result applies to any compression operator with coefficient γ ∈ (0, 1].Source: §3.3 · p. 10
  • Qsparse-local-SGD retains convergence guarantees for smooth non-convex and strongly convex objectives, including O(1/log T) convergence with decaying learning rates and O(1/(bRT)) behavior when compression does not dominate.The strongly convex result uses a decaying learning rate and requires a synchronization-gap condition depending on the compression coefficient and condition number.Source: §3.3 · p. 11

3.4 Proof Outlines

  • The proof outlines introduce virtual worker sequences, relate true–virtual differences to average memory, and bound local-sequence deviations before telescoping the resulting inequalities.For decaying rates, the local-sequence deviation contracts; for fixed rates, it is bounded using the corresponding memory and deviation lemmas.Source: §3.4.1 · pp. 12–13, §3.4.2 · p. 13

3.4.2 Proof Outline of Theorem 2

  • Theorem 2’s proof outline concludes with an upper-bound step and states that the proof is complete.Source: §3.4.2 · p. 14

3.4.3 Proof Outline of Theorem 3

  • Theorem 3’s proof uses virtual sequences and bounds valid for both convex and non-convex functions before invoking strong convexity and smoothness.The argument defines et = E[f(bxt)] − f∗ and uses a modified result from [SCJ18, Lemma 3.3].Source: §3.4.3 · p. 14
  • Theorem 3 assumes ηt ≤ 1/4L, derived from a > 32L, and uses ηt = 8/[µ(a+t)] with weights wt = (a+t)^2.Source: §3.4.3 · p. 14
  • Theorem 3’s proof finishes by applying convexity and forming a weighted average over iterates before concluding the theorem.Source: §3.4.3 · p. 14

4 Distributed Asynchronous Operation

The asynchronous method permits workers to synchronize at arbitrary times under a uniform delay bound, while convergence guarantees hold for smooth non-convex and strongly convex objectives with arbitrary compression operators. Its asymptotic convergence matches distributed vanilla SGD under explicit conditions on synchronization delays, batch size, workers, and compression.

4 Distributed Asynchronous Operation

  • Qsparse-local-SGD supports arbitrary worker synchronization times, bounded per-worker delays H, and master aggregation of updates from any subset of workers.Workers take the same number of local steps per global-clock unit, while the master updates and broadcasts only to workers that synchronize.Source: §4 · pp. 14–15

4.1 Main Results

  • For smooth non-convex and strongly convex objectives, the asynchronous algorithm retains convergence guarantees under arbitrary compression operators with compression coefficient γ.The results assume the same conditions as the corresponding synchronous theorems and cover fixed and decaying learning rates.Source: §4.1 · pp. 15–16

4.2 Proof Outlines

  • The asynchronous proof controls deviations between local, virtual, and true sequences, but these bounds can be weaker than in the synchronous setting because workers update the global vector between others’ synchronization times.The analysis introduces additional deviation terms caused by asynchronous updates.Source: §4.2 · p. 17

4.1 Main Results

  • Asymptotically, convergence matches distributed vanilla SGD when H = O(√γT 1/8/(bR)3/8) for smooth non-convex objectives and H = O(√γ(T/(bR))1/4) for strongly convex objectives.These conditions quantify allowable synchronization delays in terms of compression, iterations, batch size, and worker count.Source: §4.2 · p. 18

4.2 Proof Outlines

  • The method allows communication-saving tradeoffs by increasing batch size or synchronization period H, changing Topk sparsity k, or adjusting quantizer configurations.The paper reports numerics in Section 5 for savings in exchanged bits.Source: §4.2 · p. 18

5 Experimental Results

Experiments on ImageNet and MNIST show that Qsparse-local-SGD preserves convergence while substantially reducing communication through quantization, sparsification, error compensation, and local computation. The method remains effective in synchronous and asynchronous distributed settings.

5.1.1 Experiment Setup

  • Experiments train a 25,610,216-parameter ResNet-50 on ImageNet using 8 NVIDIA Tesla V100 GPUs, momentum 0.9, and Topk updates capped at 99,400 coordinates per step.The implementation uses Horovod, SignTopk, and unscaled QTopk with βk,s < 1.Source: §5.1.1 · pp. 18–19

5.1.2 Results

  • On ImageNet, QTopk-SGD and SignTopk-SGD show almost no convergence-rate penalty relative to vanilla SGD, while outperforming other schemes in communicated bits and test accuracy.QTopk uses a 4-bit quantizer, whereas SignTopk uses a 1-bit sign quantizer; error compensation accumulates compression errors.Source: §5.1.2 · pp. 19–20, Figure 1 · p. 19
  • Adding local iterations has little effect on convergence and yields average communication savings of 6 to 8 times over corresponding Qsparse operators.This trend is reported for the non-convex experiments across the methods shown in Figure 2.Source: §5.1.2 · p. 20, Figure 2 · p. 20
  • Qsparse-local-SGD requires around 1/16 as many bits as Topk-SGD and over 1000× fewer than vanilla SGD to reach the same loss or top-1 accuracy.The method combines quantization, sparsification, local computation, and error compensation while outperforming individually used techniques.Source: §5.1.2 · p. 21, Figure 3 · p. 21

5.2 Convex Objective

  • The convex experiments use softmax regression with ℓ2 regularization on MNIST, 15 workers, batch size 8, sparsity k = 40, and synchronization period H.The learning-rate schedule follows c λ(a+t), with parameters selected through a hyperparameter sweep.Source: §5.2 · p. 21, §5.2.1 · p. 22, §5.2.2 · p. 23

5.2.3 Results

  • In convex experiments, composed quantizer–sparsifier operators preserve convergence, while their communication gains over the state-of-the-art reach 6-8 times.The 2-bit QSGD configuration is slower than the 4-bit configuration, attributed to a lower compression coefficient γ.Source: Figure 4 · p. 22, §5.2.3 · p. 23
  • For test error approximately 0.1, Qsparse-local-SGD requires 10–15 times fewer bits than TopK-SGD and 1000× fewer than vanilla SGD in the convex setting.Figure 6 compares QTopk and SignTopk with vanilla SGD, ef-QSGD, ef-signSGD, and TopK-SGD.Source: §5.2.3 · p. 23, Figure 6 · p. 25
  • QTopk, SignTopk, and TopK-SGD converge at the same rate as vanilla SGD while improving communication efficiency in synchronous convex experiments.The comparison includes ef-QSGD and ef-signSGD [KRSJ19].Source: §5.2.3 · p. 23, Figure 6 · p. 25

6 Conclusion · A Omitted Details from Section 2

The paper concludes that Qsparse-local-SGD combines quantization, aggressive sparsification, local computation, and error compensation into a communication-efficient method matching vanilla distributed SGD’s convergence rates across analyzed settings. Momentum is used numerically but remains outside the main analysis, while preliminary results suggest compatibility with blockwise momentum updates.

6 Conclusion

  • Qsparse-local-SGD combines unbiased and biased quantization, aggressive sparsification, and local computation into a communication-efficient distributed algorithm.The framework offers multiple options for mitigating communication bottlenecks in bandwidth-limited training of high-dimensional models.Source: §6 · p. 25
  • The method matches vanilla distributed SGD’s convergence rate for synchronous and asynchronous optimization of convex and non-convex objectives.Without compression, the framework also subsumes or generalizes several recent local-SGD results with similar convergence rates.Source: §6 · p. 25
  • Momentum acceleration is included in the numerical experiments, but its analysis is left for future research, potentially using ideas from [YJY19].Preliminary results suggest the method also works when momentum is applied to a block of updates, although this was not the paper’s main focus.Source: §6 · pp. 25–26
  • Figure 7 compares the scheme with ef-signSGD [KRSJ19] and TopK-SGD [SCJ18,AHJ+18] for asynchronous convex optimization.The supplied passage identifies the comparison scope but does not provide numerical values or a winner.Source: Figure 7 · p. 26

A.1 Proof of Lemma 1 … B.2 Proof of Lemma 5

The proofs establish compression guarantees for quantized Topk/Randk operators and bound memory-error terms under synchronization gaps, learning-rate schedules, and fixed step sizes. Together, they formalize the conditions and coefficients used in the algorithm’s convergence analysis.

A.1 Proof of Lemma 1

  • For βk,s < 1, quantizing Topk or Randk yields a compression operator with coefficient γ = (1 −βk,s)k.The result uses a stochastic quantizer satisfying Definition 1, with expectation over both compression and quantization randomness.Source: §A.1 · p. 26

A.2 Proof of Lemma 2

  • For stochastic quantization, QsCompk has compression coefficient γ = k d(1+βk,s).The proof uses unbiasedness, the Topk/Randk inner-product identity, and the bound EC[∥Compk(x)∥2 2] ≥ k d∥x∥2.Source: §A.2 · pp. 27–28

A.3 Proof of Lemma 3

  • Lemma 3 derives compression bounds for arbitrary positive integer m by comparing Topk and Randk moment terms, with the auxiliary inequality restricted to m ∈{1, 2}.The auxiliary inequality is equality when m = 2, and the proof separately handles m = 1.Source: §A.3 · pp. 28–29

B.1 Proof of Lemma 4

  • With gap(IT ) ≤H and ηt = ξ a+t under the stated parameter conditions, Lemma 4 bounds each worker’s memory term by 4η2 t γ2 CH2G2.The proof treats synchronization times and intervening iterations separately, using unchanged local memory between synchronization indices and an induction argument.Source: §B.1 · pp. 30, 32
  • Lemma 4’s induction relies on synchronization gaps bounded by H, nonincreasing step sizes, and a condition such as β ≥2H to propagate the memory bound.The proof also uses ηt ≤ηt(i) after synchronization and establishes the bound first at synchronization indices, then between them.Source: §B.1 · pp. 31–32

B.2 Proof of Lemma 5

  • For a fixed learning rate, Lemma 5 bounds the worker memory term by 4η2(1 −γ2) γ2 H2G2 independently of t.The proof unfolds the recurrence as a geometric sum and minimizes the auxiliary bound at p = 2.Source: §B.2 · p. 33

B.3 Proof of Lemma 6 · B.4 Proof of Lemma 7 · B.5 Proof of Lemma 8

These appendices prove Lemmas 6–8 for Algorithm 1, establishing the relationship between true and virtual sequences, bounding local-sequence deviation, and handling decaying learning rates under bounded communication gaps.

B.3 Proof of Lemma 6

  • Lemma 6 identifies the difference between the true and virtual sequences with the average memory maintained by Algorithm 1.The proof derives this identity by relating the sequences across communication times and rolling out the resulting expression.Source: §B.3 · pp. 33–34
  • The Lemma 6 proof concludes that the virtual-sequence discrepancy equals the average memory, completing the argument for Algorithm 1.The final step explicitly identifies the accumulated quantity as the average memory.Source: §B.3 · p. 34

B.4 Proof of Lemma 7

  • Lemma 7 provides a bound on the deviation of the local sequences when Algorithm 1 uses a fixed learning rate η.Its proof specializes the corresponding argument by setting η_tr = η.Source: §B.4 · p. 34

B.5 Proof of Lemma 8

  • Lemma 8 establishes a bound for Algorithm 1 with a decaying learning rate η_t under the condition gap(I_T) ≤ H.The proof follows the approach of [Sti19, Lemma 3.3] and upper-bounds the relevant quantity using an averaging inequality for R vectors.Source: §B.5 · pp. 34–35

B.6 Proof of Theorem 1

The proof of Theorem 1 derives the convergence inequality using smoothness, conditional expectations, and controlled learning rates, then completes the argument through telescoping and random-iterate sampling.

Proof setup

  • Starting from the minimizer x∗ of f(x), the proof uses decaying then fixed learning rates, while remaining unchanged for any learning-rate schedule through (43), including ηt = η.Source: §B.6 · p. 35

One-step bound

  • Conditional expectation over mini-batch sampling and Lipschitz gradient continuity, together with L-smoothness, control the update terms.The proof uses η_t ≤ 1/(2L) and the inequality ∥u+v∥2 ≤ 2∥u∥2 + 2∥v∥2 when taking full-process expectations.Source: §B.6 · pp. 35–36

Error control

  • The analysis bounds the discrepancy between averaged and auxiliary iterates by 4η^2(1−γ^2)G^2H^2/γ^2 using Lemmas 5 and 6.This bound supplies the error-control term used in the subsequent convergence argument.Source: §B.6 · p. 36

Conclusion

  • A telescoping sum over t = 0,…,T−1 and random sampling of z_T with probability 1/(RT) conclude the proof.The sampling rule implies E∥z_T∥^2 = 1/(RT).Source: §B.6 · pp. 36–37

B.7 Proof of Theorem 2

The proof of Theorem 2 follows the proof of Theorem 1 through equation (43), then combines auxiliary lemmas and a telescopic sum to establish weak convergence. It concludes by sampling z_T and relating E∥∇f(z_T)∥^2 to the accumulated terms.

Proof structure

  • The proof reuses Theorem 1 through (43) under the step-size condition η_t ≤ 1/(2L), implied by a ≥ 2ξL.This establishes the initial part of the Theorem 2 argument under the stated assumption.Source: §B.7 · p. 37
  • Combining Lemmas 8, 6, and 4, the proof applies a telescopic sum from t = 0 to T − 1 to derive the convergence bound.The proof also establishes the required lower bound on P_T near its conclusion.Source: §B.7 · p. 37

Convergence result

  • The resulting argument establishes a weak convergence result and completes the proof of Theorem 2.The result is stated for the iterates indexed by r = 1, . . . , R and t = 0, 1, . . . , T − 1, with a probability qualification.Source: §B.7 · p. 38
  • The proof samples a parameter z_T and expresses E∥∇f(z_T)∥^2 using the accumulated quantity P_T and the weights δ_t.The passage gives the relation involving E[δ_t] = δ_t P_T and the normalization by P_T.Source: §B.7 · p. 38

B.8 Proof of Theorem 3 · C Omitted Details from Section 4

The omitted details prove Theorem 3 by analyzing averaged virtual sequences, bounding gradient and distance terms with smoothness and strong convexity, and applying a weighted recursion. The asynchronous section begins by defining virtual sequences for each worker.

B.8 Proof of Theorem 3

  • The proof starts from the minimizer x* with ∇f(x*) = 0 and analyzes averages of the workers’ virtual sequences.Source: §B.8 · p. 38
  • Conditioning on past mini-batch samples makes the final sampling term vanish after expectation, yielding the central recursion.Source: §B.8 · p. 38
  • Smoothness bounds the gradient term through ∥∇f(x̃_t) − ∇f(x*)∥2 ≤ 2L(f(x̃_t) − f(x*)), using ∇f(x*) = 0.Source: §B.8 · p. 39
  • Strong convexity and smoothness separately control the two terms in the distance bound, which are then combined under a ≥ 32L/µ and η_t ≤ 1/4L.Source: §B.8 · pp. 39–40
  • The resulting inequalities are substituted into the expected objective-gap recursion, followed by a modified Lemma 3.3 argument with η_t = 8/[µ(a+t)] and w_t = (a+t)^2.Source: §B.8 · pp. 40–41
  • Convexity completes the proof by relating the final weighted average of iterates to the established recursion.Source: §B.8 · p. 41

C Omitted Details from Section 4

C.1 Proof of Lemma 9 … C.4 Proof of Lemma 12

Appendix C proves Lemmas 9–12 by bounding deviations among local, true, and virtual sequences under bounded synchronization gaps, with separate analyses for decaying and fixed learning rates. The proofs use synchronization identities, Jensen’s inequality, compressor bounds, and previously established lemmas.

C.1 Proof of Lemma 9

  • Lemma 9 bounds deviations of local sequences under Algorithm 2 with a decaying learning rate and synchronization gaps bounded by H.The proof separates two deviation terms and uses the fact that local parameters equal global parameters at synchronization steps.Source: §C.1 · pp. 42–43
  • Lemma 9’s proof applies Lemma 4 because its argument requires only that every worker’s synchronization gap is at most H, not network synchrony.The analysis combines bounds on the two terms to complete the local-sequence deviation bound.Source: §C.1 · p. 43

C.2 Proof of Lemma 10

  • Lemma 10 analyzes Algorithm 2 with fixed learning rate η assuming every worker’s synchronization gap satisfies gap(I(r)) ≤ H.Its proof uses the compressor second-moment bound E∥QComp_k(u)∥2 ≤ B∥u∥2, with B = (4 − 2γ), and bounds both deviation terms.Source: §C.2 · pp. 43–44
  • The Lemma 10 proof combines the fixed-rate bounds for both terms to obtain the stated result.The final step substitutes the preceding estimates into the decomposition of the deviation quantity.Source: §C.2 · p. 44

C.3 Proof of Lemma 11

  • Lemma 11 bounds the difference between true and virtual sequences for Algorithm 2 with a decaying learning rate under synchronization gaps at most H.Unlike the synchronous case, the asynchronous setting does not directly identify the true and virtual averages, so the proof decomposes their difference into three terms.Source: §C.3 · p. 44
  • Lemma 11 controls the three-term decomposition using compressor bounds, synchronization-step identities, unchanged local memories between synchronizations, and Lemma 4.The resulting estimates are combined to complete the asynchronous true-versus-virtual sequence bound.Source: §C.3 · pp. 44–46

C.4 Proof of Lemma 12

  • Lemma 12 establishes the corresponding true-versus-virtual sequence bound for Algorithm 2 with fixed learning rate η and synchronization gaps at most H.The proof reuses the constant-rate bound for one term and combines bounds from Lemma 5 and the preceding analysis.Source: §C.4 · p. 46

D Omitted Details from Section 5

In non-convex experiments, unscaled QTopk matches or outperforms scaled QTopk despite weaker theoretical guarantees, especially with more local iterations. Error compensation preserves vanilla-SGD-like convergence under compression and infrequent communication.

QTopk comparison

  • Unscaled QTopk performs at least as well as scaled QTopk experimentally and strictly better in some cases, although scaling has stronger theoretical convergence guarantees.The authors attribute this gap to scaling being sufficient theoretically rather than necessarily beneficial in practice.Source: D Omitted Details from Section 5 · p. 46
  • At target loss or accuracy, scaled and unscaled QTopk transmit almost equally many bits for L = 0, 4, while unscaled QTopk performs better for L = 8.Consequently, the non-convex experiments use unscaled QTopk from Lemma 1.Source: D Omitted Details from Section 5 · p. 47, Figure 8 · p. 47

Error compensation

  • With error compensation, compressed and infrequently communicated Qsparse-local-SGD recovers convergence rates matching vanilla SGD.Without error compensation, stochastic-quantization variance blow-up dominates quantized-SGD convergence; Figure 8 compares the resulting behavior.Source: D Omitted Details from Section 5 · pp. 46–47

Related papers

Loading 1906.02367v2…