acceptodds
Under review as a conference paper at ICLR 2027

Intermittent Error Recycling: Narrowing the Gap Between Compressed and Uncompressed SGD

Abstract

Gradient compression is a standard remedy for communication overhead in distributed optimization. Yet, existing unbiased compression methods can substantially degrade convergence by inflating the variance of stochastic updates, creating a gap between compressed and uncompressed training. In this work, we show that this degradation is not fundamental and can be mitigated by exploiting a simple distinction: unlike stochastic gradient noise, compression error is directly observable. We propose Intermittent Error Recycling (IER), a framework in which workers accumulate compression residuals locally and periodically communicate an uncompressed correction. This allows compression errors to be amortized over time rather than repeatedly injected into the optimization dynamics. We show that IER recovers the dominant stochastic convergence term of uncompressed distributed SGD without compression-induced variance inflation, while confining compression-dependent effects to faster-decaying terms. This mechanism does not increase the total communication cost, with the correction frequency determined directly from the communication budget, allowing IER to retain the benefits of compression without its associated variance penalty. We empirically corroborate our theoretical guarantees and demonstrate the efficacy of our approach.

Primary area:
optimization
Keywords:
gradient compression, communication-efficient learning, unbiased compression

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_nvWvOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

Gradient compression is a well-known technique for reducing the communication overhead of distributed training. Unbiased gradient compression techniques are useful. However, they increase the variance of the gradient estimate. This makes the convergence rate slower. Specifically in the standard distributed SGD the rate converges as σ/T\sigma/\sqrt{T} where \sigma is the variance of the gradient estimate and T is the number of iterations. However, when unbiased gradient compression is used, it increases to (σ+C1)/T(\sigma + C_1)/\sqrt{T} where the constant C1C_1 depends upon the variance in the unbiased compression estimate.

The paper addresses this loss in convergence rate through a technique called intermittent error recycling. The basic idea is that the error in the compression estimate is known exactly by each individual worker. The worker keeps accumulating this error and periodically sends out the full gradient along with the accumulated errors. This helps to reset the error in the iterations and allows the authors to obtain a faster convergence rate where the leading term matches the case of the standard distributed SGD.

The central result of the paper is of interest to the community.

Critical strengths

The paper addresses an important issue and in my opinion Theorem 4.1 appears to be correct.

Critical weaknesses
  1. I believe that there is flaw in the case where momentum (Appendix B) is considered.

  2. It appears to this reviewer that the central claim of changing the scaling in the convergence rate has been addressed in the prior work of Karimireddy et al. ICML 2019. Specifically, I looked at Remark 4 in their paper, where they clearly state the compression factor term has been moved the convergence term that scales as 1/T. This is followed by Remark 5, where their method is shown to apply to unbiased compressors as well. Given that this is true, the novelty and contribution level of this paper is questionable.

  3. The main body of the paper is quite repetitive and all the core technical content has been relegated to the Appendix. While I read the Appendix in some detail, a person who reads only the main paper is not likely to get too much out of the paper. I mean, the authors could try to structure the paper by providing plausible sketches of proofs based on well-known results.

  4. The paper needs to do a better job of outlining the implications of its results. COnsider the third term on the RHS of the equation in Theorem 4.1. One needs to really consider the relative values of (ω(K−1))1/3M1/3T2/3\frac{(\omega(K-1))^{1/3}}{M^{1/3} T^{2/3}} and 1MT\frac{1}{\sqrt{MT}}. When T→∞T \to \infty, clearly the second term dominates. However, one needs T≥M[ω(K−1)2]T \geq M [\omega(K-1)^2]. It is not clear from the results, how to interpret these. For instance in Fig. 1a, the K=1000,M=32K=1000,M=32 so that TT needs be greater that 32×106×ω232 \times 10^6 \times \omega^2. It seems like this can be a very large number and it is unclear if the algorithm can be proved to really provide an advantage here. While the results show advantages, the test accuracy appears to flatten out around 70%. Perhaps this can be explained better, as to why this is happening?

Detailed comments

  1. Lemma B.4 in Appendix B is incorrect as stated. The justification from (76) to (77) is not valid. Note that mt−1m_{t-1} is Ft\mathcal{F}_t-measurable, so it is incorrect to replace it with the conditional expectation. Moreover, the cross-term will not go to zero in general. This affects the transition from (92) to (93) and hence the main result. Given that this is a pretty dense paper, I essentially stopped reading the paper at this point.

  2. Going from eq. (24) to (25) was a difficult stretch. While the authors have cited Dorfman et. al 2024, I believe this can be derived by relatively standard techniques, using the L-smoothness and the descent lemma and using the standard conditional expectation arguments. Also note that inner conditional expectation on the third term of the RHS is not required as the quantity is F\mathcal{F}-measurable.

  3. Typo - Equation eq. 31.

  4. Supplement pg. 13, a different TeX symbol is used for epsilon.

