mlsanityData to 7 Oct 2026

Solving a Class of Non-Convex Minimax Optimization in Federated Learning

arXiv 2310.03613 ↗First posted 5 Oct 2023cs.LG cs.AIcited by 10

Not on the map. Why?

Abstract (arXiv)

The minimax problems arise throughout machine learning applications, ranging from adversarial training and policy evaluation in reinforcement learning to AUROC maximization. To address the large-scale data challenges across multiple clients with communication-efficient distributed training, federated learning (FL) is gaining popularity. Many optimization algorithms for minimax problems have been developed in the centralized setting (i.e. single-machine). Nonetheless, the algorithm for minimax problems under FL is still underexplored. In this paper, we study a class of federated nonconvex minimax optimization problems. We propose FL algorithms (FedSGDA+ and FedSGDA-M) and reduce existing complexity results for the most common minimax problems. For nonconvex-concave problems, we propose FedSGDA+ and reduce the communication complexity to O(varepsilon-6). Under nonconvex-strongly-concave and nonconvex-PL minimax settings, we prove that FedSGDA-M has the best-known sample complexity of O(kappa3 N-1varepsilon-3) and the best-known communication complexity of O(kappa2varepsilon-2). FedSGDA-M is the first algorithm to match the best sample complexity O(varepsilon-3) achieved by the single-machine method under the nonconvex-strongly-concave setting. Extensive experimental results on fair classification and AUROC maximization show the efficiency of our algorithms.

Key facts. Cited by 10 papers in the map (data through 7 Oct 2026). Builds on 58 of its 78 references that are in the map. First posted on arXiv 5 Oct 2023.

Builds on

58 of 78 references.

References · 58

  1. 2015Deep Residual Learning for Image Recognitioncited by 51,809
  2. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,592
  3. 2018Federated Optimization in Heterogeneous Networkscited by 2,971
  4. 2017Improved Training of Wasserstein GANscited by 2,223
  5. 2020Adaptive Federated Optimizationcited by 1,036
  6. 2018A Convergence Theory for Deep Learning via Over-Parameterizationcited by 784
  7. 2019Momentum-Based Variance Reduction in Non-Convex SGDcited by 302
  8. 2018SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimatorcited by 283
  9. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 266
  10. 2018Stochastic model-based minimization of weakly convex functionscited by 157
  11. 2020Mime: Mimicking Centralized Stochastic Algorithms in Federated Learningcited by 152
  12. 2019Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methodscited by 148
38 more
  1. 2021Distributionally Robust Federated Averagingcited by 104
  2. 2020Robust Federated Learning: The Case of Affine Distribution Shiftscited by 102
  3. 2017Stability and Generalization of Learning Algorithms that Converge to Global Optimacited by 100
  4. 2020Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimizationcited by 94
  5. 2020FedGAN: Federated Generative Adversarial Networks for Distributed Datacited by 89
  6. 2019Efficient Algorithms for Smooth Minimax Optimizationcited by 75
  7. 2020Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problemscited by 75
  8. 2019Stochastic AUC Maximization with Deep Neural Networkscited by 61
  9. 2022FedNest: Federated Bilevel, Minimax, and Compositional Optimizationcited by 60
  10. 2021Faster Single-loop Algorithms for Minimax Optimization without Strong Concavitycited by 47
  11. 2019A Decentralized Parallel Algorithm for Training Generative Adversarial Netscited by 43
  12. 2021STEM: A Stochastic Two-Sided Momentum Algorithm Achieving Near-Optimal Sample and Communication Complexities for Federated Learningcited by 43
  13. 2021Local Stochastic Gradient Descent Ascent: Convergence Analysis and Communication Efficiencycited by 40
  14. 2020Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimizationcited by 39
  15. 2022Federated Minimax Optimization: Improved Convergence Analyses and Algorithmscited by 37
  16. 2022Faster Adaptive Federated Learningcited by 35
  17. 2023Robust Multi-Agent Reinforcement Learning with State Uncertaintycited by 35
  18. 2019Adversarial Attack Generation Empowered by Min-Max Optimizationcited by 32
  19. 2019An accelerated inexact proximal point method for solving nonconvex-concave min-max problemscited by 30
  20. 2020Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networkscited by 27
  21. 2021Decentralized Local Stochastic Extra-Gradient for Variational Inequalitiescited by 25
  22. 2022SAPD+: An Accelerated Stochastic Method for Nonconvex-Concave Minimax Problemscited by 23
  23. 2021Federated Deep AUC Maximization for Heterogeneous Data with a Constant Communication Complexitycited by 21
  24. 2022What is the Solution for State-Adversarial Multi-Agent Reinforcement Learning?cited by 21
  25. 2022Adversarial Weight Perturbation Improves Generalization in Graph Neural Networkscited by 21
  26. 2021Efficient Algorithms for Federated Saddle Point Optimizationcited by 20
  27. 2023MAC-PO: Multi-Agent Experience Replay via Collective Priority Optimizationcited by 20
  28. 2019What is Local Optimality in Nonconvex-Nonconcave Minimax Optimization?cited by 19
  29. 2020Gradient Descent Ascent for Minimax Problems on Riemannian Manifoldscited by 16
  30. 2022Nest Your Adaptive Algorithm for Parameter-Agnostic Nonconvex Minimax Optimizationcited by 16
  31. 2022RetrievalGuard: Provably Robust 1-Nearest Neighbor Image Retrievalcited by 15
  32. 2022An Accelerated Doubly Stochastic Gradient Method with Faster Explicit Model Identificationcited by 14
  33. 2021Unified Convergence Analysis for Adaptive Optimization with Moving Average Estimatorcited by 13
  34. 2021AdaGDA: Faster Adaptive Gradient Descent Ascent Methods for Minimax Optimizationcited by 13
  35. 2022FeDXL: Provable Federated Learning for Deep X-Risk Optimizationcited by 10
  36. 2022A Law of Robustness beyond Isoperimetrycited by 9
  37. 2022A Communication-efficient Algorithm with Linear Convergence for Federated Minimax Learningcited by 9
  38. 2023Federated Minimax Optimization with Client Heterogeneitycited by 8

50 most cited of 58 All 58 (JSON)

Built on by

Cited by year

Citing papers per year: 2023: 3; 2024: 4; 2025: 3.

10 papers.

  1. 2024Towards Unified Multi-Modal Personalization: Large Vision-Language Models for Generative Recommendation and Beyondcited by 25
  2. 2023Every Parameter Matters: Ensuring the Convergence of Federated Learning with Dynamic Heterogeneous Models Reductioncited by 24
  3. 2024Auto-Train-Once: Controller Network Guided Automatic Network Pruning from Scratchcited by 20
  4. 2023On the Role of Server Momentum in Federated Learningcited by 16
  5. 2023Stochastic Smoothed Gradient Descent Ascent for Federated Minimax Optimizationcited by 4
  6. 2024Achieving Near-Optimal Convergence for Distributed Minimax Optimization with Adaptive Stepsizescited by 1
  7. 2025Heterogeneity-Aware Client Sampling for Optimal and Efficient Federated Learningcited by 1
  8. 2025Federated Instrumental Variable Analysis via Federated Generalized Method of Momentscited by 1
  9. 2025Federated Stochastic Minimax Optimization under Heavy-Tailed Noisescited by 1
  10. 2024FedEGG: Federated Learning with Explicit Global Guidancecited by 0