The Hacker News thread about the following preprint may be of interest, since there are members who write and use optimization codes.
Regularized Newton Method with Global O(1/k2) Convergence
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 xk+1=xk−(∇2f(xk)+H∥∇f(xk)∥−−−−−−−−−√I)−1∇f(xk), where H>0 is a constant, converge globally with a O(1k2) 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.