  We consider large scale empirical risk minimization (ERM) problems, where
both the problem dimension and variable size is large. In these cases, most
second order methods are infeasible due to the high cost in both computing the
Hessian over all samples and computing its inverse in high dimensions. In this
paper, we propose a novel adaptive sample size second-order method, which
reduces the cost of computing the Hessian by solving a sequence of ERM problems
corresponding to a subset of samples and lowers the cost of computing the
Hessian inverse using a truncated eigenvalue decomposition. We show that while
we geometrically increase the size of the training set at each stage, a single
iteration of the truncated Newton method is sufficient to solve the new ERM
within its statistical accuracy. Moreover, for a large number of samples we are
allowed to double the size of the training set at each stage, and the proposed
method subsequently reaches the statistical accuracy of the full training set
approximately after two effective passes. In addition to this theoretical
result, we show empirically on a number of well known data sets that the
proposed truncated adaptive sample size algorithm outperforms stochastic
alternatives for solving ERM problems.
