mlsanityData to 14 Oct 2026

Exact and Inexact Subsampled Newton Methods for Optimization

arXiv 1609.08502 ↗First posted 27 Sep 2016math.OC stat.MLcited by 38

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 12; 2022: 8; 2023: 5; 2024: 4; 2025: 8; 2026: 1.

38 papers.

Sort:

By area:

  1. 2022On the Effectiveness of Parameter-Efficient Fine-Tuningcited by 141
  2. 2023Towards Sustainable Learning: Coresets for Data-efficient Deep Learningcited by 44
  3. 2021An Adaptive Stochastic Sequential Quadratic Programming with Differentiable Exact Augmented Lagrangianscited by 25
  4. 2021Inequality Constrained Stochastic Nonlinear Optimization via Active-Set Sequential Quadratic Programmingcited by 17
  5. 2021Doubly Adaptive Scaled Algorithm for Machine Learning Using Second-Order Informationcited by 16
  6. 2021Adaptive Newton Sketch: Linear-time Optimization with Quadratic Convergence and Effective Hessian Dimensionalitycited by 14
  7. 2022Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergencecited by 14
  8. 2021SVRG Meets AdaGrad: Painless Variance Reductioncited by 13
  9. 2022SP2: A Second Order Stochastic Polyak Methodcited by 13
  10. 2024Recent and Upcoming Developments in Randomized Numerical Linear Algebra for Machine Learningcited by 11
  11. 2021Large-Scale Deep Learning Optimizations: A Comprehensive Surveycited by 10
  12. 2024Exact Gauss-Newton Optimization for Training Deep Neural Networkscited by 10
26 more
  1. 2022Stochastic Variance-Reduced Newton: Accelerating Finite-Sum Minimization with Large Batchescited by 9
  2. 2022SketchySGD: Reliable Stochastic Optimization via Randomized Curvature Estimatescited by 8
  3. 2021slimTrain -- A Stochastic Approximation Method for Training Separable Deep Neural Networkscited by 6
  4. 2023Constrained Optimization via Exact Augmented Lagrangian and Randomized Iterative Sketchingcited by 5
  5. 2021Adaptive Sampling Quasi-Newton Methods for Zeroth-Order Stochastic Optimizationcited by 4
  6. 2023Target-based Surrogates for Stochastic Optimizationcited by 4
  7. 2023FedZeN: Towards superlinear zeroth-order federated learning via incremental Hessian estimationcited by 4
  8. 2025SAPPHIRE: Preconditioned Stochastic Variance Reduction for Faster Large-Scale Statistical Learningcited by 4
  9. 2021Regularization by Denoising Sub-sampled Newton Method for Spectral CT Multi-Material Decompositioncited by 3
  10. 2024Second-order Information Promotes Mini-Batch Robustness in Variance-Reduced Gradientscited by 3
  11. 2025Efficient Curvature-Aware Hypergradient Approximation for Bilevel Optimizationcited by 3
  12. 2025Fundamental Bias in Inverting Random Sampling Matrices with Application to Sub-sampled Newtoncited by 2
  13. 2025A stochastic gradient method for trilevel optimizationcited by 2
  14. 2025A Sketch-and-Project Analysis of Subsampled Natural Gradient Algorithmscited by 2
  15. 2021A Retrospective Approximation Approach for Smooth Stochastic Optimizationcited by 1
  16. 2022On the efficiency of Stochastic Quasi-Newton Methods for Deep Learningcited by 1
  17. 2022Computational Complexity of Sub-Linear Convergent Algorithmscited by 1
  18. 2024Stochastic Newton Proximal Extragradient Methodcited by 1
  19. 2021Discriminative Bayesian filtering lends momentum to the stochastic Newton method for minimizing log-convex functionscited by 0
  20. 2021Non-PSD Matrix Sketching with Applications to Regression and Optimizationcited by 0
  21. 2022An Efficient Nonlinear Acceleration method that Exploits Symmetry of the Hessiancited by 0
  22. 2023Information-Theoretic Trust Regions for Stochastic Gradient-Based Optimizationcited by 0
  23. 2025What is a Sketch-and-Precondition Derivation for Low-Rank Approximation? Inverse Power Error or Inverse Power Estimation?cited by 0
  24. 2025Computationally efficient Gauss-Newton reinforcement learning for model predictive controlcited by 0
  25. 2025SUPN: Shallow Universal Polynomial Networks for Efficient Function Approximationcited by 0
  26. 2026Fast Gauss-Newton for Multiclass Cross-Entropycited by 0