acceptodds
Under review as a conference paper at ICLR 2027

Error Feedback for Accelerated Distributed Optimization with Single Compressed Uplink

51 views

Abstract

Distributed optimization across multiple workers can incur substantial communication costs due to frequent exchange with a central server. Compressing high-dimensional gradients alleviates this bottleneck, but biased compression introduces persistent errors that complicate acceleration. Error feedback can correct compression error, yet combining it with Nesterov acceleration is subtle because acceleration accumulates gradient-estimation errors with time-varying weights. We introduce , a Nesterov-aligned error-compensation method for smooth distributed convex optimization. Each worker compresses a gradient-difference message corrected using its two most recent controlled-error states, with coefficients chosen so that the Nesterov-weighted history of gradient-estimation errors telescopes to the current averaged error state. Consequently, EC-NAG requires only one compressed uplink vector per worker per iteration. We develop a non-asymptotic analysis and show that EC-NAG preserves the deterministic accelerated rate, while in the stochastic setting it achieves the standard decay. Thus, we match the stochastic lower-bound exponent in . Experiments on distributed least-squares and classification problems demonstrate favorable convergence as a function of communicated uplink bits.

Primary area:
optimization
Keywords:
distributed optimization, stochastic optimization, compression, error feedback, Nesterov acceleration, biased contractive compressor

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_WciKOpenReview ↗
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 O(1/T2)O(1/T^2) convergence in the deterministic setting and O(1/T)O(1/\sqrt{T}) 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 O(1/T2)O(1/T^2) deterministic convergence rate and an O(1/T)O(1/\sqrt{T}) 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 nn, 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 nn, unlike ADEF. Is this limitation inherent to the proposed single-uplink mechanism, or could a tighter analysis recover the 1/n1/n dependence?

1 comment

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)O(T^{-2}) convergence and match ADEF's compression-independent leading stochastic term, O(D2σ2/(nbε2))O(D^2\sigma^2/(nb\varepsilon^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/n1/n? It does now in the revised analysis for the leading stochastic term. The remaining mixed ε−3/2\varepsilon^{-3/2} term has no 1/n1/n factor in either displayed bound. Ours includes 1−δ\sqrt{1-\delta}, 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/n1/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 nn 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.

Reviewer_murzOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies distributed optimization with contractive compression. To improve the convergence guarantees, the authors propose to incorporate the states from previous iterations, as well as the Nesterov-type weighting of previous gradients, into the algorithm design. This allows the authors to obtain an accelerated convergence rate. In contrast to prior work, this result is obtained with a single compression call on the client side. The experiments on simple problems demonstrate that the algorithm can be competitive in practice.

Critical strengths
  • The authors propose an algorithm that achieves an accelerated convergence rate using Nesterov-type acceleration. Importantly, this is achieved by using only a single compression call by the clients. The authors also propose a clear and intuitive explanation behind the algorithm design to achieve improved convergence, based on gradient tracking.

  • The analysis is conducted under standard assumptions without imposing strong heterogeneity bounds. I also find the analysis to be clean and without crucial mistakes.

  • The experiments on least-squares demonstrate that the algorithm is competitive in practice in controllable settings.

Critical weaknesses
  • The paper does not contain AI Usage Statement, violating the ICLR 2027 guidelines.

  • The stochastic term in the rate is not optimal. Instead of σ2D2nε2\frac{\sigma^2D^2}{n\varepsilon^2} it is also affected by the compression ratio δ\delta as σ2D2ε2\frac{\sigma^2D^2}{\varepsilon^2}. In practice, δ\delta is small; therefore, this is a crucial limitation of this work. The authors should have discussed this limitation in the paper and added it to the conclusion. I also believe that it should have been studied at least in practice to demonstrate that the algorithm's performance doesn't degrade that badly with δ\delta in practice. This is the most crucial weakness of this work: using one compression call comes with a significantly worse stochastic term in the rate.

  • The experiments are too simple and not realistic. I acknowledge that the main contribution of this work is a theoretical analysis of the proposed algorithm, but understanding the practicality of the algorithm is also important, since the main motivation comes from real-world applications. Adding experiments on Resnet/ViT-type models on CIFAR10/CIFAR100/Imagenet1k datasets and NanoGPT-type models on Fineweb dataset would improve the paper.

  • No experiments that verify the theoretical analysis in controllable settings. Adding experiments that show the scaling with \detla\detla and bb would improve the paper. Typically, the convergence of non-distributed algorithms can improve with increasing batch size. Therefore, it is important to show the benefits of EC-NAG across multiple batch sizes.

  • The authors have misleading sentences like the ones in lines 315-317. The leading stochastic term in ADEF does not have δ\delta terms. It is contained in higher-order terms. The authors should be careful with wording.

  • The statement of Theorem 1 requires setting q0i=C(ui0)=u0iq_0^i = C(u_i^0)= u_0^i, i.e., no compression at the first stage. This can be crucial in practice, when transmitting the full stochastic gradient is infeasible.

  • [minor] Some parts of the paper are not compiled correctly. For example, the titles in Figure 2 are cut off.

