Abstract
This paper introduces DSGDA, a novel decentralized algorithm for solving finite-sum minimax optimization problems. By combining a recursive variance-reduced gradient estimator with a gradient tracking communication scheme, the proposed method achieves a state-of-the-art communication complexity of $O(1/\epsilon^2)$, significantly outperforming previous decentralized stochastic methods that were limited to $O(1/\epsilon^3)$. DSGDA eliminates the need for periodic full gradient computations, enhancing both computational and sample efficiency. Theoretical analysis in the nonconvex-strongly-concave setting and empirical evaluations on AUC maximization tasks demonstrate that DSGDA consistently outperforms existing baselines in convergence speed and resource efficiency.
Introduction
Minimax optimization—where one player minimizes a function while another maximizes it—is a foundational component of modern machine learning, powering adversarial training, distributionally robust optimization, and AUC maximization. In decentralized environments, data is distributed across multiple workers connected in a network without a central coordinator. This setting introduces significant challenges: workers must reach a consensus through local neighbor communication while simultaneously optimizing their local models.
Existing decentralized minimax methods typically suffer from two primary drawbacks: high communication overhead (often requiring $O(1/\epsilon^3)$ rounds) and high computational costs due to the requirement of periodic "full gradient" computations over local datasets. This paper addresses these limitations through the DSGDA algorithm.
Methodology
DSGDA is built upon two primary pillars designed to optimize both communication and computation:
- Recursive Variance Reduction: The algorithm utilizes a recursive gradient estimator inspired by the SARAH/SPIDER family. Instead of relying on noisy stochastic gradients, it maintains a stable estimate of the gradient. Crucially, DSGDA does not require computing a full gradient at the start of every epoch, making it significantly more efficient for large-scale datasets.
- Gradient Tracking: To mitigate the impact of data heterogeneity (where local datasets differ significantly), DSGDA employs a gradient tracking scheme. This ensures that local search directions on each worker eventually align with the global gradient of the entire distributed dataset.
Theoretical guarantees are provided for the nonconvex-strongly-concave setting, ensuring the algorithm's applicability to a wide range of practical machine learning models.
Experimental Evaluation
The authors evaluated DSGDA on three binary classification datasets from the LIBSVM repository: a9a, w8a, and ijcnn1. These datasets are characterized by class imbalance, making them ideal for testing AUC Maximization, which was reformulated as a minimax problem for these experiments.
Key Results
DSGDA demonstrates clear theoretical and empirical superiority over existing methods:
- Communication Efficiency: It is the first work to achieve $O(1/\epsilon^2)$ communication complexity for this class of decentralized problems, matching the complexity of standard decentralized minimization.
- Sample Efficiency: By avoiding periodic full gradients, DSGDA achieves a sample complexity of $O(\sqrt{n}/\epsilon^2)$, improving upon the $O(n + \sqrt{n}/\epsilon^2)$ seen in prior state-of-the-art finite-sum methods.
- Rapid Convergence: In experiments with 10 workers, DSGDA converged significantly faster than baselines such as DM-HSGD and GT-SRVR across all tested datasets.
Discussion and Conclusion
DSGDA represents a significant step forward in decentralized minimax optimization. By breaking the $1/\epsilon^3$ communication barrier and removing the computational burden of full gradient resets, it provides a robust and scalable solution for distributed learning. While the current theory assumes strong concavity in the maximization variable, future work may extend this framework to nonconvex-nonconcave problems, such as those found in Generative Adversarial Networks (GANs). Additionally, exploring communication-efficient techniques like gradient compression could further enhance the algorithm's performance in bandwidth-constrained environments.
Summary updated