Federated Minimax Optimization: Improved Convergence Analyses and Algorithms

Pranay Sharma, Rohan Panda, Gauri Joshi, Pramod K. Varshney

Minimax optimization is the engine behind some of the most exciting—and challenging—frontiers in machine learning, from training Generative Adversarial Networks (GANs) to building models resistant to adversarial attacks. As datasets grow and privacy concerns mount, there is a pressing need to solve these "saddle-point" problems in a Federated Learning (FL) setting, where data remains on local devices and only model updates are shared.

In their paper, Federated Minimax Optimization: Improved Convergence Analyses and Algorithms, researchers provide a much-needed theoretical foundation and a powerful new algorithm for this domain, proving that federated minimax optimization can be just as efficient and scalable as standard federated minimization.

The Challenge of Federated Minimax Optimization

In standard federated learning, the goal is typically to minimize a global loss function. In minimax optimization, however, we are looking for a saddle point: we want to minimize a loss with respect to one set of parameters ($x$) while maximizing it with respect to another ($y$).

While "Local SGD" (where clients perform several local updates before syncing with a server) is well-understood for simple minimization, its minimax counterpart, Local SGDA (Stochastic Gradient Descent Ascent), has lacked rigorous theoretical backing. Previous analyses were often asymptotic or provided suboptimal rates that failed to match the best centralized results when scaled down to a single client.

Methods: Tighter Bounds and Momentum

The researchers focused on the Local SGDA algorithm, where each client performs $\tau$ local steps of gradient descent on $x$ and gradient ascent on $y$ before communicating with the server. Their primary contribution is a tighter convergence analysis across four major function classes:

  1. NC-SC: Nonconvex in $x$, Strongly-Concave in $y$.
  2. NC-PL: Nonconvex in $x$, satisfying the Polyak-Łojasiewicz (PL) condition in $y$ (a generalization of strong concavity).
  3. NC-C: Nonconvex in $x$, Concave in $y$.
  4. NC-1PC: Nonconvex in $x$, 1-Point-Concave in $y$.

Beyond the analysis, they propose Momentum Local SGDA. This algorithm uses momentum-based gradient estimators to "smooth out" the noise inherent in stochastic gradients. This is particularly vital in federated settings where data heterogeneity (different clients having very different data distributions) can cause local models to drift apart rapidly.

Key Insights and Theoretical Contributions

The theoretical improvements in this paper are substantial, filling significant gaps in the literature:

  • Linear Speedup: The paper proves that by using $n$ clients, you can reach a target error $\epsilon$ in $n$ times fewer total iterations compared to a single client. This "linear speedup" is highly sought after in distributed optimization.
  • Communication Efficiency: The authors show that you can perform many local updates ($\tau > 1$) without hurting the asymptotic convergence rate, saving on expensive communication rounds between edge devices and the server.
  • Matching the Centralized Baseline: Their analysis is the first to show that Local SGDA matches the optimal $\mathcal{O}(1/\epsilon^4)$ complexity of centralized minimax algorithms when $n=1$.
Comparison of complexity bounds showing the tighter guarantees provided by this work.

For the NC-PL class specifically, they improved the gradient complexity from a previous best of $\mathcal{O}(\kappa^{12}/(n\epsilon^6))$ to a much tighter $\mathcal{O}(\kappa^4/(n\epsilon^4))$.

Empirical Results

The researchers evaluated their algorithms on two primary tasks in a simulated federated environment with 20 clients and non-IID data partitions (using a Dirichlet distribution):

  • Fair Classification: Using the FashionMNIST dataset with a VGG11 model, where the minimax objective ensures equitable performance across classes.
  • Robust Neural Network Training: Using the CIFAR10 dataset with a VGG11 model to train a network resilient to adversarial perturbations.

The empirical results strongly support the theoretical claims. Increasing the number of local updates ($\tau$) leads to significant communication savings. Furthermore, the Momentum version of the algorithm consistently reaches higher accuracy faster than the standard version.

Test accuracy vs. communication rounds for Local SGDA and Momentum Local SGDA.

Limitations and Future Work

While the paper makes huge strides, the authors acknowledge a few remaining hurdles:

  • The NC-1PC Challenge: While they proved convergence for the broad 1-Point-Concave class, proving a linear speedup for this specific class in the presence of local updates remains an open theoretical problem.
  • Real-World Complexity: The current analysis assumes all clients participate in every round. Future work could extend these proofs to systems where clients drop in and out or perform different numbers of local updates based on hardware capabilities.

Ultimately, this work provides the rigorous "math under the hood" necessary to make federated minimax optimization a viable, efficient tool for large-scale, privacy-preserving machine learning.

Summary updated

Abstract

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 order-optimal sample complexity for several classes of nonconvex-concave and nonconvex-nonconcave minimax problems, and also enjoys linear 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.
BibTeX
@inproceedings{sharma2022federated,
  author = {Pranay Sharma and Rohan Panda and Gauri Joshi and Pramod K. Varshney},
  title = {{Federated Minimax Optimization: Improved Convergence Analyses and Algorithms}},
  booktitle = {International Conference on Machine Learning},
  year = {2022},
  url = {https://openreview.net/forum?id=IQqyXuc4or},
}
Figure