Abstract
To lower the communication complexity of federated min-max learning, a natural approach is to utilize the idea of infrequent communications (through multiple local updates) same as in conventional federated learning. However, due to the more complicated inter-outer problem structure in federated min-max learning, theoretical understandings of communication complexity for federated min-max learning with infrequent communications remain very limited in the literature. This is particularly true for settings with non-i.i.d. datasets and partial client participation. To address this challenge, in this paper, we propose a new algorithmic framework called stochastic sampling averaging gradient descent ascent (SAGDA), which i) assembles stochastic gradient estimators from randomly sampled clients as control variates and ii) leverages two learning rates on both server and client sides. We show that SAGDA achieves a linear speedup in terms of both the number of clients and local update steps, which yields an $\mathcal{O}(\epsilon^{-2})$ communication complexity that is orders of magnitude lower than the state of the art. Interestingly, by noting that the standard federated stochastic gradient descent ascent (FSGDA) is in fact a control-variate-free special version of SAGDA, we immediately arrive at an $\mathcal{O}(\epsilon^{-2})$ communication complexity result for FSGDA. Therefore, through the lens of SAGDA, we also advance the current understanding on communication complexity of the standard FSGDA method for federated min-max learning.
Introduction
Federated Learning (FL) has emerged as a powerful paradigm for training machine learning models across decentralized clients without centralizing raw data. However, the high communication cost between the server and clients remains a primary bottleneck. While "local update" methods like FedAvg have successfully addressed this in standard minimization tasks, their application to min-max optimization—essential for Generative Adversarial Networks (GANs), adversarial training, and AUC maximization—is significantly more complex.
The intricate "inner-outer" structure of min-max problems often leads to slow convergence and high communication overhead, particularly under non-i.i.d. data distributions and partial client participation. This research addresses a fundamental question: Can federated min-max learning achieve the same "linear speedup" (where convergence speed scales with the number of clients and local steps) seen in standard FL?
The SAGDA Framework
The authors introduce Stochastic Sampling Averaging Gradient Descent Ascent (SAGDA), a novel framework designed to minimize communication rounds. SAGDA relies on two primary technical pillars:
- Control Variates: By assembling stochastic gradient estimators from randomly sampled clients, SAGDA creates control variates that mitigate the "local drift" caused by data heterogeneity. This allows clients to perform multiple local updates while remaining aligned with the global objective.
- Two-Level Learning Rates: The framework employs distinct learning rates for the server and the clients. This dual-rate structure is vital for stabilizing the competitive dynamics inherent in min-max optimization within a distributed environment.
The framework supports two implementation options: Option I uses stateful control variates maintained by clients, while Option II calculates them instantly through an additional communication round.
Theoretical Contributions and Results
A major breakthrough of this work is proving that federated min-max learning can indeed achieve a linear speedup relative to both the number of clients ($m$) and the number of local steps ($K$). This implies that increasing hardware resources or local computation directly reduces the required communication rounds.
Furthermore, the authors demonstrate that the standard Federated Stochastic Gradient Descent Ascent (FSGDA) is a special, control-variate-free case of SAGDA. By applying the SAGDA analysis framework to FSGDA, they established significantly improved theoretical bounds for the standard method.
Performance Comparison
The theoretical advantages of SAGDA are summarized in the table below, highlighting its superior communication complexity compared to existing literature.
As shown in the table, SAGDA achieves a communication complexity of $\mathcal{O}(\epsilon^{-2})$, a substantial improvement over previous state-of-the-art methods that required $\mathcal{O}(\epsilon^{-3})$ to $\mathcal{O}(\epsilon^{-6})$ rounds. Notably, SAGDA achieves these rates without requiring the restrictive "bounded gradient dissimilarity" (BGD) assumption, enhancing its robustness for real-world heterogeneous data.
Empirical Validation
The efficacy of SAGDA was tested across three diverse tasks:
- Logistic Regression: Evaluated using the a9a dataset.
- AUC Maximization: Formulated as a min-max problem on the MNIST dataset.
- GAN Training: Evaluated on MNIST to test performance in non-convex-non-concave settings.
In all experiments, SAGDA consistently outperformed baselines such as CD-MAGE+ and Parallel-SGDA, converging faster in terms of both communication rounds and total sample complexity.
Conclusion and Future Directions
While SAGDA sets a new benchmark for federated min-max learning, some theoretical gaps remain. For standard FSGDA under partial client participation, a linear speedup was proven for the number of clients ($m$) but not yet for the number of local steps ($K$). Achieving this remains an open challenge. Additionally, while the current theory focuses on non-convex-PL problems, the successful GAN experiments suggest that the framework's theoretical foundations could be expanded to even more general non-convex-non-concave structures.
Summary updated