Questions for authors
  • The analysis is based on the idea of using virtual iterates. Acknowledging that this technique is well-known in the literature and adding references to prior works that also use it is a standard practice to give proper credit to foundational techniques and help readers navigate the background material

  • Since the analysis uses a heavy notation, I encourage the authors to add a table of notation to help navigate the readers.

  • Can ideas like using momentum tracking instead of gradient tracking improve the stochastic term in the rate?

  • Adding a table with the convergence rate derived in this work and prior work would improve the readability. It would allow readers to understand how the rate is improved in this work directly.

  • Can the authors comment on the following: ADEF's convergence rate has 3 terms (stochastic, deterministic, and intermediate), while EC-NAG has only two. Where does the difference come from? Is it the reason, why the stochastic term in this paper is not optimal?

  • Can this algorithm be extended to server-side optimizers like DiLoCo? Can this help with improving the convergence analysis?

3 comments

Thank you for being so specific about where the paper fell short. Your concern that one compression call came at the cost of the leading stochastic term went to the heart of the work. It sent us back to the proof, and we are grateful for that push.

1. Stochastic rate and why there are now three terms. You were right that ADEF's leading stochastic term is compression-independent and that our original wording obscured this difference. Under the comparison convention in Table 1, we now have the following sufficient iteration count:

\frac{D^2\sigma^2}{nb\varepsilon^2} + \frac{D^2\sqrt{L}\\,\sigma\sqrt{1-\delta}}{\delta^2\sqrt{b}\\,\varepsilon^{3/2}} + \frac{D\sqrt{L}}{\delta^2\sqrt{\varepsilon}} \right).$$ The old analysis bounded ordinary oracle noise and compression of noisy gradient differences at the same order. In the revised finite-horizon inequality below Theorem 1, they enter with different powers of the stepsize scale, $M^{-1}$ and $M^{-2}$. Balancing them separately yields $T^{-1/2}$ and $T^{-2/3}$ in the objective gap, alongside the deterministic accelerated term. The resulting bound matches ADEF's leading stochastic term with one compressor call. Sec. 3 explains when it can dominate, and Sec. 4 qualifies worker speedup as asymptotic. **2. Compression, batch size, and larger models.** **Figs. 1–3 in Sec. 4** now vary $\delta$, $b$, and $n$ using a common target of $10^{-2}$. We agree that a neural-network experiment would help assess practicality. We could not complete the ResNet-18 experiment in time for this revision. We will finish it and would appreciate the opportunity to include the results in the camera-ready version if accepted. **3. Initialization, attribution, and presentation.** **Theorem 1** now allow a compressed first message, $q_0^i=C(g_0^i)$, as used in the Top-K runs. The result shows that the initialization error contributes a transient that decays as $T^{-2}$. Table 1 compares rates and communication requirements, Table 2 collects notation, and Sec. 3 adds a proof sketch. Sec. 1.1 now credits the earlier virtual-iterate analyses of Karimireddy et al., Stich and Karimireddy, and Gao et al. The AI Use Statement is also included. We have also addressed other minor concerns. **4. Momentum tracking and DiLoCo.** Local momentum tracking could smooth the mini-batch noise entering the compressor. To establish an improved rate, we would need to control the tracking bias and recover the weighted error cancellation. A DiLoCo-style extension is definitely possible and could compress differences of local model updates, but those updates incorporate drift across local steps. An extension of the analysis would need to control that drift alongside compression error. Your review pushed us to improve the proof, test the remaining trade-off, and make the paper easier to read. We would be grateful if you would take another look and reconsider your recommendation in light of the revision.
Reviewer_murzOpenReview ↗

