mlsanityData to 7 Oct 2026

Federated Stochastic Minimax Optimization under Heavy-Tailed Noises

arXiv 2511.04456 ↗First posted 6 Nov 2025cs.LGcited by 1

Not on the map. Why?

Abstract (arXiv)

Heavy-tailed noise has attracted growing attention in nonconvex stochastic optimization, as numerous empirical studies suggest it offers a more realistic assumption than standard bounded variance assumption. In this work, we investigate nonconvex-PL minimax optimization under heavy-tailed gradient noise in federated learning. We propose two novel algorithms: Fed-NSGDA-M, which integrates normalized gradients, and FedMuon-DA, which leverages the Muon optimizer for local updates. Both algorithms are designed to effectively address heavy-tailed noise in federated minimax optimization, under a milder condition. We theoretically establish that both algorithms achieve a convergence rate of O(1/(TNp)^fracs-12s). To the best of our knowledge, these are the first federated minimax optimization algorithms with rigorous theoretical guarantees under heavy-tailed noise. Extensive experiments further validate their effectiveness.

Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 39 of its 52 references that are in the map. First posted on arXiv 6 Nov 2025.

Builds on

39 of 52 references.

References · 39

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
  2. 2015Character-level Convolutional Networks for Text Classificationcited by 2,293
  3. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 526
  4. 2025Muon is Scalable for LLM Trainingcited by 381
  5. 2019Why gradient clipping accelerates training: A theoretical justification for adaptivitycited by 335
  6. 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 302
  7. 2019A Tail-Index Analysis of Stochastic Gradient Noise in Deep Neural Networkscited by 213
  8. 2024Old Optimizer, New Norm: An Anthologycited by 173
  9. 2019Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methodscited by 148
  10. 2020The Heavy-Tail Phenomenon in SGDcited by 122
  11. 2020Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clippingcited by 104
  12. 2021Distributionally Robust Federated Averagingcited by 104
27 more
  1. 2020Robust Federated Learning: The Case of Affine Distribution Shiftscited by 102
  2. 2023Linear attention is (maybe) all you need (to understand transformer optimization)cited by 97
  3. 2020FedGAN: Federated Generative Adversarial Networks for Distributed Datacited by 89
  4. 2025Understanding Gradient Orthogonalization for Deep Learning via Non-Euclidean Trust-Region Optimizationcited by 81
  5. 2021High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tailscited by 80
  6. 2024Heavy-Tailed Class Imbalance and Why Adam Outperforms Gradient Descent on Language Modelscited by 78
  7. 2025A Note on the Convergence of Muoncited by 78
  8. 2025Practical Efficiency of Muon for Pretrainingcited by 74
  9. 2021On Large-Cohort Training for Federated Learningcited by 73
  10. 2019Stochastic AUC Maximization with Deep Neural Networkscited by 61
  11. 2025ASGO: Adaptive Structured Gradient Optimizationcited by 55
  12. 2024From Gradient Clipping to Normalization for Heavy Tailed SGDcited by 48
  13. 2021Faster Single-loop Algorithms for Minimax Optimization without Strong Concavitycited by 47
  14. 2021Heavy Tails in SGD and Compressibility of Overparametrized Neural Networkscited by 44
  15. 2024Nonconvex Stochastic Optimization under Heavy-Tailed Noises: Optimal Convergence without Gradient Clippingcited by 42
  16. 2021Local Stochastic Gradient Descent Ascent: Convergence Analysis and Communication Efficiencycited by 40
  17. 2025Lions and Muons: Optimization via Stochastic Frank-Wolfe under Heavy-Tailed Noisecited by 38
  18. 2022Federated Minimax Optimization: Improved Convergence Analyses and Algorithmscited by 37
  19. 2023Revisiting the Noise Model of Stochastic Gradient Descentcited by 35
  20. 2020Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networkscited by 27
  21. 2023Breaking the Lower Bound with (Little) Structure: Acceleration in Non-Convex Stochastic Optimization with Heavy-Tailed Noisecited by 27
  22. 2024Revisiting Gradient Normalization and Clipping for Nonconvex SGD under Heavy-Tailed Noise: Necessity, Sufficiency, and Accelerationcited by 18
  23. 2020Distributed Saddle-Point Problems: Lower Bounds, Near-Optimal and Robust Algorithmscited by 14
  24. 2022Taming Fat-Tailed ("Heavier-Tailed'' with Potentially Infinite Variance) Noise in Federated Learningcited by 10
  25. 2023Solving a Class of Non-Convex Minimax Optimization in Federated Learningcited by 10
  26. 2025Efficient Distributed Optimization under Heavy-Tailed Noisecited by 7
  27. 2023Stochastic Smoothed Gradient Descent Ascent for Federated Minimax Optimizationcited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Optimal Asynchronous Stochastic Nonconvex Optimization under Heavy-Tailed Noisecited by 2