# Limited-Memory Greedy Quasi-Newton Method with Non-asymptotic Superlinear Convergence Rate

arXiv: https://arxiv.org/abs/2306.15444 · HTML: https://mlsanity.com/paper/2306.15444/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 38 references that are in the map.
- First posted on arXiv 27 Jun 2023.

## Builds on (most cited first, 16 of 16)

- [Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergence](https://mlsanity.com/paper/1505.02250/) (2015)
- [A Progressive Batching L-BFGS Method for Machine Learning](https://mlsanity.com/paper/1802.05374/) (2018)
- [A Linearly-Convergent Stochastic L-BFGS Algorithm](https://mlsanity.com/paper/1508.02087/) (2015)
- [RSN: Randomized Subspace Newton](https://mlsanity.com/paper/1905.10874/) (2019)
- [Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update](https://mlsanity.com/paper/2107.07480/) (2021)
- [Greedy Quasi-Newton Methods with Explicit Superlinear Convergence](https://mlsanity.com/paper/2002.00657/) (2020)
- [Global Convergence of Online Limited Memory BFGS](https://mlsanity.com/paper/1409.2045/) (2014)
- [Non-asymptotic Superlinear Convergence of Standard Quasi-Newton Methods](https://mlsanity.com/paper/2003.13607/) (2020)
- [Adaptive Newton Sketch: Linear-time Optimization with Quadratic Convergence and Effective Hessian Dimensionality](https://mlsanity.com/paper/2105.07291/) (2021)
- [Rates of superlinear convergence for classical quasi-Newton methods](https://mlsanity.com/paper/2003.09174/) (2020)
- [Precise expressions for random projections: Low-rank approximation and randomized Newton](https://mlsanity.com/paper/2006.10653/) (2020)
- [Quasi-Newton Methods for Machine Learning: Forget the Past, Just Sample](https://mlsanity.com/paper/1901.09997/) (2019)
- [Quasi-Newton Methods: Superlinear Convergence Without Line Searches for Self-Concordant Functions](https://mlsanity.com/paper/1612.06965/) (2016)
- [A Robust Multi-Batch L-BFGS Method for Machine Learning](https://mlsanity.com/paper/1707.08552/) (2017)
- [Sharpened Quasi-Newton Methods: Faster Superlinear Rate and Larger Local Convergence Neighborhood](https://mlsanity.com/paper/2202.10538/) (2022)
- [Limited-Memory BFGS with Displacement Aggregation](https://mlsanity.com/paper/1903.03471/) (2019)

## Abstract (arXiv)

Non-asymptotic convergence analysis of quasi-Newton methods has gained attention with a landmark result establishing an explicit local superlinear rate of O((1/√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 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(τ d) where τ≤ d is the size of the window and d is the problem dimension reducing the O(d2) 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 can achieve 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 an explicit 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.