Decentralized Stochastic Variance Reduced Extragradient Method

This paper studies decentralized convex-concave minimax optimization problems of the form minxmaxy f(x,y) triangleqfrac1msumi=1m fi(x,y), where m is the number of agents and each local function can be written as fi(x,y)=frac1nsumj=1n fi,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√n)log(1/varepsilon)) SFO calls for strongly-convex-strongly-concave problem and mathcal O((n+√nL/varepsilon)log(1/varepsilon)) SFO call for general convex-concave problem to achieve varepsilon-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.