Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2502.04799 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911241735241728 |
|---|---|
| author | Zhou, Yuhao Xu, Jintao Li, Bingrui Bao, Chenglong Ding, Chao Zhu, Jun |
| author_facet | Zhou, Yuhao Xu, Jintao Li, Bingrui Bao, Chenglong Ding, Chao Zhu, Jun |
| contents | Finding an $ε$-stationary point of a nonconvex function with a Lipschitz continuous Hessian is a central problem in optimization. Regularized Newton methods are a classical tool and have been studied extensively, yet they still face a trade-off between global and local convergence. Whether a parameter-free algorithm of this type can simultaneously achieve optimal global complexity and quadratic local convergence remains an open question. To bridge this long-standing gap, we propose a new class of regularizers constructed from the current and previous gradients, and leverage the conjugate gradient approach with a negative curvature monitor to solve the regularized Newton equation. The proposed algorithm is adaptive, requiring no prior knowledge of the Hessian Lipschitz constant, and achieves a global complexity of $O(ε^{-3/2})$ in terms of the second-order oracle calls, and $\tilde{O}(ε^{-7/4})$ for Hessian-vector products, respectively. When the iterates converge to a point where the Hessian is positive definite, the method exhibits quadratic local convergence. Preliminary numerical results, including training the physics-informed neural networks, illustrate the competitiveness of our algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_04799 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Regularized Newton Method for Nonconvex Optimization with Global and Local Complexity Guarantees Zhou, Yuhao Xu, Jintao Li, Bingrui Bao, Chenglong Ding, Chao Zhu, Jun Optimization and Control Machine Learning Finding an $ε$-stationary point of a nonconvex function with a Lipschitz continuous Hessian is a central problem in optimization. Regularized Newton methods are a classical tool and have been studied extensively, yet they still face a trade-off between global and local convergence. Whether a parameter-free algorithm of this type can simultaneously achieve optimal global complexity and quadratic local convergence remains an open question. To bridge this long-standing gap, we propose a new class of regularizers constructed from the current and previous gradients, and leverage the conjugate gradient approach with a negative curvature monitor to solve the regularized Newton equation. The proposed algorithm is adaptive, requiring no prior knowledge of the Hessian Lipschitz constant, and achieves a global complexity of $O(ε^{-3/2})$ in terms of the second-order oracle calls, and $\tilde{O}(ε^{-7/4})$ for Hessian-vector products, respectively. When the iterates converge to a point where the Hessian is positive definite, the method exhibits quadratic local convergence. Preliminary numerical results, including training the physics-informed neural networks, illustrate the competitiveness of our algorithm. |
| title | A Regularized Newton Method for Nonconvex Optimization with Global and Local Complexity Guarantees |
| topic | Optimization and Control Machine Learning |
| url | https://arxiv.org/abs/2502.04799 |