Regularized Newton Method with Global $O(1/k^2)$ Convergence
This addresses the challenge of slow or unreliable convergence in optimization for researchers and practitioners, offering a novel hybrid approach with incremental improvements over existing methods.
The paper tackles the problem of achieving fast global convergence for Newton-type methods from any initialization on convex objectives with Lipschitz Hessians, resulting in a method with global O(1/k^2) convergence rate and cheap iterations.
We present a Newton-type method that converges fast from any initialization and for arbitrary convex objectives with Lipschitz Hessians. We achieve this by merging the ideas of cubic regularization with a certain adaptive Levenberg--Marquardt penalty. In particular, we show that the iterates given by $x^{k+1}=x^k - \bigl(\nabla^2 f(x^k) + \sqrt{H\|\nabla f(x^k)\|} \mathbf{I}\bigr)^{-1}\nabla f(x^k)$, where $H>0$ is a constant, converge globally with a $\mathcal{O}(\frac{1}{k^2})$ rate. Our method is the first variant of Newton's method that has both cheap iterations and provably fast global convergence. Moreover, we prove that locally our method converges superlinearly when the objective is strongly convex. To boost the method's performance, we present a line search procedure that does not need prior knowledge of $H$ and is provably efficient.