Timezone: »

 
Poster
Adaptive Newton Method for Empirical Risk Minimization to Statistical Accuracy
Aryan Mokhtari · Hadi Daneshmand · Aurelien Lucchi · Thomas Hofmann · Alejandro Ribeiro

Tue Dec 06 09:00 AM -- 12:30 PM (PST) @ Area 5+6+7+8 #91 #None
in Tuesday Posters »

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 that we can iteratively increase the sample size while applying single Newton iterations without line search and staying within the statistical accuracy of the regularized empirical risk. In particular, we can double the size of the training set in each iteration when the number of samples is sufficiently large. Numerical experiments on various datasets confirm the possibility of increasing the sample size by factor 2 at each iteration which implies that Ada Newton achieves the statistical accuracy of the full training set with about two passes over the dataset.

Keywords: Large Scale Learning and Big Data · Convex Optimization

Author Information

Aryan Mokhtari (University of Pennsylvania)
Hadi Daneshmand Daneshmand (ETH Zurich)
Aurelien Lucchi (ETH Zurich)
Thomas Hofmann (ETH Zurich)
Alejandro Ribeiro (University of Pennsylvania)

More from the Same Authors