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.

基于 Polyak-Lojasiewicz 条件，本文提出了用于解决 minimax 优化问题的随机一阶算法 SPIDER-GDA，该算法在有限和的情况下达到了更好的优化效果，并降低了计算成本。