Non-asymptotic convergence analysis of quasi-Newton methods has gained
attention with a landmark result establishing an explicit superlinear rate of
O$((1/\sqrt{t})^t)$. The methods that obtain this rate, however, exhibit a
well-known drawback: they require the storage of the previous Hessian
approximation matrix or instead storing all past curvature information to form
the current Hessian inverse approximation. Limited-memory variants of
quasi-Newton methods such as the celebrated L-BFGS alleviate this issue by
leveraging a limited window of past curvature information to construct the
Hessian inverse approximation. As a result, their per iteration complexity and
storage requirement is O$(\tau d)$ where $\tau \le d$ is the size of the window
and $d$ is the problem dimension reducing the O$(d^2)$ computational cost and
memory requirement of standard quasi-Newton methods. However, to the best of
our knowledge, there is no result showing a non-asymptotic superlinear
convergence rate for any limited-memory quasi-Newton method. In this work, we
close this gap by presenting a limited-memory greedy BFGS (LG-BFGS) method that
achieves an explicit non-asymptotic superlinear rate. We incorporate
displacement aggregation, i.e., decorrelating projection, in post-processing
gradient variations, together with a basis vector selection scheme on variable
variations, which greedily maximizes a progress measure of the Hessian estimate
to the true Hessian. Their combination allows past curvature information to
remain in a sparse subspace while yielding a valid representation of the full
history. Interestingly, our established non-asymptotic superlinear convergence
rate demonstrates a trade-off between the convergence speed and memory
requirement, which to our knowledge, is the first of its kind. Numerical
results corroborate our theoretical findings and demonstrate the effectiveness
of our method.

本研究提出了一种有界存储拟牛顿方法（LG-BFGS），通过在控制存储需求的情况下利用过去的曲率信息来实现非渐近超线性收敛，并在速度和存储需求之间找到了一种平衡。