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

Aleksandar Armacki; Haoyuan Cai; Ali H. Sayed

math.OCOct 7, 2026

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

Authors: Aleksandar Armacki, Haoyuan Cai, Ali H. Sayed

Organizations: Ecole Polytechnique Fédérale de Lausanne, Lausanne, Switzerland

Abstract

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 ( $\mathtt{DSGD}$ ). For smooth non-convex costs under bounded $p$ -th moment noise, $p \in (1,2]$ , we show that clipped $\mathtt{DSGD}$ 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 $\mathtt{DSGD}$ can fail to converge, clipping retains magnitude information, enabling $\mathtt{DSGD}$ to be convergent and order-optimal. Numerical experiments validate our theory.

Figures & tables

Work	Algorithm	Nonlinearity	Noise Moment	Guarantees	Oracle Comp.	Lin. Speed-up
Yang et al. (2025)	DSGD	clipping	$p\in(1,2]$	HP	$\widetilde{\mathcal{O}}\bigg(\epsilon^{\frac{4p}{1-p}}\bigg)$	✗
Li and Chi (2025) †	gt + mini-b. + compr. + ef	$\begin{gathered}\text{smooth}\\[-3.46594pt] \text{clipping}\end{gathered}$	$p=2$	IE	$\mathcal{O}\Big(\epsilon^{-4}\Big)$	✗
Yu et al. (2026a)	gt + local momentum	normalization	$p\in(1,2]$	IE	$\mathcal{O}\bigg(\epsilon^{\frac{3p-2}{1-p}}\bigg)$	✗
Wang et al. (2026) ‡	gt + mini-b. + acc. gossip	normalization	$p\in(1,2]$	IE	$\mathcal{O}\bigg(\epsilon^{\frac{3p-2}{1-p}}/n\bigg)$	✓
This work	DSGD	clipping	$p\in(1,2]$	HP & IE	$\widetilde{\mathcal{O}}\bigg(\epsilon^{\frac{3p-2}{1-p}}/n\bigg)$	✓

Table 1: Comparison of decentralized methods using gradient nonlinearities. “Algorithm” refers to the underlying algorithmic dynamics, e.g., “GT + mini-b.” indicates gradient tracking and mini-batch gradients. “Nonlinearity” specifies the nonlinear map applied to the gradient estimator. “Noise Moment” gives the moment assumption, with

p=2

implying bounded variance and

p<2

allowing heavier tails. “Guarantees” indicates high-probability (HP) or in-expectation (IE) results. “Oracle Comp.” gives the per-agent number of

\mathcal{SFO}

calls needed to reach an

\epsilon

-stationary point. § “Lin. Speed-up” indicates whether linear speed-up in the number of agents is achieved.

Figure 1: Convergence of vanilla, normalized and clipped DSGD on a quadratic cost. While normalization gets stuck at the initial point and fails to converge, both vanilla and clipped DSGD converge to the true minima. For more details, see Supplement C .

Panel of Figure 2 — Figure 2: Convergence of decentralized methods under heavy-tailed gradient noise. Left: Student’s $t$ noise; right: Lévy $\alpha$ -stable noise. Solid curves show the mean estimation error, while shaded regions indicate one standard deviation.

Panel of Figure 3 — Figure 3: Convergence of DSGD-Clip under heavy-tailed noise for networks of size $n\in\{10,20,30,40,50\}$ . Left: Student’s $t$ noise; right: Lévy $\alpha$ -stable noise. We can see that DSGD-Clip accelerates with network size, achieving linear speed-up.

Algorithms	“Multi30k”	“Tiny Shakespeare”
DSGD	$4.634{\pm 0.026}$	$2.357{\pm 0.006}$
DSGD-N	$4.386{\pm 0.016}$	$1.966{\pm 0.035}$
DSGD-Clip	$4.375{\pm 0.021}$	$1.980{\pm 0.050}$
DSGD-CClip	3.962 $\pm$ 0.008	1.725 $\pm$ 0.010

Table 2: Validation loss after 20 epochs on “Multi30k” and “Tiny Shakespeare” datasets. We report the mean and standard deviation over five independent runs.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 4 — Figure 4: Convergence of vanilla, normalized and clipped DSGD on a quadratic example.

Panel of Figure 5 — Figure 5: Validation loss versus training epoch for decentralized transformer training. Left: “Multi30k”; right: “Tiny Shakespeare” dataset.

Explore similar work

Vanilla SGD with Momentum Survives Heavy-Tailed Noise: Convergence Analysis without Gradient Clipping or Normalization
Jul 9, 2026Ryusei Yamada, Naoki Sato, Hideaki IidukaHeavy-Tailed Noise Stochastic Optimization Convergence
Meiji University, Japan
High-Probability Convergence in Decentralized Stochastic Optimization with Gradient Tracking
Apr 30, 2026Aleksandar Armacki, Haoyuan Cai, Ali H. SayedConvergence Analysis Stochastic Optimization Convergence
Ecole Polytechnique Fédérale de Lausanne, Lausanne, Switzerland
Decentralized SGD with Controlled Disagreement Finds Flatter Minima
Feb 2, 2026Zesen Wang, Mikael JohanssonDecentralized Learning Flat Minima
Division of Decision and Control Systems KTH Royal Institute of Technology

Jul 9, 2026, cs.LGJ/K move · Enter open · S save

Vanilla SGD with Momentum Survives Heavy-Tailed Noise: Convergence Analysis without Gradient Clipping or Normalization

Ryusei Yamada, Naoki Sato, Hideaki Iiduka

Meiji University, Japan

Heavy-Tailed Noise Stochastic Optimization Convergence Heavy-Tailed Distributions Heavy-Tailed Stochastic Optimization Stochastic Gradient Descent

Open paper AskPDF arXiv

Stochastic gradient descent (SGD) is a cornerstone of modern optimization. While its performance under heavy-tailed noise is often addressed through specialized modifications such as gradient clipping or normalization, we investigate a more fundamental question: how does vanilla SGD, particularly with momentum, perform in the presence of heavy-tailed noise? In this paper, we refine existing convergence results for vanilla SGD and, more importantly, provide the first comprehensive convergence analysis of vanilla SGD with momentum for strongly convex, convex, and nonconvex objectives, without employing any gradient control mechanisms. Our results demonstrate that the obtained convergence rates are inferior to the optimal rates achieved by clipped or normalized variants of SGD, thereby revealing inherent limitations of vanilla methods under heavy-tailed noise. The theoretical findings are supported by experiments on synthetic functions.

Abstract

Explore similar work

Vanilla SGD with Momentum Survives Heavy-Tailed Noise: Convergence Analysis without Gradient Clipping or Normalization

High-Probability Convergence in Decentralized Stochastic Optimization with Gradient Tracking

Decentralized SGD with Controlled Disagreement Finds Flatter Minima