Response to the rebuttals

I thank the authors for posting the rebuttals.

  • However, given the short time to check them, I would like to ask for the detailed explanation behind the proof updates to obtain the new rate. Without it, I cannot check the meaningfulness of the rate in a short time. Interestingly, it matches the rate of ADEF with only one compressed message.

  • I do not see the updates in Figures 1-3, as well as other additions mentioned in the rebuttals. Can the authors check that they uploaded the revised file?

  • Please explain why the initialization can use only the compressed message. What was changed in the proof?

Thank you for following up and for flagging the version discrepancy. We appreciate that a changed rate is hard to assess on a short timeline, so we give the key derivation directly here. The equation numbers below refer to the latest revision.

1. What changed in the proof. The decisive change is the weight on the squared compression error in the inexact-NAG lemma. The original Eq. (80) had a constant contribution to that weight. In the revised proof, Eq. (88) evaluates the stochastic-oracle cross term exactly by conditioning on the past. Eq. (89) uses the full Bregman term toward the minimizer in a single Young bound on the gradient–error cross term. With the Young parameter set to 2, the resulting error weight is in Eqs. (71). For at=(t+c)/Ma_t=(t+c)/M and ηt≤2/M\eta_t\le 2/M, this gives wt=O(L(t+c)/M)w_t=O(L(t+c)/M). Keeping this dependence on MM is what changes the order of the compression term.

The coupled state estimate (126) bounds the weighted residual sum by movement terms, local stochastic noise, and a boundary term from initialization. Average smoothness converts the movement terms into the two Bregman divergences retained in Lemma 1, and the stability conditions (128) allow those terms to be absorbed. The remaining local-noise contribution is proportional to (σ2/b)∑t=1T−1wt+1at+12(\sigma^2/b)\sum_{t=1}^{T-1}w_{t+1}a_{t+1}^2. Using AT≥(T+c)2/(2M)A_T\ge(T+c)^2/(2M), the weighted sum divided by ATA_T is bounded by O(LT(T+c)/M2)O(LT(T+c)/M^2). The ordinary oracle noise enters separately and benefits from averaging independent workers. The resulting Eq. (138), p. 34, is

\frac{c^2F_0+D^2M}{(T+c)^2} +\frac{3\sigma^2 T}{2nbM} +\frac{125L(1-\delta)\sigma^2 T(T+c)}{b\gamma^2\delta^2M^2} +\frac{27(c+1)^2E_0^2}{\gamma^2\delta M(T+c)^2},$$ where $F_T=\mathbb E[f(y_T)]-f^{\star}$ and $c=10/\gamma$. In the original Eq. (147), both stochastic contributions scaled as $M^{-1}$. Here, balancing the $M^{-1}$ oracle term and the $M^{-2}$ compression term separately against $D^2M/(T+c)^2$ gives a square-root and a cube-root choice of $M$, respectively. The corresponding gap terms decay as $T^{-1/2}$ and $T^{-2/3}$. On inversion, **Eq. (23), p. 7**, therefore matches leading $O(D^2\sigma^2/(nb\varepsilon^2))$ term with one compressor call. **2. Why the first message can be compressed.** The original Appendix D.2 too tracked nonzero initialization error in Eq. (151), while the main theorem set it to zero only for simplicity. However, in the revised **Eq. (19) and Theorem 1**, we retain $E_0$. In the weighted recursion **(126)**, the initial residual contributes only a boundary term, which yields the last term in Eq. (138). Balancing it gives an additional $O(DE_0/(\gamma^2\sqrt{\delta}\\,T^2))$ contribution in **Eq. (22)**. Thus the compressed start adds a $T^{-2}$ transient and preserves the leading stochastic rate. Eq. (23) takes $E_0=0$ for the direct ADEF comparison. **3. Identifying the revised PDF.** The revised PDF is already on OpenReview, and we can view it on our end. Thank you for flagging the discrepancy. We’ll upload it again, and if you still can’t access the revised version, we'll reach out to the OpenReview team. We appreciate the opportunity to clarify the proof. Please let us know if there’s anything else we can clarify or provide.
Reviewer_FrN3OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

