mlsanityData to 7 Oct 2026

Federated Minimax Optimization with Client Heterogeneity

arXiv 2302.04249 ↗First posted 8 Feb 2023cs.LG cs.DC math.OCcited by 8

Not on the map. Why?

Abstract (arXiv)

Minimax optimization has seen a surge in interest with the advent of modern applications such as GANs, and it is inherently more challenging than simple minimization. The difficulty is exacerbated by the training data residing at multiple edge devices or textitclients, especially when these clients can have heterogeneous datasets and local computation capabilities. We propose a general federated minimax optimization framework that subsumes such settings and several existing methods like Local SGDA. We show that naive aggregation of heterogeneous local progress results in optimizing a mismatched objective function -- a phenomenon previously observed in standard federated minimization. To fix this problem, we propose normalizing the client updates by the number of local steps undertaken between successive communication rounds. We analyze the convergence of the proposed algorithm for classes of nonconvex-concave and nonconvex-nonconcave functions and characterize the impact of heterogeneous client data, partial client participation, and heterogeneous local computations. Our analysis works under more general assumptions on the intra-client noise and inter-client heterogeneity than so far considered in the literature. For all the function classes considered, we significantly improve the existing computation and communication complexity results. Experimental results support our theoretical claims.

Key facts. Cited by 8 papers in the map (data through 7 Oct 2026). Builds on 67 of its 83 references that are in the map. First posted on arXiv 8 Feb 2023.

Builds on

67 of 83 references.

References · 67

  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. 2022Generative Adversarial Networkscited by 5,603
  4. 2019Advances and Open Problems in Federated Learningcited by 3,021
  5. 2019Federated Learning: Challenges, Methods, and Future Directionscited by 1,531
  6. 2018Federated Learning with Non-IID Datacited by 1,099
  7. 2020Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimizationcited by 897
  8. 2018Local SGD Converges Fast and Communicates Littlecited by 595
  9. 2020Federated Learning with Matched Averagingcited by 564
  10. 2016Federated Optimization: Distributed Machine Learning for On-Device Intelligencecited by 558
  11. 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 526
  12. 2019Agnostic Federated Learningcited by 451
38 more
  1. 2019Robust and Communication-Efficient Federated Learning from Non-IID Datacited by 415
  2. 2020A Unified Theory of Decentralized SGD with Changing Topology and Local Updatescited by 361
  3. 2018Learning Adversarially Fair and Transferable Representationscited by 353
  4. 2021A Field Guide to Federated Optimizationcited by 312
  5. 2015Data-driven Distributionally Robust Optimization Using the Wasserstein Metric: Performance Guarantees and Tractable Reformulationscited by 285
  6. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 266
  7. 2019Tighter Theory for Local SGD on Identical and Heterogeneous Datacited by 266
  8. 2021Achieving Linear Speedup with Partial Worker Participation in Non-IID Federated Learningcited by 192
  9. 2019On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimizationcited by 178
  10. 2018Stochastic model-based minimization of weakly convex functionscited by 157
  11. 2019Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methodscited by 148
  12. 2020Minibatch vs Local SGD for Heterogeneous Distributed Learningcited by 147
  13. 2021Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradientscited by 122
  14. 2020Near-Optimal Algorithms for Minimax Optimizationcited by 119
  15. 2019Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronizationcited by 106
  16. 2021Distributionally Robust Federated Averagingcited by 104
  17. 2020Robust Federated Learning: The Case of Affine Distribution Shiftscited by 102
  18. 2018Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problemscited by 75
  19. 2019Efficient Algorithms for Smooth Minimax Optimizationcited by 75
  20. 2020Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problemscited by 75
  21. 2021Accelerated Algorithms for Smooth Convex-Concave Minimax Problems with O(1/k2) Rate on Squared Gradient Normcited by 71
  22. 2018Weakly-Convex Concave Min-Max Optimization: Provable Algorithms and Applications in Machine Learningcited by 62
  23. 2022FedVARP: Tackling the Variance Due to Partial Client Participation in Federated Learningcited by 62
  24. 2021Fast Extra Gradient Methods for Smooth Structured Nonconvex-Nonconcave Minimax Problemscited by 61
  25. 2016Efficiency of minimizing compositions of convex functions and smooth mapscited by 59
  26. 2020A Single-Loop Smoothed Gradient Descent-Ascent Algorithm for Nonconvex-Concave Min-Max Problemscited by 57
  27. 2020A Unified Single-loop Alternating Gradient Projection Algorithm for Nonconvex-Concave and Convex-Nonconcave Minimax Problemscited by 56
  28. 2020Straggler-Resilient Federated Learning: Leveraging the Interplay Between Statistical Accuracy and System Heterogeneitycited by 56
  29. 2019Hybrid Block Successive Approximation for One-Sided Non-Convex Min-Max Problems: Algorithms and Applicationscited by 55
  30. 2018On the Convergence and Robustness of Training GANs with Regularized Optimal Transportcited by 51
  31. 2021Faster Single-loop Algorithms for Minimax Optimization without Strong Concavitycited by 47
  32. 2021The Complexity of Nonconvex-Strongly-Concave Minimax Optimizationcited by 44
  33. 2021Anarchic Federated Learningcited by 42
  34. 2021Local Stochastic Gradient Descent Ascent: Convergence Analysis and Communication Efficiencycited by 40
  35. 2022Federated Minimax Optimization: Improved Convergence Analyses and Algorithmscited by 37
  36. 2021Stability and Generalization of Stochastic Gradient Methods for Minimax Problemscited by 35
  37. 2021Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyondcited by 35
  38. 2020Improved Algorithms for Convex-Concave Minimax Optimizationcited by 34

50 most cited of 67 All 67 (JSON)

Built on by

Cited by year

Citing papers per year: 2023: 5; 2024: 3.

8 papers.

  1. 2023SimFBO: Towards Simple, Flexible and Communication-efficient Federated Bilevel Learningcited by 14
  2. 2023Solving a Class of Non-Convex Minimax Optimization in Federated Learningcited by 10
  3. 2024Robust Decentralized Learning with Local Updates and Gradient Trackingcited by 8
  4. 2023Federated Distributionally Robust Optimization with Non-Convex Objectives: Algorithm and Analysiscited by 4
  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. 2023Federated Multi-Sequence Stochastic Approximation with Local Hypergradient Estimationcited by 0
  8. 2024Fast Decentralized Gradient Tracking for Federated Minimax Optimization with Local Updatescited by 0