mlsanityData to 13 Oct 2026

A Communication-efficient Algorithm with Linear Convergence for Federated Minimax Learning

arXiv 2206.01132 ↗First posted 2 Jun 2022cs.LG cs.DCcited by 9

Not on the map. Why?

Abstract (arXiv)

In this paper, we study a large-scale multi-agent minimax optimization problem, which models many interesting applications in statistical learning and game theory, including Generative Adversarial Networks (GANs). The overall objective is a sum of agents' private local objective functions. We first analyze an important special case, empirical minimax problem, where the overall objective approximates a true population minimax risk by statistical samples. We provide generalization bounds for learning with this objective through Rademacher complexity analysis. Then, we focus on the federated setting, where agents can perform local computation and communicate with a central server. Most existing federated minimax algorithms either require communication per iteration or lack performance guarantees with the exception of Local Stochastic Gradient Descent Ascent (SGDA), a multiple-local-update descent ascent algorithm which guarantees convergence under a diminishing stepsize. By analyzing Local SGDA under the ideal condition of no gradient noise, we show that generally it cannot guarantee exact convergence with constant stepsizes and thus suffers from slow rates of convergence. To tackle this issue, we propose FedGDA-GT, an improved Federated (Fed) Gradient Descent Ascent (GDA) method based on Gradient Tracking (GT). When local objectives are Lipschitz smooth and strongly-convex-strongly-concave, we prove that FedGDA-GT converges linearly with a constant stepsize to global ε-approximation solution with O(log (1/ε)) rounds of communication, which matches the time complexity of centralized GDA method. Finally, we numerically show that FedGDA-GT outperforms Local SGDA.

Key facts. Cited by 9 papers in the map (data through 13 Oct 2026). Builds on 35 of its 69 references that are in the map. First posted on arXiv 2 Jun 2022.

Builds on

35 of 69 references.

References · 35

  1. 2016Communication-Efficient Learning of Deep Networks from Decentralized Datacited by 7,653
  2. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,379
  3. 2017Improved Training of Wasserstein GANscited by 2,226
  4. 2019Distributionally Robust Neural Networks for Group Shifts: On the Importance of Regularization for Worst-Case Generalizationcited by 1,242
  5. 2016Least Squares Generative Adversarial Networkscited by 1,000
  6. 2020Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimizationcited by 903
  7. 2019Agnostic Federated Learningcited by 453
  8. 2018Learning Models with Uniform Performance via Distributionally Robust Optimizationcited by 335
  9. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 266
  10. 2017Generalization and Equilibrium in Generative Adversarial Nets (GANs)cited by 165
  11. 2016Variance-based regularization with convex objectivescited by 153
  12. 2019Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methodscited by 148
23 more
  1. 2018A Variational Inequality Perspective on Generative Adversarial Networkscited by 144
  2. 2017Deep Decentralized Multi-task Multi-Agent Reinforcement Learning under Partial Observabilitycited by 143
  3. 2019A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approachcited by 142
  4. 2013Communication Efficient Distributed Optimization using an Approximate Newton-type Methodcited by 132
  5. 2018Rademacher Complexity for Adversarially Robust Generalizationcited by 132
  6. 2021Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradientscited by 123
  7. 2020FedSplit: An algorithmic framework for fast federated optimizationcited by 108
  8. 2021Distributionally Robust Federated Averagingcited by 104
  9. 2020Robust Federated Learning: The Case of Affine Distribution Shiftscited by 102
  10. 2020Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimizationcited by 94
  11. 2020FedGAN: Federated Generative Adversarial Networks for Distributed Datacited by 90
  12. 2019Improved Sample Complexities for Deep Networks and Robust Classification via an All-Layer Margincited by 56
  13. 2017On the Discrimination-Generalization Tradeoff in GANscited by 48
  14. 2019A Decentralized Parallel Algorithm for Training Generative Adversarial Netscited by 43
  15. 2020Train simultaneously, generalize better: Stability of gradient-based minimax learnerscited by 43
  16. 2021Local Stochastic Gradient Descent Ascent: Convergence Analysis and Communication Efficiencycited by 40
  17. 2016Efficient Distributed Learning with Sparsitycited by 38
  18. 2022Federated Minimax Optimization: Improved Convergence Analyses and Algorithmscited by 37
  19. 2016A Minimax Approach to Supervised Learningcited by 33
  20. 2019Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Netscited by 29
  21. 2018Approximability of Discriminators Implies Diversity in GANscited by 28
  22. 2020Generalization Bounds for Stochastic Saddle Point Problemscited by 27
  23. 2021Fed-TGAN: Federated Learning Framework for Synthesizing Tabular Datacited by 9

Built on by

Cited by year

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

9 papers.

  1. 2023Understanding Generalization of Federated Learning via Stability: Heterogeneity Matterscited by 27
  2. 2023Solving a Class of Non-Convex Minimax Optimization in Federated Learningcited by 10
  3. 2023Federated Minimax Optimization with Client Heterogeneitycited by 8
  4. 2024Robust Decentralized Learning with Local Updates and Gradient Trackingcited by 8
  5. 2023Particle-based Online Bayesian Samplingcited by 7
  6. 2023Communication-Efficient Gradient Descent-Accent Methods for Distributed Variational Inequalities: Unified Analysis and Local Updatescited by 4
  7. 2023Stochastic Smoothed Gradient Descent Ascent for Federated Minimax Optimizationcited by 4
  8. 2024Debiasing Federated Learning with Correlated Client Participationcited by 1
  9. 2024Fast Decentralized Gradient Tracking for Federated Minimax Optimization with Local Updatescited by 0