PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Aleksandar Armacki, Haoyuan Cai, Ali H. Sayed

arXiv:2610.10527v1math.OCcs.LGcs.MA

TL;DR

Heavy-tailed noise is well studied centrally, but convergence and nonlinear methods remain less understood in decentralized optimization. The paper analyzes baseline DSGD with gradient clipping and establishes optimal oracle complexity and linear speed-up under standard assumptions.

  • Problem

    Although heavy-tailed noise and nonlinear remedies are studied centrally, their convergence behavior remains incompletely understood in decentralized settings.

    Source: §1 · pp. 1–2

  • Method

    The paper studies baseline decentralized SGD with gradient clipping, without additional algorithmic modifications.

    Source: §1.2 · p. 4

  • Results

    Clipped DSGD achieves optimal oracle complexity and linear speed-up under standard assumptions.

    Source: §1.2 · p. 4

  • Takeaways & Limitations

    The results indicate that an appropriately chosen nonlinearity can let a simple decentralized method achieve optimal complexity, with clipping and normalization having distinct effects.

    Source: §1.2 · p. 4

    The guarantees assume unbiased stochastic gradient estimates and network weights induced by undirected graphs or a class of strongly connected digraphs with doubly stochastic weights.

    Source: §2.1 · p. 5, §3.1 · p. 6

Abstract

from arXiv · show

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.

1 Introduction

Distributed training lets agents process local data while exchanging model or gradient parameters; decentralized training has become particularly relevant as heavy-tailed noise and nonlinear gradient methods raise unresolved convergence questions. The paper answers those questions with clipped DSGD, reporting optimal oracle complexity and linear speed-up without additional algorithmic modifications.

1 Introduction

  • Distributed training has agents jointly train while storing and processing data locally and exchanging model or gradient parameters; decentralized agents communicate with one another rather than a central server.The paper focuses on the more general decentralized setup, noting that client-server training is mathematically equivalent over a fully connected network.Source: §1 · p. 1

1.1 Related Literature

  • Prior decentralized nonlinear-method results require strong heterogeneity bounds or modifications such as local momentum, mini-batches, or accelerated gossip; normalized DSGD can fail even on a simple quadratic.The paper asks whether a standard decentralized method with a nonlinear map can achieve optimal complexity under heavy-tailed noise without further algorithmic modification.Source: §1.1 · p. 3
  • Clipping fixes the non-convergence induced by normalization in the illustrated quadratic example, and the paper presents clipped DSGD as a positive answer to the optimal-complexity question.Table 1 compares decentralized nonlinear methods by algorithm, nonlinearity, noise moment, guarantee type, per-agent oracle complexity, and linear speed-up.Source: Table 1 · p. 2, §1.1 · pp. 3–4

1.2 Contributions

  • Baseline DSGD with gradient clipping achieves optimal oracle complexity and linear speed-up under standard assumptions, without additional algorithmic modifications.The authors also report experiments on decentralized transformer training, finding that clipping improves performance under heavy tails and clipped DSGD performs on par with or better than normalized DSGD.Source: §1.2 · p. 4
  • A sharp consensus analysis and a coupling of step-size with clipping radius relegate network effects to higher-order terms and help relax prior strong heterogeneity bounds.The analysis also uses the result that averaging clipped vectors reduces variance.Source: §1.2 · p. 4

2 Preliminaries

The paper formulates a decentralized optimization problem in which agents minimize a shared cost over a communication network. It then introduces clipped DSGD, where agents clip local stochastic gradients before updating their models through local communication.

2.1 Problem Setup

  • Agents seek to minimize a shared objective whose global cost is composed of their local costs.The network is modeled as a connected graph that induces a communication weight matrix.Source: §2.1 · p. 5
  • Each agent queries a stochastic first-order oracle for an unbiased estimate of its local gradient.The oracle model covers both offline batch and online streaming learning.Source: §2.1 · p. 5

2.2 Proposed Method

  • Clipped DSGD clips each agent’s local stochastic gradient before updating its local model.Agents choose a fixed step size, clipping radius, and initial models before iterations begin.Source: §2.2 · p. 5
  • Agents combine information from themselves and their communicating neighbors using the adapt-then-combine diffusion approach.This variant differs from the combine-then-adapt approach used by Yang et al. (2025).Source: §2.2 · p. 5

3 Main Results

Under smooth non-convex costs, a bounded p-th moment noise condition, and decentralized network assumptions, clipped DSGD achieves high-probability and in-expectation guarantees. Its leading rate matches centralized optimal rates, with linear speed-up and network effects confined to higher-order terms.

3.1 Assumptions

  • The guarantees assume costs bounded below with L-Lipschitz gradients, a gradient heterogeneity bound, and independent samples with conditionally zero-mean noise whose p-th moment is bounded for p ∈ (1, 2].Source: §3.1 · pp. 6–7

