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

Jul 9, 2026cs.LG

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

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.

Ryusei Yamada, Naoki Sato, Hideaki Iiduka

Meiji University, Japan

Stochastic Gradient Descent Convergence Momentum Gradient Clipping

Ask PDF

Apr 30, 2026cs.LG

High-Probability Convergence in Decentralized Stochastic Optimization with Gradient Tracking

We study high-probability (HP) convergence guarantees in decentralized stochastic optimization, where multiple agents collaborate to jointly train a model over a network. Existing HP results in decentralized settings almost exclusively focus on the Decentralized Stochastic Gradient Descent (

\mathtt{DSGD}

) algorithm, which requires strong assumptions, such as bounded data heterogeneity, or strong convexity of each agent's cost. This is contrary to the mean-squared error (MSE) results, where methods incorporating bias-correction techniques are known to converge under relaxed assumptions and achieve better practical performance. In this paper we provide the first step toward bridging the gap, by studying HP convergence of

\mathtt{DSGD}

incorporating the gradient tracking technique, in the presence of noise satisfying a relaxed sub-Gaussian condition. We show that the resulting method, dubbed

\mathtt{GT-DSGD}

, achieves order-optimal HP convergence rates for both non-convex and Polyak-Łojasiewicz costs, of order

\mathcal{O}\Big(\frac{\log(1/δ)}{\sqrt{nT}}\Big)

and

\mathcal{O}\Big(\frac{\log(1/δ)}{nT}\Big)

, respectively, where

n

is the number of agents,

T

is the time horizon and

δ\in (0,1)

is the confidence parameter. Our results establish that

\mathtt{GT-DSGD}

converges in the HP sense under the same conditions on the cost as in the MSE sense, while achieving comparable transient times. To the best of our knowledge, these are the first HP guarantees for decentralized optimization methods incorporating bias-correction. Numerical experiments on real and synthetic data verify our theoretical findings, underlining the superior performance of

\mathtt{GT-DSGD}

and highlighting that the benefits of incorporating bias-correction are also maintained in the HP sense.

Aleksandar Armacki, Haoyuan Cai, Ali H. Sayed

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

Decentralized Optimization Stochastic Gradient Descent Stochastic Optimization Convergence

Ask PDF

Feb 2, 2026cs.LG

Decentralized SGD with Controlled Disagreement Finds Flatter Minima

Decentralized training is often regarded as inferior to centralized training because the consensus errors between workers are thought to undermine convergence and generalization. This work challenges this view by introducing decentralized SGD with Adaptive Consensus (DSGD-AC), which uses a time-dependent scaling mechanism to maintain consensus errors throughout the training. We show that adaptive consensus changes the stationary variance of disagreement modes by balancing two effects: it preserves consensus-error magnitude through weaker graph damping while still allowing curvature-dependent damping to shape the disagreement directions. This balance can produce a stronger Hessian-weighted loss-envelope penalty around the deployed model, even when normalized Hessian alignment is weaker than in standard DSGD. Empirical results on image classification show that DSGD-AC reaches flatter solutions and higher test accuracy than standard DSGD and even centralized SGD. Together, these results support consensus errors as a useful implicit regularizer and open a new perspective on the design of decentralized learning algorithms.

Zesen Wang, Mikael Johansson

Division of Decision and Control Systems KTH Royal Institute of Technology

Decentralized Learning Stochastic Gradient Descent Quadratic Slack Penalty Flat Minima Disagreement

Ask PDF