acceptodds
Under review as a conference paper at ICLR 2027

Decentralized Nonconvex Optimization under Heavy-Tailed Noise with Fixed-Batch Local Updates

Abstract

Multiple local updates can reduce communication in decentralized optimization, but under heavy-tailed gradient noise, obtaining reliable gradient estimates from a fixed batch is challenging. We study smooth nonconvex decentralized optimization under conditionally centered gradient noise with a bounded conditional -th moment, , using a fixed batch size per local update. We first establish a dimension-independent lower bound on the trade-off between uniform bias and worst-case mean squared error (MSE) in fixed-sample mean estimation. We then augment a three-block coordinatewise median-of-means (MoM) estimator with a clipped correction toward the pooled mean computed from the same batch, and show that the resulting estimator matches this lower bound up to constants depending only on . Building on this estimator, we propose CRAFT, a decentralized method combining corrected robust estimation, recursive filtering, and local gradient tracking. We establish finite-time stationarity and consensus guarantees and show that, with a fixed batch size per local update, increasing the number of local updates between communications with the horizon reduces the sufficient communication complexity, while the total numbers of local updates and samples required per agent remain of the same order as with a fixed local period. Experiments on image classification, language modeling, and controlled synthetic problems evaluate communication efficiency, robustness under heavy-tailed perturbations, and the roles of estimator correction and recursive filtering.

