# Online estimation of the inverse of the Hessian for stochastic optimization with application to universal stochastic Newton algorithms

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 49 references that are in the map.
- First posted on arXiv 15 Jan 2024.

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

- [SGD: General Analysis and Improved Rates](https://mlsanity.com/paper/1901.09401/) (2019)
- [Minimizing Finite Sums with the Stochastic Average Gradient](https://mlsanity.com/paper/1309.2388/) (2013)
- [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)
- [Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares](https://mlsanity.com/paper/1411.0347/) (2014)
- [RSN: Randomized Subspace Newton](https://mlsanity.com/paper/1905.10874/) (2019)
- [Adaptivity of averaged stochastic gradient descent to local strong convexity for logistic regression](https://mlsanity.com/paper/1303.6149/) (2013)
- [Towards stability and optimality in stochastic gradient descent](https://mlsanity.com/paper/1505.02417/) (2015)
- [On Projected Stochastic Gradient Descent Algorithm with Weighted Averaging for Least Squares Regression](https://mlsanity.com/paper/1606.03000/) (2016)
- [Non-Asymptotic Analysis of Stochastic Approximation Algorithms for Streaming Data](https://mlsanity.com/paper/2109.07117/) (2021)
- [Online stochastic Newton methods for estimating the geometric median and applications](https://mlsanity.com/paper/2304.00770/) (2023)

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

- [A Full Adagrad algorithm with O(Nd) operations](https://mlsanity.com/paper/2405.01908/) (2024)
- [When Does Dynamic Preconditioning Preserve the Polyak-Ruppert CLT? A Stabilization Threshold](https://mlsanity.com/paper/2604.23498/) (2026)
- [An hybrid stochastic Newton algorithm for logistic regression](https://mlsanity.com/paper/2512.01790/) (2025)

## Abstract (arXiv)

This paper addresses second-order stochastic optimization for estimating the minimizer of a convex function written as an expectation. A direct recursive estimation technique for the inverse Hessian matrix using a Robbins-Monro procedure is introduced. This approach enables to drastically reduces computational complexity. Above all, it allows to develop universal stochastic Newton methods and investigate the asymptotic efficiency of the proposed approach. This work so expands the application scope of secondorder algorithms in stochastic optimization.