# Incremental Quasi-Newton Methods with Faster Superlinear Convergence Rates

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 44 references that are in the map.
- First posted on arXiv 4 Feb 2024.

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

- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [Minimizing Finite Sums with the Stochastic Average Gradient](https://mlsanity.com/paper/1309.2388/) (2013)
- [A Stochastic Quasi-Newton Method for Large-Scale Optimization](https://mlsanity.com/paper/1401.7020/) (2014)
- [Tight Complexity Bounds for Optimizing Composite Objectives](https://mlsanity.com/paper/1605.08003/) (2016)
- [A Linearly-Convergent Stochastic L-BFGS Algorithm](https://mlsanity.com/paper/1508.02087/) (2015)
- [Stochastic Quasi-Newton Methods for Nonconvex Stochastic Optimization](https://mlsanity.com/paper/1607.01231/) (2016)
- [Stochastic Block BFGS: Squeezing More Curvature out of Data](https://mlsanity.com/paper/1603.09649/) (2016)
- [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)
- [RES: Regularized Stochastic BFGS Algorithm](https://mlsanity.com/paper/1401.7625/) (2014)
- [IQN: An Incremental Quasi-Newton Method with Local Superlinear Convergence Rate](https://mlsanity.com/paper/1702.00709/) (2017)
- [A Variance Reduced Stochastic Newton Method](https://mlsanity.com/paper/1503.08316/) (2015)
- [A Stochastic Extra-Step Quasi-Newton Method for Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/1910.09373/) (2019)
- [Block BFGS Methods](https://mlsanity.com/paper/1609.00318/) (2016)
- [Explicit Superlinear Convergence Rates of The SR1 Algorithm](https://mlsanity.com/paper/2105.07162/) (2021)

## Built on by (most cited first, 2 of 2)

- [From Understanding to Excelling: Template-Free Algorithm Design through Structural-Functional Co-Evolution](https://mlsanity.com/paper/2503.10721/) (2025)
- [Incremental Gauss--Newton Methods with Superlinear Convergence Rates](https://mlsanity.com/paper/2407.03195/) (2024)

## Abstract (arXiv)

We consider the finite-sum optimization problem, where each component function is strongly convex and has Lipschitz continuous gradient and Hessian. The recently proposed incremental quasi-Newton method is based on BFGS update and achieves a local superlinear convergence rate that is dependent on the condition number of the problem. This paper proposes a more efficient quasi-Newton method by incorporating the symmetric rank-1 update into the incremental framework, which results in the condition-number-free local superlinear convergence rate. Furthermore, we can boost our method by applying the block update on the Hessian approximation, which leads to an even faster local convergence rate. The numerical experiments show the proposed methods significantly outperform the baseline methods.