Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2305.08742 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908865656782848 |
|---|---|
| author | Tsipinakis, Nick Tigkas, Panagiotis Parpas, Panos |
| author_facet | Tsipinakis, Nick Tigkas, Panagiotis Parpas, Panos |
| contents | Newton's method may exhibit slower convergence than vanilla Gradient Descent in its initial phase on strongly convex problems. Classical Newton-type multilevel methods mitigate this but, like Gradient Descent, achieve only linear convergence near the minimizer. We introduce an adaptive multilevel Newton-type method with a principled automatic switch to full Newton once its quadratic phase is reached. The local quadratic convergence for strongly convex functions with Lipschitz continuous Hessians and for self-concordant functions is established and confirmed empirically. Although per-iteration cost can exceed that of classical multilevel schemes, the method is efficient and consistently outperforms Newton's method, Gradient Descent, and the multilevel Newton method, indicating that second-order methods can outperform first-order methods even when Newton's method is initially slow. The promising empirical results open new avenues for designing reduced-cost second- and high-order methods with extremely fast convergence rates. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2305_08742 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Adaptive Multilevel Newton: A Quadratically Convergent Optimization Method Tsipinakis, Nick Tigkas, Panagiotis Parpas, Panos Optimization and Control Newton's method may exhibit slower convergence than vanilla Gradient Descent in its initial phase on strongly convex problems. Classical Newton-type multilevel methods mitigate this but, like Gradient Descent, achieve only linear convergence near the minimizer. We introduce an adaptive multilevel Newton-type method with a principled automatic switch to full Newton once its quadratic phase is reached. The local quadratic convergence for strongly convex functions with Lipschitz continuous Hessians and for self-concordant functions is established and confirmed empirically. Although per-iteration cost can exceed that of classical multilevel schemes, the method is efficient and consistently outperforms Newton's method, Gradient Descent, and the multilevel Newton method, indicating that second-order methods can outperform first-order methods even when Newton's method is initially slow. The promising empirical results open new avenues for designing reduced-cost second- and high-order methods with extremely fast convergence rates. |
| title | Adaptive Multilevel Newton: A Quadratically Convergent Optimization Method |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2305.08742 |