Questions for authors
  1. I'm convinced that there is a flaw in Appendix B. While this can perhaps be fixed with some work, I do not think in a short conference paper window, fixing the proof and expecting reviewers to check it again is reasonable.

  2. If the authors could better situate their work in the context of Karimireddy et al. ICML 2019, that would be helpful for a future submission.

3 comments

Thank you for your thorough and thoughtful review! We address the concerns you raised below.

W1-Q1 - Proof in Appendix B

We thank the reviewer for pointing this out. This issue is simply a typo in the statement of Lemma B.4, where Emt\mathbb{E}m_t should be replaced by the conditional expectation E[mt∣Ft]\mathbb{E}[m_t\mid\mathcal{F}_t].

Importantly, the proof of Lemma B.4 already uses the conditional expectation and requires no changes. The fix therefore consists only of correcting the statement of Lemma B.4 and making the same substitution in Eq.(92) (Now Eq.(87) in the revision). This fully resolves the issue, without changing any subsequent derivations, results, or constants.

We also inadvertently left an outdated draft of the proof immediately after the correct proof of Lemma B.4. The invalid transition from (76) to (77) identified by the reviewer appears in this outdated draft, which we have removed from the revised appendix.

W2-Q2 - Comparison to Karimireddy 2019

We thank the reviewer for highlighting this connection. We acknowledge that Karimireddy et al. (2019) established that error feedback can shift compression dependence to higher-order terms. However, their theoretical analysis is restricted to the single-worker setting, as explicitly acknowledged in their work. This limitation is well recognized in the literature. In particular, EF21 [1] and EF21-SGDM [2] discuss this work and emphasize that extending classical error-feedback analyses to distributed optimization is not trivial and poses additional theoretical challenges. In contrast, our Theorem 4.1 directly addresses distributed stochastic optimization.

Moreover, Karimireddy et al. (2019) requires uniformly bounded second moments of stochastic gradients, i.e., E∣g(x)∣2≤σ2\mathbb{E}\\|g(x)\\|^2\leq \sigma^2, which is strictly more restrictive than bounded stochastic-gradient variance, E∣g(x)−∇f(x)∣2≤σ2\mathbb{E}\\|g(x)-\nabla f(x)\\|^2\leq \sigma^2 that we assume. The bounded second moments assumption is well-recognized as restrictive and potentially unrealistic even for simple quadratic objectives [1,2]. Finally, their analysis relies on contractive compressors (Remark 5 rescales unbiased compressors into contractive ones), whereas our method operates directly on unbiased compressors and employs a distinct mechanism based on intermittent exact correction of accumulated compression errors.

We have clarified these distinctions in our related work section (in the EF paragraph).

W3 - proof sketch

Thank you for this suggestion, we agree that adding a proof sketch will help make our method clearer. We have therefore added a short proof sketch for Lemma 4.1 in the paper.

W4 - stochastic vs compression dominant regimes

We thank the reviewer for this observation. As discussed in Appendix C.3, IER provides theoretical improvements in both regimes: by eliminating the dependence on ω\omega in the leading stochastic term (in the stochastic-dominated regime), or by achieving faster decay with TT (T−2/3T^{-2/3} versus T−1/2T^{-1/2}) (in the compression-dominated regime).

Importantly, these are upper bounds and need not fully reflect practical performance. As the reviewer correctly notes, our experiments operate in the compression-dominated regime, yet IER still demonstrates significant empirical improvements under the same communication budget. These results demonstrate that IER maintains its advantage at realistic finite horizons, without requiring the stochastic-dominated regime to be reached.

Regarding the accuracy plateau, this is consistent with previously reported ResNet-18 performance on Mini-ImageNet, with accuracies around 65–68% [3,4]. A similar plateau is also observed for uncompressed SGD in our experiments.

Detailed comments

We thank the reviewer for these helpful suggestions. We have fixed the typos and added a self-contained lemma following Dorfman et al. (2024) which the proofs now use directly, as the reviewer suggested. We agree that it helps improve clarity, but emphasize that these changes are purely expository and do not affect the theoretical guarantees or analyses.

We thank the reviewer again for their thorough review and helpful comments. These have certainly improved our work! We look forward to your response.

References

[1] Richtarik et al., new, simpler, theoretically better, and practically faster error feedback, NeurIPS, 2021.

[2] Fatkhullin et al., Momentum provably improves error feedback!, NeurIPS, 2023.

[3] Liu et al., Bandwidth-Aware Adaptive Gradient Quantization for Cross-Organization Federated Learning, IFIP Networking, 2025.

[4] Li et al., U-ResNet, a Novel Network Fusion Method for Image Classification and Segmentation, Sensors, 2025.

I appreciate the responses provided by the authors. I am not exactly convinced that the contributions over and above the Karimireddy 2019 work (acknowledging that the authors consider a distributed setup) are significant, especially in light of the other work that has also been highlighted by other reviewers. In addition, I am still not convinced about the response to critical weakness #4. Most importantly, as I had mentioned earlier, essentially the entire paper appears in the Appendix. It is essentially impossible to expect reviewers to plow through a very dense Appendix to really understand what is going on. The alternative is to take what is written in the main body of the paper on face value.

