# Adaptive Newton Method for Empirical Risk Minimization to Statistical Accuracy

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 May 2016.

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

- [Regularized Newton Method with Global O(1/k2) Convergence](https://mlsanity.com/paper/2112.02089/) (2021)
- [Sampling Through the Lens of Sequential Decision Making](https://mlsanity.com/paper/2208.08056/) (2022)
- [Exploiting Local Convergence of Quasi-Newton Methods Globally: Adaptive Sample Size Approach](https://mlsanity.com/paper/2106.05445/) (2021)
- [Pairwise Learning via Stagewise Training in Proximal Setting](https://mlsanity.com/paper/2208.04075/) (2022)
- [Robust Federated Learning under Adversarial Attacks via Loss-Based Client Clustering](https://mlsanity.com/paper/2508.12672/) (2025)

## Abstract (arXiv)

We consider empirical risk minimization for large-scale datasets. We introduce Ada Newton as an adaptive algorithm that uses Newton's method with adaptive sample sizes. The main idea of Ada Newton is to increase the size of the training set by a factor larger than one in a way that the minimization variable for the current training set is in the local neighborhood of the optimal argument of the next training set. This allows to exploit the quadratic convergence property of Newton's method and reach the statistical accuracy of each training set with only one iteration of Newton's method. We show theoretically and empirically that Ada Newton can double the size of the training set in each iteration to achieve the statistical accuracy of the full training set with about two passes over the dataset.