- 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 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 where the constant 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
-
I believe that there is flaw in the case where momentum (Appendix B) is considered.
-
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.
-
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.
-
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 and . When , clearly the second term dominates. However, one needs . It is not clear from the results, how to interpret these. For instance in Fig. 1a, the so that needs be greater that . 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
-
Lemma B.4 in Appendix B is incorrect as stated. The justification from (76) to (77) is not valid. Note that is -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.
-
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 -measurable.
-
Typo - Equation eq. 31.
-
Supplement pg. 13, a different TeX symbol is used for epsilon.
Questions for authors
-
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.
-
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
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, , whereas we only assume bounded variance, . 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 , whereas ours depends on . The distinction between Karimireddy's versus IER's is substantial: can be much larger than , 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 , matching uncompressed distributed SGD.
- Compression-dominated regime: The compression-dependent term decays as , rather than the compression-inflated 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 , 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
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 should be replaced by the conditional expectation E[mt∣Ft].
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, which is strictly more restrictive than bounded stochastic-gradient variance, E∣g(x)−∇f(x)∣2≤σ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 ω in the leading stochastic term (in the stochastic-dominated regime), or by achieving faster decay with T (T−2/3 versus T−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.