This paper considers stochastic first-order algorithms for minimax optimization under Polyak-{\L}ojasiewicz (PL) conditions.

This paper considers stochastic first-order algorithms for minimax optimization under Polyak-{\L}ojasiewicz (PL) conditions. We prove SPIDER-GDA could find an \epsilon -approximate 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. 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.