People who're familiar with Newton's method might be surprised at the convergence rate. 1/k^2 is slower than the textbook rate for Newton's method with line sea

People who're familiar with Newton's method might be surprised at the convergence rate. 1/k^2 is slower than the textbook rate for Newton's method with line search, which is 2^{-2^k}, basically implying convergence in a constant number of steps. The rate in this paper seems to be no faster than plain gradient descent on a strongly convex function! So why go through the trouble of the much more complicated update? Because the textbook proof of the fast convergence of Newton's method make additional assumptions on the objective function, for example that it is strongly convex, or it is self concordant. This paper only assumes Lipschitz continuous Hessians. The idea of dampening the Hessian is old (it's sometimes called "damped newton method", or "trust region newton method", or "levenberg-marquardt", though the latter two refer to more specific ideas). This paper offers a view to how much dampening to apply.