# Fast Unconstrained Optimization via Hessian Averaging and Adaptive Gradient Sampling Methods

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 94 references that are in the map.
- First posted on arXiv 14 Aug 2024.

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

- [Gaussian Error Linear Units (GELUs)](https://mlsanity.com/paper/1606.08415/) (2016)
- [Fourier Neural Operator for Parametric Partial Differential Equations](https://mlsanity.com/paper/2010.08895/) (2020)
- [Decoupled Weight Decay Regularization](https://mlsanity.com/paper/1711.05101/) (2017)
- [Optimizing Neural Networks with Kronecker-factored Approximate Curvature](https://mlsanity.com/paper/1503.05671/) (2015)
- [FourCastNet: A Global Data-driven High-resolution Weather Model using Adaptive Fourier Neural Operators](https://mlsanity.com/paper/2202.11214/) (2022)
- [Sophia: A Scalable Stochastic Second-order Optimizer for Language Model Pre-training](https://mlsanity.com/paper/2305.14342/) (2023)
- [Convergence rates of sub-sampled Newton methods](https://mlsanity.com/paper/1508.02810/) (2015)
- [Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update](https://mlsanity.com/paper/2107.07480/) (2021)
- [An operator learning perspective on parameter-to-observable maps](https://mlsanity.com/paper/2402.06031/) (2024)
- [Sub-sampled Newton Methods with Non-uniform Sampling](https://mlsanity.com/paper/1607.00559/) (2016)
- [Efficient PDE-Constrained optimization under high-dimensional uncertainty using derivative-informed neural operators](https://mlsanity.com/paper/2305.20053/) (2023)
- [Derivative-informed neural operator acceleration of geometric MCMC for infinite-dimensional Bayesian inverse problems](https://mlsanity.com/paper/2403.08220/) (2024)
- [An Adaptive Sampling Sequential Quadratic Programming Method for Equality Constrained Stochastic Optimization](https://mlsanity.com/paper/2206.00712/) (2022)
- [Derivative-Free Optimization via Adaptive Sampling Strategies](https://mlsanity.com/paper/2404.11893/) (2024)
- [Modified Line Search Sequential Quadratic Methods for Equality-Constrained Optimization with Unified Global and Local Convergence Guarantees](https://mlsanity.com/paper/2406.11144/) (2024)
- [On the efficiency of Stochastic Quasi-Newton Methods for Deep Learning](https://mlsanity.com/paper/2205.09121/) (2022)
- [Stochastic Newton Proximal Extragradient Method](https://mlsanity.com/paper/2406.01478/) (2024)

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

- [LazyDINO: Fast, scalable, and efficiently amortized Bayesian inversion via structure-exploiting and surrogate-driven measure transport](https://mlsanity.com/paper/2411.12726/) (2024)

## Abstract (arXiv)

We consider minimizing finite-sum and expectation objective functions via Hessian-averaging based subsampled Newton methods. These methods allow for gradient inexactness and have fixed per-iteration Hessian approximation costs. The recent work (Na et al. 2023) demonstrated that Hessian averaging can be utilized to achieve fast Oleft(√tfraclog kkright) local superlinear convergence for strongly convex functions in high probability, while maintaining fixed per-iteration Hessian costs. These methods, however, require gradient exactness and strong convexity, which poses challenges for their practical implementation. To address this concern we consider Hessian-averaged methods that allow gradient inexactness via norm condition based adaptive-sampling strategies. For the finite-sum problem we utilize deterministic sampling techniques which lead to global linear and sublinear convergence rates for strongly convex and nonconvex functions respectively. In this setting we are able to derive an improved deterministic local superlinear convergence rate of Oleft(tfrac1kright). For the %expected risk expectation problem we utilize stochastic sampling techniques, and derive global linear and sublinear rates for strongly convex and nonconvex functions, as well as a Oleft(tfrac1√kright) local superlinear convergence rate, all in expectation. We present novel analysis techniques that differ from the previous probabilistic results. Additionally, we propose scalable and efficient variations of these methods via diagonal approximations and derive the novel diagonally-averaged Newton (Dan) method for large-scale problems. Our numerical results demonstrate that the Hessian averaging not only helps with convergence, but can lead to state-of-the-art performance on difficult problems such as CIFAR100 classification with ResNets.