mlsanityData to 7 Oct 2026

Federated Minimax Optimization: Improved Convergence Analyses and Algorithms

arXiv 2203.04850 ↗First posted 9 Mar 2022math.OC cs.DC cs.LGcited by 37

Not on the map. Why?

Abstract (arXiv)

In this paper, we consider nonconvex minimax optimization, which is gaining prominence in many modern machine learning applications such as GANs. Large-scale edge-based collection of training data in these applications calls for communication-efficient distributed optimization algorithms, such as those used in federated learning, to process the data. In this paper, we analyze Local stochastic gradient descent ascent (SGDA), the local-update version of the SGDA algorithm. SGDA is the core algorithm used in minimax optimization, but it is not well-understood in a distributed setting. We prove that Local SGDA has textitorder-optimal sample complexity for several classes of nonconvex-concave and nonconvex-nonconcave minimax problems, and also enjoys textitlinear speedup with respect to the number of clients. We provide a novel and tighter analysis, which improves the convergence and communication guarantees in the existing literature. For nonconvex-PL and nonconvex-one-point-concave functions, we improve the existing complexity results for centralized minimax problems. Furthermore, we propose a momentum-based local-update algorithm, which has the same convergence guarantees, but outperforms Local SGDA as demonstrated in our experiments.

Key facts. Cited by 37 papers in the map (data through 7 Oct 2026). Builds on 77 of its 106 references that are in the map. First posted on arXiv 9 Mar 2022.

Builds on

77 of 106 references.

References · 77

  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. 2017Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithmscited by 4,283
  4. 2019Advances and Open Problems in Federated Learningcited by 3,021
  5. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  6. 2017Improved Training of Wasserstein GANscited by 2,223
  7. 2016Optimization Methods for Large-Scale Machine Learningcited by 1,140
  8. 2020Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimizationcited by 897
  9. 2019Towards Federated Learning at Scale: System Designcited by 826
  10. 2018Local SGD Converges Fast and Communicates Littlecited by 595
  11. 2020Federated Learning with Matched Averagingcited by 564
  12. 2016Federated Optimization: Distributed Machine Learning for On-Device Intelligencecited by 558
38 more
  1. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 526
  2. 2019Agnostic Federated Learningcited by 451
  3. 2020A Unified Theory of Decentralized SGD with Changing Topology and Local Updatescited by 361
  4. 2019Lower Bounds for Non-Convex Stochastic Optimizationcited by 303
  5. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 266
  6. 2019Tighter Theory for Local SGD on Identical and Heterogeneous Datacited by 266
  7. 2020Loss landscapes and optimization in over-parameterized non-linear systems and neural networkscited by 231
  8. 2017Training GANs with Optimismcited by 217
  9. 2018Applied Federated Learning: Improving Google Keyboard Query Suggestionscited by 202
  10. 2021Achieving Linear Speedup with Partial Worker Participation in Non-IID Federated Learningcited by 192
  11. 2019On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimizationcited by 178
  12. 2018Stochastic model-based minimization of weakly convex functionscited by 157
  13. 2016Variance-based regularization with convex objectivescited by 153
  14. 2019On the Convergence of Local Descent Methods in Federated Learningcited by 150
  15. 2019Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methodscited by 148
  16. 2017Convergence Analysis of Two-layer Neural Networks with ReLU Activationcited by 137
  17. 2018Optimistic mirror descent in saddle-point problems: Going the extra (gradient) milecited by 132
  18. 2020Near-Optimal Algorithms for Minimax Optimizationcited by 119
  19. 2018An Alternative View: When Does SGD Escape Local Minima?cited by 115
  20. 2021Distributionally Robust Federated Averagingcited by 104
  21. 2020Robust Federated Learning: The Case of Affine Distribution Shiftscited by 102
  22. 2017Stability and Generalization of Learning Algorithms that Converge to Global Optimacited by 100
  23. 2020Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimizationcited by 94
  24. 2017On the convergence properties of a K-step averaging stochastic gradient descent algorithm for nonconvex optimizationcited by 91
  25. 2020The Complexity of Constrained Min-Max Optimizationcited by 81
  26. 2018Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problemscited by 75
  27. 2019Efficient Algorithms for Smooth Minimax Optimizationcited by 75
  28. 2020Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problemscited by 75
  29. 2021Fast Federated Learning in the Presence of Arbitrary Device Unavailabilitycited by 72
  30. 2021Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k2) Rate on Squared Gradient Normcited by 71
  31. 2020Towards Flexible Device Participation in Federated Learningcited by 64
  32. 2018Weakly-Convex Concave Min-Max Optimization: Provable Algorithms and Applications in Machine Learningcited by 62
  33. 2021Fast Extra Gradient Methods for Smooth Structured Nonconvex-Nonconcave Minimax Problemscited by 61
  34. 2016Efficiency of minimizing compositions of convex functions and smooth mapscited by 59
  35. 2020A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for Nonconvex-Concave Min-Max Problemscited by 57
  36. 2020A Unified Single-loop Alternating Gradient Projection Algorithm for Nonconvex-Concave and Convex-Nonconcave Minimax Problemscited by 56
  37. 2019Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applicationscited by 55
  38. 2020The limits of min-max optimization algorithms: convergence to spurious non-critical setscited by 50

