# Exact and Inexact Subsampled Newton Methods for Optimization

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

## Key facts

- Cited by 38 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Sep 2016.

## Built on by (most cited first, 30 of 38)

- [On the Effectiveness of Parameter-Efficient Fine-Tuning](https://mlsanity.com/paper/2211.15583/) (2022)
- [Towards Sustainable Learning: Coresets for Data-efficient Deep Learning](https://mlsanity.com/paper/2306.01244/) (2023)
- [An Adaptive Stochastic Sequential Quadratic Programming with Differentiable Exact Augmented Lagrangians](https://mlsanity.com/paper/2102.05320/) (2021)
- [Inequality Constrained Stochastic Nonlinear Optimization via Active-Set Sequential Quadratic Programming](https://mlsanity.com/paper/2109.11502/) (2021)
- [Doubly Adaptive Scaled Algorithm for Machine Learning Using Second-Order Information](https://mlsanity.com/paper/2109.05198/) (2021)
- [Adaptive Newton Sketch: Linear-time Optimization with Quadratic Convergence and Effective Hessian Dimensionality](https://mlsanity.com/paper/2105.07291/) (2021)
- [Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence](https://mlsanity.com/paper/2204.09266/) (2022)
- [SVRG Meets AdaGrad: Painless Variance Reduction](https://mlsanity.com/paper/2102.09645/) (2021)
- [SP2: A Second Order Stochastic Polyak Method](https://mlsanity.com/paper/2207.08171/) (2022)
- [Recent and Upcoming Developments in Randomized Numerical Linear Algebra for Machine Learning](https://mlsanity.com/paper/2406.11151/) (2024)
- [Large-Scale Deep Learning Optimizations: A Comprehensive Survey](https://mlsanity.com/paper/2111.00856/) (2021)
- [Exact Gauss-Newton Optimization for Training Deep Neural Networks](https://mlsanity.com/paper/2405.14402/) (2024)
- [Stochastic Variance-Reduced Newton: Accelerating Finite-Sum Minimization with Large Batches](https://mlsanity.com/paper/2206.02702/) (2022)
- [SketchySGD: Reliable Stochastic Optimization via Randomized Curvature Estimates](https://mlsanity.com/paper/2211.08597/) (2022)
- [slimTrain -- A Stochastic Approximation Method for Training Separable Deep Neural Networks](https://mlsanity.com/paper/2109.14002/) (2021)
- [Constrained Optimization via Exact Augmented Lagrangian and Randomized Iterative Sketching](https://mlsanity.com/paper/2305.18379/) (2023)
- [Adaptive Sampling Quasi-Newton Methods for Zeroth-Order Stochastic Optimization](https://mlsanity.com/paper/2109.12213/) (2021)
- [Target-based Surrogates for Stochastic Optimization](https://mlsanity.com/paper/2302.02607/) (2023)
- [FedZeN: Towards superlinear zeroth-order federated learning via incremental Hessian estimation](https://mlsanity.com/paper/2309.17174/) (2023)
- [SAPPHIRE: Preconditioned Stochastic Variance Reduction for Faster Large-Scale Statistical Learning](https://mlsanity.com/paper/2501.15941/) (2025)
- [Regularization by Denoising Sub-sampled Newton Method for Spectral CT Multi-Material Decomposition](https://mlsanity.com/paper/2103.13909/) (2021)
- [Second-order Information Promotes Mini-Batch Robustness in Variance-Reduced Gradients](https://mlsanity.com/paper/2404.14758/) (2024)
- [Efficient Curvature-Aware Hypergradient Approximation for Bilevel Optimization](https://mlsanity.com/paper/2505.02101/) (2025)
- [Fundamental Bias in Inverting Random Sampling Matrices with Application to Sub-sampled Newton](https://mlsanity.com/paper/2502.13583/) (2025)
- [A stochastic gradient method for trilevel optimization](https://mlsanity.com/paper/2505.06805/) (2025)
- [A Sketch-and-Project Analysis of Subsampled Natural Gradient Algorithms](https://mlsanity.com/paper/2508.21022/) (2025)
- [A Retrospective Approximation Approach for Smooth Stochastic Optimization](https://mlsanity.com/paper/2103.04392/) (2021)
- [On the efficiency of Stochastic Quasi-Newton Methods for Deep Learning](https://mlsanity.com/paper/2205.09121/) (2022)
- [Computational Complexity of Sub-Linear Convergent Algorithms](https://mlsanity.com/paper/2209.14558/) (2022)
- [Stochastic Newton Proximal Extragradient Method](https://mlsanity.com/paper/2406.01478/) (2024)

## Abstract (arXiv)

The paper studies the solution of stochastic optimization problems in which approximations to the gradient and Hessian are obtained through subsampling. We first consider Newton-like methods that employ these approximations and discuss how to coordinate the accuracy in the gradient and Hessian to yield a superlinear rate of convergence in expectation. The second part of the paper analyzes an inexact Newton method that solves linear systems approximately using the conjugate gradient (CG) method, and that samples the Hessian and not the gradient (the gradient is assumed to be exact). We provide a complexity analysis for this method based on the properties of the CG iteration and the quality of the Hessian approximation, and compare it with a method that employs a stochastic gradient iteration instead of the CG method. We report preliminary numerical results that illustrate the performance of inexact subsampled Newton methods on machine learning applications based on logistic regression.