A Fast Newton Method Under Local Lipschitz Smoothness
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910024094187520 |
|---|---|
| author | Gratton, Serge Jerad, Sadok Toint, Philippe L. |
| author_facet | Gratton, Serge Jerad, Sadok Toint, Philippe L. |
| contents | A new, fast second-order method is proposed that achieves the optimal $\mathcal{O}\left(|\log(ε)|ε^{-3/2}\right)$ complexity to obtain first-order $ε$-stationary points. Crucially, this is deduced without assuming the standard global Lipschitz Hessian continuity condition, but only using an appropriate local smoothness requirement. The algorithm exploits Hessian information to compute a Newton step and a negative curvature step when needed, in an approach similar to that of the AN2C method.Inexact versions of the Newton step and negative curvature are proposed in order to reduce the cost of evaluating second-order information. Details are given of such an iterative implementation using Krylov subspaces. An extended algorithm for finding second-order critical points is also developed and its complexity is again shown to be within a log factor of the optimal one. Initial numerical experiments are discussed for both factorised and Krylov variants, which demonstrate the competitiveness of the proposed algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_04807 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Fast Newton Method Under Local Lipschitz Smoothness Gratton, Serge Jerad, Sadok Toint, Philippe L. Optimization and Control A new, fast second-order method is proposed that achieves the optimal $\mathcal{O}\left(|\log(ε)|ε^{-3/2}\right)$ complexity to obtain first-order $ε$-stationary points. Crucially, this is deduced without assuming the standard global Lipschitz Hessian continuity condition, but only using an appropriate local smoothness requirement. The algorithm exploits Hessian information to compute a Newton step and a negative curvature step when needed, in an approach similar to that of the AN2C method.Inexact versions of the Newton step and negative curvature are proposed in order to reduce the cost of evaluating second-order information. Details are given of such an iterative implementation using Krylov subspaces. An extended algorithm for finding second-order critical points is also developed and its complexity is again shown to be within a log factor of the optimal one. Initial numerical experiments are discussed for both factorised and Krylov variants, which demonstrate the competitiveness of the proposed algorithm. |
| title | A Fast Newton Method Under Local Lipschitz Smoothness |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2505.04807 |