Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2311.06374 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914832982212608 |
|---|---|
| author | Ahmadi, Amir Ali Chaudhry, Abraar Zhang, Jeffrey |
| author_facet | Ahmadi, Amir Ali Chaudhry, Abraar Zhang, Jeffrey |
| contents | We present generalizations of Newton's method that incorporate derivatives of an arbitrary order $d$ but maintain a polynomial dependence on dimension in their cost per iteration. At each step, our $d^{\text{th}}$-order method uses semidefinite programming to construct and minimize a sum of squares-convex approximation to the $d^{\text{th}}$-order Taylor expansion of the function we wish to minimize. We prove that our $d^{\text{th}}$-order method has local convergence of order $d$. This results in lower oracle complexity compared to the classical Newton method. We show on numerical examples that basins of attraction around local minima can get larger as $d$ increases. Under additional assumptions, we present a modified algorithm, again with polynomial cost per iteration, which is globally convergent and has local convergence of order $d$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_06374 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Higher-Order Newton Methods with Polynomial Work per Iteration Ahmadi, Amir Ali Chaudhry, Abraar Zhang, Jeffrey Optimization and Control Machine Learning We present generalizations of Newton's method that incorporate derivatives of an arbitrary order $d$ but maintain a polynomial dependence on dimension in their cost per iteration. At each step, our $d^{\text{th}}$-order method uses semidefinite programming to construct and minimize a sum of squares-convex approximation to the $d^{\text{th}}$-order Taylor expansion of the function we wish to minimize. We prove that our $d^{\text{th}}$-order method has local convergence of order $d$. This results in lower oracle complexity compared to the classical Newton method. We show on numerical examples that basins of attraction around local minima can get larger as $d$ increases. Under additional assumptions, we present a modified algorithm, again with polynomial cost per iteration, which is globally convergent and has local convergence of order $d$. |
| title | Higher-Order Newton Methods with Polynomial Work per Iteration |
| topic | Optimization and Control Machine Learning |
| url | https://arxiv.org/abs/2311.06374 |