I believe the authors can address these comments given more time to edit the paper accordingly. However, for now I will keep my current rating.

We thank the reviewer for their follow-up. We would like to clarify several important points, particularly regarding the revisions already incorporated into the manuscript.

Technical accessibility and proof sketch.

We agree that adding a proof sketch would improve clarity. In direct response to your original suggestion, we have already added a proof sketch immediately following Theorem 4.1 in the main paper. This sketch explains the central steps of the analysis and captures the essence of the proof: the auxiliary uncompressed sequence, the control of accumulated compression errors through unbiasedness, and the role of periodic exact corrections in recovering the stated convergence guarantee.

The main paper now presents the algorithms, convergence guarantees, proof sketch, interpretation of the theoretical results, communication-complexity analysis, and experimental findings. Only the complete technical derivations are deferred to the appendix. We therefore respectfully emphasize that your helpful suggestion to include a proof sketch has already been implemented in the revised submission.

Significance beyond Karimireddy et al. (2019) and subsequent work.

We respectfully emphasize that the contributions of IER extend substantially beyond Karimireddy et al. (2019):

  • Distributed optimization: Karimireddy et al. analyze only the single-worker setting, whereas IER establishes guarantees for distributed stochastic optimization.
  • Substantially weaker assumptions: Karimireddy et al. assume uniformly bounded stochastic-gradient second moments, E∥g(x)∥2≤σg2\mathbb{E}\|g(x)\|^2\leq\sigma_g^2, whereas we only assume bounded variance, E∥g(x)−∇f(x)∥2≤σv2\mathbb{E}\|g(x)-\nabla f(x)\|^2\leq\sigma_v^2. This difference is substantial and discussed heavily in related work as we previously mentioned. Crucially, although both analyses obtain compression-independent stochastic terms, Karimireddy et al.'s rate depends on σg\sigma_g, whereas ours depends on σv\sigma_v. The distinction between Karimireddy's O(σg/T)O(\sigma_g/\sqrt{T}) versus IER's O(σv/MT)O(\sigma_v/\sqrt{MT}) is substantial: σg\sigma_g can be much larger than σv\sigma_v, σg\sigma_g is even infinite for simple quadratic objectives [1,2].
  • Unresolved challenges: The 2019 result did not resolve the fundamental challenges of compressed distributed optimization, as reflected in the extensive subsequent literature, including influential works such as EF21 [1], EF21-SGDM [2], and VR-MARINA [3]. These works address important challenges left open by earlier analyses, as does ours.
  • Distinctions from subsequent work: Reviewer pgqR indicated that our response addressed their concerns regarding related work. Reviewer yeku also acknowledged IER's improvements over EF21-SGDM, and we addressed their remaining concern in our subsequent response.

Interpretation of the finite-horizon guarantees.

We appreciate the reviewer highlighting this, although it is unclear which aspect of our previous explanation remains unconvincing, we would like to briefly reiterate the key points:

  • Stochastic-dominated regime: IER recovers the compression-independent leading stochastic term O(σv/MT)O(\sigma_v/\sqrt{MT}), matching uncompressed distributed SGD.
  • Compression-dominated regime: The compression-dependent term decays as T−2/3T^{-2/3}, rather than the compression-inflated T−1/2T^{-1/2} term of standard unbiased compressed SGD. Thus, entering the stochastic-dominated regime is not necessary for obtaining theoretical improvements.
  • Comparison with EF21-SGDM: IER achieves improved worker dependence in its compression-dependent terms, which improve with MM, unlike those of EF21-SGDM. This addresses a fundamental limitation of parallel scalability explicitly recognized in EF21-SGDM itself and other work (please refer to our response to Reviewer yeku for the complete details).
  • Empirical validation: Importantly, our experiments operate precisely in the compression-dominated regime, yet demonstrate substantial improvements over established baselines, including EF21-SGDM, at realistic finite horizons and matched communication budgets, across vision and NLP tasks and multiple compression schemes (Rand-k, Top-k, QSGD, and the DIANA quantizer).

Together, these results demonstrate that IER offers meaningful theoretical and empirical advantages without requiring the asymptotic stochastic-dominated regime to be reached.

Finally, we reiterate that the type identified in Appendix B was resolved in the revised manuscript, without changing the theoretical guarantees.

We appreciate the reviewer's feedback and hope these clarifications, together with the requested revisions already made, help establish the significance of our contributions.


[1] New, simpler, theoretically better, and practically faster error feedback, Fatkhullin '23

[2] Momentum provably improves error feedback! Richtarik '21

[3] Faster Non-Convex Distributed Learning with Compression, Gorbunov 21

