# Sharpened Lazy Incremental Quasi-Newton Method

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 59 references that are in the map.
- First posted on arXiv 26 May 2023.

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

- [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016)
- [Improved Techniques for Training Score-Based Generative Models](https://mlsanity.com/paper/2006.09011/) (2020)
- [Prototypical Contrastive Learning of Unsupervised Representations](https://mlsanity.com/paper/2005.04966/) (2020)
- [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)
- [Human Pose Regression with Residual Log-likelihood Estimation](https://mlsanity.com/paper/2107.11291/) (2021)
- [Error Compensated Quantized SGD and its Applications to Large-scale Distributed Optimization](https://mlsanity.com/paper/1806.08054/) (2018)
- [Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergence](https://mlsanity.com/paper/1505.02250/) (2015)
- [A Stochastic Quasi-Newton Method for Large-Scale Optimization](https://mlsanity.com/paper/1401.7020/) (2014)
- [Newton-Type Methods for Non-Convex Optimization Under Inexact Hessian Information](https://mlsanity.com/paper/1708.07164/) (2017)
- [A Linearly-Convergent Stochastic L-BFGS Algorithm](https://mlsanity.com/paper/1508.02087/) (2015)
- [Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares](https://mlsanity.com/paper/1411.0347/) (2014)
- [Stochastic Newton and Cubic Newton Methods with Simple Local Linear-Quadratic Rates](https://mlsanity.com/paper/1912.01597/) (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)
- [RES: Regularized Stochastic BFGS Algorithm](https://mlsanity.com/paper/1401.7625/) (2014)
- [Solving Ridge Regression using Sketched Preconditioned SVRG](https://mlsanity.com/paper/1602.02350/) (2016)
- [Katyusha X: Practical Momentum Method for Stochastic Sum-of-Nonconvex Optimization](https://mlsanity.com/paper/1802.03866/) (2018)
- [New Results on Superlinear Convergence of Classical Quasi-Newton Methods](https://mlsanity.com/paper/2004.14866/) (2020)
- [Rates of superlinear convergence for classical quasi-Newton methods](https://mlsanity.com/paper/2003.09174/) (2020)
- [IQN: An Incremental Quasi-Newton Method with Local Superlinear Convergence Rate](https://mlsanity.com/paper/1702.00709/) (2017)
- [Stochastic Variance-Reduced Newton: Accelerating Finite-Sum Minimization with Large Batches](https://mlsanity.com/paper/2206.02702/) (2022)
- [A Variance Reduced Stochastic Newton Method](https://mlsanity.com/paper/1503.08316/) (2015)
- [Sharpened Quasi-Newton Methods: Faster Superlinear Rate and Larger Local Convergence Neighborhood](https://mlsanity.com/paper/2202.10538/) (2022)
- [Acceleration of SVRG and Katyusha X by Inexact Preconditioning](https://mlsanity.com/paper/1905.09734/) (2019)
- [Explicit Convergence Rates of Greedy and Random Quasi-Newton Methods](https://mlsanity.com/paper/2104.08764/) (2021)
- [SAN: Stochastic Average Newton Algorithm for Minimizing Finite Sums](https://mlsanity.com/paper/2106.10520/) (2021)

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

- [Incremental Gauss--Newton Methods with Superlinear Convergence Rates](https://mlsanity.com/paper/2407.03195/) (2024)

## Abstract (arXiv)

The problem of minimizing the sum of n functions in d dimensions is ubiquitous in machine learning and statistics. In many applications where the number of observations n is large, it is necessary to use incremental or stochastic methods, as their per-iteration cost is independent of n. Of these, Quasi-Newton (QN) methods strike a balance between the per-iteration cost and the convergence rate. Specifically, they exhibit a superlinear rate with O(d2) cost in contrast to the linear rate of first-order methods with O(d) cost and the quadratic rate of second-order methods with O(d3) cost. However, existing incremental methods have notable shortcomings: Incremental Quasi-Newton (IQN) only exhibits asymptotic superlinear convergence. In contrast, Incremental Greedy BFGS (IGS) offers explicit superlinear convergence but suffers from poor empirical performance and has a per-iteration cost of O(d3). To address these issues, we introduce the Sharpened Lazy Incremental Quasi-Newton Method (SLIQN) that achieves the best of both worlds: an explicit superlinear convergence rate, and superior empirical performance at a per-iteration O(d2) cost. SLIQN features two key changes: first, it incorporates a hybrid strategy of using both classic and greedy BFGS updates, allowing it to empirically outperform both IQN and IGS. Second, it employs a clever constant multiplicative factor along with a lazy propagation strategy, which enables it to have a cost of O(d2). Additionally, our experiments demonstrate the superiority of SLIQN over other incremental and stochastic Quasi-Newton variants and establish its competitiveness with second-order incremental methods.