mlsanityData to 7 Oct 2026

Taming Fat-Tailed ("Heavier-Tailed'' with Potentially Infinite Variance) Noise in Federated Learning

arXiv 2210.00690 ↗First posted 3 Oct 2022cs.LG cs.AI cs.DCcited by 10

Not on the map. Why?

Abstract (arXiv)

A key assumption in most existing works on FL algorithms' convergence analysis is that the noise in stochastic first-order information has a finite variance. Although this assumption covers all light-tailed (i.e., sub-exponential) and some heavy-tailed noise distributions (e.g., log-normal, Weibull, and some Pareto distributions), it fails for many fat-tailed noise distributions (i.e., ``heavier-tailed'' with potentially infinite variance) that have been empirically observed in the FL literature. To date, it remains unclear whether one can design convergent algorithms for FL systems that experience fat-tailed noise. This motivates us to fill this gap in this paper by proposing an algorithmic framework called FAT-Clipping (ulfederated ulaveraging with ultwo-sided learning rates and ulclipping), which contains two variants: FAT-Clipping per-round (FAT-Clipping-PR) and FAT-Clipping per-iteration (FAT-Clipping-PI). Specifically, for the largest α ∈ (1,2] such that the fat-tailed noise in FL still has a bounded α-moment, we show that both variants achieve O((mT)^frac2-αα) and O((mT)^frac1-α3α-2) convergence rates in the strongly-convex and general non-convex settings, respectively, where m and T are the numbers of clients and communication rounds. Moreover, at the expense of more clipping operations compared to FAT-Clipping-PR, FAT-Clipping-PI further enjoys a linear speedup effect with respect to the number of local updates at each client and being lower-bound-matching (i.e., order-optimal). Collectively, our results advance the understanding of designing efficient algorithms for FL systems that exhibit fat-tailed first-order oracle information.

Key facts. Cited by 10 papers in the map (data through 7 Oct 2026). Builds on 32 of its 50 references that are in the map. First posted on arXiv 3 Oct 2022.

Builds on

32 of 50 references.

References · 32

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
  2. 2018Federated Optimization in Heterogeneous Networkscited by 2,971
  3. 2019On the Convergence of FedAvg on Non-IID Datacited by 1,220
  4. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
  5. 2020Adaptive Federated Optimizationcited by 1,036
  6. 2020Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimizationcited by 897
  7. 2013Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programmingcited by 716
  8. 2021Federated Learning Based on Dynamic Regularizationcited by 555
  9. 2019Why gradient clipping accelerates training: A theoretical justification for adaptivitycited by 335
  10. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 303
  11. 2021No Fear of Heterogeneity: Classifier Calibration for Federated Learning with Non-IID Datacited by 241
  12. 2019Differentially Private Learning with Adaptive Clippingcited by 218
20 more
  1. 2019A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networkscited by 213
  2. 2018Don't Use Large Mini-Batches, Use Local SGDcited by 201
  3. 2021Achieving Linear Speedup with Partial Worker Participation in Non-IID Federated Learningcited by 192
  4. 2020Understanding Gradient Clipping in Private SGD: A Geometric Perspectivecited by 140
  5. 2020The Heavy-Tail Phenomenon in SGDcited by 122
  6. 2020Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clippingcited by 104
  7. 2020Improved Analysis of Clipping Algorithms for Non-convex Optimizationcited by 88
  8. 2018Adaptive Communication Strategies to Achieve the Best Error-Runtime Trade-off in Local-Update SGDcited by 76
  9. 2021On Large-Cohort Training for Federated Learningcited by 73
  10. 2021Fast Federated Learning in the Presence of Arbitrary Device Unavailabilitycited by 72
  11. 2021Understanding Clipping for Federated Learning: Convergence and Client-Level Differential Privacycited by 66
  12. 2018Fluctuation-dissipation relations for stochastic gradient descentcited by 47
  13. 2019First Exit Time Analysis of Stochastic Gradient Descent Under Heavy-Tailed Gradient Noisecited by 43
  14. 2021STEM: A Stochastic Two-Sided Momentum Algorithm Achieving Near-Optimal Sample and Communication Complexities for Federated Learningcited by 43
  15. 2021Anarchic Federated Learningcited by 42
  16. 2021Convergence Rates of Stochastic Gradient Descent under Infinite Noise Variancecited by 34
  17. 2020Fractional Underdamped Langevin Dynamics: Retargeting SGD with Momentum under Heavy-Tailed Gradient Noisecited by 33
  18. 2019Non-Gaussianity of Stochastic Gradient Noisecited by 22
  19. 2020Dynamic of Stochastic Gradient Descent with State-Dependent Noisecited by 12
  20. 2022NET-FLEET: Achieving Linear Convergence Speedup for Fully Decentralized Federated Learning with Heterogeneous Datacited by 12

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 1; 2024: 4; 2025: 4; 2026: 1.

10 papers.

  1. 2023Federated Multi-Objective Learningcited by 11
  2. 2025Efficient Distributed Optimization under Heavy-Tailed Noisecited by 7
  3. 2024Version age-based client scheduling policy for federated learningcited by 5
  4. 2025Unbiased and Sign Compression in Distributed Learning: Comparing Noise Resilience via SDEscited by 4
  5. 2024Robust Federated Learning Over the Air: Combating Heavy-Tailed Noise with Median Anchored Clippingcited by 3
  6. 2024Sketched Adaptive Federated Deep Learning: A Sharp Convergence Analysiscited by 1
  7. 2024Lion Cub: Minimizing Communication Overhead in Distributed Lioncited by 1
  8. 2025Federated Stochastic Minimax Optimization under Heavy-Tailed Noisescited by 1
  9. 2025Nonconvex Decentralized Stochastic Bilevel Optimization under Heavy-Tailed Noisecited by 0
  10. 2026Federated learning with heavy-tailed gradient noise and communication noise: a variance-reduction based algorithmcited by 0