Reviewer_pgqROpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes Intermittent Error Recycling, or IER, for distributed SGD with unbiased compressors. Each worker stores its compression residuals locally and sends them uncompressed every K steps. K is chosen so that the average communication cost matches that of a target compressor. The main theorem shows that the leading sigma/sqrt(MT) term no longer depends on the compression parameter, and that compression effects move into terms that decay faster in T. Experiments on ImageNet-Mini, with more results on BERT/SST-2 and CIFAR-10 in the supplement, show IER getting close to uncompressed SGD at the same communication budget.

Critical strengths
  • The idea is simple and practical. Flushing the residual exactly every K steps means the server receives the exact sum of stochastic gradients over each window. With the explicit budget rule for K, the method is easy to implement. I went through the proof of Theorem 4.1 in the supplement and did not find errors.

  • The empirical gains are consistent. IER tracks uncompressed SGD much more closely than QSGD, EF21-SGDM, VR-MARINA and DIANA, both per epoch and per transmitted bit. This holds on ImageNet-Mini, CIFAR-10 and BERT/SST-2.

Critical weaknesses
  • The claim that IER eliminates variance inflation only holds at unrealistic horizons. The compression terms scale with omega*(K-1), and the budget rule makes K grow with omega. The supplement itself states that the stochastic term dominates only when T is at least about M*(omega(K-1))^2. With the paper's Rand-k setting, omega*(K-1) is around 10^6, so every experiment sits in the compression-dominated regime. The wording in the abstract and introduction should be toned down, or the full bounds should be compared at realistic T.

  • The relation to error feedback with periodic resets is not discussed. The proof uses the standard virtual-sequence argument from error feedback. Periodically resetting the local error has been proposed before, for example in CSER by Xie et al., NeurIPS 2020. Local SGD and dense sync every few steps are also close relatives, but none of them is discussed or used as a baseline.

  • Some baselines look untuned. In the CIFAR-10 runs all methods use a learning rate of 0.1, and plain Rand-k stays at 10% accuracy for the whole run. This suggests the baseline was not given its own learning rate. All workers are also simulated on two GPUs, so there is no wall-clock evidence.

Questions for authors

Clarifications:

  • For the ImageNet-Mini setup, at what T does the sigma/sqrt(MT) term actually dominate in Theorem 4.1? Does IER's full bound beat QSGD's at the same budget for any realistic T?
  • How does IER differ from error feedback with periodic error reset, such as CSER, and from MARINA's occasional uncompressed refresh?
  • Was the learning rate tuned separately for each baseline? Can plain Rand-k train on CIFAR-10 with a smaller learning rate?
  • Is Rand-k scaled by d/k to be unbiased? If so, how does IER stay stable at learning rate 0.1 with k' = 5,000?
  • In the DIANA comparison, how was K = 1000 derived from the budget rule, and is the budget really matched?

Suggestions:

  • Add same-budget baselines that also send dense vectors periodically, such as local SGD or gradient accumulation with a dense all-reduce.
  • Report wall-clock time in a real multi-node setup.
  • Add an ablation over K at a fixed budget.
4 comments

Thank you for your thorough and thoughtful review, and for acknowledging our work's strengths! We address the concerns you raised below (weaknesses and corresponding questions together).

W1-Q1 - compression-dominant regime and comparison to QSGD

We thank the reviewer for raising this point. We would like to clarify that our claim of eliminating variance inflation refers specifically to removing compression dependence from the leading stochastic term, rather than eliminating all compression-dependent effects. This distinction is stated in both the abstract and introduction, where we emphasize that IER recovers the compression-independent stochastic term of uncompressed SGD while confining compression-dependent effects to faster-decaying terms. Following your suggestion, we have added a discussion of the different regimes to section 4.4 (the last paragraph on page 7 in the revised version), and we refer to the appendix for the full analysis and comparisons.

Importantly, we distinguish between theoretical improvements in convergence guarantees and empirical improvements in practical training, both of which are demonstrated by our work. As the reviewer correctly notes, under aggressive compression and finite training horizons, the compression-dependent term may dominate. We analyze both regimes in Appendix C.3, showing that our method either removes compression dependence from the stochastic term (in the stochastic-dominated regime) or achieves faster decay with TT (in the compression-dominated regime).

To illustrate this for QSGD, its compression-inflated stochastic term scales as O(ω/T)O(\sqrt{\omega}/\sqrt{T}), whereas IER scales either as O(1/T)O(1/\sqrt{T}), independently of ω\omega, or as O((ω(K−1))1/3/T2/3)O((\omega(K-1))^{1/3}/T^{2/3}), thus exhibiting better dependence on TT (K=14K=14 in our experiments, determined by the matched communication budget). This improvement is also reflected in our experiments.

Empirical improvement. The exact crossover threshold between the stochastic-dominated and compression-dominated regimes of IER is difficult to compute, as it depends on problem-specific quantities (such as σ\sigma, Δ1\Delta_1, and LL) that are not known a priori. Nevertheless, we acknowledge, as the reviewer correctly points out, that our experiments most likely operate in the compression-dominated regime. Yet, our experiments demonstrate that IER significantly outperforms QSGD and other compressed baselines under matched communication budgets, even at realistic training horizons where compression-dependent effects can dominate. This demonstrates that the practical benefits of IER do not require reaching the stochastic-dominated regime.

