Faster Stochastic Algorithms for Minimax Optimization under Polyak--Łojasiewicz Conditions
This work addresses faster optimization for machine learning tasks like adversarial training, offering incremental algorithmic improvements for researchers in optimization and AI.
This paper tackles the problem of stochastic minimax optimization under Polyak–Łojasiewicz conditions by proposing SPIDER-GDA, which achieves an SFO complexity of O((n + sqrt(n)κ_xκ_y^2)log(1/ε)), improving upon the previous state-of-the-art of O((n + n^{2/3}κ_xκ_y^2)log(1/ε)).
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 $\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 $μ_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 ${\mathcal O}\left((n + \sqrt{n}\,κ_xκ_y^2)\log (1/ε)\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}κ_xκ_y^2)\log (1/ε)\big)$, where $κ_x\triangleq L/μ_x$ and $κ_y\triangleq L/μ_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}\,κ_xκ_y)\log^2 (1/ε)\big)$ SFO upper bound when $κ_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.