3.2 Theoretical Guarantees

  • The clipped-DSGD analysis combines a descent inequality with consensus-gap bounds to establish its high-probability and in-expectation convergence results.The descent inequality includes a consensus-gap term absent from standard centralized clipping analysis.Source: §3.2 · pp. 8–9
  • A refined consensus-gap bound captures heterogeneity, network connectivity, and local clipping, avoiding the leading-order network penalty of the initial deterministic bound.The initial bound alone would propagate network effects to the leading term and lose linear speed-up.Source: §3.2 · p. 8
  • The high-probability and in-expectation bounds have a leading term matching the optimal centralized rate, with linear speed-up in agents and no network dependence in that term.The network spectral gap affects only higher-order terms.Source: §3.2 · pp. 8–9
  • The clipping radius grows with heterogeneity and poorer network connectivity, while a decentralized step-size term scaling as γ^-2/3 is used to optimize network dependence and transient time.The γ^-2/3 term is novel to this decentralized setting.Source: §3.2 · p. 9
  • Compared with prior decentralized methods, clipped DSGD provides both high-probability and in-expectation results using one stochastic gradient evaluation and one communication round per iteration.The comparison also notes that the algorithm retains a heterogeneity condition.Source: §3.2 · p. 10
  • Clipping preserves gradient direction and leaves gradients unchanged below its threshold, whereas normalization always modifies direction and biases the network-averaged gradient.The paper links this distinction to clipped DSGD’s optimal complexity and linear speed-up without gradient tracking, accelerated gossip, or local momentum or mini-batches.Source: §3.2 · p. 10

4 Numerical Results

The experiments compare decentralized methods under heavy-tailed noise in synthetic regression and test nonlinear variants on transformer training with real data. Clipped DSGD accelerates with network size, while nonlinear methods improve over vanilla DSGD in the reported settings.

Linear Regression on Synthetic Data

  • Under Student’s t and Lévy α-stable noise, nonlinear methods stabilize and accelerate convergence, with DSGD-Clip and DSGD-CClip performing on par with or better than DSGD-N.The synthetic regression experiment uses a 20-agent ring network and evaluates average estimation error over 30 independent runs.Source: §4 · p. 11
  • DSGD-Clip consistently converges faster as network size increases from 10 to 50 agents, confirming linear speed-up under both tested heavy-tailed noise types.The experiments hold the network spectral parameter fixed across network sizes.Source: §4 · p. 11, Figure 3 · p. 11

Transformer Training on Real Data

  • DSGD-CClip achieves the lowest validation loss on both real-data transformer datasets, while DSGD-Clip and DSGD-N perform similarly and all three improve over vanilla DSGD.Table 2 reports validation loss after 20 epochs, averaged over five runs.Source: §4 · p. 12, Table 2 · p. 12

5 Conclusion

The paper concludes that baseline clipped DSGD achieves order-optimal convergence rates and linear speed-up under heavy-tailed noise. It identifies open questions about nonlinearities and design choices in decentralized optimization.

5 Conclusion

  • Baseline DSGD with clipping achieves order-optimal convergence rates and linear speed-up for smooth non-convex costs.The paper frames this result as an affirmative answer to whether a decentralized baseline with a local nonlinear gradient transformation can attain optimal rates under heavy-tailed noise without mini-batches or accelerated gossip.Source: §5 · p. 12
  • Open questions include whether nonlinearities can be ranked across decentralized regimes and whether gradient tracking with clipping can remove bounded heterogeneity while retaining optimal rates.The paper also asks whether clipping should be applied to local gradients or the tracker variable.Source: §5 · p. 12

Supplement

The supplement collects omitted proofs and experimental material, with its first literature subsection surveying centralized and decentralized convergence results. That survey places the paper among work on optimal rates and nonlinear methods under heavy-tailed noise.

Supplement

A Additional Literature

  • Centralized results establish optimal high-probability convergence rates for SGD on convex costs with light-tailed stochastic gradients, and show optimal high-probability rates are achievable for convex costs using median-of-means gradients.Gorbunov et al. (2020) propose an accelerated method with gradient clipping for smooth convex costs.Source: A Additional Literature · pp. 20–21
  • Decentralized work covers DSGD rates and linear speed-up, while only a few cited studies address nonlinear methods under heavy-tailed noise.The survey includes clipping for convex costs (Qin et al. (2025); Yang et al. (2026)) and smooth clipping for strongly convex costs under symmetric heavy-tailed noise (Yu et al. (2026a)).Source: A Additional Literature · p. 21

B Missing Proofs

This section identifies where the supplement’s omitted technical results and proofs are organized.

B Missing Proofs

  • Subsection B.1 gives general results, B.2 proves high-probability results, and B.3 proves in-expectation results.The section contains technical material omitted from the main body.Source: B Missing Proofs · p. 21

B.1 General Results

The general-results subsection develops bounds used in the convergence analysis, with particular attention to controlling the consensus gap. It explains why a refined gap bound is needed to avoid losing linear speed-up.

