mlsanityData to 7 Oct 2026

SAGDA: Achieving O(ε-2) Communication Complexity in Federated Min-Max Learning

arXiv 2210.00611 ↗First posted 2 Oct 2022cs.LG cs.AIcited by 0

Not on the map. Why?

Abstract (arXiv)

To lower the communication complexity of federated min-max learning, a natural approach is to utilize the idea of infrequent communications (through multiple local updates) same as in conventional federated learning. However, due to the more complicated inter-outer problem structure in federated min-max learning, theoretical understandings of communication complexity for federated min-max learning with infrequent communications remain very limited in the literature. This is particularly true for settings with non-i.i.d. datasets and partial client participation. To address this challenge, in this paper, we propose a new algorithmic framework called stochastic sampling averaging gradient descent ascent (SAGDA), which i) assembles stochastic gradient estimators from randomly sampled clients as control variates and ii) leverages two learning rates on both server and client sides. We show that SAGDA achieves a linear speedup in terms of both the number of clients and local update steps, which yields an O(ε-2) communication complexity that is orders of magnitude lower than the state of the art. Interestingly, by noting that the standard federated stochastic gradient descent ascent (FSGDA) is in fact a control-variate-free special version of SAGDA, we immediately arrive at an O(ε-2) communication complexity result for FSGDA. Therefore, through the lens of SAGDA, we also advance the current understanding on communication complexity of the standard FSGDA method for federated min-max learning.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 32 of its 49 references that are in the map. First posted on arXiv 2 Oct 2022.

Builds on

32 of 49 references.

References · 32

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
  2. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,326
  3. 2019Advances and Open Problems in Federated Learningcited by 3,021
  4. 2018Federated Optimization in Heterogeneous Networkscited by 2,971
  5. 2018Large Scale GAN Training for High Fidelity Natural Image Synthesiscited by 2,609
  6. 2018Federated Learning with Non-IID Datacited by 1,099
  7. 2018Local SGD Converges Fast and Communicates Littlecited by 595
  8. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 526
  9. 2019Robust and Communication-Efficient Federated Learning from Non-IID Datacited by 415
  10. 2017Certifying Some Distributional Robustness with Principled Adversarial Trainingcited by 333
  11. 2018Parallel Restarted SGD with Faster Convergence and Less Communication: Demystifying Why Model Averaging Works for Deep Learningcited by 277
  12. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 266
20 more
  1. 2018Communication-Efficient On-Device Machine Learning: Federated Distillation and Augmentation under Non-IID Private Datacited by 242
  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. 2019SCAFFOLD: Stochastic Controlled Averaging for Federated Learningcited by 174
  5. 2019Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methodscited by 148
  6. 2019SlowMo: Improving Communication-Efficient Distributed SGD with Slow Momentumcited by 121
  7. 2018Cooperative SGD: A unified Framework for the Design and Analysis of Communication-Efficient SGD Algorithmscited by 106
  8. 2020Robust Federated Learning: The Case of Affine Distribution Shiftscited by 102
  9. 2017On the convergence properties of a K-step averaging stochastic gradient descent algorithm for nonconvex optimizationcited by 91
  10. 2020FedGAN: Federated Generative Adversarial Networks for Distributed Datacited by 89
  11. 2019Generative Models for Effective ML on Private, Decentralized Datasetscited by 85
  12. 2018Weakly-Convex Concave Min-Max Optimization: Provable Algorithms and Applications in Machine Learningcited by 62
  13. 2019Stochastic AUC Maximization with Deep Neural Networkscited by 61
  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. 2021Local Stochastic Gradient Descent Ascent: Convergence Analysis and Communication Efficiencycited by 40
  17. 2022Federated Minimax Optimization: Improved Convergence Analyses and Algorithmscited by 37
  18. 2020Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networkscited by 27
  19. 2021Federated Deep AUC Maximization for Heterogeneous Data with a Constant Communication Complexitycited by 21
  20. 2018LoAdaBoost: loss-based AdaBoost federated machine learning with reduced computational complexity on IID and non-IID intensive care datacited by 9

Built on by

Not cited yet.