# Efficient Distributed Optimization under Heavy-Tailed Noise

arXiv: https://arxiv.org/abs/2502.04164 · HTML: https://mlsanity.com/paper/2502.04164/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 58 of its 77 references that are in the map.
- First posted on arXiv 6 Feb 2025.

## Builds on (most cited first, 30 of 58)

- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019)
- [RoBERTa: A Robustly Optimized BERT Pretraining Approach](https://mlsanity.com/paper/1907.11692/) (2019)
- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [GLUE: A Multi-Task Benchmark and Analysis Platform for Natural Language Understanding](https://mlsanity.com/paper/1804.07461/) (2018)
- [SQuAD: 100,000+ Questions for Machine Comprehension of Text](https://mlsanity.com/paper/1606.05250/) (2016)
- [Deep contextualized word representations](https://mlsanity.com/paper/1802.05365/) (2018)
- [On the Convergence of FedAvg on Non-IID Data](https://mlsanity.com/paper/1907.02189/) (2019)
- [Adaptive Federated Optimization](https://mlsanity.com/paper/2003.00295/) (2020)
- [LEAF: A Benchmark for Federated Settings](https://mlsanity.com/paper/1812.01097/) (2018)
- [Scaling Vision Transformers to 22 Billion Parameters](https://mlsanity.com/paper/2302.05442/) (2023)
- [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018)
- [Convolutional Sequence to Sequence Learning](https://mlsanity.com/paper/1705.03122/) (2017)
- [A Field Guide to Federated Optimization](https://mlsanity.com/paper/2107.06917/) (2021)
- [MobileLLM: Optimizing Sub-billion Parameter Language Models for On-Device Use Cases](https://mlsanity.com/paper/2402.14905/) (2024)
- [A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networks](https://mlsanity.com/paper/1901.06053/) (2019)
- [Regularizing and Optimizing LSTM Language Models](https://mlsanity.com/paper/1708.02182/) (2017)
- [Understanding Gradient Clipping in Private SGD: A Geometric Perspective](https://mlsanity.com/paper/2006.15429/) (2020)
- [DiLoCo: Distributed Low-Communication Training of Language Models](https://mlsanity.com/paper/2311.08105/) (2023)
- [Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping](https://mlsanity.com/paper/2005.10785/) (2020)
- [Linear attention is (maybe) all you need (to understand transformer optimization)](https://mlsanity.com/paper/2310.01082/) (2023)
- [Improved Analysis of Clipping Algorithms for Non-convex Optimization](https://mlsanity.com/paper/2010.02519/) (2020)
- [Revisiting Gradient Clipping: Stochastic bias and tight convergence guarantees](https://mlsanity.com/paper/2305.01588/) (2023)
- [High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails](https://mlsanity.com/paper/2106.14343/) (2021)
- [Heavy-Tailed Class Imbalance and Why Adam Outperforms Gradient Descent on Language Models](https://mlsanity.com/paper/2402.19449/) (2024)
- [CoCoA: A General Framework for Communication-Efficient Distributed Optimization](https://mlsanity.com/paper/1611.02189/) (2016)
- [High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance](https://mlsanity.com/paper/2302.00999/) (2023)
- [Communication-Efficient Adaptive Federated Learning](https://mlsanity.com/paper/2205.02719/) (2022)
- [Why Warmup the Learning Rate? Underlying Mechanisms and Improvements](https://mlsanity.com/paper/2406.09405/) (2024)
- [First Exit Time Analysis of Stochastic Gradient Descent Under Heavy-Tailed Gradient Noise](https://mlsanity.com/paper/1906.09069/) (2019)

## Built on by (most cited first, 7 of 7)

- [On Provable Benefits of Muon in Federated Learning](https://mlsanity.com/paper/2510.03866/) (2025)
- [DeMuon: A Decentralized Muon for Matrix Optimization over Graphs](https://mlsanity.com/paper/2510.01377/) (2025)
- [Federated Stochastic Minimax Optimization under Heavy-Tailed Noises](https://mlsanity.com/paper/2511.04456/) (2025)
- [Nonconvex Decentralized Stochastic Bilevel Optimization under Heavy-Tailed Noise](https://mlsanity.com/paper/2509.15543/) (2025)
- [A Note on Stability for Orthogonalized Matrix Momentum with Client Sampling](https://mlsanity.com/paper/2606.01720/) (2026)
- [A Vision for Multisensory Intelligence: Sensing, Science, and Synergy](https://mlsanity.com/paper/2601.04563/) (2026)
- [Asynchronous Heavy-Tailed Optimization](https://mlsanity.com/paper/2602.18002/) (2026)

## Abstract (arXiv)

Distributed optimization has become the default training paradigm in modern machine learning due to the growing scale of models and datasets. To mitigate communication overhead, local updates are often applied before global aggregation, resulting in a nested optimization approach with inner and outer steps. However, heavy-tailed stochastic gradient noise remains a significant challenge, particularly in attention-based models, hindering effective training. In this work, we propose TailOPT, an efficient framework designed to address heavy-tailed noise by leveraging adaptive optimization or clipping techniques. We establish convergence guarantees for the TailOPT framework under heavy-tailed noise with potentially unbounded gradient variance and local updates. Among its variants, we highlight a memory and communication efficient instantiation which we call Bi2Clip, which performs coordinate-wise clipping at both the inner and outer optimizers, achieving adaptive-like performance (e.g., Adam) without the cost of maintaining or transmitting additional gradient statistics. Empirically, TailOPT, including Bi2Clip, demonstrates superior performance on several language tasks and models, outperforming state-of-the-art methods.