Higher-order Newton methods with polynomial work per iteration

Amir Ali Ahmadi, Abraar Chaudhry, Jeffrey Zhang

Research output: Contribution to journalArticlepeer-review

Abstract

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 dth-order method uses semidefinite programming to construct and minimize a sum of squares-convex approximation to the dth-order Taylor expansion of the function we wish to minimize. We prove that our dth-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.

Original languageEnglish (US)
Article number109808
JournalAdvances in Mathematics
Volume452
DOIs
StatePublished - Aug 2024
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Mathematics

Keywords

  • Convergence analysis
  • Newton's method
  • Semidefinite programming
  • Sum of squares methods
  • Tensor methods

Fingerprint

Dive into the research topics of 'Higher-order Newton methods with polynomial work per iteration'. Together they form a unique fingerprint.

Cite this