Faster Stochastic Algorithms for Minimax Optimization under
  Polyak--Łojasiewicz Conditions
Lesi Chen Boyuan Yao Luo Luo
This paper considers stochastic first-order algorithms for minimax
optimization under Polyak--{\L}ojasiewicz (PL) conditions. We propose
SPIDER-GDA for solving the finite-sum problem of the form $\min_x \max_y
f(x,y)\triangleq \frac{1}{n} \sum_{i=1}^n f_i(x,y)$, where the objective
function $f(x,y)$ is $\mu_x$-PL in $x$ and $\mu_y$-PL in $y$; and each
$f_i(x,y)$ is $L$-smooth. We prove SPIDER-GDA could find an $\epsilon$-optimal
solution within ${\mathcal O}\left((n + \sqrt{n}\,\kappa_x\kappa_y^2)\log
(1/\epsilon)\right)$ stochastic first-order oracle (SFO) complexity, which is
better than the state-of-the-art method whose SFO upper bound is ${\mathcal
O}\big((n + n^{2/3}\kappa_x\kappa_y^2)\log (1/\epsilon)\big)$, where
$\kappa_x\triangleq L/\mu_x$ and $\kappa_y\triangleq L/\mu_y$. For the
ill-conditioned case, we provide an accelerated algorithm to reduce the
computational cost further. It achieves $\tilde{{\mathcal
O}}\big((n+\sqrt{n}\,\kappa_x\kappa_y)\log^2 (1/\epsilon)\big)$ SFO upper bound
when $\kappa_y \gtrsim \sqrt{n}$. Our ideas also can be applied to the more
general setting that the objective function only satisfies PL condition for one
variable. Numerical experiments validate the superiority of proposed methods.