SAGDA: Achieving $\mathcal{O}(\epsilon^{-2})$ Communication Complexity in Federated Min-Max Learning

Haibo Yang, Zhuqing Liu, Xin Zhang, Jia LiuNeurIPS 2022 · OpenReview

Introduction

Researchers have developed SAGDA (Stochastic Sampling Averaging Gradient Descent Ascent), a novel algorithmic framework that brings the communication efficiency of federated min-max learning up to speed with standard minimization tasks. By utilizing control variates and dual-level learning rates, SAGDA achieves a state-of-the-art $\mathcal{O}(\epsilon^{-2})$ communication complexity and demonstrates a linear speedup as more clients join the training process.

The Challenge of Federated Min-Max Optimization

Federated Learning (FL) is typically discussed in the context of minimizing a loss function, such as training a standard image classifier. However, many modern AI tasks—including Generative Adversarial Networks (GANs), robust adversarial training, and AUC maximization—rely on min-max optimization. These are "saddle-point" problems where one player attempts to minimize the objective while another tries to maximize it.

In FL, communication between the central server and edge devices is the primary bottleneck. To conserve bandwidth, systems typically employ "local updates" (e.g., FedAvg), where clients perform multiple computation steps before synchronizing with the server. While effective for simple minimization, local updates create severe "client drift" in min-max settings due to the complex inter-dependency between the minimization and maximization variables. Previous attempts to solve this either required restrictive assumptions about data similarity across clients or suffered from poor communication complexity (often $\mathcal{O}(\epsilon^{-3})$ or worse), rendering them impractical for large-scale deployment.

The SAGDA Framework

To overcome these bottlenecks, the authors introduce SAGDA, which relies on two primary mechanisms:

  1. Control Variates: To combat data heterogeneity (the reality that every client holds different data distributions), SAGDA assembles stochastic gradient estimators from sampled clients to serve as control variates. These variates act as a correction mechanism, ensuring that local updates remain aligned with the global objective.
  2. Two-Level Learning Rates: Unlike standard methods that use a single step size, SAGDA employs distinct learning rates for the server and the clients. This decoupling allows for more stable convergence within the volatile "push-and-pull" landscape of min-max optimization.

The framework is presented in two variants:

  • Option I: Clients remain "stateful" and remember their control variates across rounds.
  • Option II: Utilizes an extra communication step to calculate variates on the fly, making it better suited for "cross-device" settings where clients frequently drop offline.

Key Insights and Results

SAGDA was evaluated on tasks like Distributionally Robust Logistic Regression (using the a9a dataset) and AUC Maximization (using a modified MNIST dataset). Data was partitioned heterogeneously across 100 workers to simulate real-world FL conditions.

Breakthrough Communication Complexity

The most significant achievement of SAGDA is hitting the $\mathcal{O}(\epsilon^{-2})$ communication complexity mark. As shown in the comparison below, this is orders of magnitude more efficient than previous state-of-the-art methods like CD-MAGE or Local SGDA, which sat at $\mathcal{O}(\epsilon^{-4})$ or $\mathcal{O}(\epsilon^{-3})$.

Comparison of complexities

Relaxing Restrictive Assumptions

Most previous proofs required a "Bounded Gradient Dissimilarity" (BGD) assumption, essentially assuming clients' data aren't too different. SAGDA's control variates allow it to function under arbitrary data heterogeneity without relying on this crutch. Furthermore, the authors discovered that standard Federated Stochastic Gradient Descent Ascent (FSGDA) is actually a special, "control-variate-free" version of SAGDA, allowing them to use their new proof techniques to improve the theoretical understanding of standard algorithms as well.

Linear Speedup

The paper proves that SAGDA achieves a "linear speedup." If you double the number of clients ($m$) or double the number of local steps ($K$), you effectively cut the required communication rounds in half, representing the gold standard for distributed optimization. Empirically, SAGDA converged significantly faster than baselines like Parallel-SGDA and CD-MAGE+ in both communication rounds and total samples processed.

Limitations and Future Work

While SAGDA represents a major leap forward, a few hurdles remain:

  • Statefulness vs. Overhead: Option I requires clients to maintain state across rounds, which is difficult in massive-scale mobile applications where clients go offline. Option II solves this but requires an extra round of communication per cycle, which could be problematic on very slow networks.
  • Partial Participation Gap: While the authors achieved linear speedup in the number of clients ($m$) under partial participation, achieving a linear speedup in local steps ($K$) under the same conditions remains an open theoretical challenge for the research community.

Summary updated

Abstract

Federated min-max learning has received increasing attention in recent years thanks to its wide range of applications in various learning paradigms. Similar to the conventional federated learning for empirical risk minimization problems, communication complexity also emerges as one of the most critical concerns that affects the future prospect of federated min-max learning. 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 \ul{s}tochastic \ul{s}ampling \ul{a}veraging \ul{g}radient \ul{d}escent \ul{a}scent ($\mathsf{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 $\mathsf{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 $\mathsf{SAGDA}$, we immediately arrive at an $\mathcal{O}(\epsilon^{-2})$ communication complexity result for FSGDA. Therefore, through the lens of $\mathsf{SAGDA}$, we also advance the current understanding on communication complexity of the standard FSGDA method for federated min-max learning.
BibTeX
@inproceedings{yang2022sagda,
  author = {Haibo Yang and Zhuqing Liu and Xin Zhang and Jia Liu},
  title = {{SAGDA: Achieving $\textbackslash\{\}mathcal\{O\}(\textbackslash\{\}epsilon^\{-2\})$ Communication Complexity in Federated Min-Max Learning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=wTp4KgVIJ5},
}
Figure