# Adaptive Newton Sketch: Linear-time Optimization with Quadratic Convergence and Effective Hessian Dimensionality

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

## Key facts

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

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

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Katyusha: The First Direct Acceleration of Stochastic Gradient Methods](https://mlsanity.com/paper/1603.05953/) (2016)
- [Communication Efficient Distributed Optimization using an Approximate Newton-type Method](https://mlsanity.com/paper/1312.7853/) (2013)
- [Newton Sketch: A Linear-time Optimization Algorithm with Linear-Quadratic Convergence](https://mlsanity.com/paper/1505.02250/) (2015)
- [GIANT: Globally Improved Approximate Newton Method for Distributed Optimization](https://mlsanity.com/paper/1709.03528/) (2017)
- [Exact and Inexact Subsampled Newton Methods for Optimization](https://mlsanity.com/paper/1609.08502/) (2016)
- [Optimal approximate matrix product in terms of stable rank](https://mlsanity.com/paper/1507.02268/) (2015)
- [Second-Order Optimization for Non-Convex Machine Learning: An Empirical Study](https://mlsanity.com/paper/1708.07827/) (2017)
- [RSN: Randomized Subspace Newton](https://mlsanity.com/paper/1905.10874/) (2019)
- [The importance of better models in stochastic optimization](https://mlsanity.com/paper/1903.08619/) (2019)
- [Randomized sketches for kernels: Fast and optimal non-parametric regression](https://mlsanity.com/paper/1501.06195/) (2015)
- [Sub-sampled Newton Methods with Non-uniform Sampling](https://mlsanity.com/paper/1607.00559/) (2016)
- [SDNA: Stochastic Dual Newton Ascent for Empirical Risk Minimization](https://mlsanity.com/paper/1502.02268/) (2015)
- [Sharper Bounds for Regularized Data Fitting](https://mlsanity.com/paper/1611.03225/) (2016)
- [An Investigation of Newton-Sketch and Subsampled Newton Methods](https://mlsanity.com/paper/1705.06211/) (2017)
- [Randomized Block Cubic Newton Method](https://mlsanity.com/paper/1802.04084/) (2018)
- [Debiasing Distributed Second Order Optimization with Surrogate Sketching and Scaled Regularization](https://mlsanity.com/paper/2007.01327/) (2020)
- [Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization](https://mlsanity.com/paper/2006.05874/) (2020)
- [Do Subsampled Newton Methods Work for High-Dimensional Data?](https://mlsanity.com/paper/1902.04952/) (2019)
- [High-Dimensional Optimization in Adaptive Random Subspaces](https://mlsanity.com/paper/1906.11809/) (2019)
- [Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform](https://mlsanity.com/paper/2002.00864/) (2020)
- [Distributed Sketching Methods for Privacy Preserving Regression](https://mlsanity.com/paper/2002.06538/) (2020)

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

- [Analytic Insights into Structure and Rank of Neural Network Hessian Maps](https://mlsanity.com/paper/2106.16225/) (2021)
- [Hessian Averaging in Stochastic Newton Methods Achieves Superlinear Convergence](https://mlsanity.com/paper/2204.09266/) (2022)
- [SketchySGD: Reliable Stochastic Optimization via Randomized Curvature Estimates](https://mlsanity.com/paper/2211.08597/) (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)
- [FedNS: A Fast Sketching Newton-Type Algorithm for Federated Learning](https://mlsanity.com/paper/2401.02734/) (2024)
- [Cubic regularized subspace Newton for non-convex optimization](https://mlsanity.com/paper/2406.16666/) (2024)
- [Fundamental Bias in Inverting Random Sampling Matrices with Application to Sub-sampled Newton](https://mlsanity.com/paper/2502.13583/) (2025)
- [DRSOM: A Dimension Reduced Second-Order Method](https://mlsanity.com/paper/2208.00208/) (2022)
- [Limited-Memory Greedy Quasi-Newton Method with Non-asymptotic Superlinear Convergence Rate](https://mlsanity.com/paper/2306.15444/) (2023)
- [FLeNS: Federated Learning with Enhanced Nesterov-Newton Sketch](https://mlsanity.com/paper/2409.15216/) (2024)
- [Online Statistical Inference of Constrained Stochastic Optimization via Random Scaling](https://mlsanity.com/paper/2505.18327/) (2025)
- [Sequential Least-Squares Estimators with Fast Randomized Sketching for Linear Statistical Models](https://mlsanity.com/paper/2509.06856/) (2025)
- [The Advantages of Fresh Sketching for Ridge Regression](https://mlsanity.com/paper/2609.38565/) (2026)

## Abstract (arXiv)

We propose a randomized algorithm with quadratic convergence rate for convex optimization problems with a self-concordant, composite, strongly convex objective function. Our method is based on performing an approximate Newton step using a random projection of the Hessian. Our first contribution is to show that, at each iteration, the embedding dimension (or sketch size) can be as small as the effective dimension of the Hessian matrix. Leveraging this novel fundamental result, we design an algorithm with a sketch size proportional to the effective dimension and which exhibits a quadratic rate of convergence. This result dramatically improves on the classical linear-quadratic convergence rates of state-of-the-art sub-sampled Newton methods. However, in most practical cases, the effective dimension is not known beforehand, and this raises the question of how to pick a sketch size as small as the effective dimension while preserving a quadratic convergence rate. Our second and main contribution is thus to propose an adaptive sketch size algorithm with quadratic convergence rate and which does not require prior knowledge or estimation of the effective dimension: at each iteration, it starts with a small sketch size, and increases it until quadratic progress is achieved. Importantly, we show that the embedding dimension remains proportional to the effective dimension throughout the entire path and that our method achieves state-of-the-art computational complexity for solving convex optimization programs with a strongly convex component.