Adaptive Newton Method for Empirical Risk Minimization to Statistical Accuracy

By Aryan Mokhtari, Hadi Daneshmand, Aurélien Lucchi, Thomas Hofmann, Alejandro Ribeiro. 2016

33 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Mechanics, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Peter Richtárik
2. Simon Lacoste-Julien
3. Nicolas Loizou
4. Aryan Mokhtari
5. Issam Hadj Laradji
6. Alejandro Ribeiro
7. Jakub Konecný
8. Mark W. Schmidt

In Computational Mechanics

1. Peter Richtárik
2. Simon Lacoste-Julien
3. Aryan Mokhtari
4. Nicolas Loizou
5. Issam Hadj Laradji
6. Martin Takác
7. Alejandro Ribeiro
8. Sharan Vaswani

In Optimization & Training

1. Simon Lacoste-Julien
2. Peter Richtárik
3. Nicolas Loizou
4. Issam Hadj Laradji
5. Sharan Vaswani
6. Aryan Mokhtari
7. Mark W. Schmidt
8. Martin Takác

Citations in the corpus

• Fast and Furious Convergence: Stochastic Second Order Methods under Interpolation (2019, methodology): “Mokhtari et al. (2016); Eisen et al. (2018) introduce the Ada Newton method that computes a geometrically increasing batch-size based on a targeted statistical accuracy and show local quadratic convergence for self-concordant functions with high probability.”
• Large Scale Empirical Risk Minimization via Truncated Adaptive Newton Method (2017, methodology): “We consider in this paper the empirical risk minimization (ERM) problem for a convex function f ( x , z ), where z is a realization of a random variable Z .”
• Quasi-Newton Methods for Deep Learning: Forget the Past, Just Sample (2019, background): “[41] Aryan Mokhtari, Hadi Daneshmand, Aurelien Lucchi, Thomas Hofmann, and Alejandro Ribeiro.”