The paper considers the problem of distributed optimization of a function

f(x) = \frac{1}{n} \sum_i f_i(x)

where the i-th worker is responsible for computing the gradient of f_i(x).

The paper considers scenarios where x \in \mathbb{R}^d and d is very large. Accordingly, the gradients sent by the workers are compressed before sending to keep the communication overhead manageable. However, many compressors are biased and hence error feedback is used to allow for convergence of the optimization over iterations. While this is relatively well understood for vanilla GD and SGD algorithms, the paper specifically considers Nesterov accelerated methods, where this is harder to do.

As I understand it, the main selling point is that their EC-NAG algorithm only transmits one compressed vector per iteration, that compresses a gradient difference term plus two corrections that depend on the two most recent error states. Other algorithms such as prior work ADEF send at least two compressed workers per iteration.

Under L-smoothness, bounded variance stochastic gradients and a specific class of contractive compressors, the manuscript shows an O(1/\sqrt{T}) convergence in the stochastic setting.

Editorial note - The paper does not have the required AI use statement.

Critical strengths
  1. The update equations in the paper appear to be sound.

  2. The O(1/\sqrt{T}) convergence appears to be correct and a good result.

  3. The stated results also appear to be an improvement over the current state of the art, though I do have questions about it.

Critical weaknesses

I should clarify that I am not an expert in this area. Nevertheless, I tried my best to read the paper as carefully as possible. That said there are about 8 pages of actual text in the paper and over 23 pages of Appendix that go over some rather detailed calculations. In fact, apart from the main algorithm, most of the paper is in the Appendix. With the current review backlog, I was not able to go over the Appendix in detail.

  1. The comparison with T_{ADEF} needs to be done more carefully. In particular, just a quick look at the result of the ADEF paper seems to suggest that their 1/\epsilon^2 term is scaled by 1/n whereas, in the current manuscript one part of the term is like C_1/\epsilon^2. My understanding is that communication becomes a bottleneck in the regime when n is large. So, this should be clarified.

  2. The above point also makes me wonder if indeed the reduction from two messages to one indeed translates into a lower communication cost, if one wants to reach the same accuracy.

  3. The paper lacks the required AI use statement.

Questions for authors

Given the review backlog in current-day ML conference, it is not reasonable to have a paper that has almost all details in the Appendix. The current manuscript has very dense calculations in the Appendix; perhaps unavoidably so. However, in its current form, the manuscript may be better suited to an optimization journal or equivalent, where a careful examination of the underlying mathematics can be undertaken.

1 comment

Thank you for taking the time to work through a dense submission. The fundamental question we address is whether one compressor call per worker can preserve both Nesterov acceleration and leading-order stochastic worker speedup. The key step is where the entire weighted error history into the current averaged error state:

∑s=0tas+1(g^s−gs)=at+1et.\sum_{s=0}^{t} a_{s+1}(\widehat{g}_s-g_s)=a_{t+1}e_t.

Making the argument accessible in the main text. We understand your concern about how much of the paper a conference reviewer could assess without working through the appendix. The proof sketch with Theorem 1 explains how we bound that state and displays the finite-horizon inequality that separates oracle noise from compression noise. The comparison with ADEF follows. Appendix D supplies the detailed derivations, and Tables 1 and 2 put the rate comparison and notation in the main text. We removed the former Appendix B.1, which motivated the use of gradient tracking in the compressor input. We can further remove the background on classical NAG in Appendix A and the extended motivation in Appendix B if the reviewer wants.

Your concern about the 1/n1/n factor was well founded. The original result included a compression-dependent ε−2\varepsilon^{-2} contribution without 1/n1/n scaling. Revised result recovers the same compression-independent leading stochastic term as ADEF, O(D2σ2/(nbε2))O(D^2\sigma^2/(nb\varepsilon^2)). The mixed stochastic-compression term is now of order ε−3/2\varepsilon^{-3/2} and has no 1/n1/n factor in either bound. It can still matter at finite accuracy, especially with many workers or aggressive compression. The leading term gives asymptotic linear worker speedup for fixed nn, bb, and δ\delta and positive stochastic variance.

Your review helped us improve both the guarantee and the way we present it. We also added the AI Use Statement. We would be grateful if you would reconsider your recommendation in light of the revision.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.