# Sub-sampled Newton Methods with Non-uniform Sampling

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Jul 2016.

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

- [A Distributed Data-Parallel PyTorch Implementation of the Distributed Shampoo Optimizer for Training Neural Networks At-Scale](https://mlsanity.com/paper/2309.06497/) (2023)
- [Hessian Eigenspectra of More Realistic Nonlinear Models](https://mlsanity.com/paper/2103.01519/) (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)
- [Faster Differentially Private Convex Optimization via Second-Order Methods](https://mlsanity.com/paper/2305.13209/) (2023)
- [Unified Convergence Theory of Stochastic and Variance-Reduced Cubic Newton Methods](https://mlsanity.com/paper/2302.11962/) (2023)
- [Recent and Upcoming Developments in Randomized Numerical Linear Algebra for Machine Learning](https://mlsanity.com/paper/2406.11151/) (2024)
- [ISAAC Newton: Input-based Approximate Curvature for Newton's Method](https://mlsanity.com/paper/2305.00604/) (2023)
- [Improving Stochastic Cubic Newton with Momentum](https://mlsanity.com/paper/2410.19644/) (2024)
- [Regularization by Denoising Sub-sampled Newton Method for Spectral CT Multi-Material Decomposition](https://mlsanity.com/paper/2103.13909/) (2021)
- [Fundamental Bias in Inverting Random Sampling Matrices with Application to Sub-sampled Newton](https://mlsanity.com/paper/2502.13583/) (2025)
- [Learning-Augmented Sketches for Hessians](https://mlsanity.com/paper/2102.12317/) (2021)
- [Augmented Newton Method for Optimization: Global Linear Rate and Momentum Interpretation](https://mlsanity.com/paper/2205.11033/) (2022)
- [FOSI: Hybrid First and Second Order Optimization](https://mlsanity.com/paper/2302.08484/) (2023)
- [Safe Collaborative Filtering](https://mlsanity.com/paper/2306.05292/) (2023)
- [Fast Unconstrained Optimization via Hessian Averaging and Adaptive Gradient Sampling Methods](https://mlsanity.com/paper/2408.07268/) (2024)
- [Discriminative Bayesian filtering lends momentum to the stochastic Newton method for minimizing log-convex functions](https://mlsanity.com/paper/2104.12949/) (2021)
- [Non-PSD Matrix Sketching with Applications to Regression and Optimization](https://mlsanity.com/paper/2106.08544/) (2021)
- [Explicit Second-Order Min-Max Optimization: Practical Algorithms and Complexity Analysis](https://mlsanity.com/paper/2210.12860/) (2022)
- [What is a Sketch-and-Precondition Derivation for Low-Rank Approximation? Inverse Power Error or Inverse Power Estimation?](https://mlsanity.com/paper/2502.07993/) (2025)
- [Non-Asymptotic Optimization and Generalization Bounds for Stochastic Gauss-Newton in Overparameterized Models](https://mlsanity.com/paper/2511.03972/) (2025)

## Abstract (arXiv)

We consider the problem of finding the minimizer of a convex function F: mathbb Rd rightarrow mathbb R of the form F(w) := sumi=1n fi(w) + R(w) where a low-rank factorization of nabla2 fi(w) is readily available. We consider the regime where n gg d. As second-order methods prove to be effective in finding the minimizer to a high-precision, in this work, we propose randomized Newton-type algorithms that exploit textitnon-uniform sub-sampling of nabla2 fi(w)i=1n, as well as inexact updates, as means to reduce the computational complexity. Two non-uniform sampling distributions based on it block norm squares and it block partial leverage scores are considered in order to capture important terms among nabla2 fi(w)i=1n. We show that at each iteration non-uniformly sampling at most mathcal O(d log d) terms from nabla2 fi(w)i=1n is sufficient to achieve a linear-quadratic convergence rate in w when a suitable initial point is provided. In addition, we show that our algorithms achieve a lower computational complexity and exhibit more robustness and better dependence on problem specific quantities, such as the condition number, compared to similar existing methods, especially the ones based on uniform sampling. Finally, we empirically demonstrate that our methods are at least twice as fast as Newton's methods with ridge logistic regression on several real datasets.