Abstract. 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 add the identity matrix scaled by the square root of the gradient norm to the Hessian, and obtain a method that converges with O(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 hyperparameters and is provably efficient.
Regularized Newton Method with Global O(1/k^2) Convergence
06.12.2021 15:30 - 16:30
Organiser:
R. I. Boț (U Wien), S. Sabach (Technion - Israel Institute of Technology Haifa), M. Staudigl (Maastricht U)
Location:
Zoom Meeting
Verwandte Dateien
- abstract_Mishchenko_OWOS.pdf 147 KB