Decentralized Stochastic Variance Reduced Extragradient Method

Abstract

This paper studies decentralized convex-concave minimax optimization problems of the form ${\min }_x{\max }_{y}f(x,y)\triangleq \frac{1}{m}{\sum }_{i=1}^m{f}_i(x,y)$, where $m$ is the number of agents and each local function can be written as $f_i(x,y)=\frac{1}{n}{\sum }_{j=1}^n{f}_{i,j}(x,y)$. We propose a novel decentralized optimization algorithm, called multi-consensus stochastic variance reduced extragradient, which achieves the best known stochastic first-order oracle (SFO) complexity for this problem. Specifically, each agent requires $\mathcal{O}((n+\kappa \sqrt{n})\log (1/\epsilon ))$ SFO calls for strongly-convex-strongly-concave problem and $\mathcal{O}((n+\sqrt{n}L/\epsilon )\log (1/\epsilon ))$ SFO call for general convex-concave problem to achieve $\epsilon$-accurate solution in expectation, where $\kappa$ is the condition number and $L$ is the smoothness parameter. The numerical experiments show the proposed method performs better than baselines.