Universal heavy-ball method for nonconvex optimization under Hölder continuous Hessians
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912798413422592 |
|---|---|
| author | Marumo, Naoki Takeda, Akiko |
| author_facet | Marumo, Naoki Takeda, Akiko |
| contents | We propose a new first-order method for minimizing nonconvex functions with Lipschitz continuous gradients and Hölder continuous Hessians. The proposed algorithm is a heavy-ball method equipped with two particular restart mechanisms. It finds a solution where the gradient norm is less than $ε$ in $O(H_ν^{\frac{1}{2 + 2 ν}} ε^{- \frac{4 + 3 ν}{2 + 2 ν}})$ function and gradient evaluations, where $ν\in [0, 1]$ and $H_ν$ are the Hölder exponent and constant, respectively. Our algorithm is $ν$-independent and thus universal; it automatically achieves the above complexity bound with the optimal $ν\in [0, 1]$ without knowledge of $H_ν$. In addition, the algorithm does not require other problem-dependent parameters as input, including the gradient's Lipschitz constant or the target accuracy $ε$. Numerical results illustrate that the proposed method is promising. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2303_01073 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Universal heavy-ball method for nonconvex optimization under Hölder continuous Hessians Marumo, Naoki Takeda, Akiko Optimization and Control 90C26, 90C30, 65K05 We propose a new first-order method for minimizing nonconvex functions with Lipschitz continuous gradients and Hölder continuous Hessians. The proposed algorithm is a heavy-ball method equipped with two particular restart mechanisms. It finds a solution where the gradient norm is less than $ε$ in $O(H_ν^{\frac{1}{2 + 2 ν}} ε^{- \frac{4 + 3 ν}{2 + 2 ν}})$ function and gradient evaluations, where $ν\in [0, 1]$ and $H_ν$ are the Hölder exponent and constant, respectively. Our algorithm is $ν$-independent and thus universal; it automatically achieves the above complexity bound with the optimal $ν\in [0, 1]$ without knowledge of $H_ν$. In addition, the algorithm does not require other problem-dependent parameters as input, including the gradient's Lipschitz constant or the target accuracy $ε$. Numerical results illustrate that the proposed method is promising. |
| title | Universal heavy-ball method for nonconvex optimization under Hölder continuous Hessians |
| topic | Optimization and Control 90C26, 90C30, 65K05 |
| url | https://arxiv.org/abs/2303.01073 |