W2-Q2 - Comparison to CSER, MARINA, LocalSGD

We thank the reviewer for highlighting the connections to these works. We discuss some of these in the related work section, but we elaborate below:

LocalSGD does not employ gradient compression and is therefore not directly related to this line of work (though we still discuss it briefly in the related work section). Instead, it reduces communication through a different mechanism, where workers perform local optimization steps and synchronize their models only periodically. IER communicates compressed gradients in every iteration (no local steps) and periodically transmits an uncompressed cumulative correction.

MARINA communicates compressed gradient differences during regular iterations and, with probability pp, communicates the full current gradients. However, unlike IER, MARINA does not accumulate and correct historical compression errors. In contrast, IER explicitly accumulates compression residuals locally and periodically communicates their exact cumulative correction.

CSER employs periodic error resets, but the underlying mechanisms differ fundamentally. CSER immediately incorporates compression residuals into workers' local models, causing them to diverge and evaluate gradients at different points, and periodically partially synchronizes these models to reduce their discrepancies. In contrast, IER maintains a single synchronized model, ensuring all workers evaluate gradients at the same point, while accumulating compression errors separately and periodically transmitting an exact, uncompressed correction. Furthermore, CSER assumes bounded expected-gradient norms, a restrictive assumption, whereas IER does not. Importantly, IER's compression-dependent terms improve with the number of workers MM, whereas those in CSER's bound do not (except for the stochastic term). We have added this to the related work section.

W3-Q3-Q4 - learning rate tuning and rand-k

We thank the reviewer for raising this point.

We tuned the learning rate independently for each method using the same search space 0.01,0.05,0.1,0.15\\{0.01, 0.05, 0.1, 0.15\\} (detailed in Appendix D). Thus, the reported learning rate of 0.10.1 was selected through tuning rather than imposed uniformly. Nevertheless, we extended the search to substantially smaller learning rates for plain Rand-kk (which converges for a smaller learning rate 0.0010.001 on CIFAR-10) and report the results in the revised Fig 4 and have updated the text accordingly (learning rate of 0.10.1 still performs best on the other baselines, including rand-k with k=50,000k=50{,}000, so only rand-k with k=10,000k=10{,}000 was updated). Finally, Rand-k is indeed scaled to be unbiased, as the reviewer has correctly pointed out, and the error correction mechanism is what helps IER stay stable.

Q5 - DIANA

DIANA communication budget. We thank the reviewer for requesting this clarification. Both DIANA and IER use the ℓ∞\ell_\infty-quantizer introduced by Mishchenko et al. (2023), with bucket sizes 32 and 128, respectively, and Elias encoding in this experiment.

Since the communication cost under Elias encoding depends on the quantized values and varies throughout training, we deliberately chose a conservative recycling period of K=1000K=1000 to ensure that IER remains well-within DIANA's communication budget. Importantly, we track the actual communication cost online, including all full-precision correction rounds, and report performance against cumulative communication cost in Fig. 3. We have now clarified this budget choice and communication accounting in the revised Appendix D.3.

Suggestions 1-3 - baselines, wall-clock time, ablation over K

We thank the reviewer for these valuable suggestions!

Additional baselines. Although LocalSGD and gradient accumulation are not gradient-compression methods, we agree that comparing against them enriches our evaluation. We have therefore added both baselines in Appendix D.4 (Fig. 7), comparing IER, LocalSGD, and gradient accumulation under the same communication budget. results show that IER maintains a significant performance advantage over both methods.

Wall-clock evaluation. We conducted additional experiments on a real multi-node setup comprising four physical nodes, each equipped with a single NVIDIA A10G GPU running one worker, connected via a 10 Gbps interconnect. While our access is limited to four nodes, these experiments allow us to evaluate practical distributed performance. The results show that IER achieves higher accuracy than compressed baselines at comparable wall-clock times, demonstrating that its communication efficiency translates into practical runtime benefits. We have added the experimental details and results to Appendix D.4 (Fig 8).

Ablation over K. We have added an ablation study examining different values of KK under a fixed communication budget. Importantly, varying KK requires adjusting the compression level C′\mathcal{C}' accordingly to preserve the budget constraint in Eq. (5). We provide the results in Appendix D.4 (Fig 6), demonstrating that IER is relatively robust to variations in KK.

We thank the reviewer again for their thoughtful review and helpful suggestions and comments which have improved our work! We look forward to your response.

Thank you for the detailed response and the substantial additional experiments. The clarification of how IER differs from CSER and MARINA is convincing, in particular that IER keeps a single synchronized model and that its compression-dependent terms improve with the number of workers. The new same-budget comparisons with local SGD and gradient accumulation, the ablation over K, the extended learning-rate search for plain Rand-k, and the clarified communication accounting in the DIANA experiment address my concerns about the experiments. The real multi-node wall-clock results are also a welcome addition, although they are limited to four nodes.

