Towards explicit superlinear convergence rate for SR1

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 (2nln(4ϰ)k)k/2 for general smooth strongly-convex functions where k is the iteration counter, ϰ is the condition number of the objective function, and n is the dimensionality of the problem. Furthermore, the vanilla SR1 algorithm enjoys a little faster convergence rate and can find the optima of the quadratic objective function at most n steps.