- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
This paper introduces EC-NAG, an accelerated error-feedback method for smooth convex distributed optimization that requires only one compressed uplink transmission per worker per iteration. Its core idea is a Nesterov-aligned error-compensation mechanism that causes the weighted gradient errors to telescope. The method attains convergence in the deterministic setting and in the stochastic setting. Experiments on least-squares and logistic-regression problems show that it improves communication efficiency over existing methods.
Critical strengths
The paper proposes a Nesterov-aligned error-feedback mechanism built on a weighted telescoping identity. This design enables acceleration with only one compressed uplink per iteration, thereby reducing communication compared with ADEF.
The paper establishes an deterministic convergence rate and an stochastic rate. Experiments demonstrate favorable performance relative to existing methods in terms of cumulative uplink bits.
Critical weaknesses
The primary improvement over ADEF (Gao et al., 2026) is that it reduces the number of compressed uplink vectors per iteration from two to one. Although technically interesting, this amounts to only a constant-factor reduction in communication and does not improve the asymptotic convergence rate or provide a stronger overall communication-complexity guarantee.
Its stochastic convergence guarantee is weaker than that of ADEF (Gao et al., 2026) in terms of dependence on the number of workers. Specifically, the compression-induced stochastic error term does not diminish with , so the analysis does not preserve the asymptotic linear speedup established by ADEF.
Reference: Gao, Y., Rodomanov, A., Rack, J., & Stich, S. U. (2026). Accelerated Distributed Optimization with Compression and Error Feedback. AISTATS 2026.
Questions for authors
Beyond the constant-factor reduction from two compressed uplink vectors to one, what are the main theoretical or practical advantages of EC-NAG over ADEF? Could the authors characterize more precisely the conditions under which this reduction translates into improved overall communication efficiency?
The stochastic convergence bound includes a compression-induced error term that does not decrease with the number of workers , unlike ADEF. Is this limitation inherent to the proposed single-uplink mechanism, or could a tighter analysis recover the dependence?
Thank you for pressing us on what the single uplink buys at a fixed accuracy and whether the weaker worker dependence was inherent. Those were the right questions to ask of the original submission, and they helped us sharpen the result.
What the construction establishes. The fundamental question we answer is whether Nesterov acceleration and leading-order stochastic worker speedup can coexist with one compressor call like its already known for unaccelerated algorithms. The two-lag correction gives the exact weighted cancellation that makes this possible. Revised Theorem 1, retain deterministic O(T−2) convergence and match ADEF's compression-independent leading stochastic term, O(D2σ2/(nbε2)), under the same problem, oracle, and compressor assumptions. There is also a per-round computation benefit. ADEF's second compressor input depends on the tracking update produced by its first call. EC-NAG removes that sequential stage as well as the second payload. With equal-sized compressed payloads and equal startup costs, EC-NAG saves uplink bits to reach the same target as demonstrated through our experiments.
Could tighter analysis recover 1/n? It does now in the revised analysis for the leading stochastic term. The remaining mixed ε−3/2 term has no 1/n factor in either displayed bound. Ours includes 1−δ, so this term vanishes near exact communication. As discussed in the paper, biased compression residuals can have nonzero conditional means, so cross-worker terms can survive even with independent mini-batches. Whether a sharper analysis can recover 1/n in that mixed term remains open. The same discussion gives the accuracy regime in which the leading term dominates the mixed term, explaining why the latter can still matter as n grows at a fixed target.
We are grateful that your questions pushed us to make the contribution and its limits clearer. We hope the revision addresses your major concerns; we would appreciate your reconsidering the recommendation.