On the theory, I appreciate that the regime discussion is now in the main text and that the authors acknowledge the experiments most likely operate in the compression-dominated regime. I still think the practical benefit of IER is mainly supported by the experiments rather than by the leading-term result, and I encourage the authors to keep this distinction clear in the abstract and introduction.

Since most of my concerns have been addressed, I am raising my score from 2 to 3.

We sincerely thank you for your reply and for increasing your score. We appreciate your constructive feedback and suggestions, which have helped us improve the paper. We will retain all the additions and clarifications in the revised manuscript and ensure that the distinction between our theoretical guarantees and empirical improvements remains clear throughout, particularly in the abstract and introduction.

Reviewer_yekuOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes Intermittent Error Recycling (IER), which accumulates compression residuals locally and periodically transmits an exact correction. More aggressive compression between corrections offsets their communication cost. Theorem 4.1 establishes a compression-independent leading stochastic term, with compression dependence confined to faster-decaying terms. Equation (5) specifies a budget-compatible correction period. Experiments evaluate sparsification and quantization on ResNet-18/ImageNet-Mini with 4 and 32 workers, with additional evaluations deferred to the supplement.

Critical strengths
  1. Simple mechanism with an explicit communication trade-off. Algorithms 1–2 clearly separate residual accumulation from periodic exact correction. Theorem 4.1 and Eq. (5) connect this mechanism to convergence and communication cost, making the method straightforward to understand and potentially useful in practice.

  2. Substantial empirical improvements in the reported settings. In Fig. 1(b), IER reaches approximately 67–68% accuracy, close to uncompressed SGD, compared with roughly 52–57% for QSGD and VR-MARINA across the two worker counts. Figure 1(a) also shows substantial gains under sparsification. These are approximate readings from the plots. Reporting performance against both epochs and communication is appropriate for the paper’s objective.

Critical weaknesses
  1. The theoretical advance over existing error-feedback results is insufficiently established. Theorem 3 of the cited EF21-SGDM paper [1] already obtains a compression-independent leading stochastic term proportional to σ/MT\sigma/\sqrt{MT}, with compression appearing only in faster-decaying terms. It also avoids a bounded-gradient-dissimilarity assumption, whereas IER’s Theorem 4.1 uses bounded heterogeneity. IER provides a distinct correction mechanism, but the paper needs a direct comparison of assumptions and finite-time communication complexity to establish what improves beyond this already-known asymptotic property.

  2. The central communication-efficiency evidence needs clarification. Section 6 reports (K=1000) for sparsification and K=14K=14 for quantization, but the main text does not give the numerical message costs used in Eq. (5). Moreover, Fig. 1 labels cumulative communication in bits, with displayed ranges of approximately 1.8×1071.8\times10^7 and 2×1082\times10^8. For comparison, one dense FP32 gradient for the standard 11.69-million-parameter ResNet-18 would require approximately 3.74×1083.74\times10^8 bits [2]. If the full model is trained, this suggests an unstated normalization or labeling issue. This may be readily explainable, but it currently prevents an independent assessment of the claimed communication savings.

[1] Fatkhullin, Tyurin, and Richtárik. Momentum Provably Improves Error Feedback! NeurIPS 2023. Theorem 3 and Corollary 2.

[2] Torchvision. ResNet-18 documentation. Standard model parameter count.

