# Nys-Newton: Nystr"om-Approximated Curvature for Stochastic Optimization

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 44 references that are in the map.
- First posted on arXiv 16 Oct 2021.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [EfficientNet: Rethinking Model Scaling for Convolutional Neural Networks](https://mlsanity.com/paper/1905.11946/) (2019)
- [SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives](https://mlsanity.com/paper/1407.0202/) (2014)
- [Laplace Redux -- Effortless Bayesian Deep Learning](https://mlsanity.com/paper/2106.14806/) (2021)
- [SARAH: A Novel Method for Machine Learning Problems Using Stochastic Recursive Gradient](https://mlsanity.com/paper/1703.00102/) (2017)
- [ADAHESSIAN: An Adaptive Second Order Optimizer for Machine Learning](https://mlsanity.com/paper/2006.00719/) (2020)
- [A Kronecker-factored approximate Fisher matrix for convolution layers](https://mlsanity.com/paper/1602.01407/) (2016)
- [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)
- [A Linearly-Convergent Stochastic L-BFGS Algorithm](https://mlsanity.com/paper/1508.02087/) (2015)
- [SLANG: Fast Structured Covariance Approximations for Bayesian Deep Learning with Natural Gradient](https://mlsanity.com/paper/1811.04504/) (2018)
- [Understanding Approximate Fisher Information for Fast Convergence of Natural Gradient Descent in Wide Neural Networks](https://mlsanity.com/paper/2010.00879/) (2020)
- [Tractable structured natural gradient descent using local parameterizations](https://mlsanity.com/paper/2102.07405/) (2021)
- [Adaptive Newton Sketch: Linear-time Optimization with Quadratic Convergence and Effective Hessian Dimensionality](https://mlsanity.com/paper/2105.07291/) (2021)
- [A Divide-and-Conquer Solver for Kernel Support Vector Machines](https://mlsanity.com/paper/1311.0914/) (2013)
- [Structured second-order methods via natural gradient descent](https://mlsanity.com/paper/2107.10884/) (2021)
- [Generalization of Quasi-Newton Methods: Application to Robust Symmetric Multisecant Updates](https://mlsanity.com/paper/2011.03358/) (2020)

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

- [Nystrom Method for Accurate and Scalable Implicit Differentiation](https://mlsanity.com/paper/2302.09726/) (2023)
- [SOFIM: Stochastic Optimization Using Regularized Fisher Information Matrix](https://mlsanity.com/paper/2403.02833/) (2024)
- [Accelerated Training of Federated Learning via Second-Order Methods](https://mlsanity.com/paper/2505.23588/) (2025)
- [Hybrid Quantum-Classical PINNs for Scientific Computing: A Multi-GPU Open-Source Framework](https://mlsanity.com/paper/2604.15645/) (2026)

## Abstract (arXiv)

Second-order optimization methods are among the most widely used optimization approaches for convex optimization problems, and have recently been used to optimize non-convex optimization problems such as deep learning models. The widely used second-order optimization methods such as quasi-Newton methods generally provide curvature information by approximating the Hessian using the secant equation. However, the secant equation becomes insipid in approximating the Newton step owing to its use of the first-order derivatives. In this study, we propose an approximate Newton sketch-based stochastic optimization algorithm for large-scale empirical risk minimization. Specifically, we compute a partial column Hessian of size (d× m) with mll d randomly selected variables, then use the Nystr"om method to better approximate the full Hessian matrix. To further reduce the computational complexity per iteration, we directly compute the update step (Deltaboldsymbolw) without computing and storing the full Hessian or its inverse. We then integrate our approximated Hessian with stochastic gradient descent and stochastic variance-reduced gradient methods. The results of numerical experiments on both convex and non-convex functions show that the proposed approach was able to obtain a better approximation of Newtontextquotesingle s method, exhibiting performance competitive with that of state-of-the-art first-order and stochastic quasi-Newton methods. Furthermore, we provide a theoretical convergence analysis for convex functions.