# Federated Minimax Optimization with Client Heterogeneity

arXiv: https://arxiv.org/abs/2302.04249 · HTML: https://mlsanity.com/paper/2302.04249/

## Key facts

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

## Builds on (most cited first, 30 of 67)

- [Communication-Efficient Learning of Deep Networks from Decentralized Data](https://mlsanity.com/paper/1602.05629/) (2016)
- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Generative Adversarial Networks](https://mlsanity.com/paper/2203.00667/) (2022)
- [Advances and Open Problems in Federated Learning](https://mlsanity.com/paper/1912.04977/) (2019)
- [Federated Learning: Challenges, Methods, and Future Directions](https://mlsanity.com/paper/1908.07873/) (2019)
- [Federated Learning with Non-IID Data](https://mlsanity.com/paper/1806.00582/) (2018)
- [Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization](https://mlsanity.com/paper/2007.07481/) (2020)
- [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018)
- [Federated Optimization: Distributed Machine Learning for On-Device Intelligence](https://mlsanity.com/paper/1610.02527/) (2016)
- [Federated Learning with Matched Averaging](https://mlsanity.com/paper/2002.06440/) (2020)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Agnostic Federated Learning](https://mlsanity.com/paper/1902.00146/) (2019)
- [Robust and Communication-Efficient Federated Learning from Non-IID Data](https://mlsanity.com/paper/1903.02891/) (2019)
- [A Unified Theory of Decentralized SGD with Changing Topology and Local Updates](https://mlsanity.com/paper/2003.10422/) (2020)
- [Learning Adversarially Fair and Transferable Representations](https://mlsanity.com/paper/1802.06309/) (2018)
- [A Field Guide to Federated Optimization](https://mlsanity.com/paper/2107.06917/) (2021)
- [Data-driven Distributionally Robust Optimization Using the Wasserstein Metric: Performance Guarantees and Tractable Reformulations](https://mlsanity.com/paper/1505.05116/) (2015)
- [On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/1906.00331/) (2019)
- [Tighter Theory for Local SGD on Identical and Heterogeneous Data](https://mlsanity.com/paper/1909.04746/) (2019)
- [Achieving Linear Speedup with Partial Worker Participation in Non-IID Federated Learning](https://mlsanity.com/paper/2101.11203/) (2021)
- [On the Linear Speedup Analysis of Communication Efficient Momentum SGD for Distributed Non-Convex Optimization](https://mlsanity.com/paper/1905.03817/) (2019)
- [Stochastic model-based minimization of weakly convex functions](https://mlsanity.com/paper/1803.06523/) (2018)
- [Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods](https://mlsanity.com/paper/1902.08297/) (2019)
- [Minibatch vs Local SGD for Heterogeneous Distributed Learning](https://mlsanity.com/paper/2006.04735/) (2020)
- [Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients](https://mlsanity.com/paper/2102.07053/) (2021)
- [Near-Optimal Algorithms for Minimax Optimization](https://mlsanity.com/paper/2002.02417/) (2020)
- [Local SGD with Periodic Averaging: Tighter Analysis and Adaptive Synchronization](https://mlsanity.com/paper/1910.13598/) (2019)
- [Distributionally Robust Federated Averaging](https://mlsanity.com/paper/2102.12660/) (2021)
- [Robust Federated Learning: The Case of Affine Distribution Shifts](https://mlsanity.com/paper/2006.08907/) (2020)
- [Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems](https://mlsanity.com/paper/2001.03724/) (2020)

## Built on by (most cited first, 8 of 8)

- [SimFBO: Towards Simple, Flexible and Communication-efficient Federated Bilevel Learning](https://mlsanity.com/paper/2305.19442/) (2023)
- [Solving a Class of Non-Convex Minimax Optimization in Federated Learning](https://mlsanity.com/paper/2310.03613/) (2023)
- [Robust Decentralized Learning with Local Updates and Gradient Tracking](https://mlsanity.com/paper/2405.00965/) (2024)
- [Federated Distributionally Robust Optimization with Non-Convex Objectives: Algorithm and Analysis](https://mlsanity.com/paper/2307.14364/) (2023)
- [Stochastic Smoothed Gradient Descent Ascent for Federated Minimax Optimization](https://mlsanity.com/paper/2311.00944/) (2023)
- [Achieving Near-Optimal Convergence for Distributed Minimax Optimization with Adaptive Stepsizes](https://mlsanity.com/paper/2406.02939/) (2024)
- [Federated Multi-Sequence Stochastic Approximation with Local Hypergradient Estimation](https://mlsanity.com/paper/2306.01648/) (2023)
- [Fast Decentralized Gradient Tracking for Federated Minimax Optimization with Local Updates](https://mlsanity.com/paper/2405.04566/) (2024)

## 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.