A Stochastic GDA Method With Backtracking For Solving Nonconvex Concave Minimax Problems
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866918498672836608 |
|---|---|
| author | Aybat, Necdet Serhat Xu, Qiushui Zhang, Xuan Gürbüzbalaban, Mert |
| author_facet | Aybat, Necdet Serhat Xu, Qiushui Zhang, Xuan Gürbüzbalaban, Mert |
| contents | We propose a stochastic GDA (gradient descent ascent) method with backtracking (SGDA-B) to solve nonconvex-concave (NCC) minimax problems of the form: $\min_{\mathbf{x}} \max_y \sum_{i=1}^N g_i(x_i)+f(\mathbf{x},y)-h(y)$, where $h$ and $g_i$ for $i=1,\cdots,N$ are closed, convex functions, and for some $L,μ\geq 0$, $f$ is $L$-smooth and $f(\mathbf{x},\cdot)$ is $μ$-strongly concave for all $\mathbf{x}$ in the problem domain. We consider the stochastic setting where one only has an access to an unbiased stochastic oracle of $\nabla f$ with a finite variance bound $σ^2$. While most of the existing methods assume knowledge of $L$, $μ$ and/or $σ^2$, SGDA-B is agnostic to all of these problem parameters. Moreover, SGDA-B can support random block-coordinate updates. In the deterministic setting, i.e., $σ^2=0$ and one can compute $\nabla f$ exactly, SGDA-B can compute an $ε$-stationary point within $\mathcal{O}(Lκ^2/ε^2)$ and $\mathcal{O}(L^3/ε^4)$ gradient calls when $μ>0$ and $μ=0$, respectively, where $κ\triangleq L/μ$. In the stochastic setting, i.e., $σ^2>0$, for any $p\in(0,1)$ and $ε>0$, it can compute an $ε$-stationary point with high probability, which requires $\mathcal{O}(L κ^3 ε^{-4} \log^2(1/p))$ and $\tilde{\mathcal{O}}(L^4ε^{-7}\log^2(1/p))$ stochastic oracle calls, with probability at least $1-p$, when $μ>0$ and $μ=0$, respectively. To our knowledge, SGDA-B is the first GDA-type method with backtracking to solve NCC minimax problems and achieves the best complexity among the methods that are agnostic to $L$, $μ$ and $σ^2$. We also provide numerical results for SGDA-B on a distributionally robust learning problem illustrating the potential performance gains that can be achieved by SGDA-B. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_07806 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Stochastic GDA Method With Backtracking For Solving Nonconvex Concave Minimax Problems Aybat, Necdet Serhat Xu, Qiushui Zhang, Xuan Gürbüzbalaban, Mert Optimization and Control We propose a stochastic GDA (gradient descent ascent) method with backtracking (SGDA-B) to solve nonconvex-concave (NCC) minimax problems of the form: $\min_{\mathbf{x}} \max_y \sum_{i=1}^N g_i(x_i)+f(\mathbf{x},y)-h(y)$, where $h$ and $g_i$ for $i=1,\cdots,N$ are closed, convex functions, and for some $L,μ\geq 0$, $f$ is $L$-smooth and $f(\mathbf{x},\cdot)$ is $μ$-strongly concave for all $\mathbf{x}$ in the problem domain. We consider the stochastic setting where one only has an access to an unbiased stochastic oracle of $\nabla f$ with a finite variance bound $σ^2$. While most of the existing methods assume knowledge of $L$, $μ$ and/or $σ^2$, SGDA-B is agnostic to all of these problem parameters. Moreover, SGDA-B can support random block-coordinate updates. In the deterministic setting, i.e., $σ^2=0$ and one can compute $\nabla f$ exactly, SGDA-B can compute an $ε$-stationary point within $\mathcal{O}(Lκ^2/ε^2)$ and $\mathcal{O}(L^3/ε^4)$ gradient calls when $μ>0$ and $μ=0$, respectively, where $κ\triangleq L/μ$. In the stochastic setting, i.e., $σ^2>0$, for any $p\in(0,1)$ and $ε>0$, it can compute an $ε$-stationary point with high probability, which requires $\mathcal{O}(L κ^3 ε^{-4} \log^2(1/p))$ and $\tilde{\mathcal{O}}(L^4ε^{-7}\log^2(1/p))$ stochastic oracle calls, with probability at least $1-p$, when $μ>0$ and $μ=0$, respectively. To our knowledge, SGDA-B is the first GDA-type method with backtracking to solve NCC minimax problems and achieves the best complexity among the methods that are agnostic to $L$, $μ$ and $σ^2$. We also provide numerical results for SGDA-B on a distributionally robust learning problem illustrating the potential performance gains that can be achieved by SGDA-B. |
| title | A Stochastic GDA Method With Backtracking For Solving Nonconvex Concave Minimax Problems |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2403.07806 |