Efficient First Order Method for Saddle Point Problems with Higher Order Smoothness
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912147371458560 |
|---|---|
| author | Wang, Nuozhou Zhang, Junyu Zhang, Shuzhong |
| author_facet | Wang, Nuozhou Zhang, Junyu Zhang, Shuzhong |
| contents | This paper studies the complexity of finding approximate stationary points for the smooth nonconvex-strongly-concave (NC-SC) saddle point problem: $\min_x\max_yf(x,y)$. Under the standard first-order smoothness conditions where $f$ is $\ell$-smooth in both arguments and $μ_y$-strongly concave in $y$, existing literature shows that the optimal complexity for first-order methods to obtain an $ε$-stationary point is $\tilde{O}\big(\sqrt{κ_y}\ellε^{-2}\big)$, where $κ_y=\ell/μ_y$ is the condition number. However, when $Φ(x):=\max_y f(x,y)$ has $L_2$-Lipschitz continuous Hessian in addition, we derive a first-order algorithm with an $\tilde{O}\big(\sqrt{κ_y}\ell^{1/2}L_2^{1/4}ε^{-7/4}\big)$ complexity by designing an accelerated proximal point algorithm enhanced with the "Convex Until Proven Guilty" technique. Moreover, an improved $Ω\big(\sqrt{κ_y}\ell^{3/7}L_2^{2/7}ε^{-12/7}\big)$ lower bound for first-order method is also derived for sufficiently small $ε$. As a result, given the second-order smoothness of the problem, the complexity of our method improves the state-of-the-art result by a factor of $\tilde{O}\big(\big(\frac{\ell^2}{L_2ε}\big)^{1/4}\big)$, while almost matching the lower bound except for a small $\tilde{O}\big(\big(\frac{\ell^2}{L_2ε}\big)^{1/28}\big)$ factor. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2304_12453 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Efficient First Order Method for Saddle Point Problems with Higher Order Smoothness Wang, Nuozhou Zhang, Junyu Zhang, Shuzhong Optimization and Control This paper studies the complexity of finding approximate stationary points for the smooth nonconvex-strongly-concave (NC-SC) saddle point problem: $\min_x\max_yf(x,y)$. Under the standard first-order smoothness conditions where $f$ is $\ell$-smooth in both arguments and $μ_y$-strongly concave in $y$, existing literature shows that the optimal complexity for first-order methods to obtain an $ε$-stationary point is $\tilde{O}\big(\sqrt{κ_y}\ellε^{-2}\big)$, where $κ_y=\ell/μ_y$ is the condition number. However, when $Φ(x):=\max_y f(x,y)$ has $L_2$-Lipschitz continuous Hessian in addition, we derive a first-order algorithm with an $\tilde{O}\big(\sqrt{κ_y}\ell^{1/2}L_2^{1/4}ε^{-7/4}\big)$ complexity by designing an accelerated proximal point algorithm enhanced with the "Convex Until Proven Guilty" technique. Moreover, an improved $Ω\big(\sqrt{κ_y}\ell^{3/7}L_2^{2/7}ε^{-12/7}\big)$ lower bound for first-order method is also derived for sufficiently small $ε$. As a result, given the second-order smoothness of the problem, the complexity of our method improves the state-of-the-art result by a factor of $\tilde{O}\big(\big(\frac{\ell^2}{L_2ε}\big)^{1/4}\big)$, while almost matching the lower bound except for a small $\tilde{O}\big(\big(\frac{\ell^2}{L_2ε}\big)^{1/28}\big)$ factor. |
| title | Efficient First Order Method for Saddle Point Problems with Higher Order Smoothness |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2304.12453 |