A Fast Newton Method Under Local Lipschitz Smoothness

A new, fast second-order method is proposed that achieves the optimal
O(|\log(eps)|epsi^{-3/2})$
complexity to obtain first-order eps-stationary points.
Crucially, this is deduced without assuming the
standard global Lipschitz Hessian continuity condition, but only
using an appropriate local smoothness requirement. The algorithm
exploits Hessian information to compute a Newton step and a negative
curvature step when needed, in an approach similar to that of
\cite{GratJerToin23bIMA}.
Inexact versions of the Newton step and negative curvature are
proposed in order to reduce the cost of evaluating second-order information.
Details are given of such an iterative implementation using Krylov subspaces.
An extended algorithm for finding second-order
critical points is also developed and its complexity is again shown
to be within a log factor of the optimal one.
Initial numerical experiments are discussed for both factorised
and Krylov variants, which demonstrate the competitiveness of the
proposed algorithm.