# SAN: Stochastic Average Newton Algorithm for Minimizing Finite Sums

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Jun 2021.

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

- [KKT Conditions, First-Order and Second-Order Optimization, and Distributed Optimization: Tutorial and Survey](https://mlsanity.com/paper/2110.01858/) (2021)
- [SP2: A Second Order Stochastic Polyak Method](https://mlsanity.com/paper/2207.08171/) (2022)
- [SAPPHIRE: Preconditioned Stochastic Variance Reduction for Faster Large-Scale Statistical Learning](https://mlsanity.com/paper/2501.15941/) (2025)
- [Sharpened Lazy Incremental Quasi-Newton Method](https://mlsanity.com/paper/2305.17283/) (2023)
- [Adaptive pruning-based Newton's method for distributed learning](https://mlsanity.com/paper/2308.10154/) (2023)

## Abstract (arXiv)

We present a principled approach for designing stochastic Newton methods for solving finite sum optimization problems. Our approach has two steps. First, we re-write the stationarity conditions as a system of nonlinear equations that associates each data point to a new row. Second, we apply a Subsampled Newton Raphson method to solve this system of nonlinear equations. Using our approach, we develop a new Stochastic Average Newton (SAN) method, which is incremental by design, in that it requires only a single data point per iteration. It is also cheap to implement when solving regularized generalized linear models, with a cost per iteration of the order of the number of the parameters. We show through extensive numerical experiments that SAN requires no knowledge about the problem, neither parameter tuning, while remaining competitive as compared to classical variance reduced gradient methods (e.g. SAG and SVRG), incremental Newton and quasi-Newton methods (e.g. SNM, IQN).