Large Scale Empirical Risk Minimization via Truncated Adaptive Newton Method
This incremental improvement addresses computational bottlenecks in large-scale ERM for machine learning practitioners, offering a more efficient alternative to stochastic methods.
The authors tackled the computational challenge of large-scale empirical risk minimization (ERM) by proposing a truncated adaptive Newton method that reduces Hessian computation costs and uses truncated eigenvalue decomposition, achieving the statistical accuracy of the full training set in approximately two effective passes.
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.