Higher-Order Newton Methods with Polynomial Work per Iteration
Amir Ali Ahmadi Abraar Chaudhry Jeffrey Zhang
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$.