# Exploiting Local Convergence of Quasi-Newton Methods Globally: Adaptive Sample Size Approach

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 20 of its 38 references that are in the map.
- First posted on arXiv 10 Jun 2021.

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

- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Momentum-Based Variance Reduction in Non-Convex SGD](https://mlsanity.com/paper/1905.10018/) (2019)
- [SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator](https://mlsanity.com/paper/1807.01695/) (2018)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [Katyusha: The First Direct Acceleration of Stochastic Gradient Methods](https://mlsanity.com/paper/1603.05953/) (2016)
- [A Stochastic Quasi-Newton Method for Large-Scale Optimization](https://mlsanity.com/paper/1401.7020/) (2014)
- [A Linearly-Convergent Stochastic L-BFGS Algorithm](https://mlsanity.com/paper/1508.02087/) (2015)
- [Convergence rates of sub-sampled Newton methods](https://mlsanity.com/paper/1508.02810/) (2015)
- [Competing with the Empirical Risk Minimizer in a Single Pass](https://mlsanity.com/paper/1412.6606/) (2014)
- [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)
- [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)
- [A globally convergent incremental Newton method](https://mlsanity.com/paper/1410.5284/) (2014)
- [Adaptive Newton Method for Empirical Risk Minimization to Statistical Accuracy](https://mlsanity.com/paper/1605.07659/) (2016)
- [Batch-Expansion Training: An Efficient Optimization Framework](https://mlsanity.com/paper/1704.06731/) (2017)
- [First-Order Adaptive Sample Size Methods to Reduce Complexity of Empirical Risk Minimization](https://mlsanity.com/paper/1709.00599/) (2017)

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

- [Green, Quantized Federated Learning over Wireless Networks: An Energy-Efficient Design](https://mlsanity.com/paper/2207.09387/) (2022)
- [FUSE: First-Order and Second-Order Unified SynthEsis in Stochastic Optimization](https://mlsanity.com/paper/2503.04204/) (2025)

## Abstract (arXiv)

In this paper, we study the application of quasi-Newton methods for solving empirical risk minimization (ERM) problems defined over a large dataset. Traditional deterministic and stochastic quasi-Newton methods can be executed to solve such problems; however, it is known that their global convergence rate may not be better than first-order methods, and their local superlinear convergence only appears towards the end of the learning process. In this paper, we use an adaptive sample size scheme that exploits the superlinear convergence of quasi-Newton methods globally and throughout the entire learning process. The main idea of the proposed adaptive sample size algorithms is to start with a small subset of data points and solve their corresponding ERM problem within its statistical accuracy, and then enlarge the sample size geometrically and use the optimal solution of the problem corresponding to the smaller set as an initial point for solving the subsequent ERM problem with more samples. We show that if the initial sample size is sufficiently large and we use quasi-Newton methods to solve each subproblem, the subproblems can be solved superlinearly fast (after at most three iterations), as we guarantee that the iterates always stay within a neighborhood that quasi-Newton methods converge superlinearly. Numerical experiments on various datasets confirm our theoretical results and demonstrate the computational advantages of our method.