Heavy-ball Differential Equation Achieves $O(\varepsilon^{-7/4})$ Convergence for Nonconvex Functions
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_ | 1866912356615847936 |
|---|---|
| author | Okamura, Kaito Marumo, Naoki Takeda, Akiko |
| author_facet | Okamura, Kaito Marumo, Naoki Takeda, Akiko |
| contents | First-order optimization methods for nonconvex functions with Lipschitz continuous gradient and Hessian have been extensively studied. State-of-the-art methods for finding an $\varepsilon$-stationary point within $O(\varepsilon^{-{7/4}})$ or $\tilde{O}(\varepsilon^{-{7/4}})$ gradient evaluations are based on Nesterov's accelerated gradient descent (AGD) or Polyak's heavy-ball (HB) method. However, these algorithms employ additional mechanisms, such as restart schemes and negative curvature exploitation, which complicate their behavior and make it challenging to apply them to more advanced settings (e.g., stochastic optimization). As a first step in investigating whether a simple algorithm with $O(\varepsilon^{-{7/4}})$ complexity can be constructed without such additional mechanisms, we study the HB differential equation, a continuous-time analogue of the AGD and HB methods. We prove that its dynamics attain an $\varepsilon$-stationary point within $O(\varepsilon^{-{7/4}})$ time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_06100 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Heavy-ball Differential Equation Achieves $O(\varepsilon^{-7/4})$ Convergence for Nonconvex Functions Okamura, Kaito Marumo, Naoki Takeda, Akiko Optimization and Control 90C26 (Primary), 90C30 (Secondary), 65K05, 90C06 First-order optimization methods for nonconvex functions with Lipschitz continuous gradient and Hessian have been extensively studied. State-of-the-art methods for finding an $\varepsilon$-stationary point within $O(\varepsilon^{-{7/4}})$ or $\tilde{O}(\varepsilon^{-{7/4}})$ gradient evaluations are based on Nesterov's accelerated gradient descent (AGD) or Polyak's heavy-ball (HB) method. However, these algorithms employ additional mechanisms, such as restart schemes and negative curvature exploitation, which complicate their behavior and make it challenging to apply them to more advanced settings (e.g., stochastic optimization). As a first step in investigating whether a simple algorithm with $O(\varepsilon^{-{7/4}})$ complexity can be constructed without such additional mechanisms, we study the HB differential equation, a continuous-time analogue of the AGD and HB methods. We prove that its dynamics attain an $\varepsilon$-stationary point within $O(\varepsilon^{-{7/4}})$ time. |
| title | Heavy-ball Differential Equation Achieves $O(\varepsilon^{-7/4})$ Convergence for Nonconvex Functions |
| topic | Optimization and Control 90C26 (Primary), 90C30 (Secondary), 65K05, 90C06 |
| url | https://arxiv.org/abs/2406.06100 |