Decentralized Nonconvex Optimization under Heavy-Tailed Noise: Normalization and Optimal Convergence
Authors: Shuhua Yu
Dusan Jakovetic
Soummya Kar
Venue: ICLR 2026 Poster (2026)
Keywords: Stochastic optimization
heavy-tailed noise
decentralized optimization
normalization
Primary area: optimization

Abstract: Heavy-tailed noise in nonconvex stochastic optimization has garnered increasing research interest, as empirical studies, including those on training attention models, suggest it is a more realistic gradient noise condition. This paper studies first-order nonconvex stochastic optimization under heavy-tailed gradient noise in a decentralized setup, where each node can only communicate with its direct neighbors in a predefined graph. Specifically, we consider a class of heavy-tailed gradient noise that is zero-mean and has only $p$-th moment for $p \in (1, 2]$. We propose GT-NSGDm, Gradient Tracking based Normalized Stochastic Gradient Descent with momentum, that utilizes normalization, in conjunction with gradient tracking and momentum, to cope with heavy-tailed noise on distributed nodes. We show that, when the communication graph admits primitive and doubly stochastic weights, GT-NSGDm guarantees, for the first time in the literature, that the expected gradient norm converges at an optimal non-asymptotic rate $O\big(1/T^{(p-1)/(3p-2)}\big)$, which matches the lower bound in the centralized setup. When the tail index $p$ is unknown, GT-NSGDm attains a non-asymptotic rate $O\big( 1/T^{(p-1)/(2p)} \big)$ that is, for $p < 2$, topology independent and has a speedup factor $n^{1-1/p}$ in terms of the number of nodes $n$. Finally, experiments on nonconvex linear regression with tokenized synthetic data and decentralized training of language models on a real-world corpus demonstrate that GT-NSGDm is more robust and efficient than  baselines.

Published as a conference paper at ICLR 2026
DECENTRALIZED NONCONVEX OPTIMIZATION UNDER HEAVY-TAILED NOISE: NORMALIZATION AND OPTI- MAL CONVERGENCE
Shuhua Yu
Dušan Jakovetić
Department of Electrical and Computer Engineering Camegie Mellon University Pitsburgh, PA 15213, USA Mauhhaa@@adress cww.cmu.......oo edu
Department of Mathematics and Informatics University of Novi Sad Novi Sad, 21000, Serbia dusan. aakoeticcedee uns. ac rs
Soummya Kar
Department of Electrical and Computer Engineering Camegie Mellon University Pittsurgh,, PA 15213, USA Coummyak@andien cmu. edu
ABSTRACT
Heavy-tailed noise in nonconvex stochastic optimization has garnered increasing research interest, as empirical studies, including those on training attention mod- els, suggest it is a more realistic gradient noise condition. This paper studies first-order nonconvex stochastic optimization under heavy-tailed gradient noise in decentralized setup. where each node only communicate with its di- rect neighbors in predefined graph. Specifically, we consider class of heavy- tailed gradient noise that is zero-mean and has only p-th moment for p E (1, 2]. We propose CT-NSGDm, Gradient Tracking based Normalized Stochastic Gra- dient Descent with momentum, that utilizes normalization, in conjunction with gradient tracking and momentum, to cope with heavy-tailed noise on distributed nodes. We show that, when the communication graph admits primitive and dou- bly stochastic weights, GT-NSGDm guarantees, for the first time in the litera- ture, that the expected gradient norm converges at an optimal non- asymptommm rate O(1/T(e-1)/(55p2 which matches the lower bound in the centralized setup. When the tail index is unknown, GT GT-NSGDm attains non-asymptotic rate O(1/T(x-1//(p)) that is, for p < 2, topology independent and has a speedup factor 1-11 in terms of the number of nodes n. Finally, experiments non- convex linear regression with tokenized synthetic data and decentralized training of language models real-world corpus demonstrate that GT-NSGDm is more robust and efficient than baselines.
INTRODUCTION
In this paper, we address the problem of nonconvex stochastic optimization under heavy-tailed gra- dient noise in the decentralized setup. Consider graph with nodes connected by a predefined topology G := (V,E), where y == (1....,n) n) is the set of node indices, and & is the collection of directed pairs ri,r), i, E such that node can send information to the neighboring node Each node i E V holds local nonconvex differentiable cost function fi _dd - R. and can access its stochastic gradient, subject to zero mean noise with bounded p-th moment for some p (1, Cooperatively. these nodes aim solve min f(x) = (1/n) Σi fi(x), through local computation and sper-to-peer communication only with their immediate neighbors.
Decentralized optimization in the above formulation has been studied for decades Tsitsiklis al. 1986), and has recently attracted growing research interest due to its advantages in scalability and privacy preservation across wide range of distributed machine leaming, signal processing, and

---

Published as a conference paper at ICLR 2026
control tasks over networks (Nedić et al., 2018 Li et al. 2020 Kairouz al. 202 For instance, in privacy-sensitive applications such as those in the medical domain (Bisimi et al. 2018 training data often distributed across nodes due to privacy constraints. In such cases, each f. represents an empirical risk function, e.g., a neural network, defined over the local dataset on node i, and all nodes collaboratively train global predictive model via peer-to-peer communication without shar- ing raw data. Moreover, decentralized optimization is also employed in data centers to reduce com- munication bottlenecks associated with the central node in traditional centralized training paradigms Lian et al. 2017).
In decentralized optimization, first-order methods are widely favored for their simplicity and scal- ability (Xin et al. 2020b). However, computing the exact gradient of each local objective function Si at every iteration can be computationally expensive, particularly in large-scale settings where each node holds a substantial volume of local data. To alleviate this computational burden, de- centralized stochastic gradient methods, which approximate exact gradients, have been extensively studied. Most existing approaches, including decentralized stochastic (sub)gradient descent (Sund- har Ram et al.] 2010 Koloskova et al. 2020 Wang & Joshi 202Tb, variance reduction techniques -aasing--seddddd based schemes (Di Lorenzo & Scutari, 2016 Pu & Nedić, 2021). typically assume that stochastic gradient noise has a finite variance. Nevertheless, recent em- pirical and theoretical evidence indicates that, when optimizing certain neural network architectures, especially attention-based models such as Transformers (Vaswani et al., 2017). the gradient noise often follows a heavy-tailed distribution I with significantly large or even infinite variance (Simsekli ctt al. [2019] Zhang et al. 2020, Gorbunov et al. 2020; Gurbuzbalaban et al., 2021; Ahn et al. 2024] Kunstner et al. 2024). The presence of heavy-tailed gradient noise poses substantial challenges for existing methods. Empirically, some stochastic gradient descent (SGD) based methods can suffer from instability and even dramatic drop of training accuracies (Zhang et al. 2020 Charles et all
( Yuan et al. 2018), and gradient tracking-
2 Yang et al.] 2022), particularly in distributed large-cohort training. Theoretically, unbounded variance renders many established analyses invalid, and centralized settings it necessitates the
use of nonlinear adaptive techniques such as clipping, sign, and normalization (Zhang et al., 2020
Sadiev et al., 2023] Compagnoni et al. 2025b, Hübler et al.) 2024 Liu & Zhou 2025 Armacki
al.] 2025) to combat the strong noise. However, incorporating such adaptive strategies in decen-
tralized algorithms introduces inherent nonlinearity into the algorithmic dynamics associated with
the average-sum structured function f, making the design and analysis of decentralized algorithms under heavy-tailed noise significantly more challenging.
Decentralized optimization under heavy-tailed gradient noise remains underexplored. To the best of our knowledge, only recent studies [Sun & Chen (2024); Yu et al.] (023) have attempted to address this problem under restrictive assumptions. Specifically, [unn & Chen 2024 considers zero-mean gradient noise with bounded p-th central moment (p E (1, similar to our setting but assumes a compact domain or bounded gradients. Their proposed decentralized gradient descent method with l gradient clipping achieves almost sure convergence for strongly convex local functions. How- ever, the restrictive compact domain or gradients assumption in Sun & Chen (2024) limits its prac- tical applicability, and the convergence rate is not explicitly provided. Another work, Yu et al. (023). also assumes strongly convex local objectives and develops a decentralized gradient method with smoothed clipping and error feedback under gradient noise that is zero-mean, symmetric, and has bounded first absolute moment, showing an in -xeexecctttion convergence rate of 1/t for some 5 E (0, 2/5). Although the noise assumption in Yu et al. (2023) is weaker than ours (as it requires only a first-moment bound), the additional assumptions of noise symmetry and the dependence of the rate exponent d on both the problem dimension and condition number restrict its general ap- plicability. Moreover, both works Sun & Chen (022)): Yu et al. (2023) assume strong convexity, whereas many practical optimization problems involving heavy-tailed noise, particularly in modern machine learning, are inherently nonconvex. Further, the convergence rates in Sun & Chen (024); et al. (2023) are either unclear or sub- sub-optimal, even compared the optimal iteration complexity bound O 1/T (tp--- ()/(3))))) for general nonconvex functions. In this work, we relax these restrictive assumptions and address the following question:
A random variable X is called taived if it exhibits a heavier tail than any exponential distribution; formally, for any constant > 0, lim sup...o P(X >> 2)eax - oo Nair et al. 2022 While some heavy- tailed distributions, such as log-normal and Weibull, still have bounded variance, this paper also considers the sub-class of heavy tailed gradient noise that may have unhounded (infinite) variance such as a-stable noise.
2