Questions for authors
  1. How does Theorem 4.1 compare with EF21-SGDM’s Theorem 3 under matched communication costs, including the lower-order terms? In particular, which finite-horizon regimes favor IER? An unbiased compressor can be rescaled into a contractive compressor without changing the transmitted payload, so this comparison appears relevant.

  2. Please specify the trainable parameter count, communication precision, c(C)c(C), c(C′)c(C'), and cmax⁡c_{\max} that yield the reported correction periods. What normalization, if any, is applied to Fig. 1’s communication axes, and are VR-MARINA’s full refreshes included?

Is there a matched-budget ablation that uses the same full-precision communication schedule but omits accumulated residual correction? This would distinguish the benefit of recycling errors from the benefit of occasional full-gradient updates.

4 comments

Thank you for your thorough and thoughtful review, and for acknowledging our work's strengths! We address the concerns you raised below (weaknesses and corresponding questions together).

W1-Q1 - Comparison to EF21-SGDM

We thank the reviewer for highlighting EF21-SGDM. We agree that an unbiased compressor with variance parameter ω\omega can be rescaled into a contractive compressor with α=1/(1+ω)\alpha=1/(1+\omega), without increasing its communication cost, making a direct comparison with EF21-SGDM relevant. We also acknowledge that its Theorem 3 achieves the same compression-independent leading stochastic term O(σ/MT)O(\sigma/\sqrt{MT}) and that our analysis assumes bounded heterogeneity. However, IER employs unbiased compressors directly, demonstrating that the variance inflation, typically induced by their direct application in SGD, can be eliminated from the leading stochastic term through a distinct mechanism based on periodic exact correction of accumulated compression errors. We provide a more thorough comparison between IER and EF21-SGDM below.

First, IER's compression-dependent terms improve with the number of workers, scaling as M−1/2T−1M^{-1/2}T^{-1} and M−1/3T−2/3M^{-1/3}T^{-2/3}, whereas EF21-SGDM's corresponding terms do not improve with MM. In particular, IER has a strictly smaller compression-dependent T−1T^{-1} factor for the communication-matched configurations considered below. Moreover, EF21-SGDM incurs an additional compression-dependent T−3/4T^{-3/4} term, absent from IER.

Second, under matched communication budgets, comparing the T−2/3T^{-2/3} compression-dependent factors identifies regimes favoring IER whenever

αω(K−1)(1+ξ/σ)2<M,\alpha\omega(K-1)(1+\xi/\sigma)^2<M,

where α\alpha and ω\omega are the respective compression parameters, and the recycling period KK is determined by the communication budget.

As an example, The table below identifies the sparsification and quantization regimes in which IER has a smaller T−2/3T^{-2/3} compression-dependent factor than EF21-SGDM, for practical worker counts and homogeneous data. For sparsification, it reports the minimum baseline density k/dk/d above which IER is favored, and for quantization it lists the quantization levels ss favoring IER.

Workers MMSparsification: min. k/dk/dQuantization: favorable ss
420.00%—
813.33%64
168.00%4, 8, 16, 32, 64
324.44%2, 4, 8, 16, 32, 64
642.35%2, 4, 8, 16, 32, 64
1281.21%2, 4, 8, 16, 32, 64

For sparsification, EF21-SGDM uses Top-kk or biased rescaled rand-kk, while IER uses unbiased Rand-k′k' with k′=k/2k'=k/2. For quantization, EF21-SGDM uses rescaled QSGD with level ss, while IER uses QSGD with s′=s−1s'=s-1. In both cases, the recycling period KK is determined by Eq.5 (and Eq.(106)-(107) (or (111)-(112) in the old version) in App.C1 for rand-kk and QSGD).

Importantly, these comparisons concern theoretical upper-bound factors, which suppress constants and might not fully reflect practical performance. Indeed, although the T−2/3T^{-2/3} factor comparison does not favor IER under extreme sparsification, our experiments (Fig. 1a) demonstrate that IER nevertheless outperforms EF21-SGDM under matched communication budgets precisely in this challenging regime (k/d=0.1%k/d=0.1\%, M=4,32M=4,32). Thus, IER's practical advantages extend beyond the regimes identified by the theoretical comparison.

Our related work section now positions this more thoroughly, and this full detailed comparison is now included in Appendix C.3.1

W2-Q2 - Communication graphs

We thank the reviewer for pointing out this discrepancy. The communication axes in the figures were inadvertently plotted using normalized communication values (involving FP16 word-size and training-step normalization), rather than actual cumulative transmitted bits. We agree that this normalization was unnecessary and have revised the figures to report cumulative communication directly in bits. In our experiments, ResNet-18 has d=11,689,512d=11{,}689{,}512 trainable parameters, with cmax⁡=16dc_{\max}=16d bits. For sparsification, c(C)=400,000c(\mathcal C)=400{,}000 and c(C′)=200,000c(\mathcal C')=200{,}000 bits (corresponding to k=10,000k=10{,}000 and k′=5,000k'=5{,}000, respectively, using 16-bit values and 24-bit indices). For QSGD, c(C)=35,608,552c(\mathcal C)=35{,}608{,}552 and c(C′)=23,379,040c(\mathcal C')=23{,}379{,}040 bits, corresponding to s=2s=2 and s′=1s'=1, respectively. Appendix C.1 provides the exact communication-cost formulas for both Rand-kk and QSGD (these numerical values follow directly by substitution).

Importantly, this correction only affects the scale of the x-axis. Since the normalization was applied uniformly across all methods within each graph, their relative comparisons, and consequently our conclusions, remain unchanged. We further clarify that the communication accounting, in both the original and revised figures, includes all transmitted updates, including IER's uncompressed correction rounds and VR-MARINA's full-gradient refreshes.

Q3 - Error recycling ablation

We thank the reviewer for this valuable suggestion, which helps make our empirical analysis more complete. We have conducted the proposed matched-budget ablation, using the same full-precision communication schedule as IER but without accumulated residual correction. We included the results in the expanded ablation study in Appendix D.4 ("Periodic Dense SGD" in Fig.7).

The results show that IER performs substantially better, demonstrating that its improvements cannot be attributed merely to occasional full-precision updates. Rather, they highlight the importance of IER's accumulated compression-error correction mechanism, which explicitly recovers information lost during compressed communication.

We thank you again for your review and important suggestion, which helped improved our paper, and we look forward to your response.

Thank you for the clarifications and extra ablation, which take care of my communication accounting as well as residual recycling issue. Better worker dependence is gain, but EF21-SGDM already has the same leading stochastic rate, while IER is bounded heterogeneity. Moreover, no matter how small the proposed step-size-scaling coefficient B remains, it forgoes the dependency on extreme sparsification where S(t)→0S(t) \rightarrow 0 (in the extreme case S(t)=1S(t)=1). Although the empirical results are convincing, this incremental contribution is still not enough for an acceptance and I keep the same score.

We thank you for your thoughtful follow-up. We are glad that our response addressed several of your concerns, and particularly appreciate your acknowledgment that our empirical results are strong and convincing. We would like to further clarify the significance of IER's improved worker dependence, which we believe constitutes a substantial contribution beyond the shared leading stochastic rate.

Significance of improved worker dependence.

We respectfully emphasize that this improvement addresses a well-recognized, fundamental challenge in distributed optimization: compression-dependent terms that do not improve with the number of workers can severely limit parallel scalability, even when the leading stochastic term achieves the optimal O(σ/MT)O(\sigma/\sqrt{MT}) rate.

This challenge has been extensively studied and emphasized in the compression literature [1-4]. In particular, Huang et al. [1] explicitly analyze this limitation across several established compression methods, highlighting its detrimental effect on distributed scalability. Importantly, Fatkhullin et al. [2] themselves explicitly identify this as a limitation of EF21-SGDM, emphasizing that its intermediate terms can dominate the optimal stochastic term as the number of workers grows, negatively impacting its finite-time complexity across all problem parameters.

IER directly addresses this limitation through a distinct correction mechanism, exploiting the fundamental observation that compression noise, unlike inherent stochastic gradient noise, can be tracked and exactly corrected. IER achieves compression-dependent terms that improve with MM, unlike those of EF21-SGDM. Consequently, the training horizon required for this compression-dependent term (1/(M1/3T2/3)1/(M^{1/3}T^{2/3}) for IER and 1/T2/31/T^{2/3} for EF21-SGDM) to become dominated by the leading stochastic term grows as O(M3)O(M^3) for EF21-SGDM, compared with only O(M)O(M) for IER (holding other parameters fixed). Thus, EF21-SGDM's compression penalty can hinder the benefits of parallelism over finite training horizons, while IER substantially mitigates this scalability bottleneck. This constitutes a meaningful improvement in finite-time distributed scalability, beyond matching the asymptotic stochastic rate, as explicitly acknowledged by [1-4]. Regarding heterogeneity, IER's assumption is particularly natural in the widely used data-parallel settings which remain a significant and popular training framework [5-7].

Importantly, these theoretical improvements are strongly supported by our extensive empirical evaluation. We demonstrate substantial improvements in convergence per training step, communication efficiency, and actual wall-clock time, across multiple datasets, vision and NLP tasks, worker configurations, and compression schemes (Rand-kk, Top-kk, QSGD, and the DIANA quantizer). Our direct comparisons with EF21-SGDM under matched communication budgets further demonstrate substantial practical gains, even under extreme sparsification. Thus, IER's contribution goes beyond improved theoretical upper bounds: its distinct correction mechanism delivers substantial, consistently observed practical benefits, supporting its significance beyond an incremental refinement.

We will update the paper to reflect and position this more thoroughly.

Clarification regarding BB and S(t)S(t).

We are not entirely sure what the "step-size-scaling coefficient B" and S(t)S(t) mentioned in your response refer to, as we do not use this notation or any additional step-size-scaling mechanism in our paper. Nevertheless, regarding extreme sparsification, our matched-budget experiments demonstrate substantial improvements over EF21-SGDM even at the extreme 0.1% density, across multiple settings.

We thank you again for your review, additional reply, and helpful suggestions, which helped our make our paper clearer and more complete!


References

[1] X. Huang, Y. Chen, W. Yin, and K. Yuan. Lower Bounds and Nearly Optimal Algorithms in Distributed Learning with Communication Compression. NeurIPS, 2022.

[2] I. Fatkhullin, A. Tyurin, and P. Richtárik. Momentum Provably Improves Error Feedback! NeurIPS, 2023.

[3] K. Huang and S. Pu. CEDAS: A Compressed Decentralized Stochastic Gradient Method with Improved Convergence. IEEE, 2025.

[4] C. Chen, C. Ma, Z. Li, Y. He, Y. Dong, and K. Yuan. An All-Reduce Compatible Top-K Compressor for Communication-Efficient Distributed Learning. IEEE (CloudCom), 2025.

[5] Li et al. PyTorch Distributed: Experiences on Accelerating Data Parallel Training. PVLDB, 2020.

[6] Khaled et al. Tighter Theory for Local SGD on Identical and Heterogeneous Data. AISTATS, 2020.

[7] Karimireddy et al. SCAFFOLD: Stochastic Controlled Averaging for Federated Learning. ICML, 2020.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.