Paper deep dive
Decentralized SGD under Heavy-Tailed Noise: Optimal Convergence Rates and the Role of Gradient Clipping
Aleksandar Armacki, Haoyuan Cai, Ali H. Sayed
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 95%
Last extracted: 10/8/2026, 6:05:14 AM
Summary
This paper analyzes the convergence of decentralized Stochastic Gradient Descent (DSGD) under heavy-tailed noise. It demonstrates that using gradient clipping allows the baseline DSGD algorithm to achieve order-optimal convergence rates and linear speed-up with respect to the number of agents, without requiring additional modifications like mini-batches or local momentum. The authors provide theoretical guarantees for smooth non-convex costs with bounded p-th moment noise (p in (1,2]) and validate their findings with numerical experiments, including decentralized transformer training.
Entities (10)
Relation Signals (8)
Aleksandar Armacki → affiliatedwith → École Polytechnique Fédérale de Lausanne
confidence 99% · Aleksandar Armacki Affiliation: École Polytechnique Fédérale de Lausanne
Ali H. Sayed → affiliatedwith → École Polytechnique Fédérale de Lausanne
confidence 99% · Ali H. Sayed Affiliation: École Polytechnique Fédérale de Lausanne
Haoyuan Cai → affiliatedwith → École Polytechnique Fédérale de Lausanne
confidence 99% · Haoyuan Cai Affiliation: École Polytechnique Fédérale de Lausanne
Clipped DSGD → achieves → Optimal Convergence Rates
confidence 95% · clipped DSGD achieves order-optimal rates both with high probability and in expectation.
Clipped DSGD → handles → Heavy-Tailed Noise
confidence 95% · We answer affirmatively with clipped decentralized SGD (DSGD)... under heavy-tailed noise
Clipped DSGD → provides → Linear Speed-up
confidence 95% · Moreover, we establish a linear speed-up in the number of agents
Gradient Clipping → enables → Convergence
confidence 90% · clipping retains magnitude information, enabling DSGD to be convergent
Normalized DSGD → failstoconverge → Heavy-Tailed Noise
confidence 90% · while normalized DSGD can fail to converge
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2610.10527v1
- Canonical: https://arxiv.org/abs/2610.10527v1
Trouble viewing inline? Open PDF directly →
Full Text
133,143 characters extracted from source content.
Expand or collapse full text
Decentralized SGD under Heavy-Tailed Noise: Optimal Convergence Rates and the Role of Gradient Clipping Aleksandar Armacki Affiliation: École Polytechnique Fédérale de Lausanne, Lausanne, Switzerland, aleksandar.armacki, haoyuan.cai, ali.sayed@epfl.ch Haoyuan Cai Affiliation: École Polytechnique Fédérale de Lausanne, Lausanne, Switzerland, aleksandar.armacki, haoyuan.cai, ali.sayed@epfl.ch Ali H. Sayed Affiliation: École Polytechnique Fédérale de Lausanne, Lausanne, Switzerland, aleksandar.armacki, haoyuan.cai, ali.sayed@epfl.ch 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 (DSGD). For smooth non-convex costs under bounded p-th moment noise, p∈(1,2]p∈(1,2], we show that clipped 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 DSGD can fail to converge, clipping retains magnitude information, enabling DSGD to be convergent and order-optimal. Numerical experiments validate our theory. 1 Introduction Modern learning systems, fueled by an abundance of data, often incur huge computation and storage costs. This naturally gives rise to distributed training, a paradigm where n agents jointly train a model, storing and processing their data locally, only exchanging model or gradient parameters (Sayed, 2014; McMahan et al., 2017; Vlaski et al., 2023). Two well-known instances are the client-server and the decentralized setup, differing mainly in the communication is performed: in the client-server setup agents communicate with a central server, while in the decentralized one agents communicate with each other. Noting that the client-server setup is mathematically equivalent to the decentralized one over a fully connected network, we focus on the more general decentralized setup. Another issue hampering modern learning systems is the emergence of heavy-tailed noise. First observed by Zhang et al. (2020) during training of the BERT model, the effects of heavy-tailed noise have been extensively studied in centralized settings, e.g., (Simsekli et al., 2019; Gurbuzbalaban et al., 2021; Barsbey et al., 2021; Nair et al., 2022; Battash et al., 2024), with nonlinear methods like clipping, normalization and sign widely used to deal with heavy tails. Recently, Gürbüzbalaban et al. (2025) showed that heavy-tailed noise arises naturally in decentralized settings, with decentralized SGD (DSGD) in some cases exhibiting heavier tails than its centralized counterpart. However, as we discuss next, convergence under heavy-tailed noise and the role of nonlinear methods are yet to be fully understood in decentralized settings. 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=2p=2 implying bounded variance and p<2p<2 allowing heavier tails. “Guarantees” indicates high-probability (HP) or in-expectation (IE) results. “Oracle Comp.” gives the per-agent number of ℱSFO calls needed to reach an ϵε-stationary point.§ “Lin. Speed-up” indicates whether linear speed-up in the number of agents is achieved. Work Algorithm Nonlinearity Noise Moment Guarantees Oracle Comp. Lin. Speed-up Yang et al. (2025) DSGD clipping p∈(1,2]p∈(1,2] HP ~(ϵ4p1−p) O (ε 4p1-p ) ✗ Li and Chi (2025)† gt + mini-b. + compr. + ef smoothclipping gatheredsmooth\\[-3.46594pt] clipping gathered p=2p=2 IE (ϵ−4)O (ε^-4 ) ✗ Yu et al. (2026a) gt + local momentum normalization p∈(1,2]p∈(1,2] IE (ϵ3p−21−p)O (ε 3p-21-p ) ✗ Wang et al. (2026)‡ gt + mini-b. + acc. gossip normalization p∈(1,2]p∈(1,2] IE (ϵ3p−21−p/n)O (ε 3p-21-p/n ) ✓ This work DSGD clipping p∈(1,2]p∈(1,2] HP & IE ~(ϵ3p−21−p/n) O (ε 3p-21-p/n ) ✓ § @sectionsign Because prior works use different stationarity metrics, we compare oracle complexities using target criteria based on both network-averaged iterates and agent-averaged local iterates, i.e., mint∈[T]‖∇f(x¯t)‖q≤ϵq _t∈[T]\|∇ f( x^t)\|^q≤ε^q and mint∈[T][1n∑i∈[n]‖∇f(xit)‖q]≤ϵq _t∈[T] [ 1n _i∈[n]\|∇ f(x^t_i)\|^q ]≤ε^q, q∈1,2q∈\1,2\. † Li and Chi (2025) use communication compression and error-feedback (EF) techniques, with mini-batch gradients of size b∝ϵ−2b ε^-2. The smooth clipping operator is defined as φ(x)=τ+‖x‖x (x)= τ+\|x\|x, for a user-specified τ>0τ>0. ‡ To mitigate network effects and achieve linear speed-up, Wang et al. (2026) use mini-batches of size b∝ϵp1−p/nb ε p1-p/n and, for undirected graphs, perform Θ~(1/1−λ) (1/ 1-λ ) communication rounds per iteration, where 1−λ1-λ is the network spectral gap (see Section 3 for definition). 1.1 Related Literature We next review convergence results under heavy-tailed noise, focusing on non-convex costs. For further literature, including convex results, see Supplement A. Centralized Settings. Moment assumptions on the stochastic first-order oracle (ℱSFO) including heavy-tailed regimes with only a finite p-th moment, p>1p>1, go back to Nemirovskiĭ and Yudin (1983). More recently, Zhang et al. (2020) noticed that the gradient noise during training of attention models resembles Levy α-stable noise and proposed the use of the bounded p-th moment condition. They establish an in-expectation (IE) lower bound Ω(ϵ3p−21−p) (ε 3p-21-p ) on the oracle complexity,11 1 Meaning the number of ℱSFO calls needed to reach an ϵε-stationary point, see Table 1 for details. and show it is achieved by clipped SGD. Cutkosky and Mehta (2021) complement this in the high-probability (HP) sense, for clipped + normalized momentum SGD. Sadiev et al. (2023); Nguyen et al. (2023) then establish HP guarantees for clipped SGD, with Nguyen et al. (2023) showing the optimal HP oracle complexity, while the same is established for normalization in (Liu and Zhou, 2025; Hübler et al., 2025) and sign SGD in (Kornilov et al., 2025). Liu et al. (2023b) show an accelerated rate and improved complexity, using a STORM-like method (Cutkosky and Orabona, 2019) with clipping + normalization, while Armacki et al. (2026a) demonstrate order of magnitude faster tail decay of clipped SGD. A related line of work studies symmetric heavy-tailed noise, dating back to Polyak and Tsypkin (1979). Among them, Bernstein et al. (2019); Chen et al. (2020) analyze IE guarantees of sign and clipped SGD, showing (ϵ−4)O(ε^-4) oracle complexity, while Armacki et al. (2025); Armacki et al. (2026d); Armacki et al. (2026b) study a nonlinear SGD framework that includes sign, normalization and clipping, among other results establishing (ϵ−4)O(ε^-4) IE and HP oracle complexity. Finally, a recent line of work shows that vanilla SGD can converge under heavy-tailed noise without any nonlinear methods, e.g., (Fatkhullin et al., 2025; Liu, 2026). Decentralized Settings. Nonlinear methods have a long history of use in decentralized settings, including applications such as estimation, adversarial learning and differential privacy, e.g., (Kar et al., 2012; Chen et al., 2019; Yu and Kar, 2023; Zhu et al., 2025). However, only a few works study convergence of nonlinear decentralized methods under heavy-tailed noise. In particular, Yang et al. (2025) study HP convergence of clipped DSGD in online dynamic optimization under p-th moment noise, requiring bounded gradients and achieving ~(ϵ4p1−p) O (ε 4p1-p ) per-agent oracle complexity.22 2 Per-agent complexity is the number of ℱSFO calls needed per agent to reach an ϵε-stationary point, implying a total complexity of n × the per-agent one. Li and Chi (2025) study communication-efficient learning under bounded variance noise (p=2p=2), requiring a strong heterogeneity bound (see Subsection 3.1 and Footnote 5 ahead) and using a complex method (see Table 1) to achieve (ϵ−4)O (ε^-4 ) IE oracle complexity. Yu et al. (2026a) study convergence of gradient tracking (GT) with normalization and local momentum under p-th moment noise, achieving (ϵ3p−21−p)O (ε 3p-21-p ) IE oracle complexity, while Wang et al. (2026) similarly study GT with normalization, using large mini-batches and accelerated gossip (i.e., multiple communication rounds per iteration) to achieve the optimal (ϵ3p−21−p/n)O (ε 3p-21-p/n ) per-agent IE oracle complexity.33 3 Optimal in the sense that the total complexity matches the optimal complexity achieved in centralized settings. All of the said works require either strong heterogeneity bounds, or algorithmic modifications like local-momentum, mini-batches and accelerated gossip, with only (Wang et al., 2026) achieving the optimal complexity and linear speed-up in the number of agents.44 4 While the (ϵ−4)O (ε^-4 ) per-agent complexity in Li and Chi (2025) matches the optimal centralized complexity under noise with bounded variance, it implies a sub-optimal (nϵ−4)O (nε^-4 ) total complexity. Similarly, while the per-agent complexity in (Yu et al., 2026a) matches the optimal centralized complexity, the total complexity is sub-optimal by a factor of n, due to not achieving linear speed-up. The need for algorithmic modifications when using nonlinear methods is further supported in (Yu et al., 2026a, Proposition 1), where it is shown that normalized DSGD with noiseless gradients can fail to converge even on a simple quadratic cost. These observations naturally led us to ask: Can a standard decentralized method with a nonlinear map achieve optimal complexity under heavy-tailed noise, without further algorithmic modification? To answer this question, we revisit the guarantees of DSGD using gradient clipping. In Figure 1 we show that clipping indeed fixes the non-convergence induced by normalization, while Table 1 provides a detailed comparison of nonlinear decentralized methods that converge to stationarity, giving a positive answer to the question above, in the form of clipped DSGD. 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. 1.2 Contributions Our full contributions can be summarized as follows. • We study convergence of decentralized methods using a nonlinearity under heavy-tailed noise, showing that baseline DSGD with gradient clipping achieves optimal oracle complexity and linear speed-up, under standard assumptions (see Subsection 3.1) and without any additional algorithmic modifications. • Compared to results on clipping in decentralized settings, we relax the strong heterogeneity bounds and, to our knowledge, show the first linear speed-up result for clipped DSGD. Compared to works using normalization, we show that a simple decentralized method can achieve optimal complexity with an appropriately chosen nonlinearity, establishing important insights on the effects of clipping and normalization in decentralized settings (see Subsection 3.2). • We extensively test our theory on several problems, including decentralized transformer training on real data, showing that: (i)(i) clipping improves performance under heavy tails, (ii)(i) clipped DSGD achieves linear speed-up; (iii)(i) clipped DSGD regularly performs on par with or outperforms normalized DSGD. Novelty. Our results are facilitated by several novelties and improvements. First, we relax the strong heterogeneity bounds in prior works via a sharp analysis and careful choice of clipping radius. Next, a novel consensus bound in Lemma 4 and a novel coupling of step-size and clipping radius (see Subsection 3.2) ensure that the network only affects higher-order terms. Finally, we achieve linear speed-up by combining these results, an improved analysis, improved choice of step-size and clipping radius, and Lemma 1, which shows that averaging clipped vectors reduces the variance. Paper Organization. The rest of the paper is organized as follows. Section 2 gives the preliminaries, Section 3 states the main results, Section 4 presents experiments, while Section 5 concludes the paper. Supplement contains results omitted from the main body. The rest of this section introduces some notation. Notation. ℕN, ℝR and ℝdR^d denote positive integers, real numbers and d-dimensional vectors. For m∈ℕm , [m][m] denotes positive integers up to and including m. ⟨⋅,⋅⟩ ·,· is the Euclidean inner product, while ∥⋅∥\|·\| is the induced vector/matrix norm. Subscripts denote agents and superscripts denote the iteration, e.g., xitx^t_i refers to agent i’s model in iteration t. The “big O” notation (⋅)O(·) hides global constants, while ~(⋅) O(·) additionally hides poly-logarithmic factors, unless stated otherwise. 2 Preliminaries In this section we outline the preliminaries. Subsection 2.1 introduces the problem, while Subsection 2.2 presents the clipped DSGD method. 2.1 Problem Setup Formally, the problem we aim to solve is given by argminx∈ℝdf(x)=1n∑i∈[n]fi(x), _x ^d \f(x)= 1n _i∈[n]f_i(x) \, (1) where x∈ℝdx ^d represents model parameters, n≥2n≥ 2 is the number of agents, while fi:ℝd↦ℝf_i:R^d is the cost of agent i. The communication network is modeled via a connected graph G=(V,E)G=(V,E), where V=[n]V=[n] is the set of agents, while E⊆V×VE V× V is the set of communication links. The graph G induces a weight matrix W∈ℝn×nW ^n× n, whose (i,j)(i,j)-th entry [W]ij=wij[W]_ij=w_ij is strictly positive if i,j∈E\i,j\∈ E, otherwise wij=0w_ij=0. As discussed in the introduction, the goal is to solve (1) in the presence of heavy-tailed gradient noise. To that end, we assume that agents have access to a Stochastic First-order Oracle (ℱSFO), which, when queried by agent i∈[n]i∈[n] with input x∈ℝdx ^d, returns gi∈ℝdg_i ^d, an unbiased estimator of ∇fi(x)∇ f_i(x). The ℱSFO model is widely used and subsumes both batch (i.e., offline) and streaming (i.e., online) learning settings. 2.2 Proposed Method To solve (1) under heavy-tailed noise, we use the clipped DSGD method, which consists of the following steps. At the beginning agents choose a fixed step-size α>0α>0 and clipping radius γ>0γ>0, and initial models xi1∈ℝdx^1_i ^d, i∈[n]i∈[n]. In iteration t≥1t≥ 1, each agent i∈[n]i∈[n] queries the ℱSFO with their current model xitx^t_i and receives gitg^t_i. Agents then clip their local stochastic gradient and update the local model via the rule xit+1=∑j∈iwij(xjt−αg~jt),x^t+1_i= _j _iw_ij (x^t_j-α g^t_j ), (2) where i≔j∈V:i,j∈E∪iN_i \j∈ V:\i,j\∈ E\∪\i\ are the agents that can communicate with agent i (itself included), while g~jt=clip(gjt)=min1,γ‖gjt‖gjt g^t_j= clip(g_j^t)= \1, γ\|g_j^t\| \g_j^t is the clipped estimator. The procedure is summarized in Algorithm 1. The variant of clipped DSGD studied in our work uses the adapt-then-combine (i.e., diffusion) approach, e.g., (Lopes and Sayed, 2008; Chen and Sayed, 2012) and differs from the version in Yang et al. (2025), which uses the combine-then-adapt approach, e.g., (Nedić and Ozdaglar, 2009; Kar and Moura, 2013). Algorithm 1 Clipped DSGD 0: Model initialization xi1∈ℝdx^1_i ^d, step-size α>0α>0 and clipping radius γ>0γ>0; 1: for t=1,2,…t=1,2,…, each agent i∈[n]i∈[n] in parallel do 2: Query the ℱSFO with xitx^t_i to obtain gitg^t_i; 3: Perform clipping: g~it=min1,γ‖git‖git g^t_i= \1, γ\|g^t_i\| \g^t_i; 4: Update the model: xit+1=∑j∈iwij(xjt−αg~jt)x^t+1_i= _j _iw_ij (x_j^t-α g^t_j ); 5: end for 3 Main Results In this section we provide the main results. Subsection 3.1 states the assumptions, while Subsection 3.2 presents the guarantees and discusses the results. 3.1 Assumptions We start with the assumption on the weight matrix. Assumption 1. The weight matrix W∈ℝn×nW ^n× n is primitive, doubly stochastic, and it holds that ‖W−1nnn⊤‖<1\|W- 1n1_n1_n \|<1, where n∈ℝn1_n ^n is the vector of all ones. Assumption 1 covers weight matrices induced by undirected graphs and a class of strongly-connected digraphs with doubly stochastic weights, e.g., Xin et al. (2020). Denote by λ≔‖W−J‖λ \|W-J\| , where J≔1nnn⊤∈ℝn×nJ 1n1_n1_n ^n× n is the ideal communication matrix. Assumption 1 implies that λ∈[0,1)λ∈[0,1), e.g., Horn and Johnson (2012), and the quantity 1−λ1-λ is known as the network spectral gap. Next, we make a technical assumption. Assumption 2. Agents’ initial models xi1∈ℝdx_i^1 ^d, i∈[n]i∈[n], are deterministic quantities. Moreover, agents share the initialization, i.e., xi1=xj1x_i^1=x_j^1, for all i,j∈[n]i,j∈[n]. Assumption 2 allows agents to initialize their model at any deterministic and jointly selected vector. The requirement for shared initialization is made to simplify the analysis and can be realized, e.g., by running a consensus algorithm before the start of training. The next assumption states the conditions on the cost functions. Assumption 3. The global cost is bounded from below and agents’ costs have L-Lipschitz gradients, i.e., f⋆≔infx∈ℝdf(x)>−∞f _x ^df(x)>-∞ and for all i∈[n]i∈[n] and x,y∈ℝdx,y ^d, we have ‖∇fi(x)−∇fi(y)‖≤L‖x−y‖\|∇ f_i(x)-∇ f_i(y)\|≤ L\|x-y\|. Assumption 3 is standard for non-convex costs, e.g., Ghadimi and Lan (2013). Further, it is known that DSGD requires a heterogeneity bound to ensure convergence under non-convex costs, e.g., Lian et al. (2017); Koloskova et al. (2020); Vlaski and Sayed (2021b); Vlaski and Sayed (2021a). To that end, we introduce the following condition. Assumption 4. There exist constants A,B≥0A,B≥ 0 (with at least one strictly positive), such that for all x∈ℝdx ^d and i∈[n]i∈[n], we have ‖∇fi(x)‖2≤A2+B2‖∇f(x)‖2\|∇ f_i(x)\|^2≤ A^2+B^2\|∇ f(x)\|^2. Assumption 4 is a standard heterogeneity condition, e.g., (Vlaski and Sayed, 2021b; Vlaski and Sayed, 2021a; Armacki and Sayed, 2026). It is strictly weaker than the heterogeneity bounds used in other works on decentralized clipping methods, e.g., Yang et al. (2025); Li and Chi (2025),55 5 Yang et al. (2025) use uniformly bounded gradients, implying Assumption 4 with B=0B=0. Li and Chi (2025) use a condition that implies Assumption 4 with A=0A=0 and B=1312B= 1312, effectively requiring that every stationary point of f also be a stationary point for each fif_i, i∈[n]i∈[n]. however, slightly stronger than the averaged heterogeneity condition used in, e.g., (Koloskova et al., 2020). For a discussion on the necessity of this condition, see Supplement D. Prior to stating the noise assumption, denote by zit≔git−∇fi(xit)z_i^t g_i^t-∇ f_i(x_i^t) the gradient noise of agent i at time t, and let ℱt≔σ(xi1i∈[n],…,xiti∈[n])F_t σ (\\x_i^1\_i∈[n],…,\x_i^t\_i∈[n]\ ) be the σ-algebra induced by agents’ models up to t. Assumption 5. At any time t≥1t≥ 1, the stochastic quantities satisfy the following. 1. The random samples ξiki∈[n],k∈[t]\ξ^k_i\_i∈[n],k∈[t] are independent across agents and iterations. 2. The noise at each agent is conditionally zero-mean, i.e., [zit|ℱt]=0E[z^t_i\>|\>F_t]=0, for all i∈[n]i∈[n]. 3. The noise at each agent has bounded p-th moment, p∈(1,2]p∈(1,2], i.e., [‖zit‖p|ℱt]≤σipE [\|z^t_i\|^p\>|\>F_t ]≤ _i^p, for all i∈[n]i∈[n]. The first two conditions in Assumption 5 are standard, while the third requires the noise to have a bounded p-th moment for some p∈(1,2]p∈(1,2], and is widely used when studying heavy-tailed noise, e.g., (Zhang et al., 2020; Sadiev et al., 2023; Hübler et al., 2025). 3.2 Theoretical Guarantees We start by defining some useful notation. Let ∇¯ft≔1n∑i∈[n]∇fi(xit) ∇f^t 1n _i∈[n]∇ f_i(x^t_i) and g¯t≔1n∑i∈[n]git g^t 1n _i∈[n]g^t_i denote the averaged gradient and stochastic gradient, respectively, and let z¯t≔g¯t−∇¯ft=1n∑i∈[n]zit z^t g^t- ∇f^t= 1n _i∈[n]z^t_i be the averaged noise. Next, denote by g^t≔1n∑i∈[n]g~it g^t 1n _i∈[n] g^t_i the averaged clipped estimator, and define the averaged unbiased and biased components stemming from clipping as g^ut≔g^t−[g^t|ℱt] g^t_u g^t-E[ g^t\>|\>F_t] and g^bt≔[g^t|ℱt]−∇¯ft g^t_b [ g^t\>|\>F_t]- ∇f^t. Similarly, let g~i,ut≔g~it−[g~it|ℱt] g^t_i,u g^t_i-E[ g^t_i\>|\>F_t] and g~i,bt=[g~it|ℱt]−∇fi(xit) g^t_i,b=E[ g^t_i\>|\>F_t]-∇ f_i(x^t_i) be the local unbiased and biased components. It can be seen that g^t−∇¯ft=g^ut+g^bt g^t- ∇f^t= g^t_u+ g^t_b and g~it−∇fi(xit)=g~i,ut+g~i,bt g^t_i-∇ f_i(x^t_i)= g^t_i,u+ g^t_i,b, i∈[n]i∈[n]. We next state an important result. Lemma 1. Let X1,…,Xn∈ℝdX_1,…,X_n ^d be independent random vectors and let X~i=clip(Xi) X_i= clip(X_i), i∈[n]i∈[n], with X~=1n∑i∈[n]X~i X= 1n _i∈[n] X_i. If for some p∈(1,2]p∈(1,2] and all i∈[n]i∈[n] we have ‖Xi−[Xi]‖p≤σipE\|X_i-E[X_i]\|^p≤ _i^p and ‖[Xi]‖≤γ/2\|E[X_i]\|≤ γ2, then ‖X~−[X~]‖2≤18γ2−pn2∑i∈[n]σip. \| X-E[ X]\|^2≤ 18γ^2-pn^2 _i∈[n] _i^p. Denoting by σp≔1n∑i∈[n]σipσ^p 1n _i∈[n] _i^p, Lemma 1 tells us that the variance of the averaged clipped estimator scales as (σpn)O ( σ^pn ), and is crucial in establishing linear speed-up. A similar result appeared in the client-server setup in (Gorbunov et al., 2024, Lemma B.3), provided for illustrative purposes while using a different approach to show linear speed-up. On the other hand, Lemma 1 is a key result for achieving linear speed-up in our work. In Supplement B we provide an extended version of Lemma 1. Next, define the averaged model x¯t≔1n∑i∈[n]xit x^t 1n _i∈[n]x^t_i. We then have the following descent inequality. Lemma 2. If Assumption 3 holds and α≤12Lα≤ 12L, then for any t≥1t≥ 1 f(CLOSE f( OPENx¯t+1)≤f(x¯t)−α4‖∇f(x¯t)‖2−α⟨∇f(x¯t),g^ut⟩ x^t+1)≤ f( x^t)- α4\|∇ f( x^t)\|^2-α ∇ f( x^t), g^t_u +2α2L‖g^ut‖2+2α‖g^bt‖2+αL22n∑i∈[n]‖xit−x¯t‖2. +2α^2L\| g^t_u\|^2+2α\| g^t_b\|^2+ α L^22n _i∈[n]\|x^t_i- x^t\|^2. Lemma 2 is the starting point in our analysis. In addition to the standard terms appearing in centralized clipping analysis, e.g., (Sadiev et al., 2023; Nguyen et al., 2023), the inequality contains the consensus gap term, which we aim to bound next. We start with a simple but useful bound on the consensus gap. Lemma 3. If Assumptions 1 and 2 hold, then for all i∈[n]i∈[n] and any t≥1t≥ 1 ‖xit+1−x¯t+1‖≤αγλn1−λ. \|x^t+1_i- x^t+1\|≤ αγλ n1-λ. Lemma 3 provides an initial deterministic bound on the consensus gap and is useful since it indicates that, for a sufficiently small step-size, the consensus gap can be controlled by the clipping radius. However, only using Lemma 3 would propagate the network effect to the leading term and result in the loss of linear speed-up in the final bound (see Remark 1 in Supplement B for details). To fix this issue, we next provide an additional refined bound on the consensus gap. Lemma 4. If Assumptions 1-4 hold, then for all t≥1t≥ 1 1n∑i∈[n]‖xit+1−x¯t+1‖2≤8α2λ2A2(1−λ2)∑k=1t(1+λ22)t−k 1n _i∈[n]\|x^t+1_i- x^t+1\|^2≤ 8α^2λ^2A^2(1-λ^2) _k=1^t ( 1+λ^22 )^t-k +8α2λ2B2n(1−λ2)∑k=1t(1+λ22)t−k∑i∈[n]∥∇f(xik)∥2 + 8α^2λ^2B^2n(1-λ^2) _k=1^t ( 1+λ^22 )^t-k _i∈[n]\|∇ f(x^k_i)\|^2 +8α2λ2n(1−λ2)∑k=1t(1+λ22)t−k∑i∈[n](∥g~i,bk∥2+∥g~i,uk∥2). + 8α^2λ^2n(1-λ^2) _k=1^t ( 1+λ^22 )^t-k _i∈[n] (\| g^k_i,b\|^2+\| g^k_i,u\|^2 ). Lemma 4 establishes a more fine-grained result on the average consensus gap, capturing the effects of heterogeneity, network connectivity and local clipping. Lemmas 1-4 together are crucial in achieving our main results, stated next. We start with HP convergence. Theorem 1. Let Assumptions 1-5 hold. If for any T≥1T≥ 1 and δ∈(0,1)δ∈(0,1), the clipping radius and the step-size are chosen as γ=max2A+4BLΔ1+2λLn1−λ,(nT)13p−2γ= \2A+4B L _1+ 2λ L n1-λ,(nT) 13p-2 \ and α=min12L,1−λ28λLB3,1−λ2λL6,(1−λ2)26λ2L,(1−λ2)2/3Δ11/32(λLA)2/3T1/3123,C1γ,C2γn2p−13p−2T1−p3p−2,C3γ2/3np3(3p−2)T2(1−p)3(3p−2)α= \ 12L, 1-λ^28λ LB 3, 1-λ^2λ L 6, (1-λ^2)^26λ^2L, (1-λ^2)^2/3 _1^1/32(λ LA)^2/3T^1/3 [3]12, C_1γ, C_2γn 2p-13p-2T 1-p3p-2, C_3γ^2/3n p3(3p-2)T 2(1-p)3(3p-2) \, with C1=min1,3Δ1/2L64log(6Tδ)C_1= \1, 3 _1/2L64 ( 6Tδ ) \, C2=minΔ164σ2p,Δ1/2L192log(6Tδ)σp/2C_2= \ _164σ^2p, _1/2L192 ( 6Tδ )σ^p/2 \ and C3=Δ11/3(1−λ2)2/312σp/3λ2/3L2/3C_3= _1^1/3(1-λ^2)^2/312σ^p/3λ^2/3L^2/3, then with probability at least 1−δ1-δ 1nT∑t∈[T]∑i∈[n]‖∇f(xit)‖2=~((nT)2(1−p)3p−2), 1nT _t∈[T] _i∈[n]\|∇ f(x^t_i)\|^2= O ((nT) 2(1-p)3p-2 ), where ~(⋅) O(·) hides terms of higher-order in T. The next result establishes the IE convergence bound. Theorem 2. Let Assumptions 1-5 hold. If for any T≥2T≥ 2 the clipping radius and the step-size are chosen as γ=max2A+4BLΔ1+2λLn1−λ,(nT)13p−2γ= \2A+4B L _1+ 2λ L n1-λ,(nT) 13p-2 \ and α=min12L,1−λ28λLB3,1−λ2λL6,(1−λ2)26λ2L,(1−λ2)2/3Δ11/32(λLA)2/3T1/3123,C1γ,C2γn2p−13p−2T1−p3p−2,Δ11/3(1−λ2)2/312σp/3γ2/3λ2/3L2/3np3(3p−2)T2(1−p)3(3p−2)α= \ 12L, 1-λ^28λ LB 3, 1-λ^2λ L 6, (1-λ^2)^26λ^2L, (1-λ^2)^2/3 _1^1/32(λ LA)^2/3T^1/3 [3]12, C_1γ, C_2γn 2p-13p-2T 1-p3p-2, _1^1/3(1-λ^2)^2/312σ^p/3γ^2/3λ^2/3L^2/3n p3(3p-2)T 2(1-p)3(3p-2) \, where C1=min1,3Δ1/2L64log(6n4T5)C_1= \1, 3 _1/2L64 (6n^4T^5) \ and C2=minΔ164σ2p,Δ1/2L192log(6n4T5)σp/2C_2= \ _164σ^2p, _1/2L192 (6n^4T^5)σ^p/2 \, it then holds that 1nT∑t∈[T]∑i∈[n]‖∇f(xit)‖2=~((nT)2(1−p)3p−2), 1nT _t∈[T] _i∈[n]E\|∇ f(x^t_i)\|^2= O ((nT) 2(1-p)3p-2 ), where ~(⋅) O(·) hides terms of higher-order in T. We next discuss several aspects of our results. Convergence Rates. Theorems 1 and 2 respectively establish HP and IE convergence of clipped DSGD under heavy-tailed noise. In both cases, the leading term with respect to T is of the order ~((nT)2(1−p)3p−2) O ((nT) 2(1-p)3p-2 ), which has three important implications. First, the rate in T matches the optimal rate achieved in centralized settings (Zhang et al., 2020; Nguyen et al., 2023). Second, linear speed-up in the number of agents n is achieved, exhibiting the same exponent with respect to p. Third, the leading term has no network dependence, with the spectral gap only affecting higher-order terms. For full rates, which contain several higher-order terms, the reader is referred to Supplement B. Clipping Radius. The clipping radius in our work is of the form γ=maxCd,(nT)13p−2γ= \C_d,(nT) 13p-2 \, where Cd>0C_d>0 is a problem-related constant. Compared to centralized works (Zhang et al., 2020; Nguyen et al., 2023), where the clipping radius is also of the form γ=maxCc,T13p−2γ= \C_c,T 13p-2 \, we note a few things. First, both clipping radii have the same structure, i.e., a maximum of a problem-related constant and a term growing with T. Second, our clipping radius increases with higher heterogeneity (via A,BA,B) and worse network connectivity (via the spectral gap), which is expected, as these quantities reflect the difficulty of the decentralized problem. Third, our radius also increases with n, which is again expected in the multi-agent setting, and is consistent with Gorbunov et al. (2024), who similarly use a clipping radius that increases with n. Step-size. The step-size is of the form α=minSd,C1γ,C2γn2p−13p−2T1−p3p−2,C3γ2/3np3(3p−2)T2(1−p)3(3p−2)α= \S_d, C_1γ, C_2γn 2p-13p-2T 1-p3p-2, C_3γ^2/3n p3(3p-2)T 2(1-p)3(3p-2) \, where Sd>0S_d>0 is a problem-related constant, corresponding to standard conditions on the step-size for vanilla DSGD, e.g., (Armacki and Sayed, 2026), while the remaining terms stem from the use of clipping. The first two, scaling as ∝γ−1 γ^-1, are consistent with the step-size choice in Zhang et al. (2020); Nguyen et al. (2023) (up to n factors), while the third term, scaling as ∝γ−2/3 γ^-2/3, is novel and specific to our decentralized settings, used to optimize the network dependence and transient time. Transient Time. Using our rates, one can derive the transient time for clipped DSGD, i.e., the time needed to achieve a global, network-independent ((nT)2(1−p)3p−2)O ((nT) 2(1-p)3p-2 ) rate. Focusing on the effects of the number of agents and the spectral gap, our transient time is of the order ~(maxn2p−1p−1,n3p−42(1−λ)3p−2,n8(p−1)2+p(1−λ)4(3p−2)2+p,n5p−4p(1−λ)2(3p−2)p,n3(p−1)(1−λ)3p−2,n2(p−1)p(1−λ)2(3p−2)p,n7p−62p(1−λ)3p−2p) O ( \n 2p-1p-1, n 3p-42(1-λ)^3p-2, n 8(p-1)2+p(1-λ) 4(3p-2)2+p, n 5p-4p(1-λ) 2(3p-2)p, n^3(p-1)(1-λ)^3p-2, n 2(p-1)p(1-λ) 2(3p-2)p, n 7p-62p(1-λ) 3p-2p \ ). For p=2p=2 (i.e., bounded variance), it evaluates to (n3(1−λ)4)O ( n^3(1-λ)^4 ), matching the transient time of vanilla DSGD under bounded variance/sub-Gaussian noise, e.g., (Koloskova et al., 2020; Alghunaim and Yuan, 2022; Armacki and Sayed, 2026). For further discussion, see Supplement E. Figure 2: Convergence of decentralized methods under heavy-tailed gradient noise. Left: Student’s t noise; right: Lévy α-stable noise. Solid curves show the mean estimation error, while shaded regions indicate one standard deviation. Comparison with Existing Works. Compared to Yang et al. (2025), who study a variant of clipped DSGD, we relax the bounded gradients condition and achieve improved oracle complexity. Compared to Li and Chi (2025), who study clipped GT with compression, EF and mini-batches under bounded variance noise, we consider a much simpler algorithm under more general noise and heterogeneity conditions, and achieve improved oracle complexity. Compared to Yu et al. (2026a), who study normalized GT with local momentum, we use the baseline clipped DSGD, achieving better oracle complexity. Finally, compared to Wang et al. (2026), who study normalized GT with large mini-batches and multiple communication rounds per iteration, we achieve the same optimal oracle complexity while using a significantly simpler algorithm, with only one stochastic gradient evaluation and one communication round per iteration. We note that the GT mechanism allows Yu et al. (2026a); Wang et al. (2026) to remove the heterogeneity bound, which is not the case in (Li and Chi, 2025) despite the use of GT, or in our work and (Yang et al., 2025), where DSGD necessitates a heterogeneity bound to ensure convergence. Compared to all of the said works, which provide either HP or IE results, we show both HP and IE results. Insights. As discussed in the introduction and shown in Figure 1, normalized DSGD can fail to converge even with full gradients on a simple quadratic cost. On the other hand, our work demonstrates that clipped DSGD achieves optimal convergence rates with linear speed-up under heavy-tailed noise, highlighting a clear gap between these two nonlinearities 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. As such, normalization always biases the network-averaged gradient, while clipping can preserve the true network-averaged gradient, allowing clipped DSGD to achieve order-optimal complexity with linear speed-up, without needing mechanisms like GT, accelerated gossip and local momentum/mini-batches. 4 Numerical Results Figure 3: Convergence of DSGD-Clip under heavy-tailed noise for networks of size n∈10,20,30,40,50n∈\10,20,30,40,50\. Left: Student’s t noise; right: Lévy α-stable noise. We can see that DSGD-Clip accelerates with network size, achieving linear speed-up. In this section we present numerical experiments. We refer the reader to Supplement C for full details on experimental setup and additional results. Linear Regression on Synthetic Data. We consider the problem of robust linear regression to evaluate two main aspects of our results: convergence and linear speed-up under heavy-tailed noise. We compare the performance of vanilla DSGD to nonlinear variants using: clipping (DSGD-Clip), component-wise clipping (DSGD-CClip) and normalization (DSGD-N), with hyperparameters selected through extensive grid search. To evaluate convergence under heavy-tailed noise, we consider a network of n=20n=20 agents communicating over a ring graph. Each agent is assigned a dataset of 5050 feature-response pairs (A,b)∈ℝ20×ℝ(A,b) ^20×R, where each feature component of A is sampled independently from a Bernoulli(q) (q) distribution, where q=0.9q=0.9 for the first two, q=0.5q=0.5 for the next two, and q=0.1q=0.1 for the remaining components, the ground truth model x⋆x is drawn from (0,I20)N(0,I_20), while the responses satisfy b=⟨A,x⋆⟩b= A,x . Agents’ local costs correspond to Tukey’s biweight loss and local gradients are perturbed by Student’s t (degrees of freedom 1.51.5, scale 1.01.0) and Lévy α-stable noise (stability 1.51.5, skewness 0.50.5, scale 1.01.0), with local models initialized at the zero vector. We measure performance via the average estimation error ℰt=1n∑i=1n‖wit−w⋆‖2E_t= 1n _i=1^n \|w_i^t-w \|_2, evaluated over 3030 independent runs. The results are presented in Figure 2. We can observe that nonlinear methods stabilize and accelerate the convergence of DSGD, highlighting the importance of nonlinear methods under heavy-tailed noise, and that both DSGD-Clip and DSGD-CClip perform on par with or better than DSGD-N. To evaluate the linear speed-up of DSGD-Clip under heavy tailed noise, we consider five networks of n∈10,20,30,40,50n∈\10,20,30,40,50\ agents communicating over an undirected Erdős–Rényi graph. To better isolate the linear speed-up effect, we set the edge probability of the graph at 0.60.6 while ensuring that λ=0.8λ=0.8 across every network size, thus fixing the network spectral gap. We generate a total of 12001200 feature-response pairs using the same rules as in the previous experiments and spread them evenly among agents. We again inject Student’s t and Lévy α-stable noise to agents’ local gradients, using the same Tukey loss, model initialization and performance measure. The results are presented in Figure 3. We can see that DSGD-Clip consistently converges faster as the network size increases, confirming that linear speed-up is achieved. Transformer Training on Real Data. Finally, we test the performance of nonlinear decentralized methods on the problem of decentralized training of a decoder-only transformer with real data. The simulations are conducted using antup and additional some additional results A100 NVIDIA GPU. We consider an undirected ring network of n=8n=8 agents, trained on the “Multi30k” and “Tiny Shakespeare” datasets. “Multi30k” contains 29,000 training sentences, yielding approximately 378,000 word tokens after tokenization, while “Tiny Shakespeare” contains about 1 million training characters. We use two-layer decoder-only transformers with hidden dimension 128, four attention heads, feedforward dimension 512, and dropout 0.1. The models are trained using a batch size of 64 sequences per agent, with context length 64 and stride 32. The training data are partitioned into equally sized contiguous shards, and all agents are initialized with the same random model. We again consider DSGD, DSGD-N, DSGD-Clip, and DSGD-CClip methods and measure the performance via the log-perplexity achieved on a validation set. Table 2 reports the final validation loss averaged over five independent runs. We can see that DSGD-CClip achieves the lowest validation loss on both datasets, while DSGD-Clip and DSGD-N perform on par with one another. Importantly, all three methods improve over vanilla DSGD. Table 2: Validation loss after 20 epochs on “Multi30k” and “Tiny Shakespeare” datasets. We report the mean and standard deviation over five independent runs. Algorithms “Multi30k” “Tiny Shakespeare” DSGD 4.634±0.0264.634± 0.026 2.357±0.0062.357± 0.006 DSGD-N 4.386±0.0164.386± 0.016 1.966±0.0351.966± 0.035 DSGD-Clip 4.375±0.0214.375± 0.021 1.980±0.0501.980± 0.050 DSGD-CClip 3.962± 0.008 1.725± 0.010 5 Conclusion In this work, we studied whether a baseline decentralized algorithm with a local nonlinear gradient transformation can attain order-optimal rates under heavy-tailed noise, without further mechanisms like mini-batches or accelerated gossip. We answered affirmatively with clipped DSGD, establishing order-optimal convergence rates and linear speed-up for smooth non-convex costs. Our results also highlighted an important distinction between clipping and normalization in decentralized settings, raising broader questions about the effects of nonlinearities in decentralized optimization. Are some nonlinearities better suited to decentralized settings, and if so, can we establish a hierarchy across different regimes? Another important direction is whether baseline GT with clipping can simultaneously eliminate the bounded heterogeneity condition and retain order-optimal convergence rates. This, in turn, raises a further design question: should clipping be applied to local gradients or to the tracker variable, and what are the consequences of each choice? Acknowledgements The authors would like to thank Shuhua Yu (Meta FAIR) for helpful discussions. References Alghunaim and Yuan (2022) S. A. Alghunaim and K. Yuan A Unified and Refined Convergence Analysis for Non-Convex Decentralized Learning. IEEE Transactions on Signal Processing 70 (), p. 3264–3279. External Links: Document Cited by: Appendix E, §3.2. Armacki et al. (2026a) A. Armacki, D. Bajović, D. Jakovetić, S. Kar, and A. H. Sayed Tight Long-Term Tail Decay of (Clipped) SGD in Non-Convex Optimization. In Proceedings of Thirty Ninth Conference on Learning Theory, Proceedings of Machine Learning Research, Vol. 336, p. 337–370. External Links: Link Cited by: §1.1. Armacki et al. (2026b) A. Armacki, D. Bajović, D. Jakovetić, and S. Kar Sharp High-Probability Rates for Nonlinear SGD Under Heavy-Tailed Noise via Symmetrization. IEEE Transactions on Information Theory 72 (8), p. 6071–6092. External Links: Document Cited by: §1.1. Armacki et al. (2026c) A. Armacki, H. Cai, and A. H. Sayed High-Probability Convergence in Decentralized Stochastic Optimization with Gradient Tracking. arXiv preprint. Cited by: Appendix A. Armacki and Sayed (2026) A. Armacki and A. H. Sayed High-Probability Convergence Guarantees of Decentralized SGD. In Forty-third International Conference on Machine Learning, External Links: Link Cited by: Appendix A, Appendix D, Appendix E, §3.1, §3.2, §3.2. Armacki et al. (2026d) A. Armacki, S. Yu, D. Bajović, D. Jakovetić, and S. Kar Large Deviation Upper Bounds and Improved MSE Rates of Nonlinear SGD: Heavy-Tailed Noise and Power of Symmetry. SIAM Journal on Optimization 36 (1), p. 32–59. External Links: Document, Link, https://doi.org/10.1137/24M1704154 Cited by: §B.3, §1.1. Armacki et al. (2025) A. Armacki, S. Yu, P. Sharma, G. Joshi, D. Bajović, D. Jakovetić, and S. Kar High-probability Convergence Bounds for Online Nonlinear Stochastic Gradient Descent under Heavy-tailed Noise. In Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, Proceedings of Machine Learning Research, Vol. 258, p. 1774–1782. External Links: Link Cited by: §1.1. Bajović et al. (2023) D. Bajović, D. Jakovetić, and S. Kar Large deviations rates for stochastic gradient descent with strongly convex functions. In Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, Proceedings of Machine Learning Research, Vol. 206, p. 10095–10111. External Links: Link Cited by: Appendix A. Barsbey et al. (2021) M. Barsbey, M. Sefidgaran, M. A. Erdogdu, G. Richard, and U. Simsekli Heavy Tails in SGD and Compressibility of Overparametrized Neural Networks. In Advances in Neural Information Processing Systems, Vol. 34, p. 29364–29378. External Links: Link Cited by: §1. Battash et al. (2024) B. Battash, L. Wolf, and O. Lindenbaum Revisiting the Noise Model of Stochastic Gradient Descent. In Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, Proceedings of Machine Learning Research, Vol. 238, p. 4780–4788. External Links: Link Cited by: §1. Bernstein et al. (2019) J. Bernstein, J. Zhao, K. Azizzadenesheli, and A. Anandkumar signSGD with Majority Vote is Communication Efficient and Fault Tolerant. In International Conference on Learning Representations, External Links: Link Cited by: §1.1. Chen and Sayed (2012) J. Chen and A. H. Sayed Diffusion Adaptation Strategies for Distributed Optimization and Learning Over Networks. IEEE Transactions on Signal Processing 60 (8), p. 4289–4305. External Links: Document Cited by: §2.2. Chen et al. (2020) X. Chen, S. Z. Wu, and M. Hong Understanding Gradient Clipping in Private SGD: A Geometric Perspective. In Advances in Neural Information Processing Systems, Vol. 33, p. 13773–13782. External Links: Link Cited by: §1.1. Chen et al. (2019) Y. Chen, S. Kar, and J. M. F. Moura Resilient Distributed Estimation: Sensor Attacks. IEEE Transactions on Automatic Control 64 (9), p. 3772–3779. External Links: Document Cited by: §1.1. Chezhegov et al. (2026) S. Chezhegov, D. A. Parletta, A. Paudice, and E. Gorbunov High-Probability Bounds for the Last Iterate of Clipped SGD. In International Conference on Learning Representations, Vol. 2026, p. 1280–1310. External Links: Link Cited by: §B.3. Cutkosky and Mehta (2021) A. Cutkosky and H. Mehta High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails. In Advances in Neural Information Processing Systems, Vol. 34, p. 4883–4895. External Links: Link Cited by: §1.1. Cutkosky and Orabona (2019) A. Cutkosky and F. Orabona Momentum-Based Variance Reduction in Non-Convex SGD. In Advances in Neural Information Processing Systems, Vol. 32, p. . External Links: Link Cited by: §1.1. Fatkhullin et al. (2025) I. Fatkhullin, F. Hübler, and G. Lan Can SGD Handle Heavy-Tailed Noise?. In OPT 2025: Optimization for Machine Learning, External Links: Link Cited by: §1.1. Ghadimi and Lan (2013) S. Ghadimi and G. Lan Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming. SIAM Journal on Optimization 23 (4), p. 2341–2368. External Links: Document, Link, https://doi.org/10.1137/120880811 Cited by: Appendix A, §3.1. Gorbunov et al. (2020) E. Gorbunov, M. Danilova, and A. Gasnikov Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping. 33, p. 15042–15053. External Links: Link Cited by: Appendix A. Gorbunov et al. (2024) E. Gorbunov, A. Sadiev, M. Danilova, S. Horváth, G. Gidel, P. Dvurechensky, A. Gasnikov, and P. Richtárik High-Probability Convergence for Composite and Distributed Stochastic Minimization and Variational Inequalities with Heavy-Tailed Noise. In Proceedings of the 41st International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 235, p. 15951–16070. External Links: Link Cited by: §3.2, §3.2. Gürbüzbalaban et al. (2025) M. Gürbüzbalaban, Y. Hu, U. Şimşekli, K. Yuan, and L. Zhu Heavy-tail phenomenon in decentralized sgd. IISE Transactions 57 (7), p. 788–802. External Links: Document, Link, https://doi.org/10.1080/24725854.2024.2413888 Cited by: §1. Gurbuzbalaban et al. (2021) M. Gurbuzbalaban, U. Simsekli, and L. Zhu The Heavy-Tail Phenomenon in SGD. In Proceedings of the 38th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 139, p. 3964–3975. External Links: Link Cited by: §1. Harvey et al. (2019) N. J. A. Harvey, C. Liaw, Y. Plan, and S. Randhawa Tight analyses for non-smooth stochastic gradient descent. In Proceedings of the Thirty-Second Conference on Learning Theory, Proceedings of Machine Learning Research, Vol. 99, p. 1579–1613. External Links: Link Cited by: Appendix A. Horn and Johnson (2012) R. A. Horn and C. R. Johnson Matrix Analysis. 2 edition, Cambridge University Press. Cited by: §3.1. Hübler et al. (2025) F. Hübler, I. Fatkhullin, and N. He From Gradient Clipping to Normalization for Heavy Tailed SGD. In Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, Proceedings of Machine Learning Research, Vol. 258, p. 2413–2421. External Links: Link Cited by: §1.1, §3.1. Jakovetić et al. (2023) D. Jakovetić, D. Bajović, A. K. Sahu, S. Kar, N. Milošević, and D. Stamenković Nonlinear Gradient Mappings and Stochastic Optimization: A General Framework with Applications to Heavy-Tail Noise. SIAM Journal on Optimization 33 (2), p. 394–423. External Links: Document, Link, https://doi.org/10.1137/21M145896X Cited by: Appendix A. Jakovetić et al. (2018) D. Jakovetić, D. Bajović, A. K. Sahu, and S. Kar Convergence Rates for Distributed Stochastic Optimization Over Random Networks. In 2018 IEEE Conference on Decision and Control (CDC), Vol. , p. 4238–4245. External Links: Document Cited by: Appendix A. Kar et al. (2012) S. Kar, J. M. F. Moura, and K. Ramanan Distributed Parameter Estimation in Sensor Networks: Nonlinear Observation Models and Imperfect Communication. IEEE Transactions on Information Theory 58 (6), p. 3575–3605. External Links: Document Cited by: §1.1. Kar and Moura (2013) S. Kar and J. M.F. Moura Consensus + innovations distributed inference over networks: cooperation and sensing in networked systems. IEEE Signal Processing Magazine 30 (3), p. 99–109. External Links: Document Cited by: §2.2. Koloskova et al. (2023) A. Koloskova, H. Hendrikx, and S. U. Stich Revisiting Gradient Clipping: Stochastic bias and tight convergence guarantees. In Proceedings of the 40th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 202, p. 17343–17363. External Links: Link Cited by: Appendix A. Koloskova et al. (2020) A. Koloskova, N. Loizou, S. Boreiri, M. Jaggi, and S. Stich A Unified Theory of Decentralized SGD with Changing Topology and Local Updates. In Proceedings of the 37th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 119, p. 5381–5393. External Links: Link Cited by: Appendix A, Appendix D, Appendix E, §3.1, §3.1, §3.2. Kornilov et al. (2025) N. Kornilov, P. Zmushko, A. Semenov, A. Gasnikov, and A. Beznosikov Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under (L0,L1)(L_0,L_1)-Smoothness. arXiv preprint. Cited by: §1.1. Li and Chi (2025) B. Li and Y. Chi Convergence and Privacy of Decentralized Nonconvex Optimization With Gradient Clipping and Communication Compression. IEEE Journal of Selected Topics in Signal Processing 19 (1), p. 273–282. External Links: Document Cited by: item † , §1.1, Table 1, §3.1, §3.2, footnote 4, footnote 5. Li and Orabona (2020) X. Li and F. Orabona A high probability analysis of adaptive sgd with momentum. Workshop on “Beyond first-order methods in ML systems”, 37th International Conference on Machine Learning. Cited by: Appendix A. Lian et al. (2017) X. Lian, C. Zhang, H. Zhang, C. Hsieh, W. Zhang, and J. Liu Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descent. In Advances in Neural Information Processing Systems, Vol. 30, p. . External Links: Link Cited by: Appendix D, §3.1. Liu et al. (2023a) Z. Liu, T. D. Nguyen, T. H. Nguyen, A. Ene, and H. Nguyen High Probability Convergence of Stochastic Gradient Methods. In Proceedings of the 40th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 202, p. 21884–21914. External Links: Link Cited by: Appendix A. Liu et al. (2023b) Z. Liu, J. Zhang, and Z. Zhou Breaking the Lower Bound with (Little) Structure: Acceleration in Non-Convex Stochastic Optimization with Heavy-Tailed Noise. In Proceedings of Thirty Sixth Conference on Learning Theory, Proceedings of Machine Learning Research, Vol. 195, p. 2266–2290. External Links: Link Cited by: §1.1. Liu and Zhou (2024) Z. Liu and Z. Zhou Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods. In The Twelfth International Conference on Learning Representations, External Links: Link Cited by: Appendix A. Liu and Zhou (2025) Z. Liu and Z. Zhou Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clipping. In The Thirteenth International Conference on Learning Representations, External Links: Link Cited by: §1.1. Liu (2026) Z. Liu In-Expectation Convergence of Stochastic Gradient Methods under Heavy-Tailed Noise. arXiv preprint. Cited by: §1.1. Lopes and Sayed (2008) C. G. Lopes and A. H. Sayed Diffusion Least-Mean Squares Over Adaptive Networks: Formulation and Performance Analysis. IEEE Transactions on Signal Processing 56 (7), p. 3122–3136. External Links: Document Cited by: §2.2. Lorenzo and Scutari (2016) P. D. Lorenzo and G. Scutari NEXT: In-Network Nonconvex Optimization. IEEE Transactions on Signal and Information Processing over Networks 2 (2), p. 120–136. External Links: Document Cited by: Appendix A. Madden et al. (2024) L. Madden, E. Dall’Anese, and S. Becker High Probability Convergence Bounds for Non-convex Stochastic Gradient Descent with Sub-Weibull Noise. Journal of Machine Learning Research 25 (241), p. 1–36. External Links: Link Cited by: Appendix A. McMahan et al. (2017) B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y. Arcas Communication-Efficient Learning of Deep Networks from Decentralized Data. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, Proceedings of Machine Learning Research, Vol. 54, p. 1273–1282. External Links: Link Cited by: §1. Nair et al. (2022) J. Nair, A. Wierman, and B. Zwart The Fundamentals of Heavy Tails: Properties, Emergence, and Estimation. Cambridge Series in Statistical and Probabilistic Mathematics, Cambridge University Press. Cited by: §1. Nedić et al. (2017) A. Nedić, A. Olshevsky, and W. Shi Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs. SIAM Journal on Optimization 27 (4), p. 2597–2633. External Links: Document, Link Cited by: Appendix A. Nedić and Ozdaglar (2009) A. Nedić and A. Ozdaglar Distributed Subgradient Methods for Multi-Agent Optimization. IEEE Transactions on Automatic Control 54 (1), p. 48–61. External Links: Document Cited by: §2.2. Nemirovskiĭ et al. (2009) A. Nemirovskiĭ, A. Juditsky, G. Lan, and A. Shapiro Robust Stochastic Approximation Approach to Stochastic Programming. SIAM Journal on Optimization 19 (4), p. 1574–1609. External Links: Document, Link, https://doi.org/10.1137/070704277 Cited by: Appendix A. Nemirovskiĭ and Yudin (1983) A. S. Nemirovskiĭ and D. B. Yudin Problem Complexity and Method Efficiency in Optimization. Wiley-Interscience, John Wiley & Sons. External Links: ISBN 9780471103455, LCCN 82011065 Cited by: §1.1. Nguyen et al. (2023) T. D. Nguyen, T. H. Nguyen, A. Ene, and H. Nguyen Improved Convergence in High Probability of Clipped Gradient Methods with Heavy Tailed Noise. In Advances in Neural Information Processing Systems, Vol. 36, p. 24191–24222. External Links: Link Cited by: §B.2, §1.1, §3.2, §3.2, §3.2, §3.2. Parletta et al. (2024) D. A. Parletta, A. Paudice, M. Pontil, and S. Salzo High probability bounds for stochastic subgradient schemes with heavy tailed noise. SIAM Journal on Mathematics of Data Science 6 (4), p. 953–977. External Links: Document, Link, https://doi.org/10.1137/22M1536558 Cited by: Appendix A. Polyak and Tsypkin (1979) B. Polyak and Y. Z. Tsypkin Adaptive Estimation Algorithms: Convergence, Optimality, Stability. Automation and Remote Control 40, p. 378–389. Cited by: §1.1. Pu and Nedić (2021) S. Pu and A. Nedić Distributed stochastic gradient tracking methods. Mathematical Programming 187 (1), p. 409–457. External Links: ISSN 1436-4646, Document, Link Cited by: Appendix A. Puchkin et al. (2024) N. Puchkin, E. Gorbunov, N. Kutuzov, and A. Gasnikov Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems. In Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, Proceedings of Machine Learning Research, Vol. 238, p. 856–864. External Links: Link Cited by: Appendix A. Qin et al. (2025) Y. Qin, K. Lu, H. Xu, and X. Chen High Probability Convergence of Clipped Distributed Dual Averaging With Heavy-Tailed Noises. IEEE Transactions on Systems, Man, and Cybernetics: Systems 55 (4), p. 2624–2632. External Links: Document Cited by: Appendix A. Qu and Li (2018) G. Qu and N. Li Harnessing Smoothness to Accelerate Distributed Optimization. IEEE Transactions on Control of Network Systems 5 (3), p. 1245–1260. External Links: Document Cited by: Appendix A. Sadiev et al. (2023) A. Sadiev, M. Danilova, E. Gorbunov, S. Horváth, G. Gidel, P. Dvurechensky, A. Gasnikov, and P. Richtárik High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance. In Proceedings of the 40th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 202, p. 29563–29648. External Links: Link Cited by: §B.1, §B.2, §1.1, §3.1, §3.2, Lemma 5. Sayed (2014) A. H. Sayed Adaptive Networks. Proceedings of the IEEE 102 (4), p. 460–497. External Links: Document Cited by: §1. Simsekli et al. (2019) U. Simsekli, L. Sagun, and M. Gurbuzbalaban A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networks. In Proceedings of the 36th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 97, p. 5827–5837. External Links: Link Cited by: §1. Vlaski et al. (2023) S. Vlaski, S. Kar, A. H. Sayed, and J. M.F. Moura Networked Signal and Information Processing: Learning by multiagent systems. IEEE Signal Processing Magazine 40 (5), p. 92–105. External Links: Document Cited by: §1. Vlaski and Sayed (2021a) S. Vlaski and A. H. Sayed Distributed Learning in Non-Convex Environments— Part I: Polynomial Escape From Saddle-Points. IEEE Transactions on Signal Processing 69 (), p. 1257–1270. External Links: Document Cited by: Appendix A, Appendix D, §3.1, §3.1. Vlaski and Sayed (2021b) S. Vlaski and A. H. Sayed Distributed Learning in Non-Convex Environments—Part I: Agreement at a Linear Rate. IEEE Transactions on Signal Processing 69 (), p. 1242–1256. External Links: Document Cited by: Appendix A, Appendix D, §3.1, §3.1. Wang et al. (2026) M. Wang, Z. Liu, and L. Luo Near-Optimal Decentralized Stochastic Nonconvex Optimization with Heavy-Tailed Noise. arXiv preprint. Cited by: item ‡ , §1.1, Table 1, §3.2. Xin et al. (2020) R. Xin, U. A. Khan, and S. Kar Variance-Reduced Decentralized Stochastic Optimization With Accelerated Convergence. IEEE Transactions on Signal Processing 68 (), p. 6255–6271. External Links: Document Cited by: §3.1. Xin et al. (2021) R. Xin, U. A. Khan, and S. Kar An Improved Convergence Analysis for Decentralized Online Stochastic Non-Convex Optimization. IEEE Transactions on Signal Processing 69 (), p. 1842–1858. Cited by: Appendix A. Yang et al. (2025) Y. Yang, K. Lu, and L. Wang Online distributed optimization with clipped stochastic gradients: High probability bound of regrets. Automatica 182, p. 112525. External Links: ISSN 0005-1098, Document, Link Cited by: §1.1, Table 1, §2.2, §3.1, §3.2, footnote 5. Yang et al. (2026) Y. Yang, K. Lu, and L. Wang High Probability Convergence of Distributed Clipped Stochastic Gradient Descent with Heavy-tailed Noise. Systems & Control Letters 209, p. 106358. External Links: ISSN 0167-6911, Document, Link Cited by: Appendix A. Yu et al. (2026a) S. Yu, D. Jakovetić, and S. Kar Decentralized Nonconvex Optimization under Heavy-Tailed Noise: Normalization and Optimal Convergence. In 14th International Conference on Learning Representations, p. 8319–8332. External Links: Link Cited by: §C.1, Appendix C, §1.1, Table 1, §3.2, footnote 4. Yu et al. (2026b) S. Yu, D. Jakovetić, and S. Kar Smoothed Gradient Clipping and Error Feedback for Decentralized Optimization under Symmetric Heavy-Tailed Noise. SIAM Journal on Optimization 36 (2), p. 703–728. External Links: Document, Link, https://doi.org/10.1137/24M170747X Cited by: Appendix A. Yu and Kar (2023) S. Yu and S. Kar Secure Distributed Optimization Under Gradient Attacks. IEEE Transactions on Signal Processing 71 (), p. 1802–1816. External Links: Document Cited by: §1.1. Zhang et al. (2020) J. Zhang, S. P. Karimireddy, A. Veit, S. Kim, S. Reddi, S. Kumar, and S. Sra Why are Adaptive Methods Good for Attention Models?. In Advances in Neural Information Processing Systems, Vol. 33, p. 15383–15393. External Links: Link Cited by: §1.1, §1, §3.1, §3.2, §3.2, §3.2. Zhu et al. (2025) Z. Zhu, Y. Huang, X. Wang, S. Ji, and J. Xu Dyn-D2^2P: Dynamic Differentially Private Decentralized Learning with Provable Utility Guarantee. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25, p. 7272–7281. Note: Main Track External Links: Document, Link Cited by: §1.1. Supplement The supplement contains results omitted from the main body. Section A reviews some further literature, Section B provides technical results and proofs, Section C details the experimental setup and contains additional results, Section D discusses the heterogeneity condition, while Section E discusses the transient time. Appendix A Additional Literature In this section we provide some additional related literature. Centralized Results. Nemirovskiĭ et al. (2009) establish optimal HP convergence rates of SGD for convex costs under light-tailed stochastic gradients. Ghadimi and Lan (2013) establish, among other results, the optimal IE and HP convergence rate of SGD for non-convex costs under light-tailed noise, while Li and Orabona (2020) show the same for momentum SGD. Harvey et al. (2019) and Bajović et al. (2023) respectively provide optimal HP convergence rates for the last iterate of SGD for non-smooth and smooth strongly convex costs, while Liu and Zhou (2024) establish unified IE and HP convergence guarantees for smooth and non-smooth convex and strongly convex costs. Liu et al. (2023a) generalize the previous works on non-convex and convex costs, providing unified HP guarantees for several algorithms, including SGD and AdaGrad for smooth and non-smooth costs. Madden et al. (2024) establish HP convergence of SGD under sub-Weibull noise. Gorbunov et al. (2020) propose an accelerated method with gradient clipping for smooth convex costs, while Parletta et al. (2024) study HP convergence of sub-gradient methods for non-smooth convex costs. Koloskova et al. (2023) show that clipped SGD fails to converge for any fixed constant value of the clipping threshold γ. Jakovetić et al. (2023) study convergence of a unified nonlinear SGD framework under symmetric heavy-tailed noise and strongly convex costs. Finally, Puchkin et al. (2024) show that it is possible to achieve the optimal HP convergence rate for convex costs using the median-of-means gradient estimator. Decentralized Results. Jakovetić et al. (2018) show that DSGD converges at an optimal IE rate for strongly convex costs, while Pu and Nedić (2021) show that DSGD with a fixed step-size and the gradient tracking (GT) mechanism, e.g., Lorenzo and Scutari (2016); Nedić et al. (2017); Qu and Li (2018), converges IE to a neighborhood of the optimal solution. Vlaski and Sayed (2021b); Vlaski and Sayed (2021a) study IE guarantees of DSGD for non-convex costs and show that it escapes saddle points with high probability. Koloskova et al. (2020) provide unified IE guarantees for DSGD with local updates and changing network topology, with optimal rates and linear speed-up in the number of users for non-convex and (strongly) convex costs. Xin et al. (2021) establish optimal IE rates of DSGD with GT and linear speed-up in the number of users for non-convex costs and costs satisfying the Polyak-Łojasiewicz (PL) condition. Qin et al. (2025); Yang et al. (2026) study HP convergence of decentralized algorithms with clipping, for convex costs under heavy-tailed noise. Yu et al. (2026b) study convergence of DSGD using smooth clipping under symmetric heavy-tailed noise and strongly convex costs. Finally, a recent line of works show HP convergence with linear speed-up of vanilla DSGD and GT (Armacki and Sayed, 2026; Armacki et al., 2026c). Appendix B Missing Proofs In this section we provide several technical results and proofs omitted from the main body. Subsection B.1 provides general results, Subsection B.2 provides proofs for HP results, while Subsection B.3 provides proofs for IE results. B.1 General Results In this subsection we prove Lemmas 1-4. We start by stating a useful lemma from Sadiev et al. (2023). Lemma 5 (Lemma 5.1 in Sadiev et al. (2023)). Let X∈ℝdX ^d be a random vector and let x=[X]x=E[X] and X~=clip(X) X= clip(X) be its expectation and clipped version. If for some σ>0σ>0 and p∈(1,2]p∈(1,2] we have ‖X−x‖p≤σpE\|X-x\|^p≤σ^p and ‖x‖≤γ/2\|x\|≤ γ2, then ‖[X~]−x‖≤4σpγp−1, \|E[ X]-x\|≤ 4σ^pγ^p-1, (3) ‖X~−[X~]‖2≤18γ2−pσp. \| X-E[ X]\|^2≤ 18γ^2-pσ^p. (4) We next state and prove an extended version of Lemma 1. Lemma 1. Let X1,…,Xn∈ℝdX_1,…,X_n ^d be independent random vectors and let xi=[Xi]x_i=E[X_i] and X~i=clip(Xi) X_i= clip(X_i), i∈[n]i∈[n] be the expectation and clipped version, with x¯=1n∑i∈[n]xi x= 1n _i∈[n]x_i and X~=1n∑i∈[n]X~i X= 1n _i∈[n] X_i being the averaged values. If for some σi>0 _i>0 and p∈(1,2]p∈(1,2] we have ‖Xi−xi‖p≤σipE\|X_i-x_i\|^p≤ _i^p and ‖xi‖≤γ/2\|x_i\|≤ γ2, then ‖[X~]−x¯‖≤4σpγp−1, \|E[ X]- x\|≤ 4σ^pγ^p-1, ‖X~−[X~]‖2≤18γ2−pσpn, \| X-E[ X]\|^2≤ 18γ^2-pσ^pn, where σp=1n∑i∈[n]σipσ^p= 1n _i∈[n] _i^p. Proof. Using Jensen’s inequality and (3), we then get ‖[X~]−x¯‖≤1n∑i∈[n]‖[X~i]−x¯‖≤1n∑i∈[n]4σipγp−1=4σpγp−1,\|E[ X]- x\|≤ 1n _i∈[n]\|E[ X_i]- x\|≤ 1n _i∈[n] 4 _i^pγ^p-1= 4σ^pγ^p-1, proving the first claim. Next, using the fact that XiX_i’s are independent, we have ‖X~−[X~]‖2 \| X-E[ X]\|^2 =1n2∑i∈[n]‖X~i−[X~i]‖2+1n2∑j≠i⟨X~i−[X~i],X~j−[X~j]⟩ = 1n^2 _i∈[n]E\| X_i-E[ X_i]\|^2+ 1n^2 _j≠ iE X_i-E[ X_i], X_j-E[ X_j] =1n2∑i∈[n]‖X~i−[X~i]‖2≤1n2∑i∈[n]18γ2−pσip=18γ2−pσpn, = 1n^2 _i∈[n]E\| X_i-E[ X_i]\|^2≤ 1n^2 _i∈[n]18γ^2-p _i^p= 18γ^2-pσ^pn, where the inequality follows from (4), completing the proof. ∎ We continue by proving Lemma 2. Proof of Lemma 2. Starting from the standard descent lemma for smooth costs, we get f(x¯t+1) f( x^t+1) ≤f(x¯t)−α⟨∇f(x¯t),g^t⟩+α2L2‖g^t‖2 ≤ f( x^t)-α ∇ f( x^t), g^t + α^2L2\| g^t\|^2 =f(x¯t)−α⟨∇f(x¯t),∇¯ft⟩−α⟨∇f(x¯t),g^ut+g^bt⟩+α2L2‖g^t‖2 =f( x^t)-α ∇ f( x^t), ∇f^t -α ∇ f( x^t), g^t_u+ g^t_b + α^2L2\| g^t\|^2 ≤(i)f(x¯t)−α⟨∇f(x¯t),∇¯ft⟩−α⟨∇f(x¯t),g^ut+g^bt⟩+α2L(‖g^ut+g^bt‖2+‖∇¯ft‖2), (i)≤f( x^t)-α ∇ f( x^t), ∇f^t -α ∇ f( x^t), g^t_u+ g^t_b +α^2L (\| g^t_u+ g^t_b\|^2+\| ∇f^t\|^2), ≤(ii)f(x¯t)−α4‖∇f(x¯t)‖2−α2(1−2αL)‖∇¯ft‖2+α2‖∇f(x¯t)−∇¯ft‖2 (i)≤f( x^t)- α4\|∇ f( x^t)\|^2- α2 (1-2α L )\| ∇f^t\|^2+ α2\|∇ f( x^t)- ∇f^t\|^2 −α⟨∇f(x¯t),g^ut⟩+α(1+2αL)‖g^bt‖2+2α2L‖g^ut‖2 -α ∇ f( x^t), g^t_u +α(1+2α L)\| g^t_b\|^2+2α^2L\| g^t_u\|^2 where in (i)(i) we used ‖g^t‖2≤2‖g^ut+g^bt‖2+2‖∇¯ft‖2\| g^t\|^2≤ 2\| g^t_u+ g^t_b\|^2+2\| ∇f^t\|^2, while in (ii)(i) we applied the identities ⟨a,b⟩=12(‖a‖2+‖b‖2−‖a−b‖2) a,b = 12 (\|a\|^2+\|b\|^2-\|a-b\|^2) and ⟨a,b⟩≤‖a‖24+‖b‖2 a,b ≤ \|a\|^24+\|b\|^2, respectively to ⟨∇f(x¯t),∇¯ft⟩ ∇ f( x^t), ∇f^t and ⟨∇f(x¯t),g^ut+g^bt⟩ ∇ f( x^t), g^t_u+ g^t_b . Choosing α≤12Lα≤ 12L implies 1−2αL≥01-2α L≥ 0, which, combined with smoothness of f, gives f(x¯t+1)≤f(x¯t)−α4‖∇f(x¯t)‖2−α⟨∇f(x¯t),g^ut⟩+2α2L‖g^ut‖2+2α‖g^bt‖2+αL22n∑i∈[n]‖xit−x¯t‖2. f( x^t+1)≤ f( x^t)- α4\|∇ f( x^t)\|^2-α ∇ f( x^t), g^t_u +2α^2L\| g^t_u\|^2+2α\| g^t_b\|^2+ α L^22n _i∈[n]\|x^t_i- x^t\|^2. ∎ For ease of notation, define the vectorized, stacked notation t≔col(x1t,…,xnt)∈ℝndx^t (x_1^t,…,x_n^t) ^nd, ~t≔col(g~1t,…,g~nt)∈ℝnd g^t ( g_1^t,…, g_n^t) ^nd and ¯t≔n⊗x¯t∈ℝnd x^t 1_n x^t ^nd and let ≔W⊗Id∈ℝnd×ndW W I_d ^nd× nd, ≔J⊗Id∈ℝnd×ndJ J I_d ^nd× nd, where ⊗ denotes the Kronecker product. We next prove Lemma 3. Proof of Lemma 3. Starting from the update rule (2), it then follows that ‖t+1−¯t+1‖ \|x^t+1- x^t+1\| =‖(−)(t−α~t)‖=‖(−)(t−¯t−α~t)‖ =\|(W-J)(x^t-α g^t)\|=\|(W-J)(x^t- x^t-α g^t)\| ≤λ‖t−¯t−α~t‖≤λ‖t−¯t‖+αλ‖~t‖≤λ|t−¯t|+αγλn, ≤λ\|x^t- x^t-α g^t\|≤λ\|x^t- x^t\|+αλ\| g^t\|≤λ\|x^t- x^t\|+αγλ n, where the last inequality follows from the fact that ‖~t‖≤γn\| g^t\|≤γ n. Iterating the inequality recursively, we get ‖t+1−¯t+1‖≤λt‖1−¯1‖+αγn∑k=1t−1λt−k=(i)αγλn∑k=1t−1λt−1−k≤αγλn1−λ, \|x^t+1- x^t+1\|≤λ^t\|x^1- x^1\|+αγ n _k=1^t-1λ^t-k (i)=αγλ n _k=1^t-1λ^t-1-k≤ αγλ n1-λ, with (i)(i) following from the shared initialization. Next, noting that ‖xit−x¯t‖2≤∑i∈[n]‖xit−x¯t‖2=‖t−¯t‖2\|x^t_i- x^t\|^2≤ _i∈[n]\|x^t_i- x^t\|^2=\|x^t- x^t\|^2, it then follows that, for any i∈[n]i∈[n] and t≥1t≥ 1, we have ‖xit+1−x¯t+1‖≤‖t+1−¯t+1‖≤αγλn1−λ,\|x^t+1_i- x^t+1\|≤\|x^t+1- x^t+1\|≤ αγλ n1-λ, completing the proof. ∎ Let ∇t≔col(∇f1(x1t),…,∇fn(xnt)) ^t (∇ f_1(x_1^t),…,∇ f_n(x_n^t)) be the column stacking of agents’ full gradients evaluated at their local models at time t. We are now ready to prove Lemma 4. Proof of Lemma 4. Starting from the update rule (2) and defining Xt≔‖t−¯t‖2nX^t \|x^t- x^t\|^2n, it follows that for any t≥1t≥ 1, we have Xt+1≤1+λ22Xt+2α2λ2n(1−λ2)‖~t‖2≤1+λ22Xt+4α2λ2n(1−λ2)(‖~t−∇t‖2+‖∇t‖2), X^t+1≤ 1+λ^22X^t+ 2α^2λ^2n(1-λ^2)\| g^t\|^2≤ 1+λ^22X^t+ 4α^2λ^2n(1-λ^2) (\| g^t- ^t\|^2+\| ^t\|^2 ), where (i)(i) follows from Young’s inequality, i.e., (a+b)2≤(1+θ)a2+(1+θ−1)b2(a+b)^2≤(1+θ)a^2+(1+θ^-1)b^2 with θ=1−λ22λ2θ= 1-λ^22λ^2, while in (ii)(i) we again used Young’s inequality with θ=1θ=1. Iterating the inequality recursively, denoting by Yt≔‖~t−∇t‖2+‖∇t‖2Y^t \| g^t- ^t\|^2+\| ^t\|^2 and noting that X1=0X^1=0, we get Xt+1≤4α2λ2n(1−λ2)∑k=1t(1+λ22)t−kYk. X^t+1≤ 4α^2λ^2n(1-λ^2) _k=1^t ( 1+λ^22 )^t-kY^k. (5) We next proceed to bound YkY^k. To that end, we have Yk Y^k =‖~k−∇k‖2+‖∇k‖2=∑i∈[n](‖g~ik−∇fi(xik)‖2+‖∇fi(xik)‖2) =\| g^k- ^k\|^2+\| ^k\|^2= _i∈[n] (\| g^k_i-∇ f_i(x^k_i)\|^2+\|∇ f_i(x^k_i)\|^2 ) =∑i∈[n](‖g~i,bk+g~i,uk‖2+‖∇fi(xik)‖2)≤2∑i∈[n](‖g~i,bk‖2+‖g~i,uk‖2+A2+B2‖∇f(xik)‖2), = _i∈[n] (\| g^k_i,b+ g^k_i,u\|^2+\|∇ f_i(x^k_i)\|^2 )≤ 2 _i∈[n] (\| g^k_i,b\|^2+\| g^k_i,u\|^2+A^2+B^2\|∇ f(x^k_i)\|^2 ), where the last inequality follows from Assumption 4. Plugging the above bound into (5) completes the proof. ∎ Remark 1. Note that Lemma 3 implies the following bound on the average consensus gap 1n∑i∈[n]‖xit−x¯t‖2≤α2γ2λ2n(1−λ)2. 1n _i∈[n]\|x^t_i- x^t\|^2≤ α^2γ^2λ^2n(1-λ)^2. While nice and simple, the main issue in this bound stems from the coupling of the step-size and clipping radius of the same order, namely α2γ2α^2γ^2. From the choice of the step-size in Theorem 1, specifically α≤C2γn2p−13p−2T1−p3p−2α≤ C_2γn 2p-13p-2T 1-p3p-2 for a problem-related constant C2>0C_2>0, it follows that α2γ2λ2n(1−λ)2=(n7p−43p−2T2(1−p)3p−2(1−λ)2). α^2γ^2λ^2n(1-λ)^2=O ( n 7p-43p-2T 2(1-p)3p-2(1-λ)^2 ). While the above quantity on the right-hand side matches the decay of the leading term in Theorem 1 with respect to T, it strictly grows in n. As such, naively using the bound from Lemma 3 in the rest of the analysis would result in a term which matches the leading one in T but increases in n, destroying the linear speed-up, and propagating the network effect to the leading term (via (1−λ)−2(1-λ)^-2). On the other hand, ignoring some terms for simplicity, Lemma 4 results in the following bound 1n∑i∈[n]‖xit−x¯t‖2=(α2n∑i∈[n](‖g~i,bk‖2+‖g~i,uk‖2)). 1n _i∈[n]\|x^t_i- x^t\|^2=O ( α^2n _i∈[n] (\| g^k_i,b\|^2+\| g^k_i,u\|^2 ) ). When agents’ gradients are sufficiently small, i.e., when ‖∇fi(xit)‖≤γ2\|∇ f_i(x^t_i)\|≤ γ2, we can use Lemma 5 to get 1n∑i∈[n]‖xit−x¯t‖2=(α2γ2−p+α2γ2(1−p))=(α2γ2−p). 1n _i∈[n]\|x^t_i- x^t\|^2=O (α^2γ^2-p+α^2γ^2(1-p) )=O (α^2γ^2-p ). The above bound again couples the step-size and the clipping radius, however, this time the step-size decays at a strictly faster rate, ensuring that the consensus gap decays at a strictly faster rate than the leading term. As such, Lemma 4 provides a more fine-grained control of the consensus gap and is crucial to achieving improved rates. However, Lemma 3 is still useful, see, e.g., the proof of Lemma 9 ahead. B.2 High-Probability Results In this subsection we establish the HP convergence of clipped DSGD. In particular, a standard approach in the centralized setting is to construct a desirable event which holds with high probability and on which ‖∇f(xt)‖≤γ2\|∇ f(x^t)\|≤ γ2, for all t∈[T]t∈[T], e.g., (Sadiev et al., 2023; Nguyen et al., 2023). However, in the decentralized setting we need a slightly stronger condition, namely that ‖∇fi(xit)‖≤γ2\|∇ f_i(x^t_i)\|≤ γ2, for all i∈[n]i∈[n] and all t∈[T]t∈[T]. Constructing a desirable event, using the heterogeneity bound and Lemma 3, we will show that such condition indeed holds with high probability. We begin by first stating the celebrated Freedman’s inequality for martingales. Lemma 7. Let Xtt∈ℕ\X_t\_t be a martingale difference sequence such that for some a>0a>0 and all t∈ℕt we have |Xt|≤a|X_t|≤ a almost surely, and let σt2=[Xt2|X1,…,Xt−1]σ^2_t=E[X_t^2\>|\>X_1,…,X_t-1]. Then for any b,c>0b,c>0 and T≥1T≥ 1 ℙ(|∑t∈[T]Xt|>b and ∑t∈[T]σt2≤c)≤2exp(−b22c+2ab/3).P ( | _t∈[T]X_t |>b and _t∈[T]σ^2_t≤ c )≤ 2 (- b^22c+2ab/3 ). Next, define Δt≔f(x¯t)−f⋆ _t f( x^t)-f . Prior to constructing the desirable event, we provide another useful intermediary result, building on Lemmas 2 and 4. Lemma 8. Let Assumptions 1-4 hold. If the step-size satisfies α≤min12L,1−λ28λLB3α≤ \ 12L, 1-λ^28λ LB 3 \, then for any T≥1T≥ 1, we have α16n α16n ∑t∈[T]∑i∈[n]‖∇f(xit)‖2≤Δ1−ΔT+1−α∑t∈[T]⟨∇f(x¯t),g^ut⟩+2α2L∑t∈[T]‖g^ut‖2 _t∈[T] _i∈[n]\|∇ f(x^t_i)\|^2≤ _1- _T+1-α _t∈[T] ∇ f( x^t), g^t_u +2α^2L _t∈[T]\| g^t_u\|^2 +2α∑t∈[T]∥g^bt∥2+12α3λ2L2A2T(1−λ2)2+12α3λ2L2n(1−λ2)2∑t∈[T]∑i∈[n](∥g~i,bt∥2+∥g~i,ut∥2), +2α _t∈[T]\| g^t_b\|^2+ 12α^3λ^2L^2A^2T(1-λ^2)^2+ 12α^3λ^2L^2n(1-λ^2)^2 _t∈[T] _i∈[n] (\| g^t_i,b\|^2+\| g^t_i,u\|^2 ), Proof. Starting from Lemma 2, rearranging and summing up to time T, we get α4∑t∈[T]‖∇f(x¯t)‖2 α4 _t∈[T]\|∇ f( x^t)\|^2 ≤Δ1−ΔT+1−α∑t∈[T]⟨∇f(x¯t),g^ut⟩ ≤ _1- _T+1-α _t∈[T] ∇ f( x^t), g^t_u +2α2L∑t∈[T]∥g^tu∥2+2α∑t∈[T]∥g^tb∥2+αL22n∑t∈[T]∥t−¯t∥2. +2α^2L _t∈[T]\| g^t_u\|^2+2α _t∈[T]\| g^t_b\|^2+ α L^22n _t∈[T]\|x^t- x^t\|^2. Next, using the fact that ‖∇f(x¯t)‖2≥12n∑i∈[n]‖∇f(xit)‖2−L2n‖t−¯t‖2\|∇ f( x^t)\|^2≥ 12n _i∈[n]\|∇ f(x^t_i)\|^2- L^2n\|x^t- x^t\|^2, it follows that α8n α8n ∑t∈[T]∑i∈[n]‖∇f(xit)‖2≤Δ1−ΔT+1−α∑t∈[T]⟨∇f(x¯t),g^ut⟩ _t∈[T] _i∈[n]\|∇ f(x^t_i)\|^2≤ _1- _T+1-α _t∈[T] ∇ f( x^t), g^t_u +2α2L∑t∈[T]∥g^tu∥2+2α∑t∈[T]∥g^tb∥2+3αL24n∑t∈[T]∥t−¯t∥2. +2α^2L _t∈[T]\| g^t_u\|^2+2α _t∈[T]\| g^t_b\|^2+ 3α L^24n _t∈[T]\|x^t- x^t\|^2. Applying Lemma 4, we have α8n∑t∈[T]∑i∈[n] α8n _t∈[T] _i∈[n] ‖∇f(xit)‖2≤Δ1−ΔT+1−α∑t∈[T]⟨∇f(x¯t),g^ut⟩+2α2L∑t∈[T]‖g^ut‖2+2α∑t∈[T]‖g^bt‖2 \|∇ f(x^t_i)\|^2≤ _1- _T+1-α _t∈[T] ∇ f( x^t), g^t_u +2α^2L _t∈[T]\| g^t_u\|^2+2α _t∈[T]\| g^t_b\|^2 +6α3λ2L2n(1−λ2)∑t∈[T]∑k=1t(1+λ22)t−k∑i∈[n](∥g~i,bk∥2+∥g~i,uk∥2+A2+B2∥∇f(xik)∥2) + 6α^3λ^2L^2n(1-λ^2) _t∈[T] _k=1^t ( 1+λ^22 )^t-k _i∈[n] (\| g^k_i,b\|^2+\| g^k_i,u\|^2+A^2+B^2\|∇ f(x^k_i)\|^2 ) ≤Δ1−ΔT+1−α∑t∈[T]⟨∇f(x¯t),g^ut⟩+2α2L∑t∈[T]‖g^ut‖2+2α∑t∈[T]‖g^bt‖2 ≤ _1- _T+1-α _t∈[T] ∇ f( x^t), g^t_u +2α^2L _t∈[T]\| g^t_u\|^2+2α _t∈[T]\| g^t_b\|^2 +12α3λ2L2n(1−λ2)2∑i∈[n]∑t∈[T](∥g~i,bt∥2+∥g~i,ut∥2+A2+B2∥∇f(xit)∥2), + 12α^3λ^2L^2n(1-λ^2)^2 _i∈[n] _t∈[T] (\| g^t_i,b\|^2+\| g^t_i,u\|^2+A^2+B^2\|∇ f(x^t_i)\|^2 ), where in the second inequality we used the fact that for any non-negative sequence att∈ℕ\a_t\_t and λ∈[0,1)λ∈[0,1) ∑t∈[T]∑k∈[t]akλt−k=∑t∈[T]at∑k∈[t]λt−k≤11−λ∑t∈[T]at. _t∈[T] _k∈[t]a_kλ^t-k= _t∈[T]a_t _k∈[t]λ^t-k≤ 11-λ _t∈[T]a_t. Rearranging the terms and noting that α≤1−λ28λLB3α≤ 1-λ^28λ LB 3 implies α8−12α3λ2L2(1−λ2)2≥α16 α8- 12α^3λ^2L^2(1-λ^2)^2≥ α16, we then get α16n α16n ∑t∈[T]∑i∈[n]‖∇f(xit)‖2≤Δ1−ΔT+1−α∑t∈[T]⟨∇f(x¯t),g^ut⟩+2α2L∑t∈[T]‖g^ut‖2 _t∈[T] _i∈[n]\|∇ f(x^t_i)\|^2≤ _1- _T+1-α _t∈[T] ∇ f( x^t), g^t_u +2α^2L _t∈[T]\| g^t_u\|^2 +2α∑t∈[T]∥g^bt∥2+12α3λ2L2A2T(1−λ2)2+12α3λ2L2n(1−λ2)2∑i∈[n]∑t∈[T](∥g~i,bt∥2+∥g~i,ut∥2), +2α _t∈[T]\| g^t_b\|^2+ 12α^3λ^2L^2A^2T(1-λ^2)^2+ 12α^3λ^2L^2n(1-λ^2)^2 _i∈[n] _t∈[T] (\| g^t_i,b\|^2+\| g^t_i,u\|^2 ), which completes the proof. ∎ Lemma 8 provides a descent inequality which combines the network-averaged clipped quantities, as well as the strictly local ones. We are now ready to construct the desirable event and show that it holds with high probability. Lemma 9. Let Assumptions 1-5 hold and let the step-size and clipping threshold be chosen as γ=max2A+4BLΔ1+2λLn1−λ,(nT)13p−2γ= \2A+4B L _1+ 2λ L n1-λ,(nT) 13p-2 \ and α=min12L,1−λ28λLB3,1−λ2λL6,(1−λ2)26λ2L,(1−λ2)2/3Δ11/32(λLA)2/3T1/3123,C1γn2p−13p−2T1−p3p−2,C2γ2/3np3(3p−2)T2(1−p)3(3p−2),C3γα= \ 12L, 1-λ^28λ LB 3, 1-λ^2λ L 6, (1-λ^2)^26λ^2L, (1-λ^2)^2/3 _1^1/32(λ LA)^2/3T^1/3 [3]12, C_1γn 2p-13p-2T 1-p3p-2, C_2γ^2/3n p3(3p-2)T 2(1-p)3(3p-2), C_3γ \, where C1=minΔ164σ2p,Δ1192log(6Tδ)σp/22LC_1= \ _164σ^2p, _1192 ( 6Tδ )σ^p/2 2L \, C2≤Δ11/3(1−λ2)2/312σp/3λ2/3L2/3C_2≤ _1^1/3(1-λ^2)^2/312σ^p/3λ^2/3L^2/3 and C3=min1,3Δ164log(6Tδ)2LC_3= \1, 3 _164 ( 6Tδ ) 2L \, for δ∈(0,1)δ∈(0,1). For any N∈[T+1]N∈[T+1], let ΓN _N be the event that, for all t∈[N]t∈[N] −α∑k∈[t−1]⟨∇f(x¯k),g^uk⟩+2α2L∑k∈[t−1]∥g^uk∥2+2α∑k∈[t−1]∥g^bk∥2 -α _k∈[t-1] ∇ f( x^k), g^k_u +2α^2L _k∈[t-1]\| g^k_u\|^2+2α _k∈[t-1]\| g^k_b\|^2 +12α3λ2L2A2T(1−λ2)2+12α3λ2L2n(1−λ2)2∑k∈[t−1]∑i∈[n](‖g~i,bk‖2+‖g~i,uk‖2)≤Δ1. + 12α^3λ^2L^2A^2T(1-λ^2)^2+ 12α^3λ^2L^2n(1-λ^2)^2 _k∈[t-1] _i∈[n] (\| g^k_i,b\|^2+\| g^k_i,u\|^2 )≤ _1. It then holds that ℙ(ΓN)≥1−(N−1)δTP( _N)≥ 1- (N-1)δT. Moreover, on the event ΓN _N we have ‖∇fi(xit)‖≤γ2\|∇ f_i(x^t_i)\|≤ γ2, for all i∈[n]i∈[n] and t∈[N]t∈[N]. Proof. We prove the result by induction on N. For N=1N=1 we have Δ1≥0 _1≥ 0, which holds trivially. Next, assume that for some N∈[T]N∈[T], we have ℙ(ΓN)≥1−(N−1)δTP( _N)≥ 1- (N-1)δT. Using Lemma 8 and rearranging, it follows that under ΓN _N, we have for any t∈[N]t∈[N] Δt _t ≤Δ1−α∑k∈[t−1]⟨∇f(x¯k),g^uk⟩+2α2L∑k∈[t−1]‖g^uk‖2+2α∑k∈[t−1]‖g^bk‖2 ≤ _1-α _k∈[t-1] ∇ f( x^k), g^k_u +2α^2L _k∈[t-1]\| g^k_u\|^2+2α _k∈[t-1]\| g^k_b\|^2 +12α3λ2L2A2T(1−λ2)2+12α3λ2L2n(1−λ2)2∑k∈[t−1]∑i∈[n](‖g~i,bk‖2+‖g~i,uk‖2)≤2Δ1. + 12α^3λ^2L^2A^2T(1-λ^2)^2+ 12α^3λ^2L^2n(1-λ^2)^2 _k∈[t-1] _i∈[n] (\| g^k_i,b\|^2+\| g^k_i,u\|^2 )≤ 2 _1. (6) From the smoothness of f and (6), it follows that for all t∈[N]t∈[N] on ΓN _N we have ‖∇f(x¯t)‖≤2LΔt≤2LΔ1.\|∇ f( x^t)\|≤ 2L _t≤ 2 L _1. (7) Using the heterogeneity bound, it can then be seen that for any i∈[n]i∈[n] and t∈[N]t∈[N] ‖∇fi(xit)‖ \|∇ f_i(x^t_i)\| ≤L‖xit−x¯t‖+‖∇fi(x¯t)‖≤L‖t−¯t‖+A+B‖∇f(x¯t)‖ ≤ L\|x^t_i- x^t\|+\|∇ f_i( x^t)\|≤ L\|x^t- x^t\|+A+B\|∇ f( x^t)\| ≤(i)αγλLn1−λ+A+2BLΔ1≤(ii)λLn1−λ+A+2BLΔ1≤(iii)γ2, (i)≤ αγλ L n1-λ+A+2B L _1 (i)≤ λ L n1-λ+A+2B L _1 (i)≤ γ2, (8) where (i)(i) follows from Lemma 3, (ii)(i) follows from the choice of step-size, while (iii)(i) follows from the choice of clipping threshold. We will now show that ΓN+1 _N+1 holds with probability at least 1−NδT1- NδT. In particular, we will show that ΓN∩A⊆ΓN+1 _N∩ A _N+1 for some event A, allowing us to focus on the part of the probability space where ΓN _N holds. Using the bound in Lemma 8 with T=NT=N and the fact that the left-hand side is non-negative, we get ΔN+1≤Δ1−α∑t∈[N]⟨∇f(x¯t),g^ut⟩+2α2L∑t∈[N]‖g^ut‖2+2α∑t∈[N]‖g^bt‖2 _N+1≤ _1-α _t∈[N] ∇ f( x^t), g^t_u +2α^2L _t∈[N]\| g^t_u\|^2+2α _t∈[N]\| g^t_b\|^2 +12α3λ2L2A2T(1−λ2)2+12α3λ2L2n(1−λ2)2∑t∈[N]∑i∈[n]‖g~i,bt‖2+12α3λ2L2n(1−λ2)2∑t∈[N]∑i∈[n]‖g~i,ut‖2. + 12α^3λ^2L^2A^2T(1-λ^2)^2+ 12α^3λ^2L^2n(1-λ^2)^2 _t∈[N] _i∈[n]\| g^t_i,b\|^2+ 12α^3λ^2L^2n(1-λ^2)^2 _t∈[N] _i∈[n]\| g^t_i,u\|^2. Next, we construct martingale difference sequences by adding and subtracting t‖g^ut‖2E_t\| g^t_u\|^2 and t‖g~i,ut‖2E_t\| g^t_i,u\|^2. For ease of notation, define θt≔‖g^ut‖2−t‖g^ut‖2θ^t \| g^t_u\|^2-E_t\| g^t_u\|^2 and ηit≔‖g~i,ut‖2−t‖g~i,ut‖2η^t_i \| g^t_i,u\|^2-E_t\| g^t_i,u\|^2. We then have ΔN+1≤Δ1−α∑t∈[N]⟨∇f(x¯t),g^ut⟩+2α2L∑t∈[N]θt+2α2L∑t∈[N]t‖g^ut‖2+2α∑t∈[N]‖g^bt‖2 _N+1≤ _1-α _t∈[N] ∇ f( x^t), g^t_u +2α^2L _t∈[N]θ^t+2α^2L _t∈[N]E_t\| g^t_u\|^2+2α _t∈[N]\| g^t_b\|^2 (9) +12α3λ2L2A2T(1−λ2)2+12α3λ2L2n(1−λ2)2∑t∈[N]∑i∈[n]‖g~i,bt‖2+12α3λ2L2n(1−λ2)2∑t∈[N]∑i∈[n](ηit+t‖g~i,ut‖2). + 12α^3λ^2L^2A^2T(1-λ^2)^2+ 12α^3λ^2L^2n(1-λ^2)^2 _t∈[N] _i∈[n]\| g^t_i,b\|^2+ 12α^3λ^2L^2n(1-λ^2)^2 _t∈[N] _i∈[n] (η^t_i+E_t\| g^t_i,u\|^2 ). Recalling that we are focused on the event where ΓN _N holds and using (8), we can then apply Lemmas 1 and 5 to bound some of the terms in (9), as follows ‖g~i,bt‖2≤4σ2pγ2(p−1),‖g^bt‖2≤4σ2pγ2(p−1),t‖g~i,ut‖2≤18γ2−pσp and t‖g^ut‖2≤18γ2−pσpn.\| g^t_i,b\|^2≤ 4σ^2pγ^2(p-1),\>\>\| g^t_b\|^2≤ 4σ^2pγ^2(p-1),\>\>E_t\| g^t_i,u\|^2≤ 18γ^2-pσ^p\> and E_t\| g^t_u\|^2≤ 18γ^2-pσ^pn. Plugging back into (9) and recalling that N≤TN≤ T, we get ΔN+1≤Δ1−α∑t∈[N]⟨∇f(x¯t),g^ut⟩+2α2L∑t∈[N]θt+36α2γ2−pσpLTn+8ασ2pTγ2(p−1) _N+1≤ _1-α _t∈[N] ∇ f( x^t), g^t_u +2α^2L _t∈[N]θ^t+ 36α^2γ^2-pσ^pLTn+ 8ασ^2pTγ^2(p-1) +12α3λ2L2A2T(1−λ2)2+48α3σ2pλ2L2T(1−λ2)2γ2(p−1)+216α3γ2−pσpλ2L2T(1−λ2)2+12α3λ2L2n(1−λ2)2∑t∈[N]∑i∈[n]ηit. + 12α^3λ^2L^2A^2T(1-λ^2)^2+ 48α^3σ^2pλ^2L^2T(1-λ^2)^2γ^2(p-1)+ 216α^3γ^2-pσ^pλ^2L^2T(1-λ^2)^2+ 12α^3λ^2L^2n(1-λ^2)^2 _t∈[N] _i∈[n]η^t_i. (10) We now focus on bounding the remaining three terms in (10), i.e., B1=α∑t∈[N]⟨∇f(x¯t),g^ut⟩B_1=α _t∈[N] ∇ f( x^t), g^t_u , B2=2α2L∑t∈[N]θtB_2=2α^2L _t∈[N]θ^t and B3=12α3λ2L2n(1−λ2)2∑t∈[N]∑i∈[n]ηitB_3= 12α^3λ^2L^2n(1-λ^2)^2 _t∈[N] _i∈[n]η^t_i. Bounding B1B_1. We define the variable Zt=∇f(x¯t),if Δt≤2Δ10,otherwiseZ^t= cases∇ f( x^t),&if _t≤ 2 _1\\ 0,&otherwise cases. From the definition of ZtZ^t it follows that ‖Zt‖≤2LΔ1\|Z^t\|≤ 2 L _1, while from the definition of g^ut g^t_u it follows that ‖g^ut‖≤2γ\| g^t_u\|≤ 2γ, therefore ⟨Zt,g^ut⟩≤4γLΔ1 Z^t, g^t_u ≤ 4γ L _1, almost surely. Further, it can be seen that t⟨Zt,g^ut⟩=0E_t Z^t, g^t_u =0, making ⟨Zt,g^ut⟩ Z^t, g^t_u a bounded martingale difference sequence. Applying Lemma 7, we get ℙ(|∑t∈[N]α⟨Zt,g^ut⟩|>b and ∑t∈[N]α2t[⟨Zt,g^ut⟩2]≤c)≤2exp(−b22c+8αγbLΔ1/3),P ( | _t∈[N]α Z^t, g^t_u |>b and _t∈[N]α^2E_t [ Z^t, g^t_u ^2 ]≤ c )≤ 2 (- b^22c+8αγ b L _1/3 ), for any b,c>0b,c>0. Choosing c=Clog(6Tδ)c=C ( 6Tδ ) for some C>0C>0 (to be specified later) and b=log(6Tδ)(43αγLΔ1+169α2γ2LΔ1+2C),b= ( 6Tδ ) ( 43αγ L _1+ 169α^2γ^2L _1+2C ), (11) results in 2exp(−b22c+8αγbLΔ1/3)=δ3T.2 (- b^22c+8αγ b L _1/3 )= δ3T. (12) Next, recalling (6), it follows that Zt=∇f(x¯t)Z^t=∇ f( x^t) for all t∈[N]t∈[N] on ΓN _N, therefore B1=α∑t∈[N]⟨−Zt,g^ut⟩B_1=α _t∈[N] -Z^t, g^t_u on ΓN _N. Further, under ΓN _N, it holds that ∑t∈[N]α2t[⟨−Zt,g^ut⟩2] _t∈[N]α^2E_t [ -Z^t, g^t_u ^2 ] ≤∑t∈[N]α2t‖Zt‖2‖g^ut‖2≤4α2LΔ1∑t∈[N]t‖g^ut‖2 ≤ _t∈[N]α^2E_t\|Z^t\|^2\| g^t_u\|^2≤ 4α^2L _1 _t∈[N]E_t\| g^t_u\|^2 ≤(i)72α2γ2−pσpLΔ1Nn≤72α2γ2−pσpLΔ1Tn, (i)≤ 72α^2γ^2-pσ^pL _1Nn≤ 72α^2γ^2-pσ^pL _1Tn, (13) where (i)(i) follows from Lemma 1. Therefore, choosing C=72α2γ2−pσpLΔ1TnC= 72α^2γ^2-pσ^pL _1Tn and defining the event Ξ1=ω:B1(ω)≤b _1= \ω:B_1(ω)≤ b \, where b is given in (11), it follows that ℙ(ΓN∩Ξ1) ( _N∩ _1) =ℙ(ΓN∩∑t∈[N]α⟨−Zt,g^ut⟩≤b) =P ( _N∩ \ _t∈[N]α -Z^t, g^t_u ≤ b \ ) =(a)ℙ(ΓN∩∑t∈[N]α⟨−Zt,g^ut⟩≤b or ∑t∈[N]α2⟨−Zt,g^ut⟩2>Clog(6Tδ)) (a)=P ( _N∩ \ _t∈[N]α -Z^t, g^t_u ≤ b\> or _t∈[N]α^2 -Z^t, g^t_u ^2>C ( 6Tδ ) \ ) ≥(b)1−ℙ(ΓNc)−ℙ(∑t∈[N]α⟨−Zt,g^ut⟩>b and ∑t∈[N]α2⟨−Zt,g^ut⟩2≤Clog(6Tδ)) (b)≥1-P( _N^c)-P ( _t∈[N]α -Z^t, g^t_u >b\> and _t∈[N]α^2 -Z^t, g^t_u ^2≤ C ( 6Tδ ) \ ) ≥(c)1−(N−1)δT−δ3T=1−(N−2/3)δT. (c)≥1- (N-1)δT- δ3T=1- (N-2/3)δT. where (a)(a) follows from (13) and the choice of C, in (b)(b) we used ℙ(A∩B)≥1−ℙ(Ac)−ℙ(Bc)P(A∩ B)≥ 1-P(A^c)-P(B^c), while (c)(c) follows from (12) and the induction hypothesis. Bounding B2B_2. Recall that B2=2α2L∑t∈[N]θtB_2=2α^2L _t∈[N]θ^t, where θt=‖g^ut‖2−t‖g^ut‖2θ^t=\| g^t_u\|^2-E_t\| g^t_u\|^2. By definition, we know that t[θt]=0E_t[θ^t]=0 and |2α2Lθt|≤16α2γ2L|2α^2Lθ^t|≤ 16α^2γ^2L, hence we can apply Lemma 7, to get ℙ(|B2|>d and ∑t∈[N]4α4L2t[(θt)2]≤e)≤2exp(−d22e+32α2γ2Ld/3),P ( |B_2 |>d and _t∈[N]4α^4L^2E_t [(θ^t)^2 ]≤ e )≤ 2 (- d^22e+32α^2γ^2Ld/3 ), for any d,e>0d,e>0. Choosing e=Elog(6Tδ)e=E ( 6Tδ ) for some E>0E>0 (to be specified later) and d=log(6Tδ)(163α2γ2L+2569α4γ4L2+2E),d= ( 6Tδ ) ( 163α^2γ^2L+ 2569α^4γ^4L^2+2E ), (14) results in 2exp(−d22e+32α2γ2Ld/3)=δ3T2 (- d^22e+32α^2γ^2Ld/3 )= δ3T. Further, under ΓN _N, it holds that ∑t∈[N]t[(2α2Lθt)2] _t∈[N]E_t [(2α^2Lθ^t)^2 ] ≤(i)16α2γ2L∑t∈[N]t|2α2Lθt|≤(ii)32α4γ2L2∑t∈[N]t‖g^ut‖2 (i)≤16α^2γ^2L _t∈[N]E_t|2α^2Lθ^t| (i)≤32α^4γ^2L^2 _t∈[N]E_t\| g^t_u\|^2 ≤576α4γ4−pσpL2Nn≤576α4γ4−pσpL2Tn, ≤ 576α^4γ^4-pσ^pL^2Nn≤ 576α^4γ^4-pσ^pL^2Tn, where (i)(i) follows from |2α2Lθt|≤16α2γ2L|2α^2Lθ^t|≤ 16α^2γ^2L, in (ii)(i) we used |X−X|≤2XE|X-EX|≤ 2EX for a non-negative random variable, while (iii)(i) follows from Lemma 1. Therefore, choosing E=576α4γ4−pσpL2TnE= 576α^4γ^4-pσ^pL^2Tn, defining the event Ξ2=ω:B2(ω)≤d _2= \ω:B_2(ω)≤ d \ where d is given in (14) and following similar steps as in the previous case, it can be shown that ℙ(ΓN∩Ξ1∩Ξ2)≥1−(N−1/3)δTP( _N∩ _1∩ _2)≥ 1- (N-1/3)δT. Bounding B3B_3. Finally, consider the term B3=12α3λ2L2n(1−λ2)2∑t∈[N]∑i∈[n]ηitB_3= 12α^3λ^2L^2n(1-λ^2)^2 _t∈[N] _i∈[n]η^t_i, where ηit=‖g~i,ut‖2−t‖g~i,ut‖2η^t_i=\| g^t_i,u\|^2-E_t\| g^t_i,u\|^2. By definition, we know that t[ηit]=0E_t[η^t_i]=0 and |12α3λ2L2n(1−λ2)2ηit|≤96α3γ2λ2L2n(1−λ2)2 | 12α^3λ^2L^2n(1-λ^2)^2η^t_i |≤ 96α^3γ^2λ^2L^2n(1-λ^2)^2, hence we can apply Lemma 7, to get ℙ(|B3|>g and ∑t∈[N]t(12α3λ2L2n(1−λ2)2∑i∈[n]ηit)2≤h)≤2exp(−g22h+192α3γ2λ2L2g/3n(1−λ2)2),P ( |B_3 |>g and _t∈[N]E_t ( 12α^3λ^2L^2n(1-λ^2)^2 _i∈[n]η^t_i )^2≤ h )≤ 2 (- g^22h+192α^3γ^2λ^2L^2g/3n(1-λ^2)^2 ), for any g,h>0g,h>0. Moreover, from Assumption 5 we can conclude that ηiti∈[n]\η^t_i\_i∈[n] are independent conditioned on ℱtF_t. Combined with t[ηit]=0E_t[η^t_i]=0, it follows that on ΓN _N ∑t∈[N]t(12α3λ2L2n(1−λ2)2∑i∈[n]ηit)2=144α6λ4L4n2(1−λ2)4∑t∈[N]∑i∈[n]t[(ηit)2] _t∈[N]E_t ( 12α^3λ^2L^2n(1-λ^2)^2 _i∈[n]η^t_i )^2= 144α^6λ^4L^4n^2(1-λ^2)^4 _t∈[N] _i∈[n]E_t [(η^t_i)^2 ] ≤(i)1152α6γ2λ4L4n2(1−λ2)4∑t∈[N]∑i∈[n]t[|ηit|]≤(ii)2304α6γ2λ4L4n2(1−λ2)4∑t∈[N]∑i∈[n]t‖g~i,ut‖2 (i)≤ 1152α^6γ^2λ^4L^4n^2(1-λ^2)^4 _t∈[N] _i∈[n]E_t [|η^t_i| ] (i)≤ 2304α^6γ^2λ^4L^4n^2(1-λ^2)^4 _t∈[N] _i∈[n]E_t\| g^t_i,u\|^2 ≤(iii)41472α6γ4−pσpλ4L4Nn(1−λ2)4≤41472α6γ4−pσpλ4L4Tn(1−λ2)4, (i)≤ 41472α^6γ^4-pσ^pλ^4L^4Nn(1-λ^2)^4≤ 41472α^6γ^4-pσ^pλ^4L^4Tn(1-λ^2)^4, where in (i)(i) we used the fact that |ηit|≤8γ2|η^t_i|≤ 8γ^2, (ii)(i) follows from |X−X|≤2XE|X-EX|≤ 2EX for X≥0X≥ 0, while in (iii)(i) we used Lemma 5. Following the same reasoning as in the previous two cases, it can be seen that choosing h=Hlog(6Tδ)h=H ( 6Tδ ), where H=41472α6γ4−pσpλ4L4Tn(1−λ2)4H= 41472α^6γ^4-pσ^pλ^4L^4Tn(1-λ^2)^4 and g=log(6Tδ)(32α3γ2λ2L2n(1−λ2)2+1024α6γ4λ4L4n2(1−λ2)4+2H),g= ( 6Tδ ) ( 32α^3γ^2λ^2L^2n(1-λ^2)^2+ 1024α^6γ^4λ^4L^4n^2(1-λ^2)^4+2H ), (15) results in 2exp(−g22h+192α3γ2λ2L2g/3n(1−λ2)2)=δ3T2 (- g^22h+192α^3γ^2λ^2L^2g/3n(1-λ^2)^2 )= δ3T. Therefore, defining Ξ3=ω:B3(ω)≤g _3=\ω:B_3(ω)≤ g\ and following similar reasoning as before, it can be concluded that ℙ(ΓN∩Ξ1∩Ξ2∩Ξ3)≥1−NδT.P( _N∩ _1∩ _2∩ _3)≥ 1- NδT. (16) Completing the induction. Consider the event ΓN∩Ξ1∩Ξ2∩Ξ3 _N∩ _1∩ _2∩ _3. From (16) we know that ℙ(ΓN∩Ξ1∩Ξ2∩Ξ3)≥1−NδTP( _N∩ _1∩ _2∩ _3)≥ 1- NδT, while from (10) we know that on this event ΔN+1≤Δ1+b+d+g+36α2γ2−pσpLTn+8ασ2pTγ2(p−1) _N+1≤ _1+b+d+g+ 36α^2γ^2-pσ^pLTn+ 8ασ^2pTγ^2(p-1) +12α3λ2L2A2T(1−λ2)2+48α3σ2pλ2L2T(1−λ2)2γ2(p−1)+216α3γ2−pσpλ2L2T(1−λ2)2, + 12α^3λ^2L^2A^2T(1-λ^2)^2+ 48α^3σ^2pλ^2L^2T(1-λ^2)^2γ^2(p-1)+ 216α^3γ^2-pσ^pλ^2L^2T(1-λ^2)^2, (17) where b,d,gb,d,g are given in (11), (14) and (15). Note that if we can choose α and γ such that the right-hand side in (17) is less than or equal to 2Δ12 _1, it would then follow that on ΓN∩Ξ1∩Ξ2∩Ξ3 _N∩ _1∩ _2∩ _3 we have ΔN+1≤2Δ1 _N+1≤ 2 _1, hence ΓN∩Ξ1∩Ξ2∩Ξ3⊆ΓN+1 _N∩ _1∩ _2∩ _3 _N+1 and ℙ(ΓN+1)≥ℙ(ΓN∩Ξ1∩Ξ2∩Ξ3)≥1−NδTP( _N+1) ( _N∩ _1∩ _2∩ _3)≥ 1- NδT, completing the induction. Therefore, our aim is to show that there exist α,γα,γ such that b b +d+g+36α2γ2−pσpLTn+8ασ2pTγ2(p−1)+12α3λ2L2A2T(1−λ2)2 +d+g+ 36α^2γ^2-pσ^pLTn+ 8ασ^2pTγ^2(p-1)+ 12α^3λ^2L^2A^2T(1-λ^2)^2 +48α3σ2pλ2L2T(1−λ2)2γ2(p−1)+216α3γ2−pσpλ2L2T(1−λ2)2≤Δ1, + 48α^3σ^2pλ^2L^2T(1-λ^2)^2γ^2(p-1)+ 216α^3γ^2-pσ^pλ^2L^2T(1-λ^2)^2≤ _1, (18) where b,d,gb,d,g are given in (11), (14) and (15). Let the clipping threshold and step-size satisfy γ≥max2A+4BLΔ1+2λLn1−λ,(nT)13p−2γ≥ \2A+4B L _1+ 2λ L n1-λ,(nT) 13p-2 \ and α≤minC1n2p−13p−2T1−p3p−2γ−1,C2np3(3p−2)T2(1−p)3(3p−2)γ−23,12L,1−λ28λLB3,α≤ \C_1n 2p-13p-2T 1-p3p-2γ^-1,C_2n p3(3p-2)T 2(1-p)3(3p-2)γ^- 23, 12L, 1-λ^28λ LB 3 \, for some C1,C2>0C_1,C_2>0. It can then be verified that α2γ2−p≤nC12T−1α^2γ^2-p≤ nC_1^2T^-1, αγ2(1−p)≤C1T−1αγ^2(1-p)≤ C_1T^-1 and α3γ2−p≤C23T−1α^3γ^2-p≤ C_2^3T^-1, hence choosing C1≤minΔ112σp/22L,Δ164σ2pC_1≤ \ _112σ p2 2L, _164σ^2p \, C2≤Δ11/3(1−λ2)2/312σp/3λ2/3L2/3C_2≤ _1^1/3(1-λ^2)^2/312σ^p/3λ^2/3L^2/3 and α≤min(1−λ2)2Δ196λ2L2A2T3,1−λ2λL6α≤ \ [3] (1-λ^2)^2 _196λ^2L^2A^2T, 1-λ^2λ L 6 \, it can be verified that (18) becomes b+d+g≤3Δ18b+d+g≤ 3 _18. We now bound each of these terms. First, recall that b=log(6Tδ)(43αγLΔ1+169α2γ2LΔ1+2C),b= ( 6Tδ ) ( 43αγ L _1+ 169α^2γ^2L _1+2C ), where C=72α2γ2−pσpLΔ1Tn≤72C12σpLΔ1C= 72α^2γ^2-pσ^pL _1Tn≤ 72C_1^2σ^pL _1. Further, if α≤C3γ−1α≤ C_3γ^-1, where C3≤3Δ164log(6Tδ)2LC_3≤ 3 _164 ( 6Tδ) 2L and C1≤Δ1192log(6Tδ)σp/22LC_1≤ _1192 ( 6Tδ)σ^p/2 2L, it follows that b≤log(6Tδ)(43C3LΔ1+169C32LΔ1+144C12σpLΔ1)≤Δ18.b≤ ( 6Tδ ) ( 43C_3 L _1+ 169C_3^2L _1+144C_1^2σ^pL _1 )≤ _18. (19) Next, recall that d=log(6Tδ)(163α2γ2L+2569α4γ4L2+2E),d= ( 6Tδ ) ( 163α^2γ^2L+ 2569α^4γ^4L^2+2E ), where E=576α4γ4−pσpL2Tn≤576C12C32σpL2≤288C32LΔ11922log2(6Tδ)E= 576α^4γ^4-pσ^pL^2Tn≤ 576C_1^2C_3^2σ^pL^2≤ 288C_3^2L _1192^2 ^2( 6Tδ). From the previous choice of C3C_3, it can be verified that d≤log(6Tδ)(163C32L+2569C34L2+C32LΔ164log2(6Tδ))≤Δ18.d≤ ( 6Tδ ) ( 163C_3^2L+ 2569C_3^4L^2+ C_3^2L _164 ^2( 6Tδ) )≤ _18. (20) Finally, recall that g=log(6Tδ)(32α3γ2λ2L2n(1−λ2)2+1024α6γ4λ4L4n2(1−λ2)4+2H),g= ( 6Tδ ) ( 32α^3γ^2λ^2L^2n(1-λ^2)^2+ 1024α^6γ^4λ^4L^4n^2(1-λ^2)^4+2H ), where H=41472α6γ4−pσpλ4L4Tn(1−λ2)4≤41472α2C12C32σpλ4L4(1−λ2)4≤9Δ1α2C32λ4L316(1−λ2)4log2(6Tδ)≤Δ1C32L64log2(6Tδ)H= 41472α^6γ^4-pσ^pλ^4L^4Tn(1-λ^2)^4≤ 41472α^2C_1^2C_3^2σ^pλ^4L^4(1-λ^2)^4≤ 9 _1α^2C_3^2λ^4L^316(1-λ^2)^4 ^2( 6Tδ)≤ _1C_3^2L64 ^2( 6Tδ), where the last inequality follows from α≤(1−λ2)26λ2Lα≤ (1-λ^2)^26λ^2L. Using the same step-size condition, we then have g≤log(6Tδ)(16C32L3+2569C34L2+C32LΔ132log2(6Tδ))≤Δ18.g≤ ( 6Tδ ) ( 16C_3^2L3+ 2569C_3^4L^2+ C_3^2L _132 ^2( 6Tδ) )≤ _18. (21) Combining (19), (20) and (21), we finally get b+d+g≤3Δ18b+d+g≤ 3 _18, completing the proof. ∎ We are now ready to prove Theorem 1. Prior to that, we state the full version, including the higher-order terms omitted in the main body. Theorem 1. Let Assumptions 1-5 hold. If for any T≥1T≥ 1 and δ∈(0,1)δ∈(0,1), the clipping threshold and the step-size are chosen as γ=max2A+4BLΔ1+2λLn1−λ,(nT)13p−2γ= \2A+4B L _1+ 2λ L n1-λ,(nT) 13p-2 \ and α=min12L,1−λ28λLB3,1−λ2λL6,(1−λ2)26λ2L,(1−λ2)2/3Δ11/32(λLA)2/3T1/3123,C1γn2p−13p−2T1−p3p−2,C2γ2/3np3(3p−2)T2(1−p)3(3p−2),C3γα= \ 12L, 1-λ^28λ LB 3, 1-λ^2λ L 6, (1-λ^2)^26λ^2L, (1-λ^2)^2/3 _1^1/32(λ LA)^2/3T^1/3 [3]12, C_1γn 2p-13p-2T 1-p3p-2, C_2γ^2/3n p3(3p-2)T 2(1-p)3(3p-2), C_3γ \, where C1=minΔ164σ2p,Δ1192log(6Tδ)σp/22LC_1= \ _164σ^2p, _1192 ( 6Tδ )σ^p/2 2L \, C2=Δ11/3(1−λ2)2/312σp/3λ2/3L2/3C_2= _1^1/3(1-λ^2)^2/312σ^p/3λ^2/3L^2/3 and C3=min1,3Δ164log(6Tδ)2LC_3= \1, 3 _164 ( 6Tδ ) 2L \, then with probability at least 1−δ1-δ 1nT∑t∈[T]∑i∈[n]∥∇f(xit)∥2=~(max(nT)2(1−p)3p−2,n13p−2T3(p−1)3p−2,n−p6p−4T1−2p3p−2(1−λ), 1nT _t∈[T] _i∈[n]\|∇ f(x^t_i)\|^2= O ( \(nT) 2(1-p)3p-2, n 13p-2T 3(p-1)3p-2, n -p6p-4T 1-2p3p-2(1-λ), n2(p−1)3(3p−2)(1−λ)43T7p−43(3p−2),n2−p3(3p−2)(1−λ2)23T7p−63(3p−2),T−2/3(1−λ2)2/3,T−1(1−λ2)2,nT−11−λ). n 2(p-1)3(3p-2)(1-λ) 43T 7p-43(3p-2), n 2-p3(3p-2)(1-λ^2) 23T 7p-63(3p-2), T^-2/3(1-λ^2)^2/3, T^-1(1-λ^2)^2, nT^-11-λ \ ). Proof. Starting from Lemma 8, we have α16n α16n ∑t∈[T]∑i∈[n]‖∇f(xit)‖2≤Δ1−ΔT+1−α∑t∈[T]⟨∇f(x¯t),g^ut⟩+2α2L∑t∈[T]‖g^ut‖2 _t∈[T] _i∈[n]\|∇ f(x^t_i)\|^2≤ _1- _T+1-α _t∈[T] ∇ f( x^t), g^t_u +2α^2L _t∈[T]\| g^t_u\|^2 +2α∑t∈[T]∥g^bt∥2+12α3λ2L2A2T(1−λ2)2+12α3λ2L2n(1−λ2)2∑i∈[n]∑t∈[T](∥g~i,bt∥2+∥g~i,ut∥2). +2α _t∈[T]\| g^t_b\|^2+ 12α^3λ^2L^2A^2T(1-λ^2)^2+ 12α^3λ^2L^2n(1-λ^2)^2 _i∈[n] _t∈[T] (\| g^t_i,b\|^2+\| g^t_i,u\|^2 ). Using Lemma 9, we know that, with probability at least 1−δ1-δ α16n∑t∈[T]∑i∈[n]‖∇f(xit)‖2≤Δ1−ΔT+1−α∑t∈[T]⟨∇f(x¯t),g^ut⟩+2α2L∑t∈[T]‖g^ut‖2 α16n _t∈[T] _i∈[n]\|∇ f(x^t_i)\|^2≤ _1- _T+1-α _t∈[T] ∇ f( x^t), g^t_u +2α^2L _t∈[T]\| g^t_u\|^2 +2α∑t∈[T]∥g^bt∥2+12α3λ2L2A2T(1−λ2)2+12α3λ2L2n(1−λ2)2∑i∈[n]∑t∈[T](∥g~i,bt∥2+∥g~i,ut∥2)≤2Δ1. +2α _t∈[T]\| g^t_b\|^2+ 12α^3λ^2L^2A^2T(1-λ^2)^2+ 12α^3λ^2L^2n(1-λ^2)^2 _i∈[n] _t∈[T] (\| g^t_i,b\|^2+\| g^t_i,u\|^2 )≤ 2 _1. Dividing both sides by αT16 α T16, we get that, with probability at least 1−δ1-δ 1nT∑t∈[T]∑i∈[n]‖∇f(xit)‖2≤32Δ1αT. 1nT _t∈[T] _i∈[n]\|∇ f(x^t_i)\|^2≤ 32 _1α T. We now consider the different conditions on the step-size and clipping threshold. First, if α=constantα=constant, the above bound evaluates to (in the worst-case with respect to n and 1−λ1-λ) 1nT∑t∈[T]∑i∈[n]‖∇f(xit)‖2=(1(1−λ2)2T). 1nT _t∈[T] _i∈[n]\|∇ f(x^t_i)\|^2=O ( 1(1-λ^2)^2T ). (22) Next, if α=(1−λ2)2/3Δ11/32(λLA)2/3T1/3123α= (1-λ^2)^2/3 _1^1/32(λ LA)^2/3T^1/3 [3]12, then 1nT∑t∈[T]∑i∈[n]‖∇f(xit)‖2=(1(1−λ2)2/3T2/3). 1nT _t∈[T] _i∈[n]\|∇ f(x^t_i)\|^2=O ( 1(1-λ^2)^2/3T^2/3 ). (23) Third, if α=C1n2p−13p−2T1−p3p−2γ−1α=C_1n 2p-13p-2T 1-p3p-2γ^-1, then 1nT∑t∈[T]∑i∈[n]‖∇f(xit)‖2=~(max1(1−λ)np6p−4T2p−13p−2,1(nT)2(p−1)3p−2). 1nT _t∈[T] _i∈[n]\|∇ f(x^t_i)\|^2= O ( \ 1(1-λ)n p6p-4T 2p-13p-2, 1(nT) 2(p-1)3p-2 \ ). (24) Fourth, if α=C2np3(3p−2)T2(1−p)3(3p−2)γ−2/3α=C_2n p3(3p-2)T 2(1-p)3(3p-2)γ^-2/3, then 1nT∑t∈[T]∑i∈[n]‖∇f(xit)‖2=~(maxn2(p−1)3(3p−2)(1−λ)43T7p−43(3p−2),n2−p3(3p−2)(1−λ2)23T7p−63(3p−2)). 1nT _t∈[T] _i∈[n]\|∇ f(x^t_i)\|^2= O ( \ n 2(p-1)3(3p-2)(1-λ) 43T 7p-43(3p-2), n 2-p3(3p-2)(1-λ^2) 23T 7p-63(3p-2) \ ). (25) Finally, the only remaining case is that of α=C3γ−1α=C_3γ^-1, where we get 1nT∑t∈[T]∑i∈[n]‖∇f(xit)‖2=~(maxn(1−λ)T,n13p−2T3(p−1)3p−2). 1nT _t∈[T] _i∈[n]\|∇ f(x^t_i)\|^2= O ( \ n(1-λ)T, n 13p-2T 3(p-1)3p-2 \ ). (26) The proof is completed by combining (22)-(26). ∎ B.3 In-Expectation Results To prove the Theorem 2, we build on the HP convergence result using the fact that clipped methods generate sequences with bounded increments, an idea previously used in, e.g., (Armacki et al., 2026d; Chezhegov et al., 2026). Let ∇1≔‖∇f(x¯1)‖2 _1 \|∇ f( x^1)\|^2. We then have the following result. Theorem 2. Let Assumptions 1-5 hold. If for any T≥2T≥ 2, the clipping threshold and the step-size are chosen as γ=max2A+4BLΔ1+2λLn1−λ,(nT)13p−2γ= \2A+4B L _1+ 2λ L n1-λ,(nT) 13p-2 \ and α=min12L,1−λ28λLB3,1−λ2λL6,(1−λ2)26λ2L,(1−λ2)2/3Δ11/32(λLA)2/3T1/3123,C1γn2p−13p−2T1−p3p−2,C2γ2/3np3(3p−2)T2(1−p)3(3p−2),C3γα= \ 12L, 1-λ^28λ LB 3, 1-λ^2λ L 6, (1-λ^2)^26λ^2L, (1-λ^2)^2/3 _1^1/32(λ LA)^2/3T^1/3 [3]12, C_1γn 2p-13p-2T 1-p3p-2, C_2γ^2/3n p3(3p-2)T 2(1-p)3(3p-2), C_3γ \, where C1=minΔ164σ2p,Δ1192log(6n4T5)σp/22LC_1= \ _164σ^2p, _1192 (6n^4T^5)σ^p/2 2L \, C2=Δ11/3(1−λ2)2/312σp/3λ2/3L2/3C_2= _1^1/3(1-λ^2)^2/312σ^p/3λ^2/3L^2/3 and C3=min1,3Δ164log(6n4T5)2LC_3= \1, 3 _164 (6n^4T^5) 2L \, then 1nT∑t∈[T]∑i∈[n]∥∇f(xit)∥2=~(max(nT)2(1−p)3p−2,n13p−2T3(p−1)3p−2,n−p6p−4T1−2p3p−2(1−λ), 1nT _t∈[T] _i∈[n]E\|∇ f(x^t_i)\|^2= O ( \(nT) 2(1-p)3p-2, n 13p-2T 3(p-1)3p-2, n -p6p-4T 1-2p3p-2(1-λ), n2(p−1)3(3p−2)(1−λ)43T7p−43(3p−2),n2−p3(3p−2)(1−λ2)23T7p−63(3p−2),T−2/3(1−λ2)2/3,T−1(1−λ2)2,nT−11−λ). n 2(p-1)3(3p-2)(1-λ) 43T 7p-43(3p-2), n 2-p3(3p-2)(1-λ^2) 23T 7p-63(3p-2), T^-2/3(1-λ^2)^2/3, T^-1(1-λ^2)^2, nT^-11-λ \ ). Proof. For any T≥2T≥ 2 and δ∈(0,1)δ∈(0,1), denote by GδT≔1nT∑t∈[T]∑i∈[n]‖∇f(xit(δ))‖2G^T_δ 1nT _t∈[T] _i∈[n]\|∇ f(x^t_i(δ))\|^2 and let MδT=~(max(nT)2(1−p)3p−2,n13p−2T3(p−1)3p−2,n−p6p−4T1−2p3p−2(1−λ),n2(p−1)3(3p−2)(1−λ)43T7p−43(3p−2),n2−p3(3p−2)(1−λ2)23T7p−63(3p−2),T−2/3(1−λ2)2/3,T−1(1−λ2)2,nT−11−λ)M^T_δ= O ( \(nT) 2(1-p)3p-2, n 13p-2T 3(p-1)3p-2, n -p6p-4T 1-2p3p-2(1-λ), n 2(p-1)3(3p-2)(1-λ) 43T 7p-43(3p-2), n 2-p3(3p-2)(1-λ^2) 23T 7p-63(3p-2), T^-2/3(1-λ^2)^2/3, T^-1(1-λ^2)^2, nT^-11-λ \ ), noting that, for any δ∈(0,1)δ∈(0,1), we have [GδT] [G^T_δ] =[GδT(GTδ≤MTδ+GTδ>MTδ)]≤(i)[MδTGTδ≤MTδ]+[(GTδ)2][2GTδ>MTδ] =E [G^T_δ (I_\G^T_δ≤ M^T_δ\+I_\G^T_δ>M^T_δ\ ) ] (i)≤E [M^T_δI_\G^T_δ≤ M^T_δ\ ]+ E [ (G^T_δ )^2 ]E [I^2_\G^T_δ>M^T_δ\ ] =MδTℙ(GδT≤MδT)+[(GδT)2]ℙ(GδT>MδT)≤(ii)MδT+δ[(GδT)2], =M^T_δP (G^T_δ≤ M^T_δ )+ E [ (G^T_δ )^2 ]P (G^T_δ>M^T_δ ) (i)≤M^T_δ+ [ (G^T_δ )^2 ], (27) where (i)(i) follows from Hölder’s inequality, while (ii)(i) follows from Theorem 1. We now proceed to bound the term GδTG^T_δ. To that end, first note that for any t≥1t≥ 1, it holds that ‖t−1‖ \|x^t-x^1\| =|(t−1−1−α~t)|≤‖(t−1−1)‖+α‖~t‖ =\|W(x^t-1-x^1-α g^t)\|≤\|W(x^t-1-x^1)\|+α\|W g^t\| ≤‖t−1−1‖+αγn≤…≤αγ(t−1)n≤αγtn, ≤\|x^t-1-x^1\|+αγ n≤…≤αγ(t-1) n≤αγ t n, (28) where the second inequality follows from ‖≤1\|W\|≤ 1 and ‖~t‖≤γn\| g^t\|≤γ n. From the definition of GδTG^T_δ, we then get GδT≤2n∑i∈[n]‖∇f(xi1)‖2+2L2nT∑t∈[T]‖t−1‖2≤2∇1+2α2γ2L2T∑t∈[T]t2≤2∇1+2α2γ2L2T2,G^T_δ≤ 2n _i∈[n]\|∇ f(x_i^1)\|^2+ 2L^2nT _t∈[T]\|x^t-x^1\|^2≤ 2 _1+ 2α^2γ^2L^2T _t∈[T]t^2≤ 2 _1+2α^2γ^2L^2T^2, where the second inequality follows from (28) and the fact that agents have an identical initialization. Plugging this into (27), we get [GδT]≤MδT+2(∇1+α2γ2L2T2)δ1/2≤MδT+2(∇1+C12L2(nT)2(2p−1)3p−2)δ1/2,E [G_δ^T ]≤ M_δ^T+2( _1+α^2γ^2L^2T^2)δ^1/2≤ M_δ^T+2 ( _1+C_1^2L^2(nT) 2(2p-1)3p-2 )δ^1/2, (29) where the second inequality follows from the choice of α and γ. Choosing δ=(nT)−4∈(0,1)δ=(nT)^-4∈(0,1), it follows that [GδT]≤MδT+2∇1n2T2+C12L2(nT)2(p−1)3p−2=~(MδT).E [G^T_δ ]≤ M_δ^T+ 2 _1n^2T^2+ C_1^2L^2(nT) 2(p-1)3p-2= O (M_δ^T ). ∎ Appendix C Experiment Details In this section we provide details of the experimental setup and some additional results, following similar setups as the ones considered in (Yu et al., 2026a). Subsection C.1 details the quadratic example, Subsection C.2 details the robust regression experiments, while Subsection C.3 details the experiment on distributed training of transformers. C.1 Convergence on a Quadratic Cost As mentioned in the main body, Yu et al. (2026a) provide a simple quadratic example for which DSGD with normalization fails to converge, even with noiseless gradients. We verify numerically that the non-convergence is fixed when using gradient clipping with an appropriately chosen clipping radius. In particular, we consider a network with n=20n=20 agents communicating over a fully connected graph. Each agent has access to a local quadratic cost fi(x)=12(x−ai)2f_i(x)= 12(x-a_i)^2, where ai=0a_i=0 for agents i∈[10]i∈[10], while ai=10a_i=10 for the rest. As such, it can be readily verified that Assumption 4 is satisfied, e.g., with A=52A=5 2 and B=2B= 2.66 6 It can be shown that Assumption 4 is satisfied for any A,BA,B such that B>1B>1 and A2≥25B2B2−1A^2≥ 25B^2B^2-1. All agents are initialized at xi1=0.5x_i^1=0.5, while the global cost is minimized at x⋆=5x =5. We compare vanilla DSGD with normalized (DSGD-N) and clipped DSGD (DSGD-Clip), with all three methods having access to noiseless gradients and using the constant step-size α=0.5α=0.5, and clipped DSGD using the clipping radius γ=6γ=6. Convergence of all three methods is presented in Figure 1 in the main body, while in Figure 4 we additionally show the magnitude of the effective gradient, i.e., |1n∑i=1ng~it|, | 1n _i=1^n g_i^t |, where g~it g_i^t denotes the vanilla, normalized or clipped gradient used in the update. DSGD-N cancels out the effective gradient (Figure 4, right) and remains stuck at initialization, while DSGD-Clip preserves an effective direction, even when clipping is active in the first few iterations, gradually converging to the optimum. Figure 4: Convergence of vanilla, normalized and clipped DSGD on a quadratic example. C.2 Decentralized Linear Regression Agents have access to a local dataset (Ai,k,bi,k)k=1Ni\(A_i,k,b_i,k)\_k=1^N_i and the local cost is given by fi(x)=1Ni∑k=1Niℓ(bi,k−⟨Ai,k,x⟩)f_i(x)= 1N_i _k=1^N_i (b_i,k- A_i,k,x ), where ℓ is the Tukey biweight loss, defined as ℓ(r)=c26[1−(1−r2c2)3],|r|≤c,c26,|r|>c. (r)= cases c^26 [1- (1- r^2c^2 )^3 ],&|r|≤ c,\\[4.30554pt] c^26,&|r|>c. cases (30) We choose the constant c=4.6851c=4.6851. We tune every method (i.e., vanilla, normalized, clipped and component-wise clipped DSGD) separately for each noise distribution. All methods choose their step-size α over the grid α∈10−5, 5×10−5, 10−4, 5×10−4, 10−3, 5×10−3, 10−2, 5×10−2, 10−1, 5×10−1, 1, 5, 10.α∈\10^-5,\,5×10^-5,\,10^-4,\,5×10^-4,\,10^-3,\,5×10^-3,\,10^-2,\,5×10^-2,\,10^-1,\,5×10^-1,\,1,\,5,\,10\. For DSGD-Clip and DSGD-CClip, we further chose the clipping radius γ over the grid γ∈10−3, 5×10−3, 10−2, 5×10−2, 10−1, 5×10−1, 1, 5, 10, 20, 50, 100, 500.γ∈\10^-3,\,5×10^-3,\,10^-2,\,5×10^-2,\,10^-1,\,5×10^-1,\,1,\,5,\,10,\,20,\,50,\,100,\,500\. For linear speed-up experiments, we use the best step-size and clipping radius selected in the preceding experiment, and repeat the experiment over 3030 runs with independently sampled graphs and gradient noise in each run. C.3 Decentralized Training of Transformers For each method and dataset, we chose the step-size from the grid α∈10−4,5×10−4,10−3,5×10−3,10−2,5×10−2,0.1,0.5,0.8,1,2,5,10,20,50,100,α∈\10^-4,5× 10^-4,10^-3,5× 10^-3,10^-2,5× 10^-2,0.1,0.5,0.8,1,2,5,10,20,50,100\, while for DSGD-Clip and DSGD-CClip, we additionally chose the clipping radius via a grid search over γ∈10−4,10−3,10−2,0.05,0.1,0.5,1,5,10,100,500.γ∈\10^-4,10^-3,10^-2,0.05,0.1,0.5,1,5,10,100,500\. The best hyperparameter combination is selected based on the final validation loss, measured as log-perplexity. We then run each method independently five times and report the average validation performance. Figure 5 shows the full learning curves corresponding to the results in Table 2 in the main body. We can see that DSGD-CClip consistently achieves the lowest validation loss on both datasets, while DSGD-N and DSGD-Clip perform similarly and substantially improve over vanilla DSGD. Figure 5: Validation loss versus training epoch for decentralized transformer training. Left: “Multi30k”; right: “Tiny Shakespeare” dataset. Appendix D On the Heterogeneity Condition As discussed in the main body, even the vanilla DSGD method requires a heterogeneity condition to ensure convergence under non-convex costs. Assumption 4 was previously used for vanilla DSGD in works including (Vlaski and Sayed, 2021b; Vlaski and Sayed, 2021a; Armacki and Sayed, 2026). However, convergence of vanilla DSGD has been shown under a slightly weaker notion of heterogeneity, namely the average heterogeneity, i.e., 1n∑i∈[n]‖∇fi(x)‖2≤A2+B2‖∇f(x)‖2, 1n _i∈[n]\|∇ f_i(x)\|^2≤ A^2+B^2\|∇ f(x)\|^2, (31) see, e.g., (Lian et al., 2017; Koloskova et al., 2020). In our work, control of gradients of each agent is needed to show that gradients of agents fall below the clipping threshold with high probability. This is achieved by using the heterogeneity condition in Assumption 4 and controlling the global gradient and the consensus gap, i.e., through the bound ‖∇fi(xit)‖≤L‖xit−x¯t‖+‖∇fi(x¯t)‖≤L‖xit−x¯t‖+A+B‖∇f(x¯t)‖.\|∇ f_i(x^t_i)\|≤ L\|x^t_i- x^t\|+\|∇ f_i( x^t)\|≤ L\|x^t_i- x^t\|+A+B\|∇ f( x^t)\|. While it is possible to incorporate the averaged heterogeneity condition in our work through the bound maxi∈[n]‖∇fi(x)‖2≤∑i∈[n]‖∇fi(x)‖2≤(31)nA2+nB2‖∇f(x)‖2, _i∈[n]\|∇ f_i(x)\|^2≤ _i∈[n]\|∇ f_i(x)\|^2 eq:avg-het≤nA^2+nB^2\|∇ f(x)\|^2, we note that it incurs a factor of n n in both A and B compared to Assumption 4, due to the loose bound in the first inequality. Seeing that both A and B in our results appear as conditions on the step-size, this loose bound would not result in the loss of linear speed-up and would only affect the transient time needed to achieve the global network independent rate ~((nT)2(1−p)3p−2) O ((nT) 2(1-p)3p-2 ), resulting in slightly larger transient time. Appendix E On the Transient Time In this section we provide details on the transient time resulting from our bounds. Noting that the bounds in Theorems 1 and 2 are already worst-case with respect to n and 1−λ1-λ, we can directly inspect the bound, which is given by ~(max(nT)2(1−p)3p−2,n13p−2T3(p−1)3p−2,n−p6p−4T1−2p3p−2(1−λ),n2(p−1)3(3p−2)(1−λ)43T7p−43(3p−2), O ( \(nT) 2(1-p)3p-2, n 13p-2T 3(p-1)3p-2, n -p6p-4T 1-2p3p-2(1-λ), n 2(p-1)3(3p-2)(1-λ) 43T 7p-43(3p-2), n2−p3(3p−2)(1−λ2)23T7p−63(3p−2),T−2/3(1−λ2)2/3,T−1(1−λ2)2,nT−11−λ). n 2-p3(3p-2)(1-λ^2) 23T 7p-63(3p-2), T^-2/3(1-λ^2)^2/3, T^-1(1-λ^2)^2, nT^-11-λ \ ). (32) Since our goal is to find the smallest T such that the bound in (32) becomes ~((nT)2(1−p)3p−2) O ((nT) 2(1-p)3p-2 ), it can be readily verified that this is the case for T=~(maxCLOSE T= O ( n2p−1p−1,n3p−42(1−λ)3p−2,n8(p−1)2+p(1−λ)4(3p−2)2+p, \n 2p-1p-1, n 3p-42(1-λ)^3p-2, n 8(p-1)2+p(1-λ) 4(3p-2)2+p, n5p−4p(1−λ)2(3p−2)p,n3(p−1)(1−λ)3p−2,n2(p−1)p(1−λ)2(3p−2)p,n7p−62p(1−λ)3p−2p). n 5p-4p(1-λ) 2(3p-2)p, n^3(p-1)(1-λ)^3p-2, n 2(p-1)p(1-λ) 2(3p-2)p, n 7p-62p(1-λ) 3p-2p \ ). (33) We note two things. First, as p→1p→ 1, the term n2p−1p−1n 2p-1p-1 dominates and the transient time becomes independent of network connectivity, only depending on the number of agents. Second, in the special case when p=2p=2, the transient time in (33) evaluates to ~(n3(1−λ)4) O ( n^3(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).