Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2507.13804 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912766437097472 |
|---|---|
| author | Muşat, Andreea-Alexandra Boumal, Nicolas |
| author_facet | Muşat, Andreea-Alexandra Boumal, Nicolas |
| contents | It is known that gradient descent (GD) on a $C^2$ cost function generically avoids strict saddle points when using a small, constant step size. However, no such guarantee existed for GD with a line-search method. We provide one for a modified version of the standard Armijo backtracking method with generic, arbitrarily large initial step size. The proof underlines the double role of the Luzin $N^{-1}$ property for the iteration maps, and allows to forgo the habitual Lipschitz gradient assumption.
We extend this to the Riemannian setting (RGD), assuming the retraction is real analytic (though the cost function still only needs to be $C^2$). In closing, we also improve guarantees for RGD with a constant step size in some scenarios. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_13804 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Gradient descent avoids strict saddles with a simple line-search method too Muşat, Andreea-Alexandra Boumal, Nicolas Optimization and Control Numerical Analysis Dynamical Systems 90C30 (Primary) 65K05, 37C75, 58K05 (Secondary) It is known that gradient descent (GD) on a $C^2$ cost function generically avoids strict saddle points when using a small, constant step size. However, no such guarantee existed for GD with a line-search method. We provide one for a modified version of the standard Armijo backtracking method with generic, arbitrarily large initial step size. The proof underlines the double role of the Luzin $N^{-1}$ property for the iteration maps, and allows to forgo the habitual Lipschitz gradient assumption. We extend this to the Riemannian setting (RGD), assuming the retraction is real analytic (though the cost function still only needs to be $C^2$). In closing, we also improve guarantees for RGD with a constant step size in some scenarios. |
| title | Gradient descent avoids strict saddles with a simple line-search method too |
| topic | Optimization and Control Numerical Analysis Dynamical Systems 90C30 (Primary) 65K05, 37C75, 58K05 (Secondary) |
| url | https://arxiv.org/abs/2507.13804 |