Decentralized SGD under Heavy-Tailed Noise: Optimal Convergence Rates and the Role of Gradient Clipping
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], 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.
Related
- Almost Sure Convergence Analysis of Stochastic Gradient Methods with Clipping and Additive Noise
- Convergence of Stochastic Gradient Methods under Heavy-Tailed Noise and Hölder Smoothness
- Optimal Design of Distributed Inexact Gradient Tracking: Exact Worst-case Convergence Rate and Explicit Parameters
- Weak-Lα Noise, Strong Guarantees: Gradient Clipping under Affine Heavy Tails
- Exact Average Consensus under Noisy Communication Links: A Decentralized Gradient Perspective
BibTeX
@misc{armacki2026decentralized,
title = {{Decentralized SGD under Heavy-Tailed Noise: Optimal Convergence Rates and the Role of Gradient Clipping}},
author = {Aleksandar Armacki and Haoyuan Cai and Ali H. Sayed},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.10527},
eprint = {2610.10527},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.10527},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Decentralized SGD under Heavy-Tailed Noise: Optimal Convergence Rates and the Role of Gradient Clipping
AU - Aleksandar Armacki
AU - Haoyuan Cai
AU - Ali H. Sayed
PY - 2026
DA - 2026/10/07
PB - arXiv
DO - 10.48550/arxiv.2610.10527
UR - https://arxiv.org/abs/2610.10527
AB - 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], 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.
ER -