Adaptive Multilevel Newton: A Quadratically Convergent Optimization Method
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908849395466240 |
|---|---|
| author | Tsipinakis, Nick Parpas, Panos Voigt, Matthias |
| author_facet | Tsipinakis, Nick Parpas, Panos Voigt, Matthias |
| 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_2510_24967 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Adaptive Multilevel Newton: A Quadratically Convergent Optimization Method Tsipinakis, Nick Parpas, Panos Voigt, Matthias Optimization and Control Numerical Analysis 90C30, 90C25, 49M15, 65K05 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 Numerical Analysis 90C30, 90C25, 49M15, 65K05 |
| url | https://arxiv.org/abs/2510.24967 |