# Fast large-scale optimization by unifying stochastic gradient and quasi-Newton methods

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Nov 2013.

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

- [KOALA: A Kalman Optimization Algorithm with Loss Adaptivity](https://mlsanity.com/paper/2107.03331/) (2021)
- [Low Dimensional Landscape Hypothesis is True: DNNs can be Trained in Tiny Subspaces](https://mlsanity.com/paper/2103.11154/) (2021)
- [Identifying Policy Gradient Subspaces](https://mlsanity.com/paper/2401.06604/) (2024)
- [FedSSO: A Federated Server-Side Second-Order Optimization Algorithm](https://mlsanity.com/paper/2206.09576/) (2022)
- [A Novel Fast Exact Subproblem Solver for Stochastic Quasi-Newton Cubic Regularized Optimization](https://mlsanity.com/paper/2204.09116/) (2022)
- [A Stochastic Quasi-Newton Method for Non-convex Optimization with Non-uniform Smoothness](https://mlsanity.com/paper/2403.15244/) (2024)
- [A Generalized Version of Chung's Lemma and its Applications](https://mlsanity.com/paper/2406.05637/) (2024)
- [Local Quadratic Convergence of Stochastic Gradient Descent with Adaptive Step Size](https://mlsanity.com/paper/2112.14872/) (2021)
- [Ordering for Non-Replacement SGD](https://mlsanity.com/paper/2306.15848/) (2023)

## Abstract (arXiv)

We present an algorithm for minimizing a sum of functions that combines the computational efficiency of stochastic gradient descent (SGD) with the second order curvature information leveraged by quasi-Newton methods. We unify these disparate approaches by maintaining an independent Hessian approximation for each contributing function in the sum. We maintain computational tractability and limit memory requirements even for high dimensional optimization problems by storing and manipulating these quadratic approximations in a shared, time evolving, low dimensional subspace. Each update step requires only a single contributing function or minibatch evaluation (as in SGD), and each step is scaled using an approximate inverse Hessian and little to no adjustment of hyperparameters is required (as is typical for quasi-Newton methods). This algorithm contrasts with earlier stochastic second order techniques that treat the Hessian of each contributing function as a noisy approximation to the full Hessian, rather than as a target for direct estimation. We experimentally demonstrate improved convergence on seven diverse optimization problems. The algorithm is released as open source Python and MATLAB packages.