# Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergence

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

## Key facts

- Cited by 72 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 May 2015.

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

- [A Distributed Data-Parallel PyTorch Implementation of the Distributed Shampoo Optimizer for Training Neural Networks At-Scale](https://mlsanity.com/paper/2309.06497/) (2023)
- [Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time](https://mlsanity.com/paper/2112.07628/) (2021)
- [Newton-LESS: Sparsification without Trade-offs for the Sketched Newton Update](https://mlsanity.com/paper/2107.07480/) (2021)
- [LocalNewton: Reducing Communication Bottleneck for Distributed Learning](https://mlsanity.com/paper/2105.07320/) (2021)
- [Adaptive Newton Sketch: Linear-time Optimization with Quadratic Convergence and Effective Hessian Dimensionality](https://mlsanity.com/paper/2105.07291/) (2021)
- [Efficient Convex Optimization Requires Superlinear Memory](https://mlsanity.com/paper/2203.15260/) (2022)
- [Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence](https://mlsanity.com/paper/2204.09266/) (2022)
- [Learning Augmentation Distributions using Transformed Risk Minimization](https://mlsanity.com/paper/2111.08190/) (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)
- [Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming](https://mlsanity.com/paper/2205.13687/) (2022)
- [Stochastic Variance-Reduced Newton: Accelerating Finite-Sum Minimization with Large Batches](https://mlsanity.com/paper/2206.02702/) (2022)
- [Robust, randomized preconditioning for kernel ridge regression](https://mlsanity.com/paper/2304.12465/) (2023)
- [SketchySGD: Reliable Stochastic Optimization via Randomized Curvature Estimates](https://mlsanity.com/paper/2211.08597/) (2022)
- [Covering Number of Real Algebraic Varieties and Beyond: Improved Bounds and Applications](https://mlsanity.com/paper/2311.05116/) (2023)
- [Global optimization using random embeddings](https://mlsanity.com/paper/2107.12102/) (2021)
- [Distributed Sketching for Randomized Optimization: Exact Characterization, Concentration and Lower Bounds](https://mlsanity.com/paper/2203.09755/) (2022)
- [ISAAC Newton: Input-based Approximate Curvature for Newton's Method](https://mlsanity.com/paper/2305.00604/) (2023)
- [Stochastic Online Optimization for Cyber-Physical and Robotic Systems](https://mlsanity.com/paper/2404.05318/) (2024)
- [Riemannian Natural Gradient Methods](https://mlsanity.com/paper/2207.07287/) (2022)
- [Constrained Optimization via Exact Augmented Lagrangian and Randomized Iterative Sketching](https://mlsanity.com/paper/2305.18379/) (2023)
- [Nys-Newton: Nystr"om-Approximated Curvature for Stochastic Optimization](https://mlsanity.com/paper/2110.08577/) (2021)
- [Memory-Query Tradeoffs for Randomized Convex Optimization](https://mlsanity.com/paper/2306.12534/) (2023)
- [CRONOS: Enhancing Deep Learning with Scalable GPU Accelerated Convex Neural Networks](https://mlsanity.com/paper/2411.01088/) (2024)
- [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)
- [Fast Convex Quadratic Optimization Solvers with Adaptive Sketching-based Preconditioners](https://mlsanity.com/paper/2104.14101/) (2021)
- [The Complexity of Dynamic Least-Squares Regression](https://mlsanity.com/paper/2201.00228/) (2022)
- [FedNS: A Fast Sketching Newton-Type Algorithm for Federated Learning](https://mlsanity.com/paper/2401.02734/) (2024)
- [Online estimation of the inverse of the Hessian for stochastic optimization with application to universal stochastic Newton algorithms](https://mlsanity.com/paper/2401.10923/) (2024)

## Abstract (arXiv)

We propose a randomized second-order method for optimization known as the Newton Sketch: it is based on performing an approximate Newton step using a randomly projected or sub-sampled Hessian. For self-concordant functions, we prove that the algorithm has super-linear convergence with exponentially high probability, with convergence and complexity guarantees that are independent of condition numbers and related problem-dependent quantities. Given a suitable initialization, similar guarantees also hold for strongly convex and smooth objectives without self-concordance. When implemented using randomized projections based on a sub-sampled Hadamard basis, the algorithm typically has substantially lower complexity than Newton's method. We also describe extensions of our methods to programs involving convex constraints that are equipped with self-concordant barriers. We discuss and illustrate applications to linear programs, quadratic programs with convex constraints, logistic regression and other generalized linear models, as well as semidefinite programs.