B.1 General Results

  • The proof introduces stacked notation for agents’ local models and gradients to express the network-level quantities used in subsequent bounds.It defines stacked vectors and Kronecker-product forms for the network matrices.Source: §B.1 · pp. 22–23
  • Using Lemma 3’s consensus-gap bound alone would introduce a term that grows with the number of agents, destroying linear speed-up and moving network dependence into the leading term.The resulting network factor includes (1−λ)^−2.Source: §B.1 · p. 24
  • Lemma 4’s refined consensus-gap bound decays faster than the leading term and is crucial to the improved rates.Its step-size still couples to the clipping radius, but at a strictly faster-decaying rate.Source: §B.1 · p. 24

B.2 High-Probability Results

The high-probability analysis constructs an event on which local gradients remain controlled, then uses descent and martingale bounds to establish the theorem. The full theorem statement includes higher-order terms omitted from the main text.

B.2 High-Probability Results

  • The analysis requires a high-probability event controlling each agent’s local gradient, a stronger condition than the centralized event described.The proof uses the heterogeneity bound and Lemma 3 to show that this condition holds with high probability.Source: §B.2 · p. 24
  • Lemma 8 combines network-averaged clipped quantities with strictly local quantities in a descent inequality used to construct the event.The proof then applies a martingale argument, including Freedman’s inequality.Source: §B.2 · pp. 24, 26
  • The supplement states the full version of Theorem 1, including higher-order terms omitted from the main-body statement.The supplied theorem passage gives its assumptions and threshold/step-size setup, but not the complete displayed bound.Source: §B.2 · p. 30

B.3 In-Expectation Results

The in-expectation analysis builds on the high-probability result by using bounded increments from clipping, then bounds terms involving the clipped gradients. The appendix also identifies the experimental-detail subsections covered later.

B.3 In-Expectation Results

  • The proof builds on the high-probability result by using the bounded increments generated by clipped methods.It then bounds terms involving clipped gradients and the consensus gap.Source: §B.3 · p. 32
  • The proof uses the clipped-gradient bound ∥e_t∥ ≤ γ√n when bounding a term in the expectation analysis.Source: §B.3 · p. 33
  • The analysis sets δ = (nT)^-4 before deriving the stated bound.Source: §B.3 · p. 33

C Experiment Details

  • The experiment-details section covers a quadratic example, robust regression, and decentralized transformer training.Source: C Experiment Details · p. 33

C.1 Convergence on a Quadratic Cost

On a noiseless quadratic example, normalized DSGD remains at its initialization, whereas clipped DSGD preserves an effective direction and converges to the optimum. The accompanying regression experiments tune methods for each noise distribution and repeat speed-up tests across independent runs.

C.1 Convergence on a Quadratic Cost

  • The quadratic example uses 20 agents on a fully connected graph, with local optima split between 0 and 10 and a global optimum of 5.Source: §C.1 · p. 33
  • DSGD-N cancels its effective gradient and stays at initialization, while DSGD-Clip preserves an effective direction and converges to the optimum.The comparison uses noiseless gradients; clipped DSGD has clipping radius γ = 6.Source: §C.1 · p. 33

C.2 Decentralized Linear Regression

  • The regression experiments tune vanilla, normalized, clipped, and component-wise clipped DSGD separately for each noise distribution.Source: §C.2 · p. 34
  • Linear speed-up experiments reuse the selected step-size and clipping radius and run 30 trials with independently sampled graphs and gradient noise.Source: §C.2 · p. 34

C.3 Decentralized Training of Transformers

In decentralized transformer training, component-wise clipped DSGD achieves the lowest validation loss on both datasets, while clipped and normalized DSGD perform similarly and improve over vanilla DSGD. The appendices discuss heterogeneity-condition trade-offs and transient-time behavior.

C.3 Decentralized Training of Transformers

  • The best hyperparameters are selected by final validation loss, measured as log-perplexity, and reported performance averages five independent runs.Source: §C.3 · p. 34
  • DSGD-CClip achieves the lowest validation loss on both datasets; DSGD-N and DSGD-Clip perform similarly and substantially improve over vanilla DSGD.Figure 5 shows the learning curves for Multi30k and Tiny Shakespeare.Source: §C.3 · p. 35, Figure 5 · p. 35

D On the Heterogeneity Condition

  • Using average heterogeneity would add a √n factor to both A and B, affecting transient time but not linear speed-up.The text attributes the factor to a loose bound and says it would not affect the global network-independent rate.Source: D On the Heterogeneity Condition · p. 35

E On the Transient Time

  • When the stated exponent dominates, transient time becomes independent of network connectivity and depends only on the number of agents.For p = 2, it matches the transient time of vanilla DSGD under bounded-variance or sub-Gaussian noise.Source: E On the Transient Time · p. 36

Related papers

Loading 2610.10527v1…