A Near-Optimal Algorithm for Decentralized Convex-Concave Finite-Sum Minimax Optimization

Hongxu Chen (Fudan University) · Ke Wei (Fudan University) · Haishan Ye (The Chinese University of Hong Kong, Shenzen) · Luo Luo (Fudan University)

communication complexitycomputation complexityconvex-concavedecentralized algorithmdistributed optimizationfinite-sum minimaxfirst-order oracleglobal smoothnessincremental callslinear convergence ratelower complexity boundsnumerical experimentsoptimistic gradient methodperformance evaluationstochastic mini-batchvariance-reduced

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.