Clipped Decentralized SGD Achieves Optimal Convergence Rates Under Heavy-Tailed Noise

Forum topic · 小凯 · 2026-10-09

Summary

Heavy-tailed noise is widely observed in modern machine learning, motivating gradient clipping and normalization. While these techniques are well understood in centralized settings, their behavior in decentralized optimization has been less clear, since applying a nonlinearity to local gradients affects both optimization and consensus. Prior work showed that clipping yields suboptimal rates, while normalization requires local momentum or mini-batching to converge. This paper by Armacki, Cai, and Sayed (arXiv:2610.10527) answers affirmatively whether a baseline decentralized method with a nonlinearity can achieve optimal rates under heavy-tailed noise. The authors propose clipped decentralized SGD (DSGD) and prove that, for smooth non-convex costs with noise having bounded p-th moment (p in (1,2]), clipped DSGD achieves order-optimal convergence rates both in expectation and with high probability. They also establish linear speedup with the number of agents, reportedly the first such result for clipped decentralized methods. A key technical contribution is a refined analysis of the consensus gap, placing network effects in higher-order terms. The results highlight that normalized DSGD may fail to converge while clipping preserves magnitude information. Experiments validate the theory.

Paper Overview

Field: Machine Learning Authors: Aleksandar Armacki, Haoyuan Cai, Ali H. Sayed arXiv: 2610.10527

Summary

Heavy-tailed noise has been widely observed in modern machine learning, motivating the use of 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 studied both clipping and normalization under heavy-tailed noise: clipping yielded suboptimal rates, while normalization required 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?

The authors answer affirmatively with clipped decentralized SGD (DSGD). Main contributions:

For smooth non-convex costs with noise having bounded p-th moment (p ∈ (1,2]), clipped DSGD achieves order-optimal rates both with high probability and in expectation.
They establish linear speedup with the number of agents — reportedly the first such result for clipped decentralized methods.
A key technical ingredient is a refined analysis of the consensus gap, exploiting the structure of clipping to push network effects into higher-order terms.
The results highlight an important distinction between clipping and normalization in decentralized settings: normalized DSGD may fail to converge, whereas clipping preserves magnitude information, enabling DSGD to converge with order-optimal rates.

Numerical experiments validate the theory.

--- *Collected automatically on 2026-10-09*

Clipped Decentralized SGD Achieves Optimal Convergence Rates Under Heavy-Tailed Noise

Summary

Paper Overview

Summary

Tags