Faster Stochastic Algorithms for Minimax Optimization under Polyak--Łojasiewicz Conditions
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914393835438080 |
|---|---|
| author | Chen, Lesi Yao, Boyuan Luo, Luo |
| author_facet | Chen, Lesi Yao, Boyuan Luo, Luo |
| contents | 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 (κ_y/ε) \log(1/ε)\big)$ SFO upper bound when $κ_y \gtrsim \sqrt{n}$. Our ideas can also be applied to a more general setting where the objective function only satisfies the PL condition for one variable. Numerical experiments validate the superiority of proposed methods. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_15868 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Faster Stochastic Algorithms for Minimax Optimization under Polyak--Łojasiewicz Conditions Chen, Lesi Yao, Boyuan Luo, Luo Optimization and Control Machine Learning 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 (κ_y/ε) \log(1/ε)\big)$ SFO upper bound when $κ_y \gtrsim \sqrt{n}$. Our ideas can also be applied to a more general setting where the objective function only satisfies the PL condition for one variable. Numerical experiments validate the superiority of proposed methods. |
| title | Faster Stochastic Algorithms for Minimax Optimization under Polyak--Łojasiewicz Conditions |
| topic | Optimization and Control Machine Learning |
| url | https://arxiv.org/abs/2307.15868 |