Primary area:
optimization
Keywords:
Decentralized optimization, local updates, gradient tracking, heavy-tailed noise, robust estimation

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_dU8wOpenReview ↗
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
  1. The paper establishes a dimension-independent lower bound for fixed-batch mean estimation under finite pp-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.

  2. 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 λ\lambda, 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
  1. The convergence bound contains the stochastic contribution (θ+H2η2+Hθ2)qκ(\theta+H^2\eta^2+H\theta^2)q_\kappa, which does not exhibit an explicit variance reduction with the number of agents nn or the local period HH. Under the prescribed parameter choices, these terms scale as K−r),(H2/KK^{-r}), (H^2/K, and H/KH/K, respectively, where K=THK=TH. Thus, the communication improvement does not appear to correspond to a linear speedup in the stochastic error terms. Is the absence of an nn-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?
  2. Corollary 1 shows that increasing the number of local updates HH can reduce communication complexity, but only under certain restrictions on the growth of HH. 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
AuthorsOpenReview ↗

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:

The communication complexity in Corollary 1 hides its dependence on network connectivity. Although the appendix provides constants involving λ\lambda, 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.

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−λ\delta=1-\lambda denote the spectral gap, where λ=∥W−J∥2<1\lambda=\lVert W-J\rVert_{2}<1. For fixed smoothness constant LL, the proof constants satisfy c∗=Θ(δ2)c_*=\Theta(\delta^{2}) and C∗=Θ(δ−4)C_*=\Theta(\delta^{-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.
AuthorsOpenReview ↗

Response to Reviewer dU8w (2/3)

Question 1:

The convergence bound contains the stochastic contribution (θ+H2η2+Hθ2)qκ(\theta+H^2 \eta^2 + H \theta^2) q_{\kappa}, which does not exhibit an explicit variance reduction with the number of agents nn or the local period HH. Under the prescribed parameter choices, these terms scale as K−rK^{-r}, H2/KH^2/K, and H/KH/K, respectively, where K=THK=TH. Thus, the communication improvement does not appear to correspond to a linear speedup in the stochastic error terms. Is the absence of an nn-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 nn-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 ζi\zeta_i 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.
AuthorsOpenReview ↗

Response to Reviewer dU8w (3/3)

Question 2:

Corollary 1 shows that increasing the number of local updates HH can reduce communication complexity, but only under certain restrictions on the growth of HH. 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 HH 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 HH 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 Hθ≤cH\theta\le c and H2η2≤cθH^2\eta^2\le c\theta 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 HH at a fixed budget of K=6,881,280K=6{,}881{,}280 local updates per agent (cf., new Figure 15 and Appendix I.6 of the revised manuscript). Under independent heavy-tailed noise, increasing HH from 112 to 1120 reduces the communication needed to reach and retain a mean gradient norm below 0.020.02 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.

Reviewer_mEc5OpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies decentralized nonconvex optimization under heavy-tailed gradient noise with a fixed batch size per local update. It analyzes the trade-off between bias and mean squared error and proposes a corrected median-of-means estimator. The resulting CRAFT method combines this estimator with recursive filtering and local gradient tracking. Under the stated assumptions, the analysis gives stationarity and consensus guarantees and shows how local updates improve the upper bound on communication rounds. Experiments cover image classification, language modeling, and synthetic problems.

Critical strengths
  1. CRAFT reduces the communication complexity bound through local updates while keeping the total local updates and samples per agent at the same asymptotic order.
  2. Experiments cover image classification, language modeling, and synthetic problems, with ablations on estimator correction and recursive filtering.
Critical weaknesses
  1. The MNIST and CIFAR-10 experiments use symmetric Student-t perturbations, while explicitly asymmetric noise is tested only on synthetic problems. The proposed correction aims to reduce estimation bias under asymmetric noise, but its effectiveness under such noise has limited experimental support in neural network training.
  2. Figure 10(d) examines the effect of HH on a synthetic problem. However, the MNIST experiments use different learning rates, filtering coefficients θ\theta, and correction radius κ\kappa across values of HH (Table 2). These comparisons do not isolate the effect of HH on neural network training.
Questions for authors
  1. Have you evaluated the proposed correction under asymmetric noise in neural-network experiments?
  2. Could you clarify the data partitioning or sampling scheme across agents in the GPT-2 experiments?
  3. Do you have controlled MNIST experiments varying HH while keeping the other hyperparameters fixed?
1 comment
AuthorsOpenReview ↗

Response to Reviewer mEc5 (1/1)

We thank the reviewer for the constructive comments and suggestions for strengthening the experimental evaluation. We have added controlled MNIST experiments in Appendix I and clarified the GPT-2 data partitioning and sampling protocol in the revised manuscript. We address each concern below, with the corresponding revisions highlighted in blue.

Weakness 1:

The MNIST and CIFAR-10 experiments use symmetric Student-t perturbations, while explicitly asymmetric noise is tested only on synthetic problems. The proposed correction aims to reduce estimation bias under asymmetric noise, but its effectiveness under such noise has limited experimental support in neural network training.

Question 1:

Have you evaluated the proposed correction under asymmetric noise in neural-network experiments?

Response to Weakness 1 and Question 1: We thank the reviewer for highlighting this limitation. To evaluate the correction in neural-network training under asymmetric heavy-tailed noise, we added MNIST experiments with centered-Pareto loss perturbations (tail exponent α=1.5\alpha=1.5) at H=2H=2 and H=4H=4 (cf. new Figure 12 and Appendix I.2 of the revised manuscript).

We compare MoM with and without the same-batch correction, retaining identical filtering, gradient tracking, direction clipping, and hyperparameters. Both variants use the same initialization, sampled batches, noise streams, and five paired seeds, with 256 local updates per agent. Thus, the correction is the only algorithmic difference and requires no additional samples (cf. Appendix I.1 and Table 7).

The correction improves terminal test accuracy in all five paired seeds at both local periods, with mean gains of 1.55 percentage points at H=2H=2 and 1.98 percentage points at H=4H=4. These results provide controlled evidence of the correction's incremental benefit in neural-network training under injected asymmetric heavy-tailed noise, extending the synthetic experiments in the original submission.

Weakness 2:

Figure 10 (d) examines the effect of HH on a synthetic problem. However, the MNIST experiments use different learning rates, filtering coefficients θ\theta, and correction radius κ\kappa across values of HH (Table 2). These comparisons do not isolate the effect of HH on neural network training.

Question 3:

Do you have controlled MNIST experiments varying HH while keeping the other hyperparameters fixed?

Response to Weakness 2 and Question 3: We thank the reviewer for this suggestion. We added controlled MNIST experiments varying only the local period H∈{1,2,4,8}H\in\{1,2,4,8\}, with the learning rate, filter weight, correction radius, direction-clipping radius, batch size, network, data partition, and noise protocol fixed. All configurations use the same five paired seeds (cf. new Figure 13 and Appendix I.3; settings in Table 7).

The results reveal a budget-dependent trade-off. At matched local updates and sample budgets, H=1H=1 achieves the lowest mean test loss, while larger HH reduces communication. At matched communication, larger HH permits more local updates and samples, and H=4H=4 achieves the lowest mean test loss among the tested settings. Notably, H=8H=8 performs worse than H=4H=4 under both budgets, despite using twice as many local updates at matched communication.

These controlled comparisons isolate the effect of HH at a fixed empirical configuration and show that increasing the local period is not uniformly beneficial. They complement the separately tuned MNIST comparisons in the original submission.

Question 2:

Could you clarify the data partitioning or sampling scheme across agents in the GPT-2 experiments?

Response: We thank the reviewer for requesting this clarification. In our GPT-2 experiments on WikiText-103, the preprocessed training sequences are partitioned in their stored order into four contiguous, disjoint shards of nearly equal size, one per agent. The partition is fixed and shared across all methods and network topologies.

At each gradient query, each agent independently samples 12 sequences uniformly with replacement from its own shard using a seeded sampler. Thus, sampling is IID within each local empirical distribution, while the partition across agents is contiguous rather than globally randomized. CRAFT divides each batch into three blocks of four sequences, using the same samples for the MoM anchor and pooled correction.

All methods use clean training data and are evaluated on the same fixed subset of 931 validation sequences. We have added the partitioning and sampling details to Appendix G.2.2 of the revised manuscript.

Reviewer_tn3VOpenReview ↗
Rating
3
Confidence
1
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies smooth nonconvex decentralized optimization under conditionally centered gradient noise with a bounded conditional p-th moment, p∈(1,2)p \in (1, 2). They propose CRAFT, a decentralized method combining corrected robust estimation, recursive filtering, and local gradient tracking. Experiments on a variaty of problems examine the communication efficiency, robustness under heavy-tailed perturbations, and the roles of estimator correction and recursive filtering.

Critical strengths

The fixed-sample bias–MSE lower bound (Theorem 1) is a clean statistical result. It shows that, over the class of distributions with bounded p-th central moment, no fixed-batch estimator can be uniformly unbiased with finite worst-case MSE.

The corrected estimator, a three-block coordinatewise median-of-means anchor with a clipped correction toward the pooled mean, matches this lower bound up to constants depending only on pp (Theorem 2). The correction radius gives an explicit and tunable bias–MSE trade-off, and the dimension-free MSE bound for the median anchor is simple.

Critical weaknesses

The parameter choices in Corollary 1 ( η\eta, θ\theta, κκ, etc) depend on the tail index p and the horizon T. In practice p is unknown and hard to estimate, and it may vary across layers and during training. The paper gives no analysis of robustness to a misspecified p. Moreover, the experiments use hand-tuned constant κ and θ rather than the schedule in (13), so they do not test the algorithm that is analyzed.

I am not sure whether the heavy-tailed noise assumption is realistic. Before heavy-tailed noise was considered, standard SGD already worked for large language models, so it is unclear to me why this assumption is necessary.

Questions for authors

The parameter choices in Corollary 1 depend on the tail index pp and the horizon T. How should p be chosen in practice, and how sensitive is the method to a misspecified pp?

GT-NSGDm with batch size one appears to achieve the same sample complexity without the corrected estimator. What does the estimator add to the optimization result?

4 comments
AuthorsOpenReview ↗

Response to Reviewer tn3V (1/2)

We thank the reviewer for the constructive comments on parameter tuning, the heavy-tailed noise assumption, and the role of the corrected estimator. We address these concerns below and highlight the corresponding revisions in blue in the revised manuscript.

Weakness 1:

The parameter choices in Corollary 1 (η\eta, θ\theta, κ\kappa, etc) depend on the tail index pp and the horizon TT. In practice pp is unknown and hard to estimate, and it may vary across layers and during training. The paper gives no analysis of robustness to a misspecified p. Moreover, the experiments use hand-tuned constant κ\kappa and θ\theta rather than the schedule in (13), so they do not test the algorithm that is analyzed.

Response: We agree that the moment order pp is generally unknown in practice and that the horizon-dependent schedule in Corollary 1 provides a sufficient theoretical guarantee rather than a practical tuning rule. Theorem 3 establishes convergence guarantees for CRAFT with fixed parameters satisfying sufficient stability conditions, whereas Corollary 1 specifies horizon-dependent parameter choices to obtain explicit complexity rates. We address the reviewer's concerns through theoretical sensitivity analysis and additional experiments.

Sensitivity to moment-order misspecification. Suppose the conditional moment assumption holds at order p∈(1,2]p\in(1,2], but the parameters are tuned using s∈(1,2]s\in(1,2]. Let K=THK=TH and apply the schedule in Corollary 1 with pp replaced by ss, subject to the corresponding stability and local-period restrictions. Substituting the estimator bounds at the actual moment order pp into Theorem 3 yields

=O\left(K^{-\gamma(p,s)}\right), \qquad \gamma(p,s)=\frac{\min\\{p,s\\}-1}{3s-2}.$$ Indeed, the initialization, squared-bias, and weighted-MSE terms decay at rates $K^{-2(s-1)/(3s-2)}$, $K^{-2(p-1)/(3s-2)}$, and $K^{-(s+p-2)/(3s-2)}$, respectively. The best guaranteed exponent within this schedule family is attained at $s=p$. This analysis quantifies the effect of moment-order misspecification on the theoretical convergence guarantee, without predicting empirical convergence rates. We have added this result after Corollary 1 in the revised manuscript. **Empirical robustness to varying tail behavior.** In our neural-network experiments, CRAFT's hyperparameters are selected empirically without estimating $p$ or enforcing the sufficient conditions of Theorem 3. These experiments therefore evaluate finite-budget performance rather than directly test the asymptotic schedule in Corollary 1. To assess sensitivity to tail behavior, we conducted **additional MNIST and CIFAR-10 experiments** under centered-Pareto noise with tail exponents $\alpha\in \\{1.2,1.4,1.6,1.8 \\}$. Within each task, the same hyperparameter configuration is used across all four distributions, without noise-specific retuning, using five paired seeds and matched local-update budgets. Mean terminal test accuracies range from $93.57\%$ to $94.87\%$ on MNIST and from $91.52\%$ to $91.96\%$ on CIFAR-10 (cf. Figure 14(a-b), Appendix I.4 of the revised manuscript). These results indicate that a fixed empirical configuration maintains comparable performance across the tested tail exponents, although they do not establish robustness to arbitrary noise distributions or verify the theoretical rates. We have also clarified the distinction between theoretical and empirical parameter selection in the revised manuscript (see the changes highlighted in blue on page 8). **Question 1:** > The parameter choices in Corollary 1 depend on the tail index $p$ and the horizon $T$. How should $p$ be chosen in practice, and how sensitive is the method to a misspecified $p$? **Response:** We thank the reviewer for this question, which is closely related to Weakness 1. In practice, CRAFT's hyperparameters are selected empirically without explicitly estimating the moment order $p$. The horizon-dependent schedule in Corollary 1 provides a sufficient theoretical guarantee rather than a required implementation rule. As shown in our response to Weakness 1, tuning with $s\in(1,2]$ when the moment assumption holds at order $p\in(1,2]$ yields the guaranteed convergence exponent $\gamma(p,s)=\frac{\min \\{p,s \\}-1}{3s-2}$, which is maximized at $s=p$ within this schedule family. To assess empirical sensitivity, we additionally evaluate CRAFT under four centered-Pareto tail exponents, using one fixed hyperparameter configuration per task without noise-specific retuning. The results show comparable terminal accuracy across the tested distributions. These experiments demonstrate finite-budget robustness to varying tail behavior, rather than directly testing moment-order misspecification in the theoretical schedule. Further details are provided in our response to Weakness 1 and the revised manuscript.
AuthorsOpenReview ↗

Response to Reviewer tn3V (2/2)

Weakness 2:

I am not sure whether the heavy-tailed noise assumption is realistic. Before heavy-tailed noise was considered, standard SGD already worked for large language models, so it is unclear to me why this assumption is necessary.

Response: We thank the reviewer for raising this concern. We do not claim that heavy-tailed noise is universal or that standard SGD cannot handle it. Rather, our finite pp-moment assumption extends the conventional bounded-variance setting to certain infinite-variance noise distributions.

Empirical studies motivate this setting. Zhang et al. (NeurIPS 2020) observed less concentrated minibatch gradient-noise norms in BERT than in ResNet-50, while Battash et al. (AISTATS 2024) found that coordinatewise stable models fit measured BERT gradient noise better than Gaussian models. Although these observations do not establish infinite variance, they motivate considering weaker moment assumptions.

Existing work has established convergence guarantees under heavy-tailed noise for centralized SGD (Fatkhullin et al., 2025) and decentralized GT-NSGDm (Yu et al., ICLR 2026). Our work addresses a complementary challenge: reliable fixed-batch gradient estimation with multiple local updates between communications. In this setting, the sample mean may have infinite MSE, while robust estimators can introduce bias. CRAFT addresses this trade-off through corrected robust estimation with explicit bias–MSE guarantees, combined with recursive filtering and local gradient tracking.

Question 2:

GT-NSGDm with batch size one appears to achieve the same sample complexity without the corrected estimator. What does the estimator add to the optimization result?

Response: We thank the reviewer for this question. GT-NSGDm achieves the same order of sample complexity with one sample per update, but its convergence analysis assumes communication at every update. CRAFT instead establishes convergence guarantees with multiple local updates between communications, improving the sufficient communication complexity from O(ε−(3p−2)/(p−1))O(\varepsilon^{-(3p-2)/(p-1)}) for the GT-NSGDm analysis to O(ε−(5p−4)/(2(p−1)))O(\varepsilon^{-(5p-4)/(2(p-1))}), while retaining the same order of per-agent sample complexity.

The corrected estimator provides a distinct statistical contribution. Under asymmetric heavy-tailed noise, median-of-means (MoM) estimation can be biased, whereas the unbiased sample mean may have infinite MSE. CRAFT introduces a clipped same-batch correction to MoM, yielding a tunable bias–MSE trade-off that matches our fixed-sample lower bound up to constants. These bounds enter the finite-time stationarity and consensus analysis, providing explicit control of gradient estimation errors, including an expected squared-gradient guarantee when direction clipping is disabled.

Controlled experiments further demonstrate the correction's incremental benefit. Under centered-Pareto noise, corrected MoM with filtering achieves lower median terminal squared gradients than filtered MoM alone (cf. Figure 5(a) of the original submission). In additional MNIST experiments under asymmetric heavy-tailed noise, correction improves accuracy in all five paired seeds, with mean gains of 1.55 and 1.98 percentage points at (H=2H=2) and (H=4H=4), respectively (cf. Figure 12 of the revised manuscript), under matched sampling budgets and otherwise fixed algorithmic components.

References

  • Zhang et al. (2020). Why are Adaptive Methods Good for Attention Models? NeurIPS.

  • Battash et al. (2024). Revisiting the Noise Model of Stochastic Gradient Descent. AISTATS.

  • Fatkhullin et al. (2025). Can SGD Handle Heavy-Tailed Noise? SIAM Journal on Optimization, to appear.

  • Yu et al. (2026). Decentralized Nonconvex Optimization under Heavy-Tailed Noise: Normalization and Optimal Convergence. ICLR.

I thank the authors for adequately addressing my concerns. I will maintain my original score, which I believe remains appropriate.

Thank you for your careful review and constructive feedback. We appreciate your consideration of our responses and are glad that they adequately addressed your concerns.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.