Decentralized Stochastic Variance Reduced Extragradient Method
This addresses optimization challenges in decentralized multi-agent systems, offering incremental improvements in efficiency for distributed machine learning tasks.
The paper tackles decentralized convex-concave minimax optimization problems by proposing a novel algorithm that achieves the best known stochastic first-order oracle complexity, with each agent requiring O((n+κ√n)log(1/ε)) calls for strongly-convex-strongly-concave cases and O((n+√nL/ε)log(1/ε)) for general cases to reach an ε-accurate solution.
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+κ\sqrt{n})\log(1/\varepsilon))$ SFO calls for strongly-convex-strongly-concave problem and $\mathcal O((n+\sqrt{n}L/\varepsilon)\log(1/\varepsilon))$ SFO call for general convex-concave problem to achieve $\varepsilon$-accurate solution in expectation, where $κ$ is the condition number and $L$ is the smoothness parameter. The numerical experiments show the proposed method performs better than baselines.