Sharpened Quasi-Newton Methods: Faster Superlinear Rate and Larger Local Convergence Neighborhood
Sharpened Quasi-Newton Methods: Faster Superlinear Rate and Larger Local Convergence Neighborhood
复制标题
DOI：
--
复制
发表时间：
2022-02
期刊：
影响因子：
--
通讯作者：
Qiujiang Jin;Alec Koppel;K. Rajawat;Aryan Mokhtari
中科院分区：
文献类型：
--
作者：
Qiujiang Jin;Alec Koppel;K. Rajawat;Aryan Mokhtari
最近，拟牛顿法的非渐近分析得到了广泛的关注。特别是，一些工作已经建立了一个非渐近超线性率$\mathcal{O}（（1/\sqrt{t}）^t）$的（经典）BFGS方法，利用其牛顿方向近似的误差接近零的事实。此外，最近提出了一种贪婪的变体BFGS，它通过直接逼近Hessian而不是牛顿方向来加速收敛，并实现了快速的局部二次收敛速度。唉，与BFGS为局部超线性速率所需的迭代次数相比，Greedy-BFGS的局部二次收敛需要更多的更新。这是由于在Greedy-BFGS中，Hessian被直接近似，并且牛顿方向近似可能不如BFGS的方向近似准确。在本文中，我们缩小了这一差距，并提出了一种新的BFGS方法，具有两全其美，因为它利用了BFGS和贪婪BFGS的近似思想，同时正确地近似牛顿方向和海森矩阵。我们的理论结果表明，我们的方法在收敛速度方面优于BFGS和Greedy-BFGS，而与Greedy-BFGS相比，它以更少的步骤达到其二次收敛速度。在不同数据集上的数值实验也证实了我们的理论发现。
Non-asymptotic analysis of quasi-Newton methods have gained traction recently. In particular, several works have established a non-asymptotic superlinear rate of $\mathcal{O}((1/\sqrt{t})^t)$ for the (classic) BFGS method by exploiting the fact that its error of Newton direction approximation approaches zero. Moreover, a greedy variant of BFGS was recently proposed which accelerates its convergence by directly approximating the Hessian, instead of the Newton direction, and achieves a fast local quadratic convergence rate. Alas, the local quadratic convergence of Greedy-BFGS requires way more updates compared to the number of iterations that BFGS requires for a local superlinear rate. This is due to the fact that in Greedy-BFGS the Hessian is directly approximated and the Newton direction approximation may not be as accurate as the one for BFGS. In this paper, we close this gap and present a novel BFGS method that has the best of both worlds in that it leverages the approximation ideas of both BFGS and Greedy-BFGS to properly approximate the Newton direction and the Hessian matrix simultaneously. Our theoretical results show that our method out-performs both BFGS and Greedy-BFGS in terms of convergence rate, while it reaches its quadratic convergence rate with fewer steps compared to Greedy-BFGS. Numerical experiments on various datasets also confirm our theoretical findings.