AGDA+: Proximal Alternating Gradient Descent Ascent Method with a Nonmonotone Adaptive Step-Size Search for Nonconvex Minimax Problems
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917904509829120 |
|---|---|
| author | Zhang, Xuan Xu, Qiushui Aybat, Necdet Serhat |
| author_facet | Zhang, Xuan Xu, Qiushui Aybat, Necdet Serhat |
| contents | We consider double-regularized nonconvex-strongly concave (NCSC) minimax problems of the form $(P):\min_{x\in\mathcal{X}} \max_{y\in\mathcal{Y}}g(x)+f(x,y)-h(y)$, where $g$, $h$ are closed convex, $f$ is $L$-smooth in $(x,y)$ and strongly concave in $y$. We propose a proximal alternating gradient descent ascent method AGDA+ that can adaptively choose nonmonotone primal-dual stepsizes to compute an approximate stationary point for $(P)$ without requiring the knowledge of the global Lipschitz constant $L$ and the concavity modulus $μ$. Using a nonmonotone step-size search (backtracking) scheme, AGDA+ stands out by its ability to exploit the local Lipschitz structure and eliminates the need for precise tuning of hyper-parameters. AGDA+ achieves the optimal iteration complexity of $\mathcal{O}(ε^{-2})$ and it is the first step-size search method for NCSC minimax problems that require only $3$ calls to $\nabla f$ on average per backtracking iteration. The numerical experiments demonstrate its robustness and efficiency. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_14371 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | AGDA+: Proximal Alternating Gradient Descent Ascent Method with a Nonmonotone Adaptive Step-Size Search for Nonconvex Minimax Problems Zhang, Xuan Xu, Qiushui Aybat, Necdet Serhat Optimization and Control We consider double-regularized nonconvex-strongly concave (NCSC) minimax problems of the form $(P):\min_{x\in\mathcal{X}} \max_{y\in\mathcal{Y}}g(x)+f(x,y)-h(y)$, where $g$, $h$ are closed convex, $f$ is $L$-smooth in $(x,y)$ and strongly concave in $y$. We propose a proximal alternating gradient descent ascent method AGDA+ that can adaptively choose nonmonotone primal-dual stepsizes to compute an approximate stationary point for $(P)$ without requiring the knowledge of the global Lipschitz constant $L$ and the concavity modulus $μ$. Using a nonmonotone step-size search (backtracking) scheme, AGDA+ stands out by its ability to exploit the local Lipschitz structure and eliminates the need for precise tuning of hyper-parameters. AGDA+ achieves the optimal iteration complexity of $\mathcal{O}(ε^{-2})$ and it is the first step-size search method for NCSC minimax problems that require only $3$ calls to $\nabla f$ on average per backtracking iteration. The numerical experiments demonstrate its robustness and efficiency. |
| title | AGDA+: Proximal Alternating Gradient Descent Ascent Method with a Nonmonotone Adaptive Step-Size Search for Nonconvex Minimax Problems |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2406.14371 |