Sharpened Quasi-Newton Methods: Faster Superlinear Rate and Larger Local Convergence Neighborhood
Qiujiang Jin Alec Koppel Ketan Rajawat Aryan Mokhtari Department of Electrical and Computer Engineering, The University of Texas at Austin, Austin, TX, USA. Bellevue, WA, USA. of Electrical Engineering, Indian Institute of Technology Kanpur, Kanpur, UP, INDIA. of Electrical and Computer Engineering, The University of Texas at Austin, Austin, TX, USA.
Abstract
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 i
中文速览
准经典BFGS法虽然能较快地逼近牛顿方向从而在早期收敛表现良好，但其Hessian矩阵近似精度有限；而Greedy-BFGS通过贪心选取更新方向直接逼近Hessian矩阵，最终能达到二次收敛速率，却需要更多迭代步数才能进入快速收敛阶段。本文提出"Sharpened-BFGS"，在每次迭代中同时执行一步标准BFGS更新（沿位移方向逼近牛顿方向）和一步贪心BFGS更新（最大化Hessian近似进展），从而兼顾两者的优点。理论分析表明，Sharpened-BFGS的收敛速率严格优于BFGS和Greedy-BFGS，同时比Greedy-BFGS更早进入二次收敛阶段，且每次迭代的计算开销与两者相同，均为O(d²)。多个数据集上的数值实验也验证了这一理论结论，说明该方法在不增加额外计算负担的前提下，实现了拟牛顿法收敛性能的切实提升。
原文 arXiv:2202.10538;中英对照 + 大白话阅读 https://aha.fim.ai/paper/2202.10538v2