---

Published as a conference paper at ICLR 2026
Can we design decentralized algorithm for nonconvex optimization under general zero-mean gradient noise with only a finite p-th moment for p E (1.2) with optimal iteration complexity?
1.1 CONTRIBUTIONS
We answer this question affirmatively through the following key contributions:
We develop decentralized method, called GT-NSGDm, using normalization, coupled with momentum variance reduction, to combat heavy-tailed noise, and using gradient tracking handle cross-node heterogeneity. To further shed light the design of GT-NSGDM, we provide a negative result for a vanilla variant of normalized decentralized SGD that employs neither gradient tracking nor momentum.
For general nonconvex and smooth local functions fi 's that bounded from below, we show that GT-NSGDm converges in expectation at a rate O(L/T(e-D/(ipp-) matches the lower bound the centralized setting and is order-optimal. Our convergence
which
rate significantly improves upon related works (Sun & Chen 2024 Yu et al. 2023 which assume strong convexity and lack an explicit rate exponent.
When the tail index is unknown, GT-NSGDm achieves rate of O(1/Tlx-1/(20)) match- ing the best-knows rate in the centralized setting without requiring knowledge of p. No- tably, for E (1, and sufficiently large T, this rate is independent of the network topol- ogy and exhibits a speedup in the number of nodes, with a factor of 1-1///v
We test our theoretical findings in nonconvex linear regression models on synthetic dataset that is built to simulate language tokens under controlled heavy-tailed noise injec- tions. We also test CT-NSGDm on distributed training of decoder-only Transformer models on Multi30k datasets (Elliott et al. 2016). Experiments on multiple variants of network topologies show that GT-NSGDm more robust to injected and empirical heavy-tailed noise and converges faster.
1.2 RELATED WORK
Heavy-tailed gradient noise. Recent empirical studies suggest that the distribution of gradient noise in training various deep learning models resembles heavy-tailed distributions, such as Lévy's a-stable distribution (Simsekli et al. 2019, Zhang al. 2020; Barsbey al. 2021; Battash al. 2024). For instance, the work Zhang et al. (2020) demonstrates that the empirical distribution of gradient norm samples during BERT pre-training closely aligns with an a-stable distribution, rather than Gaussian one (see their Figure 1). The presence of heavy-tailed gradient noise is also sup- ported by theoretical insights (Simsekli et al., 2019 Peluchetti et al. 2020, Gurbuzbalaban et al. 2021 Barsbey et al. 2021). In particular, (Simsekli et al. (2019) leverages generalized central limit theorems to show that the gradient noise SGD can converge to an c-stable random variable.
Adaptive methods. Under heavy-tailed noise, vanilla SGD based methods are shown to suffer from slower convergence or even model collapses in centralized settings (Zhang et al., 2020) as well as distributed settings with a central server (Yang et al. 2022 Lee et al. (2255) and adaptive methods such as clipping and normalization are introduced to stabilize training dynamics. In centralized set- tings, the work Zhang et al. (2020) provides lower bounds for both nonconvex and strongly convex smooth functions, showing that SGD with gradient clipping achieves in-expectation upper bounds matching lower bounds. In (adiev al. (2033); : Liu al. (2023); Nguyen et al. (2023); Chezhegov et al. 2024). the authors show that when equipped with gradient clipping, SGD, accelerated meth- ods, AdaGrad (Duchi et al., 2011) and Adam (Kingma & Ba 2014) can achieve (near-)opp (oparm) high--robabillity convergence under various function assumptions. Besides, the work Compagnoni al. (225b) shows that signSGD also robust to heavy-tailes noise through the lens of stochastic differential equations. Further, SGD with gradient normalization, which advantageously requires less hyper-parameter tuning than clipping, is shown to achieve optimal in-expectation convergence
(Hübler et al. 2024; Liu & Zhou 2025 Sun et al. 20244). Our method incorporates the same normal- ization and variance reduction approach as Liu & Zhou (025). Notably, in another line of works
Jakovetić et al. (2023); Armacki et al. 2205: 2024). the authors conduct unified convergence
analysis for generic nonlinear methods including clipping, sign, and normalization under symmet-
ric noise with positive probability mass around zero without assuming any noise moment bound
3

---

Published as a conference paper at ICLR 2026
or only assuming a first absolute noise moment bound. In distributed settings with server, the work worrbGorr et al. (2024) proposes an algorithm that incorporates an error feedback mechanism, wherein clipping applied to the discrepancy between a local gradient estimator and a stochastic gradient, and establishes optimal high-probabiilty bounds. Moreover, the work Compagnoni et al. asymptotic neighborhood depending on the 'fatness' of the noise tail. When multiple local updates are permitted between communication rounds, the authors of Yang et al. (022) show that clipping per local step achieves order-optimal in-expectation convergence, albeit under a restrictive bounded gradient assumption. In addition, the work Lee et al. (204)) rigorously shows that distributed training under heavy-tailes noise can col- lapse with unbounded gradients, and shows that client-side adaptive methods can stabilize training with bounded regrets in an online learning framework. More recently, the work [ee et al.. (2025) introduces the TailOPT framework, which adaptively leverages gradient geometry by applying clip- ping operators during local updates on distributed nodes and utilizing adaptive optimizers for global updates at the server, achieving in-expectation sublinear convergence rates that are independent of the moment parameter p.
(2025a) shows that distributed signSGI) converges
Nonlinearities in decentralized optimization. Extending existing methods that are robust to heavy- tailed noise, whether developed for centralized settings or distributed settings with a server, to de- centralized environments is highly nontrivial, primarily due to the nonlineurities introduced to peer- to-peer communication. This difficulty is reflected in that existing decentralized methods incorporat- ing nonlinear adaptive techniques for other purposes often impose restrictive conditions (Yu & Kar 2023 Li & Chil 2025p. For example, to achieve differential privacy through gradient clipping, the work Li & Chi 2025) establishes convergence in decentralized setups under the assumption of either bounded gradient or a stringent similarity condition, namely [z)) I| < (1/12)]l V f=))
for all [n] and all x. Similarly, to attain adversarial robustness against gradient attacks, the authors of Yu & Kar (2023) employ gradient clipping with momentum, assuming that all local func- tions are convex, share common minimizer, and that Σi= is strongly convex. Furthermore, Taheri & Thrampoulidis (023) integrates gradient tracking with normalization to address a max- margin problem. While gradient tracking is employed to ensure similarity among local gradient estimators, the method guarantees convergence only to the direction of the optimal solution un- der deterministic gradients. In this work, we significantly relax these conditions and demonstrate the effective use of nonlinearity (specifically, normalization) in decentralized optimization, thereby motivating broader applications of nonlinear techniques in this setting.
1.3 NOTATION
We denote by N_, E. R+ and R4, respectively, the set of positive natural numbers, real numbers, nonnegative real numbers, and the d-dimensional Euclidean space. We use lowercase normal letters for scalars, lowercase boldface letters for vectors, and uppercase boldface letters for matrices. Fur- ther, we denote by 1; and 02 the all-ones and all-zeros vectors of size k, respectively, and by I the k x k identity matrix. We let ||>||| denote the &2 norm of æ., and || denote the operator norm of A. For functions p(l) and q(() in I, we write p(() O(g(()) if lim sup p(1)/((() < co. Finally, we use E to denote expectation over random quantities.
PROBLEM FORMULATION
We consider graph with nodes, where each node holds local and private function ft R Rd R,
and the nodes collectively minimize the unconstrained global objective f(x) = (1/n) Σ f((x) through peer-to-peer communication. We now present some standard assumptions the problem. Assumption (Finite lower bound). There exists some f. == inf f(x) > -00.
Assumption 2 (I-smmothhesss). The local function fa at each node E [ni] is differentiable and L-smooth, ie., Vx, y E Rdd, f[))) Vf((g)) S L -
yll.
We next introduce the heavy-tailed noise model. For each node i E V. at t-th iteration with query æt. the stochastic first-order oracle returns the gradient estimator (xr 4.), where ş denotes the random sample. Let Ω, 1 denote the universe, empty set, respectively. We use the following natural filtration, i.e., an increasing family of aab-o-ag to denote the past history up to iteration t:
F- (), F. == al ..... E E [x] [n])), Vt 2 0.
4

---

Published as a conference paper at ICLR 2026
We then assume this stochastic first-order oracle has the following properties.
Assumption 3 (Heavy-tailed noise). For any Fi-measurable random vectors a E R we have the following: Vi E [n], VI 2 0, (1) Eig (xr {i Fi] = < Ji();; (2) There exist p E (1, 2], some constant a 2 0 such that (x $ ( Fi S o"; (3) The The family {c) Vt 2 0, E [n]] of random samples is independent.
Remark (Heavy-tailed distributions). Assumption S covers a broad class of heavy-tailed distri- butions, including Lévy's a-stable distributions, Student's t-distributions, and Pareto distributions. Note that we do not assume noise symmetry as in Yu et al. (2023), and when p = 2, Assumption reduces the standard bounded variance condition commonly assumed in the literature.
Empriial Dendty
Re so-
Gradient Nolee horm, Spoth
Empirica Densigg
20.0
27.5
Gradien: Nolte Nom,, Spoth
8 15.00
@ 1325
Gradient Roise Norm, Ezech 10
2-.70
25
Levy esstable Distribution
13.5-
20
10.0-
99.5
5.0
E9.5
0:30
0.32 9.34 0:35
0.38 0.40
0,30
0:35 0:40 0.65 0.50
0.0
0.35 4:40 0.45
0.50 0.50
9.00
-6 -4 -2
Iwas horm
Nose Narm
Norm
Levy random vartadle
(a) Epoch
(b) Epoch 6
(c) Epoch 10
(d) a-stable distribution
Figure I: Comparisons of the empirical density of gradient noise norm in different epochs of training a Transformer model with a synthetic Lévy a-stable distribution.
Remark 2 (Empirical evidence). Similar to Zhang et al. (020 Yang al. 2022), investigate the empirical distribution of the gradient noise norm g (x, E) f(()) in a centralized setting by the Multi30k dataset (Elliot
training GPT model (Radford et al. 2018 with 3M parameters
et al. 2016). where g(x) denotes the mini-batch stochastic gradient and f denotes the full- batch gradient. We train the model for 12 epochs using SGD and plot the empirical density of the
noise norm at the beginning of epochs O, 6, and 10. As shown in Figure | as training progresses, the tail of the empirical gradient noise norm distribution becomes heavier (and longer) and increasingly resembles that of a synthetic a-stable distribution.
For peer-to-peer communication in decentralized settings, we need to specify a mixing matrix W on graph 9 = (),
Assumption 4 (Weight matrix). The nonnegative weight matrix W, whose rit component of W, denoted as Wir, is positive if and only if (i.r) E & or = is primitive and doubly stochastic, i.e, 1, 1, and 1, =
Assumption 2 is standard in the decentralized optimization literature (Xin et al. 2020a and it guarantees that there exists some nonnegative X, i.e., spectral gap, such that
I 1, 1 /nll2 = 1.
The assumed weight matrix W can be constructed on undirected and connected graphs (Olshevsky 2014), and also on some directed and strongly connected graphs that weight-balanced (Ghare-
sifard & Cortés 2012). For instance, the family of directed exponential graphs, is weight-balance balanced and serves as an important topology configuration in decentralized training (Assran al. 2019
ALGORITHM DEVELOPMENT: GT-NSGDM
We now describe the proposed Algorithm GT GT-NSGDM and discuss the intuition of its construction. We use af to denote the estimate of a stationary point for the global cost function f at node i and t-th iteration, and recall that (z ) denotes the corresponding stochastic gradient returned from a local first-order oracle. Motivated by the error-feedback approach in Yu et al. (2023), which serves as momentun-type of variance reduction after applying nonlinear operator to handle heavy-tailed noise, we also employ local momentum variance reduction
c = Bot -1 + (1 (z)
where 3 [0, serves as the momentum coefficient. Then, we use gradient tracking (Di Lorenzo & Scutari 2016 to handle heterogeneous local functions (f:) Specifically, we estimator
5

---

Published as a conference paper at ICLR 2026
y to track the global gradient
7 Σ
wir y +
2 0/
It is known that gradient tracking helps eliminate the dependence heterogeneity among local functions {_i] such as the requirement of bounded gradient similarity. Furthermore, similar to the approach in Liu & Zhou (2025). which uses normalization to address heavy-tailed noise in centralized settings, we avoid applying normalization in the recursive updates of the local gradient estimator of in ① and the global gradient tracker y/- Instead, normalization is applied only during the update of ar., with step size a, and nonnegative mixing weights {worr where war > only when ri,r) E & or =r.
Σ Wir x
ar
y |
(3)
We combine the local updates 2 node i E V and call it GT GT-NSGDm, Gradient Tracking based Normalized Stochastic Gradient Descent with momentum. When taking / = O, this simplifies analysis shows that GT-NSCDm performs optimally for some 8 E (0, 1), making CT-NSCDm a non-trivial and optimal algorithmic design for the considered problem class. We provide tabular description for GT GT-NSGDm in Algorithm where all {**] } are initialized from the same point x" for simplicity.
to momentum-fiee gradient tracking with normalization in step 3 However,
Algorithm 1 GT NSGDm each node
Require: x; = x! = x², v. yi Od, a, B, fwir.. T.
1: for t = to T - 1 do
2: Sample c;
(random sample for stochastic gradient) (local gradient estimator) (local gradient tracker)
3:
30
+ (1 (x. {)::
4: yi Σ -= Wir (
v¹ 0. of-1);
5:
x
++1 Er= War (xt
v
(peer-to-perr communication)
6: end for
Remark (Why vanilla gradient normalization fails?). Although vanilla normalization success- fully used in centralized settings to robustify SGD against heavy-tailed noise (Hübler et al. 2024), its direct extension to the decentralized settings fails. Suppose we run vanilla decentralized nor- malized (noiseless) gradient descent, i.e., in parallel Vi E V.
x Σ Wir (at a (x(
(4)
|V
Then, the global average '' would update in the negative direction of the sum of normalized
local gradients: #1+1 = s¹ .. [V]+( Let for some t, Vr E V, x.
vf-(w())
i.e., all nodes hold the optimal global solution that Σ (f.) 0. Since [v.)( can be different quantities for r 1, 1,..., n, due to function heterogeneity, then I++1 will move away from I.. Therefore, vanilla gradient normalization adds some intrinsic errors from heterogeneous local normalizations. By incorporating gradient tracking, we expect that y would converge to its global average y', and ÿ' would converge to (1/n) En V (a())) In this way, of would move along the direction of the normalized sum of local gradients, and thus emulating the centralized setting.
arg min
In the following claim, we further demonstrate that vanilla gradient normalization can cause the iterates x to remain arbitrarily far from the optimal solution (see Appendix A for a proof).
Claim 1. Consider algorithu For any even n. for any B 2 1, there exist {f:);= satisfying Assumptions Z gradient oracle satisfying Assumption 3 mixing matrix satisfying Assumption and an initialization æo, such that the associated parameters fo, L, a, W, æn, are independent of B. Then, VT 2 v, > 0, it holds that 7. Er- E" E. [[IIV[(( 2 B.
We next break the limitations of vamilla gradient normalization in Claim by incorporating gradient tracking and momentum variance reduction. This enables the successtul use normalization to suppress heavy-tailed noise while maintaining optimal convergence despite the added nonlinearity.

---

Published as a conference paper at ICLR 2026
4 MAIN RESULTS
We present the main convergence results of GT-NSGDm and discuss their implications. The detailed analyses are deferred Appendix B
We first consider the case where the tail index p is known.
Theorem 1. Let Assumptions
3
4
hold. Denote f( fo Do. (f")))).... ..... fa()"
[I n @ )²). Take
Au(1 B)(1 A)
Au(1- X)
(1 A)2A.
min (1,
V
(5)
4LT
3.5LT
2n LT
and 1 1 = 1/T 3/ Assume 1/10, then the sequence generated by CT-NSGDD satisfies that
T-1 n
LAo
|V
3.5LAo
E [[ 0
nT
By
x
T
(1 A)T
n LDo X
oT
|VF(1, @ 1 (1 3
n2
Ao
3
Remark 4 (Order-optimal rate). Theorem 1 establishes a non-asymptotic upper bound on the mean l2 norm stationary gap of GT-NSGDm over any finite time horizon T. The O()) here only absorbs
universal constants and preserves all problem parameters. It achieves the optimal O(1/T 5-2 convergence rate terms of T as matches the lower bound proved in ZZang al. 2020 This optimal guarantee is achieved in decentralized settings for the first time.
Remark 5 (Speedup in n)) We discuss the asymptotic speedup in number of nodes For sufficiently large T (or sufficiently small target optimality gap), the upper bound in Theorem is dominated
by the leading terms (1/T (a/nn' + LL - A))_ In the high-noise regime n /
X), the upper bound has a speedup factor n 1-1p/ In practice, the noise scale (measured by o) in training attention models in other high-dimensional problems can be very large, and the speedup in n contributes as a noise reduction.
When the tail index is unknown in ad advance, we establish the following convergence rate.
Theorem 2. Let Assumptions I 3 B 2 1/10. Then GT-NSGDm guarantees that
hold and take in Take 1 - B 1/VT and assume
T-1 E
| f(x/ill
S O
LA
3.5LAu
nfT
T
X
VT
X)T
on
VF & T1)||
nt L&u
on
Au
(1=A)=V (1- A)n=
- X)
(1
X)T 2v
T
Theorem establishes an upper bound of ( " when the tail index p is unknown, matching the known rate in the centralized setting where algorithm parameters do not rely p (Liu & Zhou 2025). While the convergence rate in Yu et al] (023) is also independent of the knowledge of p, it is only for strongly convex functions and its exact rate exponent remains unspecified.
Remark 6 (Speedup in n and topology independent rate). Consider p (1, i.e., the heavy-tailed case with unbounded variance this paper focuses on. When 7' is sufficiently large (as required to achieve sufficiently small target optimality gap), the upper bound in Theorem 2 is dominated by 1/-1/P 1/-- Significantly, this upper bound is independent of network topology (A) and exhibits a speedup factor n. 1-1p in all regimes.
Remark 7 (Hyperparameter selection). We compare with the centralized work Liu & Zhou (0025) in terms of hyperparameter selections. When p is known, the centralized setup requires Do, L, o, T,
while our decentralized setup requires Ag, L, T, X, n. Notably, our selection is independent of but requires the network parameters A. When p unknown, the centralized setup requires L, T, while the decentralized case additionally requires Ag X, n. We note that n is generally easy to estimate, and give example where our hyperparameter dependence À can be eliminated. If all nodes
7

---

Published as a conference paper at ICLR 2026
(1/n) //) where L is the graph Laplacian, can obtain the estimate À $ c/n² (Mohar et al. 1991 for some universal constant c. Once we have such an upper bound, we can replace the terms involving 1/(1 A) with this estimate in equation (35); then in the final proof steps, we can select a step size that is independent of while still obtaining the same order-optimal rate.
know and set weights W =
Remark 8 (Dominant terms for small T). Both Theorems and order the upper bound terms in an increasing order of the rate exponent of 1/TT, the dominant terms are clear for sufficiently large T. We briefly discuss some cases to illustrate the effects of other parameters including n, X, and p when T is small. We discuss one varying parameter while assuming other parameters are fixed.
First, for network connectivity 1 - X, 1/T sp-2 has coefficient vi-x while the faster decaying term
VT has coefficient T-X. When 1 - x <
(Sp-2) the latter term
w//2
11/2 [1-A]=
will dominate.
VT
Second, for nn 2 (1 2/2 will also have a dominant term
LA/ Third, (1-1)
/T
for p (1,2]: When p approaches 1 from above, 76-11//p-2] will have coefficient
LAo
an
and the speedup in terms of the number of nodes will vanish, but the change in Te/05-2 (1-X)175 will not introduce a new dominant term if we focus on the dependence on
since there already
exists slower term 1 n
VT 1-X Similarly, when approaches 2, the speedup in n is more significant; 1/2
the term T</ 27 (1- Xj1/5 only gets smaller and does not change the dominant terms. Although our rates are established for general p E (1. we can compare parameter dependence with rates obtained for p = only. For example, in Xin et al. (202T), for large enough T, the upper bound is
Ao +oVT of
VuoL. (1 (1-x2 + FI (0 ).
n1/171/1
(1 22)3/2T
If we set p = 2 in our bounds, dropping some higher order terms, we have
o T1/4 (V
LAu 1-X 1/2
1 VT
/..5AD V 1-> VI
on A1- (1 2)1/2
n L
(IVF(E")I
We compare the above two bounds. For coefficients of 1/T2/4, our bound has dependence 1 1/n2/2 which is faster than the 1/n2/1 in the 2 case, but the dependence in 1/v1 - À is worse. For coefficients of 1/VT, our bounds have dependence 1/(1 - X) while the 2 case has dependence 1/(1 X3)3/2, which is strictly larger than ours.
5 EXPERIMENTS
We assess the performance of GT-NSGDm through numerical experiments. We first conduct studies on synthetic datasets that mimic language modeling under controlled heavy-tailed noise injection, following Lee al. (025). We also present experiments on decentralized training of a decoder-only Transformer (GPT) model with 3M parameters on the Multi30k dataset.
Baselines. We compare GT NSGDm with four decentralized baselines: DSGD Nedic Ozdaglar 2009) GT-DSGD (Xin et al. 2020b), DSCD-Clip Sunn & Chen 2024). and SClip-Bi -Network YYu et al. 2023). DSGD and GT-DSGD handle regular stochastic noise with bounded variance. DSGD- C1 ip converges for strongly convex functions under bounded domains or gra- dients (Sun Chen 2024). Delip-EF-Nete work achieves convergence under symmetric noise with bounded E
< P [ii]] for p 1. All methods are initialized identically and tuned via grid
search. Detailed baseline descriptions appear in Table 2 (Appendix C.T.
Graph topology. We consider three graph topologies: undirected ring, directed exponential, and complete graphs (see Lian et al. (2017): Nedić et al. (2018): Assran et al. (2019)). Weight matrices set the number of nodes to n = 20, we obtain À = 0.904, 0.714, and 0 for the ring, exponential, and complete graphs, respectively. For Transformer training with 8, we have corresponding X 0.804, 0.6, and 0.
Metropolis weights (Xiao et al.) 2005). For synthetic experiments,
8

---

Published as a conference paper at ICLR 2026
5.1 ROBUST LINEAR REGRESSION ON SYNTHETIC TOKENIZED DATA
We use this synthetic experiment to test our convergence rates under controlled heavy-tailed noise. We consider nonconvex regularized linear regression on synthetic data mimicking language tokens. In language modeling, token frequencies exhibit heavy-tailed distributions: few tokens appear fre- quently, while most are rare but contextually important. We construct the following synthetic dataset X of 1k samples of dimension d 20. The first four features simulate frequent tokens and are sam- pled independently from Bernoulli distributions: the first two from Bern(0.9) and the next two from (0rn(..5). The remaining 16 features represent rare tokens, each sampled from Bor1(0.1). The op- timal weight w, is Gaussian Gaussian-sampled sampled, with labels y = X The synthetic dataset (X, y) is evenly distributed over n 20 nodes, where each node i holds sub-dataset (X;, y:). estimate wz; and a linear regression model with nonconvex robust Tukey's biweight loss function (Beaton & Tukey 1974) to estimate w,, We inject three different zero-mean noises, Gaussian noise (O, 34)33 Smi dent's s noise (degrees of freedom 1.5, scale 1.0), and Lévy a-stable noise (stability parameter 1.5, skewness parameter 0.5, scale 1.0, non-symmetric, multiplied by 0.1) into the exact gradient, using corrupted stochastic gradients for updates. See Appendix for additional details.
In Figure we evaluate GT-NSGDm against baselines on ring graphs under various gradient noise. DSGD and GT-DSGD converge under Gaussian noise but become unstable under heavy- tailed noise. DSGD-Clip remains stable but fails to reach the optimum. Both GT-NSGDm and SCl Sclip-EFF -Fpp-=F-Netwrrd exhibit robust convergence and near-optimal performance across all sce- narios, consistent with their theoretical guarantees under heavy-tailed noise.
Ring Graph, Gaussian Noise
Ring Graph, Student's Noise
Graph, Lévy o-stable Noise
Average escimaation enror 12
DSGD
DSGD Clip
Average essimation
GT DSGD
Average essimation
GT-N5GDe
SCIp CF Network
2000
3030
0000
5000
10000
2000
3000
0000
5000
10000
2002
-050
0000
5000
10000
Step count
Step count
Step count
(a) Gaussian Noise
(b) Student's noise
(c) Lévy cx-stable noise
Figure 2: Comparison of performance ring graph under various types of injected stochastic
gradient noise, measured by the average estimation error (1/n) Σ ||w] w. over step count t.
In Figure S we test GT GN-NGSD'ss dependence on connectivity (A), noise level (a), and the number of nodes (n), varying each while fixing others. In Figure B a), we inject Lévy o-stable noise and test the performance of GT NNGDDm on ring, directed exponential, undirected exponential, and complete graphs with \ 0.904, 0.714, 0.6, O, respectively. GT-NSGDm achieves comparable final errors under weak connectivity (i.e., large X) versus complete graphs, showing favorable dependence on network connectivity under heavy-tailed noise. In Figure B(),, we evaluate GT-NSGDm's perfor- mance under different noise levels on directed exponential graph. Under Gaussian noise with scale (unit variance), GT-NSGDm reaches the best optimality; the final error increases as a grows, as observed under both Gaussian and Lévy a-stable noise. In Figure 3J., we inject Lévy cr-table noise on complete graphs (A = 0 for all n) with varying number of nodes. As n increases from 2 to 40, convergence speed improves with final errors [0.4, 0.35, 0.29, 0.20. 0.21]. demonstrating speedup over certain n ranges, supporting theoretical discussions in Remarks and
5.2 DECENTRALIZED TRAINING OF TRANSFORMERS
We evaluate GT-NSGDm's 's empirical performance on language modeling using a 3M-parmmeter GPT model (Radford et al. 2018) for auto-regressive modeling on Multi30k (29k sentences, 4.4M to- kens). We assess performance using validation log-perplexity. On 8-node graphs with three topolo- gies, we distribute training data evenly and initialize identical GPT models per node. We introduce three additional baselines: DSGD-GClip (DSGD with constant step size and lz gradient clipping level), DSGD-CClip (DSGD with constant step size and component-wise gradient clipping level), QG-DSGDm (Lin al. 2021 and GT-Adam (Carnevale et al. 2022 (all without theoretical guar-
9

---

Published as a conference paper at ICLR 2026
Lévy costable Noise, Varying Graphs
Directed Exponential Graph, Varying Noise
Complete Graph, Varying 2s
Ring Graph
Averoge estima tton error
Garso in noba, scale
Diected Exponental Graph
Gauss noite, scale
Averoge estimation
Undioeted Experential Graph
Stutlent's moiee
Averoge estima tion 10
Complets Guph
Lisy cistable noiee
Luy costable noiue 0.2
Step count
Step count
Step count
(a) Dependence on X
(b) Dependence on
(c)
Dependence on n
Figure 3: Empirical studies on GT-NSGDm's dependence on problem parameters X, G, n.
antees under heavy-tailed noise; see Table in Appendix w We run all methods for 12 epochs with batch size 64. See Appendix C.3 for model and hyperparameter details.
Table I presents average validation loss and standard deviation five independent runs for each algorithm across three topologies. Results show that CT-NSGDm nearly matches the best baseline DSGD- BDED-GClipp ip (which lacks theoretical guarantees under heavy-tailed gradient noise) while signifi- cantly outperforning the other two aeooretically-guraanteee baselines across all topologies. We note that this decentralized training experiment is simulated to demonstrate algorithm effectiveness and has practical limitations.
Table 1:
Topologies ring, directed exponential (Exp.), and complete (Comp.) graphs. Algorithms are grouped by theoretical (Theo.) guarantees under heavy-tailed noise: with (w/) without (w/o).
Algorithms
Theo.
Ring
Exp.
Comp.
DSGD
w/o
5.633
5.63220.007
5.635.0.007
DSGD-GClip
w/o
0. 40.037
00.000
0.267
DSGD-CClip
w/o
2. 2.72543.11 179
5.058
8.225+1.093
GT-DSGD
w/o 5.36210.002
5.63210.0m
5.631 10.002
GT-Adam
w/o
0.520 10.038
0.587 10.099
0.52410.045
QG-DSGDM w/o 00.04700.077
1.388110.033
0.353
SClip-BP-Network
w/
5.653
3.632
5.63640.000
DSGD-Clip w/
5.663
5.659
5.66140.006
GT-NSGDm w/
0. 258 0.255810.007 10.007
0.261 1.0.07
0.2822:0.009
CONCLUSION AND FUTURE WORK
In this paper, we have proposed GT GI-NSGDM for solving decentralized nonconvex smooth optimiza- tion to address heavy-tailed noise. The key idea is to leverage normalization, together with momen- tum variance reduction, combat heavy-tailed noise, and use gradient tracking handle cross-node heterogeneity and the nonlinearity introduced by normalization. Theoretical analyses establish that GT-NSGDM attains an optimal convergence rate when the tail index p is known, and rate that matches the best centralized one when is unknown. Extensive experiments nonconvex linear regression and decentralized Transformer training show that GT-NSGDm. is robust and efficient un- der heavy-tailed noise across various topologies. and achieves speedup in Future directions include extending the current analysis to other nonlinearities, such as sign and clipping (Zhang al. 2020), and generalizing GT-NSGDm handle objective functions under relaxed smoothness conditions (Liu & Zhou 2025).
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
We thank the anonymous reviewers for their valuable feedback that improved the presentation of this paper and for identifying minor errors in the proofs. The work S. Yu and S. Kar is supported in part by NSF grant ECCS 2330196. The work of D. Jakovetic was supported by the Ministry of Science, Technological Development, and Innovation (Grants No. 451-03-33/2026-03 200125 & 451 151-03-3442026-033 200125); and the Science Fund of Republic of Serbia, project "LASCADO" (grant 7359).
REPRODUCIBLE STATEMENT
We provide detailed proofs for Claim in Appendix AapendixAAaandd for our main theoretical results, Theorems D and in Appendix B In Appendix provide detailed hardware configurations, algorithm descriptions, and hyperparameter settings for our numerical experiments.
REFERENCES
Kwangjun Ahn, Xiang Cheng, Minhak Song, Chulhee Yun, Ali Jadbabaie, and Suvrit Sra. Lin- ear attention is (maybe) all you need (to understand transformer optimization). The Twelfth International Conference Learning Representations, 2024.
Aleksandar Armacki, Shuhua Yu, Dragana Bajovic, Dusan Jakovetic, and Soummya Kar. Large deviations and improved mean- meua-- error rates of nonlinear sgd: Heavy-tailed noise and power of symmetry. arXiv preprint arXiv:2410. 15637, 2024.
Aleksandar Armacki, Shuhua Yu, Pranay Sharma, Gauri Joshi, Dragana Bajovic, Dusan Jakovetic, and Soummya Kar. sig-ppoobability convergence bounds for online nonlinear stochastic gradient descent under heavy-tailed noise. In The 28th International Conference on Artificial Intelligence and Statistics, 2025.
Mahmoud Assran, Nicolas Loizou, Nicolas Ballas, and Mike Rabbat. Stochastic gradient push for distributed deep learning. In International Conference on Machine Learning, pp. 344-353. PMLR, 2019.
Melih Barsbey, Milad Sefidgaran, Murat A Erdogdu, Gael Richard, and Umut Simsekli. Heavy tails in sgd and compressibility of overparametrized neural networks. Advances in neural information processing systems, 02223344-93788 2021.
Barak Battash, Lior Wolf, and Ofir Lindenbaum. Revisiting the noise model of stochastic gradient descent. In International Conference Artificial Intelligence and Statistics, pp. 4780-4788 PMLR, 2024.
Albert E Beaton and John W Tukey. The fitting of power series, meaning polynomials, illustrated on sund-spectroscopic data. Technometrics, 16(2):147-185, 1974.
Theodora S Brisimi, Ruidi Chen, Theofanie Mela, Alex Olshevsky, Ioannis Ch Paschalidis, and Wei Shi. Federated learning of predictive models from federated electronic health records. Interna- lional journal of medical informatics, 1 11::99-6 67, 2018.
Guido Carnevale, Francesco Farina, Ivano Notarnicola, and Giuseppe Notarstefano. Gtadam: Gra- dient tracking with adaptive momentum for distributed online optimization. IEEE Transactions on Control of Network Systems, 10(3):14366 1448, 2022.
Zachary Charles, Zachary Garrett, Zhouyuan Huo, Sergei Shmulyian, and Virginia Smith. On large- cohort training for federated learning. Advances in neural information processing systems, 34: 20461-20475, 2021.
Savelii Chezhegov, Yaroslav Klyukin, Andrei Semenov. Aleksandr Beznosikov, Alexander Gas- nikov, Samuel Horváth, Martin Takáč, and Eduard Gorbunov. Gradient clipping improves adagrad when the noise is heavy-tailed. arXiv preprint arXiv:2406. 240V:22000.04443,, 04443, 2024.
11

---

Published as a conference paper at ICLR 2026
Enea Monzio Compagnoni. Rustem Islamov, Frank Norbert Proske, and Aurelien Lucchi. Unbiased and sign compression in distributed learning: Comparing noise resilience via SDEs. In The 28th International Conference Artificial Intelligence and Statistics, 2025a.
Enea Monzio Compagnoni, Tianlin Liu, Rustem Islamov, Frank Norbert Proske, Antonio Orvieto, and Aurelien Lucchi. Adaptive methods through the lens of SDEs: Theoretical insights on the role of noise. In The Thirteenth International Conference on Learning Representations, 2025b.
Paolo Di Lorenzo and Gesualdo Scutari. Next: In-network nonconvex optimization. IEEE Transac- fions on Signal and Information Processing over Networks, 2(2): 136, 2016.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of machine learning research, 12(7), 2011.
Desmond Elliott, Stella Frank, Khalil Sima' an, and Lucia Specia, Multi30k: Multilingual english- german image descriptions. arXiv preprint arXiv: 160.00040 2016.
Bahman Gharesifard and Jorge Cortés. Distributed strategies for generating weight-balanced and doubly stochastic digraphs. European Journal of Control. 18(6):539-557) 2012.
Eduard Gorbunov, Marina Danilova, and Alexander Gasnikov. Stochastic optimization with heavy- tailed noise via accelerated gradient clipping. Advances Neural Information Processing Sys- lems, 33:15042-15053, 2020.
Eduard Gorbunov, Abdurakhmon Sadiev, Marina Danilova, Samuel Horváth, Gauthier Gidel, Pavel Dvurechensky, Alexander Gasnikov, and Peter Richtárik. High-prooe sesh-probbbblity convergence for com- posite and distributed stochastic minimization and variational inequalities with heavy-tailed noise, 2024. URL https: http:////peeeeeieeeee ntt//ooruute wtt.oorummmiiiooooooooo OpMoee
Mert Gurbuzbalaban, Umut Simsekli, and Lingjiong Zhu. The heavy-tail phenomenon in sgd. In International Conference on Machine Learning, pp. 3964-3975. PMLR, 2021.
Florian Hübler, Ilyas Fatkhullin, and Niao He. From gradient clipping to normalization for heavy tailed sgd. arXiv preprint arXiv:2410. 13849, 2024.
Dusan Jakovetić, Dragana Bajović, Anit Kumar Sahu, Soummya Kar, Nemanja Milosević, and Du- san Stamenković. Nonlinear gradient mappings and stochastic optimization: general framework with applications to heavy-tail noise. SIAM Journal on Optimization, 33(2):394-473 2023.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Ad- vances and open problems in federated learning. Foundations and Trends@ in Machine Learning, 14(1-2):1-210, 2021.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 1:Xiv:1412.69882 69800, 2014.
Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian Stich. A unified theory of decentralized sgd with changing topology and local updates. In International Confer- ence on Machine Learning, pp. 5381-5393. PMLR, 2020.
Frederik Kunstner, Alan Milligan, Robin Yadav, Mark Schmidt, and Alberto Bietti. Heavy-tailed class imbalance and why adam outperforms gradient descent language models. Advances in Neural Information Processing Systems, 37:30 106-3014,, 2024.
Su Hyeong Lee, Sidharth Sharma, Manzil Zaheer, and Tian Li. Efficient adaptive federated opti- mization. arXiv preprint arXiv:2410. 18/11, 2024.
Su Hyeong Lee, Manzil Zaheer, and Tian Li. Efficient distributed optimization under heavy-tailed noise. arXiv preprint arXiv:2002.04164 2025.
Boyue Li and Yuejie Chi. Convergence and privacy of decentralized nonconvex optimization with gradient clipping and communication compression. JEEE Journal of Selected Topics in Signal Processing, 2025.
12

---

Published as a conference paper at ICLR 2026
Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Challenges, methods, and future directions. IEEE signal processing magazine, 37(3):50 60, 2020.
Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsich, Wei Zhang, and Ji Liu, Can decentralized algorithms outperform centralized algorithms? case study for decentralized parallel stochastic gradient descent. Advances in neural information processing systems, 30, 2017.
Tao Lin, Sai Praneeth Karimireddy, Sehastian Stich, and Martin Jaggi. Quasi-global momentum: Accelerating decentralized deep learning on heterogeneous data. In International Conference on Machine Learning, pp. 1654-6665. PMLR, 2021.
Zijian Liu and Zhengyuan Zhou. Nonconvex stochastic optimization under heavy-tailed noises: Optimal convergence without gradient clipping. In The Thirleenth International Conference on Learning Reprexentations, 2025.
Zijian Liu, Jiawei Zhang, and Zhengyuan Zhou. Breaking the lower bound with (little) structure: Acceleration in non non-convex stochastic optimization with heavy-tailed noise. In The Thirty Sixth Annual Conference on Leurning Theory, pp. 2266-2290. PMLR, 2023.
Bojan Mohar, Y Alavi, G Chartrand, and Ortrud Oellermann. The laplacian spectrum of graphs. Graph theory, combinatorics, and applications, 2(871 1991.
Jayakrishnan Nair, Adam Wierman, and Bert Zwart. The fundamentasss of heavy tails: Properties, emergence, and estimation, volume 53, Cambridge University Press, 2022.
Angelia Nedic and Asuman Ozdaglar. Distributed subgradient methods for multi-agent optimiza- tion. IEEE Transactions on Automatic Control, 54(1):48-61, 2009.
Angelia Nedić, Alex Olshevsky, and Michael Rabbat. Network topology and communication- computation tradeoffs in decentralized optimization. Proceedings of the IEEE, 106(5):953-97) 2018.
Ta Duy Nguyen, Thien H Nguyen, Alina Enc, and Huy Nguyen. Improved convergence in high probability of clipped gradient methods with heavy tailed noise. Advances in Neural Information Processing Systems, 36:24191-24222 2023.
Alex Olshevsky. Linear time average consensus on fixed graphs and implications for decentralized optimization and multi-agent control. arXiv preprint 1xXiv::411.44 2014.
Stefano Peluchetti, Stefano Favaro, and Sandra Fortini. Stable behaviour of infinitely wide deep neural networks. In International Conference on Artificial Intelligence and Statistics, pp. 1137- 1146. PMLR, 2020.
Shi Pu and Angelia Nedié. Distributed stochastic gradient tracking methods. Mathematical Pro- gramming, 187(1):409 457, 2021.
Alec Radford, Karthik Narasimhan, Tim Salimans, llya Sutskever, al. Improving language under- standing by generative tre-training. 2018.
Abdurakhmon Sadiev, Marina Danilova, Eduard Gorbunov, Samuel Horváth, Gauthier Gidel, Pavel Dvurechensky, Alexander Gasnikov, and Peter Richtárik. High-probability bounds for stochas- tic optimization and variational inequalities: the case of unbounded variance. In International Conference on Machine Learning. pp. 29563-29648. PMLR, 2023.
Egor Shulgin, Sarit Khirirat, and Peter Richtárik. Smoothed normalization for efficient distributed private optimization. arXiv preprint arXiv:2502.13482. 2025.
Umut Simsekli, Levent Sagun, and Mert Gurbuzbalaban. A tail-index analysis stochastic gradient noise in deep neural networks. In International Conference on Machine Learning, pp. 5827-5877. PMLR, 2019.
Chao Sun and Bo Chen. Distributed stochastic strongly convex optimization under heavy-tailed noises. In 2024 IEEE International Conference Cybernetics and Intelligent Systems (CIS) and JEEE International Conference on Robotics, Automation and Mechatronics (RAM), pp. 150-155. IEEE, 2024.
13

---

Published as a conference paper at ICLR 2026
Tao Sun, Xinwang Liu, and Kun Yuan. Gradient normalization provably benefits nonconvex sgd under heavy-tailed noise. arXiv preprint 244::22400.6661,,, 2024.
S Sundhar Ram, Angelia Nedić, and Venugopal V Veeravalli. Distributed stochastic subgradient projection algorithms for convex optimization. Journal of optimization theory and applications, 147:516-545, 2010.
Hossein Taheri and Christos Thrampoulidis. On generalization of decentralized learning with sep- arable data. In International Conference on Artificial Intelligence and Statistics, pp. 4917-4945.
PMLR, 2023.
John Tsitsiklis, Dimitri Bertsekas, and Michael Athans. Distributed asynchronous deterministic and stochastic gradient optimization algorithms. IEEE transactions on automatic control, 31()): 803-812, 1986.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural informa- tion processing systems, 30, 2017.
Jianyu Wang and Gauri Joshi. Cooperative sgd: A unified framework for the design and analysis of local-update sgd algorithms. Journal Machine Learning Research, 22(213):1-50, 2021.
Lin Xiao, Stephen Boyd, and Sanjay Lall. A scheme for robust distributed sensor fusion based on average consensus. In IPSN 2005. Fourth International Symposium on Information Processing in Sensor Networks, 2005., pp- 63-70. IEEE, 2005.
Ran Xin, Usman A Khan, and Soummya Kar. Variance-reduced decentralized stochastic optimiza- tion with accelerated convergence. IEEE Transactions on Signal Processing, 6222,, 2020a.
Ran Xin, Shi Pu, Angelia Nedić, and Usman A Khan. A general framework for decentralized optimization with first-order methods. Proceedings of the IEEE, 108(1 10:1869-1888 2020b.
Ran Xin, Usman A Khan, and Soummya Kar. An improved convergence analysis for decentralized online stochastic non-convex optimization. IEEE Transactions on Signal Processing, 69; 1842- 1858, 2021.
Haibo Yang, Peiwen Qiu, and Jia Liu. Taming fat-tailed ("heavier-tailed" with potentially infinite variance) noise in federated learning. Advances in Neural Information Processing Systems, 35: 17017-17029, 2022.
Shuhua Yu and Soummya Kar. Secure distributed optimization under gradient attacks. IEEE Trans- actions Signal Processing, 2023.
Shuhua Yu, Dusan Jakovetic, and Soummya Kar. Smoothed gradient clipping and error feedback for decentralized optimization under symmetric heavy-tailed noise. arXiv preprint arXiv:2310.16920, 2023.
Kun Yuan, Bicheng Ying, Jiageng Liu, and Ali H Sayed. Variance-reduced stochastic learning by networked agents under random reshuffling. IEEE Transactions on Signal Processing, (7))): 351-366, 2018
Jingzhao Zhang, Sai Praneeth Karimireddy, Andreas Veit, Seungyeon Kim, Sashank Reddi, Sanjiv Kumar, and Suvrit Sra. Why are adaptive methods good for attention models? Advances in Neural Information Processing Systems, 33:15383-15399 2020.
14


Reviews:
[{"review_id": "LxvpCHsO7e", "reviewer": "Reviewer_28WH", "summary": "The paper presents and analyzes a decentralized normalized SGD with momentum algorithm based on gradient tracking. Crucially, for heavy-tailed gradient noise (observed specially in transformer optimization) with known $p \\in (1, 2]$ moment, the paper provides tight convergence rates in the non-convex setting. The paper also gives another bound when $p$ is unknown.", "questions": "please see previous part.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The heavy-noise gradient problem is very timely specially given the ubiquity of transformers. The decentralized optimization framework is a very well-studied  and classic setup for distributed optimization. The paper is sound and well-written for the most part. The analysis is sound, rigorous and appears to be tight as it matches the rate of centralized optimization. Experiments such as a decentralized GPT training simulation show the convergence and efficacy of the algorithm, although the performance of Clip-based algorithms is comparable.", "weaknesses": "-The algorithm and analysis benefits greatly from the recent works on the centralized setup (specially (Liu∗and Zhou, 2025)). The adaptations of normalized gradient descent algorithm to the decentralized setup based on gradient tracking, have been done in literature (although in a different context), including discussions on why the naive normalized Decentralized SGD fails (e.g., see section 2.4. in reference [1] below). Can the authors also please highlight the novelties in the proof needed to extend the proof of centralized setup to the decentralized setup?\n\n-How do the hyper-parameter selections compare to the centralized setup? Is the fact that $\\beta$ depends on unknown $T$ also the case in the centralized setup?\n\n-The displayed bounds include many additive terms with complex dependencies on $n,\\lambda, T,p$ and other parameters. It's not very obvious which term will dominate in practice, for example as $p$ varies. \n\n\ntypo: \n\nline 589: appendix 5\n\n[1] On Generalization of Decentralized Learning with Separable Data, Taheri et al. AISTATS 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lE996S1YoW", "reviewer": "Reviewer_E5CE", "summary": "The paper studies decentralized nonconvex optimization under heavy-tailed gradient noise, assuming only the $p$-th moment is finite ($p\\in(1,2]$). It proposes a method (GT-NSGDm) that combines gradient normalization, momentum-based variance reduction, and gradient tracking. Theoretically, the authors prove an order-optimal non-asymptotic rate $O\\big(T^{-(p-1)/(3p-2)}\\big)$ when $p$ is known (matching centralized lower bounds), and an adaptive $O\\big(T^{-(p-1)/(2p)}\\big)$ rate when $p$ is unknown that is topology-independent for $p<2$, yielding an $n^{1-1/p}$ speedup in the number of nodes.", "questions": "The paper offers strong theory (optimal rates, topology independence for unknown $p$) and a convincing negative result, but relies on mature building blocks, has a nontrivial tuning/assumption burden, and could broaden empirical validation.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Optimal/non-asymptotic theory. Establishes $O\\big(T^{-(p-1)/(3p-2)}\\big)$ for decentralized nonconvex problems with heavy tails (known $p$), matching centralized lower bounds; for unknown $p$, obtains $O\\big(T^{-(p-1)/(2p)}\\big)$ that is independent of graph topology for $p<2$, together with an $n^{1-1/p}$ speedup.\n\n- Design justification. A clear negative result demonstrates why gradient tracking + momentum are required beyond vanilla normalization in heterogeneous decentralized settings.\n\n- Unified view of practical ingredients. Normalization, momentum-based variance reduction, and gradient tracking are integrated into a single algorithm with a complete analysis.", "weaknesses": "- Incremental feel in building blocks. Although the combination achieves new rates, the core components (normalization, gradient tracking, momentum) are mature; algorithmic novelty per se is modest.\n\n- Assumption/tuning burden. Guarantees require primitive, doubly-stochastic mixing and nontrivial step-size/momentum schedules; several constants depend on spectral gap $\\lambda$, smoothness $L$, initial gap $\\Delta_0$, etc. Practical robustness when these are unknown is under-discussed.\n\n-  Results are stated in expectation, not high-probability guarantees.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "bmp5tRRUAh", "reviewer": "Reviewer_iF7b", "summary": "The authors propose a new decentralized optimization algorithm under heavy-tailed noise that achieves the optimal convergence rate in expectation when the tail constant $p$ is known, which matches centralized lower bounds. When $p$ is unknown, they still achieve the SoTA rate. The idea of the algorithm combines gradient tracking with normalization (on the search direction) plus momentum‑based variance reduction.", "questions": "Please see weaknesses. For suggestions, I don't have much; the paper appears solid. One suggestion might be that for the result that training collapses under heavy-tailed noise in distributed (or non-centralized) settings, there is also the work [1] which isn't cited in the paper.\n\n[1] Lee et al., Efficient Adaptive Federated Optimization. Arxiv, 2025.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The paper provides an algorithm achieving the optimal convergence rate $O\\left(T^{-(p-1) /(3 p-2)}\\right)$ for decentralized nonconvex optimization under heavy-tailed noise when $p$ is known.\n\n2. Incorporating normalization with gradient tracking and momentum is simultaneously seeks to address all three challenges of nonlinearity, heterogeneity, and heavy-tailed noise.\n\n3. The analysis holds for general smooth nonconvex functions, which relaxes assumptions used in some prior work.", "weaknesses": "1. The analysis is dense, and the presentation of the proofs may be improved for better clarify. For example, more intuitive scaffolding may be added. \n\n2. In Table 1, why do SClip-EF-Network and DSGD-Clip perform so poorly? Have the hyperparameters been tuned properly? For the latter, if an algorithm with heavy-tailed convergence guarantees perform this poorly, then does it cast doubt on the usefulness of the theoretical bound?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BqMQRlb5tK", "reviewer": "Reviewer_RYNE", "summary": "This paper introduces GT-NSGDm, a novel algorithm for decentralized nonconvex optimization under heavy-tailed gradient noise. By combining normalization, gradient tracking, and momentum, the method is the first to achieve an optimal convergence rate that matches the theoretical lower bound for the centralized setting. The algorithm's effectiveness is demonstrated on synthetic data and in training a transformer model.", "questions": "N/A", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The paper establishes a groundbreaking optimal convergence rate for this problem setting, a significant theoretical advance.\n\n- It addresses the well-documented issue of heavy-tailed noise in training large models and provides a robust design that works even when noise characteristics are unknown.\n\n- The theoretical results are well-supported by comprehensive experiments on both synthetic and real-world tasks.", "weaknesses": "- The analysis is limited to communication graphs with \"primitive and doubly stochastic weights,\" which may not hold in all practical scenarios.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)