<story><title>Regularized Newton Method with Global $O(1/k^2)$ Convergence</title><url>https://arxiv.org/abs/2112.02089</url></story><parent_chain></parent_chain><comment><author>rahimiali</author><text>People who&amp;#x27;re familiar with Newton&amp;#x27;s method might be surprised at the convergence rate. 1&amp;#x2F;k^2 is slower than the textbook rate for Newton&amp;#x27;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?&lt;p&gt;Because the textbook proof of the fast convergence of Newton&amp;#x27;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.&lt;p&gt;The idea of dampening the Hessian is old (it&amp;#x27;s sometimes called &amp;quot;damped newton method&amp;quot;, or &amp;quot;trust region newton method&amp;quot;, or &amp;quot;levenberg-marquardt&amp;quot;, though the latter two refer to more specific ideas). This paper offers a view to how much dampening to apply.</text></comment>
<story><title>Regularized Newton Method with Global $O(1/k^2)$ Convergence</title><url>https://arxiv.org/abs/2112.02089</url></story><parent_chain></parent_chain><comment><author>civilized</author><text>This is very interesting. It looks like the innovation is to scale the identity matrix in the L-M step formula by the square root of the norm of the gradient. Very simple and elegant, and trivial to implement. Lots of people are going to be shaking their heads wondering why they didn&amp;#x27;t think of this first.&lt;p&gt;The motivation for the idea is very nice and easy to understand. The author completely explains it before the middle of the second page. I encourage you to look at it if you know enough vector calc to make sense of the notation. Essentially, he takes a well-known fast-converging method whose steps are hard to compute and shows how these steps can be approximated cheaply while still retaining much of the convergence rate benefit.&lt;p&gt;This may have implications for many large-scale optimization problems as L-M regularized Newton steps are a sort of natural halfway house between gradient descent and the full Newton&amp;#x27;s method, both theoretically and practically.</text></comment>