- Rating
- 3
- Confidence
- 2
- Informativeness
- 3
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies decentralized smooth nonconvex optimization under heavy-tailed gradient noise with a fixed batch size per local update. The authors first establish a dimension-independent lower bound on the bias–MSE trade-off for fixed-sample mean estimation and propose a corrected three-block median-of-means (MoM) estimator that matches this bound up to constants depending on the moment parameter. Building on this estimator, they develop CRAFT, which combines robust gradient estimation, recursive filtering, and local gradient tracking. The theoretical analysis establishes stationarity and consensus guarantees and shows that allowing the local period to grow with the training horizon can reduce the sufficient communication complexity without increasing the order of sample complexity. Experiments on synthetic problems, image classification, and language modeling demonstrate the method's robustness and communication efficiency
Critical strengths
-
The paper establishes a dimension-independent lower bound for fixed-batch mean estimation under finite -th moment noise and proposes a corrected MoM estimator that matches the bound up to constants. This provides a principled motivation for combining a robust median anchor with a clipped correction toward the pooled mean. The estimator analysis is supported by numerical experiments examining the predicted bias and MSE scaling.
-
The convergence analysis shows that the local period can grow with the horizon while preserving the order of the total local-update and sample complexities. This is a useful theoretical result under fixed per-update batch sizes and heterogeneous local objectives. The experiments also show promising robustness under heavy-tailed perturbations, and the component ablations provide evidence for the complementary benefits of estimator correction and recursive filtering
Critical weaknesses
The communication complexity in Corollary 1 hides its dependence on network connectivity. Although the appendix provides constants involving , it remains unclear how the communication complexity scales with the network spectral gap and whether this dependence improves upon or matches that of existing decentralized methods.
Questions for authors
- The convergence bound contains the stochastic contribution , which does not exhibit an explicit variance reduction with the number of agents or the local period . Under the prescribed parameter choices, these terms scale as , and , respectively, where . Thus, the communication improvement does not appear to correspond to a linear speedup in the stochastic error terms. Is the absence of an -dependent improvement primarily due to allowing dependent gradient noises across agents? Could stronger assumptions, such as conditional independence across agents, yield a sharper stochastic bound while retaining the communication savings from local updates?
- Corollary 1 shows that increasing the number of local updates can reduce communication complexity, but only under certain restrictions on the growth of . Could the authors provide more intuition for why these restrictions are necessary? Are they mainly due to client drift and the accumulation of consensus and gradient-tracking errors between communication rounds, or are there other factors? It would also be helpful to clarify whether these restrictions are inherent to the proposed algorithm or arise from the current analysis.
5 comments
Response to Reviewer dU8w (2/3)
Question 1:
The convergence bound contains the stochastic contribution , which does not exhibit an explicit variance reduction with the number of agents or the local period . Under the prescribed parameter choices, these terms scale as , , and , respectively, where . Thus, the communication improvement does not appear to correspond to a linear speedup in the stochastic error terms. Is the absence of an -dependent improvement primarily due to allowing dependent gradient noises across agents? Could stronger assumptions, such as conditional independence across agents, yield a sharper stochastic bound while retaining the communication savings from local updates?
Response: We thank the reviewer for this insightful question. The absence of explicit -dependence partly reflects our allowance for dependent gradient noises across agents. Indeed, existing heavy-tailed decentralized analyses obtain agent-count speedup under stronger independence assumptions, including GT-NSGDm (Yu et al., ICLR 2026) and clipped decentralized SGD (Armacki et al., October 2026 arXiv preprint).
Under conditional independence across agents, the centered errors of CRAFT's corrected estimators satisfy
\left\\|\frac1n\sum_{i=1}^n\zeta_i\right\\|^2 \middle|\mathcal F \right] \le \frac{q_\kappa}{n}.$$ Thus, independence yields variance reduction in the network-averaged estimator. However, the estimator bias and local tracking and consensus errors do not generally enjoy the same reduction. Obtaining a sharper $n$-dependent stationarity bound therefore requires a refined analysis of these coupled errors. The existing communication guarantee remains valid under conditional independence, although simultaneous improvements in agent-count speedup and communication complexity are not established by our current analysis. To examine the potential benefit empirically, we **added a controlled experiment** with independent heavy-tailed noise and $n\in \\{4,8,16,32 \\}$ agents (cf. new Table 8 and Appendix I.5 of the revised manuscript). With the global objective, mixing contraction, per-agent batch size, local period, and algorithmic parameters fixed, the mean updates per agent needed to reach and retain gradient tolerance $10^{-4}$ decrease from 1694 ± 696 at $n=4$ to 796 ± 488 at $n=32$, over 40 paired seeds. These results suggest improved per-agent update efficiency under independent noise, but do not establish linear speedup or improved total sample complexity, since the system uses $6n$ samples per update. **References** - Yu et al. (2026). Decentralized Nonconvex Optimization under Heavy-Tailed Noise: Normalization and Optimal Convergence. ICLR. - Armacki et al. (October 2026 arXiv preprint). Decentralized SGD under Heavy-Tailed Noise: Optimal Convergence Rates and the Role of Gradient Clipping. arXiv preprint.Response to Reviewer dU8w (3/3)
Question 2:
Corollary 1 shows that increasing the number of local updates can reduce communication complexity, but only under certain restrictions on the growth of . Could the authors provide more intuition for why these restrictions are necessary? Are they mainly due to client drift and the accumulation of consensus and gradient-tracking errors between communication rounds, or are there other factors? It would also be helpful to clarify whether these restrictions are inherent to the proposed algorithm or arise from the current analysis.
Response: We thank the reviewer for this question. Increasing the local period reduces communication frequency but also allows local errors to accumulate before they can be corrected. During each communication-free interval, agents update their models using different local objectives and imperfect gradient estimates, causing their models and gradient trackers to diverge. This disagreement can distort subsequent local updates and further amplify the accumulated errors. Communication contracts disagreement, but less frequent exchanges provide fewer opportunities to correct it. Thus, controlling is important for obtaining convergence guarantees across heterogeneous objectives and stochastic noise conditions.
Beyond client drift, stochastic estimation errors and recursive filtering also contribute to this accumulation. These effects are coupled in our analysis, motivating the sufficient conditions and in Theorem 3. The growth restriction in Corollary 1 ensures that the resulting errors remain controlled under the prescribed parameter schedule. Although controlling accumulated local errors is important for convergence, the specific restriction is sufficient for our analysis and is not known to be necessary for CRAFT.
To illustrate this trade-off, we added a controlled synthetic experiment varying at a fixed budget of local updates per agent (cf., new Figure 15 and Appendix I.6 of the revised manuscript). Under independent heavy-tailed noise, increasing from 112 to 1120 reduces the communication needed to reach and retain a mean gradient norm below from 480 to 48 rounds, a 90% reduction. However, substantially larger periods retain higher gradient residuals over the same update budget, whereas their exact-gradient counterparts attain near-zero gradients in this example.
These findings illustrate the trade-off between communication savings and errors accumulated during local updates. While controlling these errors motivates an upper bound on the local period, the specific growth restriction in Corollary 1 is a sufficient condition of our analysis, not a proven necessary condition for CRAFT.
Response to Reviewer dU8w (1/3)
We thank the reviewer for the constructive comments and suggestions. In response, we have made the spectral-gap dependence of the communication bound explicit, clarified the effects of cross-agent noise dependence and the restrictions on local-period growth, and added controlled experiments examining the effects of agent count and local period. The corresponding theoretical derivation and experimental details are provided in Appendix I of the revised manuscript, with revisions highlighted in blue. We address each concern below.
Weakness 1:
Response: We thank the reviewer for highlighting the hidden network dependence in Corollary 1. Using the explicit constants in Appendix F.4 of the original submission, we have derived a spectral-gap-dependent communication bound and included the detailed analysis in Appendix I.7 of the revised manuscript.
Let δ=1−λ denote the spectral gap, where λ=∥W−J∥2<1. For fixed smoothness constant L, the proof constants satisfy c∗=Θ(δ2) and C∗=Θ(δ−4). Choosing network-dependent parameter prefactors that satisfy the stability conditions of Theorem 3 yields the sufficient communication bound
\delta^{-\frac{2(5p-4)}{p-1}} \varepsilon^{-\frac{5p-4}{2(p-1)}} \right).$$ This preserves Corollary 1's accuracy exponent while making a conservative dependence on network connectivity explicit. **Comparison with existing methods.** GT-NSGDm (Yu et al., ICLR 2026) also establishes finite-time stationarity guarantees under bounded $p$-th-moment noise, but assumes independent stochastic samples across agents and iterations, and communicates at every iteration. Its finite-time analysis contains multiple network-dependent terms, including factors of $(1-\lambda)^{-1}$ and $(1-\lambda)^{-1/p}$. These factors cannot be directly compared with our sufficient communication-complexity bound because the algorithms use different communication schedules, stochastic assumptions, and parameter choices. We therefore do not claim improved or matching spectral-gap dependence. **Spectral-sensitivity experiment.** Figure 9(f) of the original submission compares three mixing weights on the same 16-node ring, corresponding to spectral gaps of approximately $0.01522$, $0.03045$, and $0.05075$, under identical sample and communication-byte budgets. This single-seed, finite-budget experiment examines sensitivity to network mixing but does not establish a spectral-gap complexity law. Our communication-complexity contribution is the reduction in communication rounds through multiple local updates under heavy-tailed noise, rather than improved dependence on network connectivity. The revised manuscript now makes this distinction explicit. **References** - Yu et al. (2026). Decentralized Nonconvex Optimization under Heavy-Tailed Noise: Normalization and Optimal Convergence. ICLR.