论文标题
标准准Newton方法的非反应超级线性收敛
Non-asymptotic Superlinear Convergence of Standard Quasi-Newton Methods
论文作者
论文摘要
在本文中，我们研究并证明了包括Davidon-fletcher-Powell（DFP）方法的Broyden类的非反应性超线性收敛速率和Broyden-fletcher--fletcher--fletcher--goldfarb--shanno（bfgs）方法。这些准Newton方法的渐近超线性收敛速率已在文献中进行了广泛的研究，但是它们的显式局部收敛速率尚未得到充分研究。在本文中，我们为Broyden准Newton算法提供了有限的时间（非征血理）收敛分析，这是因为目标函数强烈凸出，其梯度是Lipschitz的连续，并且其Hessian Is Hessian Is Lipschitz在最佳解决方案处连续。我们表明，在最佳解决方案的本地社区中，由DFP和BFGS生成的迭代以$（1/k）^{k/2} $的超值速率收敛到最佳解决方案，其中$ k $是迭代的数量。对于目标函数是自信的情况，我们还证明了类似的局部超级线性收敛结果。几个数据集上的数值实验证实了我们的显式收敛速率界限。我们的理论保证是准方法为准牛顿方法提供非反应超线性收敛速率的首批结果之一。
In this paper, we study and prove the non-asymptotic superlinear convergence rate of the Broyden class of quasi-Newton algorithms which includes the Davidon--Fletcher--Powell (DFP) method and the Broyden--Fletcher--Goldfarb--Shanno (BFGS) method. The asymptotic superlinear convergence rate of these quasi-Newton methods has been extensively studied in the literature, but their explicit finite-time local convergence rate is not fully investigated. In this paper, we provide a finite-time (non-asymptotic) convergence analysis for Broyden quasi-Newton algorithms under the assumptions that the objective function is strongly convex, its gradient is Lipschitz continuous, and its Hessian is Lipschitz continuous at the optimal solution. We show that in a local neighborhood of the optimal solution, the iterates generated by both DFP and BFGS converge to the optimal solution at a superlinear rate of $(1/k)^{k/2}$, where $k$ is the number of iterations. We also prove a similar local superlinear convergence result holds for the case that the objective function is self-concordant. Numerical experiments on several datasets confirm our explicit convergence rate bounds. Our theoretical guarantee is one of the first results that provide a non-asymptotic superlinear convergence rate for quasi-Newton methods.
