Faster Stochastic Algorithms for Minimax Optimization under Polyak--Łojasiewicz Conditions

Code

• github.com/truenobility303/spider-gda
  OfficialIn papernone★ 7

Abstract

This paper considers stochastic first-order algorithms for minimax optimization under Polyak-- ojasiewicz (PL) conditions. We propose SPIDER-GDA for solving the finite-sum problem of the form _x _y f(x,y) 1n _i=1^n f_i(x,y), where the objective function f(x,y) is _x-PL in x and _y-PL in y; and each f_i(x,y) is L-smooth. We prove SPIDER-GDA could find an -optimal solution within O((n + n\,_x_y^2) (1/)) stochastic first-order oracle (SFO) complexity, which is better than the state-of-the-art method whose SFO upper bound is O((n + n^2/3_x_y^2) (1/)), where _x L/_x and _y L/_y. For the ill-conditioned case, we provide an accelerated algorithm to reduce the computational cost further. It achieves O((n+n\,_x_y)^2 (1/)) SFO upper bound when _y 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.

Reproductions