50 most cited of 77 All 77 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 6; 2023: 14; 2024: 6; 2025: 7; 2026: 4.

37 papers.

Sort:

By area:

  1. 2023Federated Learning for Generalization, Robustness, Fairness: A Survey and Benchmarkcited by 97
  2. 2023Recent Advances on Federated Learning: A Systematic Surveycited by 40
  3. 2023Certified Minimax Unlearning with Generalization Rates and Deletion Capacitycited by 29
  4. 2023Federated Multi-Objective Learningcited by 11
  5. 2022Communication-Efficient Distributionally Robust Decentralized Learningcited by 10
  6. 2022FeDXL: Provable Federated Learning for Deep X-Risk Optimizationcited by 10
  7. 2023Solving a Class of Non-Convex Minimax Optimization in Federated Learningcited by 10
  8. 2022A Communication-efficient Algorithm with Linear Convergence for Federated Minimax Learningcited by 9
  9. 2023Randomized Block-Coordinate Optimistic Gradient Algorithms for Root-Finding Problemscited by 9
  10. 2023Federated Minimax Optimization with Client Heterogeneitycited by 8
  11. 2023Federated Compositional Deep AUC Maximizationcited by 8
  12. 2024Robust Decentralized Learning with Local Updates and Gradient Trackingcited by 8
25 more
  1. 2022Generalization Bounds of Nonconvex-(Strongly)-Concave Stochastic Minimax Optimizationcited by 6
  2. 2022Adaptive Federated Minimax Optimization with Lower Complexitiescited by 5
  3. 2025Multiplayer Federated Learning: Reaching Equilibrium with Less Communicationcited by 5
  4. 2025Improved Rates of Differentially Private Nonconvex-Strongly-Concave Minimax Optimizationcited by 5
  5. 2023Near-Optimal Decentralized Momentum Method for Nonconvex-PL Minimax Problemscited by 4
  6. 2023Communication-Efficient Gradient Descent-Accent Methods for Distributed Variational Inequalities: Unified Analysis and Local Updatescited by 4
  7. 2023Federated Distributionally Robust Optimization with Non-Convex Objectives: Algorithm and Analysiscited by 4
  8. 2023Stochastic Smoothed Gradient Descent Ascent for Federated Minimax Optimizationcited by 4
  9. 2024Achieving Near-Optimal Convergence for Distributed Minimax Optimization with Adaptive Stepsizescited by 1
  10. 2024Accelerated Stochastic Min-Max Optimization Based on Bias-corrected Momentumcited by 1
  11. 2024GP-FL: Model-Based Hessian Estimation for Second-Order Over-the-Air Federated Learningcited by 1
  12. 2025MedForge: Building Medical Foundation Models Like Open Source Software Developmentcited by 1
  13. 2025Federated Instrumental Variable Analysis via Federated Generalized Method of Momentscited by 1
  14. 2025FedQuad: Federated Stochastic Quadruplet Learning to Mitigate Data Heterogeneitycited by 1
  15. 2025Federated Stochastic Minimax Optimization under Heavy-Tailed Noisescited by 1
  16. 2022SAGDA: Achieving O(ε-2) Communication Complexity in Federated Min-Max Learningcited by 0
  17. 2023Federated Composite Saddle Point Optimizationcited by 0
  18. 2023Federated Multi-Sequence Stochastic Approximation with Local Hypergradient Estimationcited by 0
  19. 2024Fast Decentralized Gradient Tracking for Federated Minimax Optimization with Local Updatescited by 0
  20. 2024Hybrid-Regularized Magnitude Pruning for Robust Federated Learning under Covariate Shiftcited by 0
  21. 2025Decoupled SGDA for Games with Intermittent Strategy Communicationcited by 0
  22. 2026Communication-Efficient Federated AUC Maximization with Cyclic Client Participationcited by 0
  23. 2026On the Stability and Generalization of First-order Bilevel Minimax Optimizationcited by 0
  24. 2026Enhancing Federated Quadruplet Learning: Stochastic Client Selection and Embedding Stability Analysiscited by 0
  25. 2026Provably Communication-Efficient and Privacy-Preserving Federated Graph Neural Networkscited by 0