- Rating
- 3(+1)
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper designs two algorithms for decentralized training with compression. They focus on the algorithm design with discounted error feedback, which allows balancing the error term into the next iterations through a multiplier. Such an idea was primarily studied in a centralized setting, so this paper extends the study to a decentralized setting.
Critical strengths
-
The dependency on the network topology is improved for the proposed algorithms compared to prior work. This is important, especially in the case of sparse communication networks.
-
The analysis is performed with and without the bounded gradient divergence assumption. To mitigate the use of this assumption, the authors incorporate standard gradient tracking into the algorithm design. This is an important step since it allows theoretical convergence without heterogeneity bounds, an important feature in federated learning applications.
-
The experiments demonstrate improved performance of the proposed algorithms in practice over existing baselines.
-
I went over the proofs and did not find any problems
Critical weaknesses
-
The motivation behind the use of discounted error feedback is not clear enough. It is unclear to me why we should focus on it. It is one of the ways that worked in the centralized setting, but there are other existing ideas. I encourage the authors to provide more discussion around it and explain why they chose to focus on it. This would make the motivation of the work clearer.
-
Figure 1 is not understandable. The text provides insufficient information to understand the idea behind it. It is not clear what is being tested there, what is changing, and so on. The authors should provide a clearer description of Figure 1, which serves as some sort of motivation that the naive idea of discounted error feedback might fail.
-
The influence of compression on the convergence is hidden in the main part. Since it is a main focus of the work, it must be shown explicitly in the main part.
- In particular, for A-DEFEAT-GT, the compression factor affect the deterministic term and the middle term . This means that the improvement in the topology comes with deterioration in the compression, since the optimal deterministic term is .
- Moreover, it seems that is also present in term through , which goes against lower bounds. This constant can significantly slow down the convergence (take ; I think the term grows with both and , while it should only with )
- For A-DEFEAT, the deterministic term becomes optimal, but at the cost of using a gradient divergence assumption.
- Therefore, the authors should discuss these limitations of the analysis, whether it's an artifact of the analysis or a property of the algorithms. I suggest adding controllable experiments that satisfy the assumptions and demonstrate that these limitations of the analysis are not critical.
-
The convergence is limited to the general non-convex setting. EControl's analysis, where the discounted error feedback was proposed, demonstrates convergence in three cases: non-convex, convex, and strongly convex. This is not the case for an alternative EF21-SGDM algorithm. The authors should discuss whether the analysis can be extended to convex and strongly convex cases to demonstrate this flexibility also in the decentralized setting.
-
The choice of hyperparameters in practice might violate the theoretical restrictions; I believe there is not enough information to confirm this. Therefore, I encourage the authors to discuss whether there is indeed a gap between theory and practice.
Questions for authors
- Can the authors clarify what ? What should be taken to here? Is it always satisfied, or only for some particular cases?
7 comments
W3(a). Thank you for highlighting this distinction. We agree that the explicit A-DEFEAT-GT bound has weaker compression dependence: the deterministic term scales as , and the term scales as . Our result therefore does not establish optimal compression dependence or a uniformly better joint dependence on compression and topology. Our contribution concerns the improved spectral-gap exponents under the stated assumptions. For example, compared with MoTEF, the topology factors improve from to in the deterministic term and from to in the intermediate stochastic term, while the compression factors worsen. Thus, the comparison depends on both network connectivity and compression quality. Under the bounded-gradient-divergence assumption, A-DEFEAT already achieves the same dependence in the and dependence in the . In our current analysis, controlling the compressed model and tracker updates together leads to larger compression penalties, which is in the objective-gap term and in the term. The additional compression factors arise in our sufficient stability analysis of the coupled compressed model and tracker recursions. We do not establish that this deterioration is unavoidable for the algorithm. Obtaining sharper joint dependence remains an open direction. We discussed the dependence on in Appendix H, but we will make it clear in the final manuscript.
W3(b). We agree that the initialization term can be large and represents a limitation of our finite-time guarantee. We will add this limitation in Appendix H in the final manuscript. Nevertheless, we believe this is a limitation of our analytical approach for gradient tracking and would like to point out that similar initialization dependence appears in the gradient tracking related methods. The stochastic contribution arises because the tracker is initialized with stochastic gradients. For example, initial Lyapunov terms also appear in BEER (Theorem 2), while MoTEF (Remark 2) retains its initial Lyapunov value under single-sample initialization.
We also would like to point out that, for a fixed problem with positive stochastic variance, this contribution decays as , faster than the leading stochastic term, and therefore does not alter the asymptotic convergence rate or linear speedup. In the deterministic setting, the guarantee remains , with an initialization-dependent coefficient. Our guarantee avoids a uniform bounded-heterogeneity assumption while retaining the initial-gradient contribution. Hence, we believe this is a limitation of our analysis but it is not a critical weakness.
W3(c). Yes. This is exactly the benefit and the limitation of A-DEFEAT. It can improve the dependence on the compression factor but at the cost of the requirement of the bounded gradient divergence assumption. Removing the bounded gradient divergence assumption is a principal motivation for introducing gradient tracking. This tradeoff is also shown in the experiments in Appendix I. However, we do not believe this is a weakness of our paper rather than a limitation of A-DEFEAT algorithm.
W3(d). We agree that the distinction between limitations of the analysis and limitations of the algorithms should be clarified. Based on our above comments, we will explicitly discuss the compression–connectivity tradeoff, the dependence on initial local-gradient norms, and the limitation of A-DEFEAT in the final manuscript. These factors arise in sufficient upper bounds, and we do not claim that their precise powers are necessary.
Our existing experiments provide evidence of useful performance across the evaluated network and heterogeneity settings. For example, on FashionMNIST with 5% top- compression and Dirichlet parameter , A-DEFEAT-GT maintains approximately 81% accuracy across rings with 10–200 nodes. These results support practical effectiveness in those settings. They do not isolate the individual theoretical factors or establish that all sufficient theorem conditions hold. Accordingly, our conclusions are limited to improved proved network dependence under the stated conditions and empirical effectiveness in the evaluated settings. We do not claim that the remaining dependencies are tight or practically negligible throughout the admissible problem class.
We will add controllable experiments (synthetic problems, possibly extension of the motivating example) in the final manuscript.
W4. Our main focus is smooth nonconvex optimization, motivated by objectives that arise in decentralized neural-network training. The cited analyses of DCD, DeepSqueeze, CHOCO-SGD, BEER, and MoTEF all cover smooth nonconvex objectives. Only CHOCO-SGD and MoTEF also cover the strong convex objectives. The smooth nonconvex setting therefore provides a common basis for comparing the methods. Our derivations can be extended to the convex cases with the different convergence bound and rate. We agree that deriving the rates that exploit convexity or strong convexity would complement the current analysis, and we leave this to future work due to the current length of our paper.
W5. Thank you for raising this point. We agree that the relationship between the theoretical restrictions and the experimental hyperparameters needs clarification. Our convergence guarantees require explicit stability conditions and learning-rate bounds, whereas the experiments select learning rates and tracker stepsizes empirically and use consensus gain . Other hyperparameters are chosen based on the theoretical conditions as discussed in the response to Reviewer 63EM. Thus, there is a gap between the parameter regime covered by our guarantees and the settings used in these experiments.
As we mentioned before, these conditions are sufficient, and we do not establish their necessity. Their violation therefore means that our theorems do not certify the corresponding runs; it does not imply that the algorithms must diverge. The experiments demonstrate practical performance beyond the certified regime, but they do not validate the convergence bounds in that regime. Our constructive consensus-gain choice provides an admissible regime for any fixed compression level, subject to the remaining assumptions and stepsize restrictions, but that choice was not used in the reported experiments.
We will make this distinction explicit in the experimental discussion and limitations, report the selected hyperparameters alongside the applicable theoretical restrictions, and identify conditions that fail or remain unverified. Extending the guarantees to the empirically effective parameter regime remains an open problem.
Q1. Here, means uniformly bounded away from zero; no quantity is required to tend to infinity. We will replace the notation with the explicit condition
where is a fixed numerical constant across the network and compression settings under consideration. This is a sufficient condition in Theorem 4.1, ensuring uniform control of the stability constants in the convergence guarantee.
We thank the reviewer for the careful reading and provide so many instructive comments, including the check of all the proofs. We would like to address the comments as follows.
W1. This is a very good comment. Our original goal was to design an efficient local error-feedback scheme for decentralized learning, where residual correction can be adjusted directly without necessarily attenuating the entire consensus correction. The reason we are using error-feedback is that it is an effective approach to compensate the error due to compression and it has been used in other papers. Centralized methods such as EControl provide a useful starting point by introducing a coefficient to regulate feedback strength. However, unlike EControl's shared-model, server-based setting, decentralized nodes maintain different local models and exchange information only with neighbors. Compression residuals therefore influence both local optimization and subsequent consensus dynamics, making their control a distinct decentralized challenge. This motivates introducing a dedicated coefficient on the residual entering each compressed model update. Its role differs from the consensus gains in CHOCO, BEER, and MoTEF, which scale the consensus correction. Furthermore, because the relative magnitudes of the residual and the current tracked update vary across nodes and training stages, we adapt this coefficient locally using their clipped norm ratio. The residual accumulates past compression errors, whereas the current tracked-gradient step reflects the present optimization scale. Comparing these quantities lets us adjust the feedback strength when accumulated errors become large or small relative to the current update. Our objective is to develop locally adaptive residual correction with a convergence guarantee under explicit conditions. This combination of direct residual control, local adaptation, and theoretical analysis explains our focus on adaptive discounted error feedback.
W2. Figure 1 is a toy motivating example that isolates the effect of the feedback-coefficient rule on a four-node quadratic optimization problem. It compares two fixed coefficients, γ=0.1 and γ=1, with an adaptive feedback rule, while keeping the data, initialization, sample sequence, and other settings identical. The example uses a ring network, learning rate η=0.1, the dense contractive map C(b)=0.05b, and averaging weights of 1/3 for each node and its two neighbors. Each panel shows node 1's trajectory over 40 iterations; the blue arrow indicates its final distance to the global minimizer. The purpose is to illustrate that choosing a fixed discount coefficient can substantially affect the trajectory, and that adapting the correction to the relative magnitudes of the local gradient and accumulated residual can be beneficial. The adaptive choice achieves a smaller final distance in this example, providing motivation for our design. We agree that the original description can be improved and will expand the caption and Appendix A with these settings, the precise adaptive rule and update order, and clear definitions of the plotted markers.
W3. Explicit compression dependence. We would like to thank Reviewer vZ3n for this comment. We will include the compression parameter explicit in all the theorems in the main paper. Currently, the explicit compression dependence is shown in Appendix F, Corollaries F.3 and F.5, equations (75) and (78), and the limitations of A-DEFEAT-GT and A-DEFEAT are discussed in Appendix H. All explicit dependence on β and ρ for the convergence upper bound is shown in Appendix G.
The appendix corollaries use consensus gain (67) and their respective prescribed stepsizes. For A-DEFEAT-GT, Corollary F.3 additionally chooses τ=1/2; this is a sufficient choice for the explicit corollary, while the main Theorem 4.1 allows general τ satisfying its stated range and stability conditions. Under the assumptions stated in Theorem 4.1 and 4.2, the resulting rates are
RTGT=O(nTσLD+(1−β)4/3ρ2/3T2/3(LDσ)2/3+(1−β)2ρTLD+nρT∥F0Π∥F2+nTE∥G0∥F2),
and
RTA=O(nTσLD+(1−β)2/3T2/3(LD)2/3(ρσ2+ρ2ϵ2)1/3+(1−β)ρTLD),
where RT=T−1∑t=0T−1E∥∇f(xˉt)∥2 and D>0 bounds the initial objective gap. The A-DEFEAT rate additionally assumes bounded gradient divergence ϵ2.