Decentralized SGD under Heavy-Tailed Noise: Optimal Convergence Rates and the Role of Gradient Clipping

The gist The clipped decentralized SGD method achieves order-optimal convergence rates and linear speed-up for smooth non-convex costs under heavy-tailed noise, establishing that clipping retains magnitude information, unlike normalization which can fail to converge in decentralized settings

Key Findings on Convergence Rates

The work shows that clipped DSGD achieves order-optimal rates both with high probability and in expectation for smooth non-convex costs under bounded p-th moment noise, where p ∈ (1, 2]. The leading term with respect to T is of the order Oe((nT)2(1−p)3p−2), which matches the optimal rate achieved in centralized settings. Furthermore, linear speed-up in the number of agents n is achieved, exhibiting the same exponent with respect to p. The leading term has no network dependence, with the spectral gap only affecting higher-order terms.

Comparison of Nonlinearities

The paper establishes an important distinction between clipping and normalization in decentralized settings. While normalized DSGD can fail to converge, clipping retains magnitude information, enabling DSGD to be convergent and order-optimal. This is intuitively because normalization always biases the network-averaged gradient, while clipping can preserve the true network-averaged gradient.

Technical Analysis of Consensus Gap

The key technical ingredient is a sharp analysis of the consensus gap that exploits the structure of clipping, relegating network effects to higher-order terms. Lemma 4 establishes a more fine-grained result on the average consensus gap, capturing the effects of heterogeneity, network connectivity and local clipping. This lemma is crucial in achieving main results.

Convergence Guarantees

The theoretical guarantees are presented in two forms: high-probability (HP) and in-expectation (IE). Theorem 1 establishes HP convergence under Assumptions 1-5 with specific choices for the clipping threshold and step-size. Theorem 2 establishes IE convergence under the same assumptions.

Experimental Validation

Numerical experiments validate the theory across several problems. In robust linear regression, DSGD-Clip and DSGD-CClip perform on par with or better than DSGD-N. In decentralized transformer training on real data, DSGD-CClip achieves the lowest validation loss on both datasets, while DSGD-Clip and DSGD-N perform similarly and substantially improve over vanilla DSGD. The results also confirm that linear speed-up is achieved as network size increases.

Design Insights

The analysis highlights a clear gap between the two nonlinearities in decentralized settings. The paper raises broader questions about whether some nonlinearities are better suited to decentralized settings and if a hierarchy can be established across different regimes. It also investigates whether baseline GT with clipping can simultaneously eliminate the bounded heterogeneity condition and retain order-optimal convergence rates. Finally, the design question is posed regarding whether clipping should be applied to local gradients or to the tracker variable.

The paper concludes by showing that there exist step-size and clipping threshold choices such that b + d + g ≤ 3∆1/8, completing the proof of Theorem 1. The transient time analysis shows that for p=2 (bounded variance), the transient time evaluates to Oe(n3(1−λ)4), matching the transient time of vanilla DSGD under bounded variance/sub-Gaussian noise. The results demonstrate that clipped DSGD achieves optimal convergence rates with linear speedup under heavy-tailed noise, highlighting a clear gap between these two nonlinearities in decentralized settings. The paper concludes by showing that there exist step-size and clipping threshold choices such that b + d + g ≤ 3∆1/8, completing the proof of Theorem 1. The transient time analysis shows that for p=2 (bounded variance), the transient time in (33) evaluates to Oe(n3(1−λ)4), matching the transient time of vanilla DSGD under bounded variance/sub-Gaussian noise in (Koloskova et al., 2020; Alghunaim and Yuan, 2022; Armacki and Sayed, 2026). The results demonstrate that clipped DSGD achieves optimal convergence rates with linear speedup under heavy-tailed noise, highlighting a clear gap between these two nonlinearities in decentralized settings. The paper concludes by showing that there exist step-size and clipping threshold choices such that b + d + g ≤ 3∆1/8, completing the proof of Theorem 1.

--- Page 26 ---

The gist The clipped decentralized SGD method achieves order-optimal convergence rates and linear speed-up for smooth non-convex costs under heavy-tailed noise, establishing that clipping retains magnitude information, unlike normalization which can fail to converge in decentralized settings

How it works

The proposed method is clipped DSGD, which consists of several steps. In iteration t ≥ 1, each agent i queries the SFO with their current model x t i and receives g t i. Agents then clip their local stochastic gradient and update the local model via the rule x t+1 i = Pj∈Ni wijx tj - αge tj. The clipped estimator is defined as ge t i = min n 1, γ g t io g t i.

Theoretical Guarantees

The analysis relies on several lemmas to establish the main results. Lemma 1 shows that the variance of the averaged clipped estimator scales as O(σp n), which is crucial in establishing linear speed-up. Lemma 2 provides a descent inequality, and Lemma 3 provides an initial deterministic bound on the consensus gap. Lemma 4 establishes a more fine-grained result on the average consensus gap, capturing the effects of heterogeneity, network connectivity and local clipping.

