论文标题
阻尼的牛顿方法达到全局$ o \ left（\ frac {1} {k^2} \ right）$和局部二次收敛率
A Damped Newton Method Achieves Global $O\left(\frac{1}{k^2}\right)$ and Local Quadratic Convergence Rate
论文作者
论文摘要
在本文中，我们介绍了牛顿方法的第一个步骤尺寸时间表，从而获得了快速的全球和本地融合保证。特别是，a）我们证明了$ o \ left（\ frac 1 {k^2} \右）$全球速率，它与Polyak and Nesterov（2006）的Cubricalized Newton方法的最先进的全球速率与Mishchenko（2021）和Doikov and Nesterov（20221）的最新全球速率匹配，该方法是匹配的。二阶方法的局部速率，c）我们的步骤尺寸公式是简单，明确的，并且不需要解决任何子问题。我们的融合证明在仿射不变的假设下与自我纠纷概念密切相关。最后，与现有基线相比，我们的方法具有竞争性能，后者具有相同的快速全球融合保证。
In this paper, we present the first stepsize schedule for Newton method resulting in fast global and local convergence guarantees. In particular, a) we prove an $O\left( \frac 1 {k^2} \right)$ global rate, which matches the state-of-the-art global rate of cubically regularized Newton method of Polyak and Nesterov (2006) and of regularized Newton method of Mishchenko (2021) and Doikov and Nesterov (2021), b) we prove a local quadratic rate, which matches the best-known local rate of second-order methods, and c) our stepsize formula is simple, explicit, and does not require solving any subproblem. Our convergence proofs hold under affine-invariance assumptions closely related to the notion of self-concordance. Finally, our method has competitive performance when compared to existing baselines, which share the same fast global convergence guarantees.
