# Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence arXiv: https://arxiv.org/abs/2204.09266 · HTML: https://mlsanity.com/paper/2204.09266/ ## Key facts - Cited by 14 papers in the map (data through 14 Oct 2026). - Builds on 39 of its 76 references that are in the map. - First posted on arXiv 20 Apr 2022. ## Builds on (most cited first, 30 of 39) - [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021) - [Optimization Methods for Large-Scale Machine Learning](https://mlsanity.com/paper/1606.04838/) (2016) - [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014) - [Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergence](https://mlsanity.com/paper/1505.02250/) (2015) - [FedNL: Making Newton-Type Methods Applicable to Federated Learning](https://mlsanity.com/paper/2106.02969/) (2021) - [Improved SVRG for Non-Strongly-Convex or Sum-of-Non-Convex Objectives](https://mlsanity.com/paper/1506.01972/) (2015) - [Exact and Inexact Subsampled Newton Methods for Optimization](https://mlsanity.com/paper/1609.08502/) (2016) - [Second-Order Optimization for Non-Convex Machine Learning: An Empirical Study](https://mlsanity.com/paper/1708.07827/) (2017) - [RSN: Randomized Subspace Newton](https://mlsanity.com/paper/1905.10874/) (2019) - [Convergence rates of sub-sampled Newton methods](https://mlsanity.com/paper/1508.02810/) (2015) - [Efficient Second Order Online Learning by Sketching](https://mlsanity.com/paper/1602.02202/) (2016) - [Stochastic Optimization Using a Trust-Region Method and Random Models](https://mlsanity.com/paper/1504.04231/) (2015) - [An Adaptive Stochastic Sequential Quadratic Programming with Differentiable Exact Augmented Lagrangians](https://mlsanity.com/paper/2102.05320/) (2021) - [Distributed Second Order Methods with Fast Rates and Compressed Communication](https://mlsanity.com/paper/2102.07158/) (2021) - [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) - [Sub-sampled Newton Methods with Non-uniform Sampling](https://mlsanity.com/paper/1607.00559/) (2016) - [Greedy Quasi-Newton Methods with Explicit Superlinear Convergence](https://mlsanity.com/paper/2002.00657/) (2020) - [Sparse sketches with small inversion bias](https://mlsanity.com/paper/2011.10695/) (2020) - [Faster Eigenvector Computation via Shift-and-Invert Preconditioning](https://mlsanity.com/paper/1605.08754/) (2016) - [An Investigation of Newton-Sketch and Subsampled Newton Methods](https://mlsanity.com/paper/1705.06211/) (2017) - [Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation](https://mlsanity.com/paper/1910.04920/) (2019) - [Inequality Constrained Stochastic Nonlinear Optimization via Active-Set Sequential Quadratic Programming](https://mlsanity.com/paper/2109.11502/) (2021) - [Fast and Simple PCA via Convex Optimization](https://mlsanity.com/paper/1509.05647/) (2015) - [Distributed estimation of the inverse Hessian by determinantal averaging](https://mlsanity.com/paper/1905.11546/) (2019) - [Non-asymptotic Superlinear Convergence of Standard Quasi-Newton Methods](https://mlsanity.com/paper/2003.13607/) (2020) - [New Results on Superlinear Convergence of Classical Quasi-Newton Methods](https://mlsanity.com/paper/2004.14866/) (2020) - [Basis Matters: Better Communication-Efficient Second Order Methods for Federated Learning](https://mlsanity.com/paper/2111.01847/) (2021) - [Randomized Block Cubic Newton Method](https://mlsanity.com/paper/1802.04084/) (2018) - [Adaptive Newton Sketch: Linear-time Optimization with Quadratic Convergence and Effective Hessian Dimensionality](https://mlsanity.com/paper/2105.07291/) (2021) ## Built on by (most cited first, 14 of 14) - [Fully Stochastic Trust-Region Sequential Quadratic Programming for Equality-Constrained Optimization Problems](https://mlsanity.com/paper/2211.15943/) (2022) - [Recent and Upcoming Developments in Randomized Numerical Linear Algebra for Machine Learning](https://mlsanity.com/paper/2406.11151/) (2024) - [Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming](https://mlsanity.com/paper/2205.13687/) (2022) - [Stochastic Variance-Reduced Newton: Accelerating Finite-Sum Minimization with Large Batches](https://mlsanity.com/paper/2206.02702/) (2022) - [Randomized Kaczmarz Methods with Beyond-Krylov Convergence](https://mlsanity.com/paper/2501.11673/) (2025) - [Constrained Optimization via Exact Augmented Lagrangian and Randomized Iterative Sketching](https://mlsanity.com/paper/2305.18379/) (2023) - [Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models](https://mlsanity.com/paper/2409.15734/) (2024) - [High Probability Complexity Bounds of Trust-Region Stochastic Sequential Quadratic Programming with Heavy-Tailed Noise](https://mlsanity.com/paper/2503.19091/) (2025) - [Second-order Information Promotes Mini-Batch Robustness in Variance-Reduced Gradients](https://mlsanity.com/paper/2404.14758/) (2024) - [A Trust-Region Interior-Point Stochastic Sequential Quadratic Programming Method](https://mlsanity.com/paper/2603.10230/) (2026) - [Stochastic Newton Proximal Extragradient Method](https://mlsanity.com/paper/2406.01478/) (2024) - [Efficient Second-Order Neural Network Optimization via Adaptive Trust Region Methods](https://mlsanity.com/paper/2410.02293/) (2024) - [Explicit Second-Order Min-Max Optimization: Practical Algorithms and Complexity Analysis](https://mlsanity.com/paper/2210.12860/) (2022) - [Sequential Least-Squares Estimators with Fast Randomized Sketching for Linear Statistical Models](https://mlsanity.com/paper/2509.06856/) (2025) ## Abstract (arXiv) We consider minimizing a smooth and strongly convex objective function using a stochastic Newton method. At each iteration, the algorithm is given an oracle access to a stochastic estimate of the Hessian matrix. The oracle model includes popular algorithms such as Subsampled Newton and Newton Sketch. Despite using second-order information, these existing methods do not exhibit superlinear convergence, unless the stochastic noise is gradually reduced to zero during the iteration, which would lead to a computational blow-up in the per-iteration cost. We propose to address this limitation with Hessian averaging: instead of using the most recent Hessian estimate, our algorithm maintains an average of all the past estimates. This reduces the stochastic noise while avoiding the computational blow-up. We show that this scheme exhibits local Q-superlinear convergence with a non-asymptotic rate of (Upsilon√log (t)/t,)t, where Upsilon is proportional to the level of stochastic noise in the Hessian oracle. A potential drawback of this (uniform averaging) approach is that the averaged estimates contain Hessian information from the global phase of the method, i.e., before the iterates converge to a local neighborhood. This leads to a distortion that may substantially delay the superlinear convergence until long after the local neighborhood is reached. To address this drawback, we study a number of weighted averaging schemes that assign larger weights to recent Hessians, so that the superlinear convergence arises sooner, albeit with a slightly slower rate. Remarkably, we show that there exists a universal weighted averaging scheme that transitions to local convergence at an optimal stage, and still exhibits a superlinear convergence rate nearly (up to a logarithmic factor) matching that of uniform Hessian averaging.