Towards explicit superlinear convergence rate for SR1

• 成果类型: Article
• 署名作者: Ye, Haishan; Lin, Dachao; Chang, Xiangyu; Zhang, Zhihua
• 署名单位: Xi'an Jiaotong University; Peking University; Peking University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-022-01865-w
• 发表日期: 2023
• 页码: 1273-1303
• 关键词: quasi-newton methods

摘要

We study the convergence rate of the famous Symmetric Rank-1 (SR1) algorithm, which has wide applications in different scenarios. Although it has been extensively investigated, SR1 still lacks a non-asymptotic superlinear rate compared with other quasi-Newton methods such as DFP and BFGS. In this paper, we address the aforementioned issue to obtain the first explicit non-asymptotic rates of superlinear convergence for the vanilla SR1 methods with a correction strategy that is used to achieve numerical stability. Specifically, the vanilla SR1 with the correction strategy achieves the rate of the form ( 2n ln (4x)/k)(k/2) for general smooth strongly-convex functions where k is the iteration counter, x is the condition number of the objective function, and n is the dimensionality of the problem. Furthermore, the vanilla SRI algorithm enjoys a little faster convergence rate and can find the optima of the quadratic objective function at most n steps.