  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.
