A Near-Optimal Algorithm for Decentralized Convex-Concave Finite-Sum Minimax Optimization
Hongxu Chen, Ke Wei, Haishan Ye, Luo Luo
Abstract
In this paper, we study the distributed convex-concave finite-sum minimax optimization over the network, and a decentralized variance-reduced optimistic gradient method with stochastic mini-batch sizes (DIVERSE) is proposed. For the strongly-convex-strongly-concave objective, it is shown that DIVERSE can achieve a linear convergence rate that depends on the global smoothness parameters, yielding sharper computation and communication complexity bounds than existing results. Furthermore, we also establish the lower complexity bounds, which show that our upper bounds are optimal up to a logarithmic factor in terms of the local incremental first-order oracle calls, the computation rounds, and the communication rounds. Numerical experiments demonstrate that our algorithm outperforms existing methods in practice.
BibTeX
@inproceedings{
chen2025a,
title={A Near-Optimal Algorithm for Decentralized Convex-Concave Finite-Sum Minimax Optimization},
author={Hongxu Chen and Ke Wei and Haishan Ye and Luo Luo},
booktitle={The Thirty-ninth Annual Conference on Neural Information Processing Systems},
year={2025},
url={https://openreview.net/forum?id=raZEmZ48h4}
}