Experimental Validation

Numerical experiments validate that DSGD-Clip accelerates with network size, achieving linear speed-up. In transformer training on real data, DSGD-CClip achieves the lowest validation loss on both datasets, while DSGD-Clip and DSGD-N perform similarly and substantially improve over vanilla DSGD. The results also confirm that linear speed-up is achieved as network size increases.

Design Insights

The work highlights a clear gap between clipping and normalization in decentralized settings. Intuitively, the gap stems from the fact that while normalization always modifies the gradient direction, clipping keeps it unchanged when the gradient norm is below a threshold, maintaining full magnitude information. This allows clipped DSGD to achieve order-optimal complexity with linear speed-up without needing mechanisms like GT, accelerated gossip and local momentum/mini-batches.

Conclusion

The work establishes order-optimal convergence rates and linear speedup for smooth non-convex costs under heavy-tailed noise, establishing that clipping retains magnitude information, unlike normalization which can fail to converge in decentralized settings. The paper concludes by showing that there exist step-size and clipping threshold choices such that b + d + g ≤ 3∆1/8, completing the proof of Theorem 1. The transient time analysis shows that for p=2 (bounded variance), the transient time evaluates to Oe(n3(1−λ)4), matching the transient time of vanilla DSGD under bounded variance/sub-Gaussian noise in (Koloskova et al., 2020; Alghunaim and Yuan, 2022; Armacki and Sayed, 2026). The results demonstrate that clipped DSGD achieves optimal convergence rates with linear speedup under heavy-tailed noise, highlighting a clear gap between these two nonlinearities in decentralized settings.

--- Page 17 ---

The gist The clipped decentralized SGD method achieves order-optimal convergence rates and linear speed-up for smooth non-convex costs under heavy-tailed noise, establishing that clipping retains magnitude information, unlike normalization which can fail to converge in decentralized settings

Key Findings on Convergence Rates

The work shows that clipped DSGD achieves order-optimal rates both with high probability and in expectation for smooth non-convex costs under bounded p-th moment noise, where p ∈ (1, 2]. The leading term with respect to T is of the order Oe((nT)2(1−p)3p−2), which matches the optimal rate achieved in centralized settings.

Comparison of Nonlinearities

The paper establishes an important distinction between clipping and normalization in decentralized settings. While normalized DSGD can fail to converge, clipping retains magnitude information, enabling DSGD to be convergent and order-optimal.

1. Bold header: Order-optimal convergence under heavy-tailed noise for decentralized SGD (DSGD). The system can achieve order-optimal rates both with high probability and in expectation by using clipped DSGD, establishing a rate of Oe((nT)2(1−p)3p−2) where the leading term has no network dependence.

2. Bold header: Linear speed-up in agent count for decentralized learning. The improved system can achieve a linear speed-up in the number of agents by using clipped DSGD, which is to our knowledge, has not been shown for decentralized methods with clipping.

3. Bold header: Robustness against heavy-tailed noise via gradient clipping. The system can maintain convergence under heavy-tailed noise where normalized DSGD can fail to converge, because clipping retains magnitude information, enabling DSGD to be convergent and order-optimal.

4. Bold header: Enhanced performance in real-world decentralized transformer training. The system can achieve a lower validation loss on tasks like transformer training by using methods like DSGD-CClip, which was shown to consistently achieve the lowest validation loss on both datasets.

5. Bold header: Elimination of necessary algorithmic modifications for optimal rates. The system can achieve convergence under heavy-tailed noise without needing additional modifications by using baseline DSGD with gradient clipping, as the paper shows that baseline DSGD with gradient clipping achieves optimal oracle complexity and linear speed-up, under standard assumptions.

Heavy-tailed noise has been widely observed in modern machine learning, motivating the use of methods like gradient clipping and normalization. While these methods are well understood in centralized settings, much less is known in decentralized ones, where applying a nonlinearity to local gradients affects both optimization and consensus. Recent works on decentralized non-convex optimization have studied both clipping and normalization under heavy-tailed noise, with clipping yielding suboptimal rates and normalization needing local momentum or mini-batches to converge. This raises the question: can a baseline decentralized method using a nonlinearity achieve optimal convergence rates under heavy-tailed noise? We answer affirmatively with clipped decentralized SGD. For smooth non-convex costs under bounded p-th moment noise, p in (1,2], we show that clipped achieves order-optimal rates both with high probability and in expectation. Moreover, we establish a linear speed-up in the number of agents, which, to our knowledge, has not been shown for decentralized methods with clipping. The key technical ingredient is a sharp analysis of the consensus gap that exploits the structure of clipping, relegating network effects to higher-order terms. Our results highlight an important distinction between clipping and normalization in decentralized settings: while normalized can fail to converge, clipping retains magnitude information, enabling to be convergent and order-optimal. Numerical experiments validate our theory.