First-Order Adaptive Sample Size Methods to Reduce Complexity of Empirical Risk Minimization
This paper studies empirical risk minimization (ERM) problems for large-scale datasets and incorporates the idea of adaptive sample size methods to improve the guaranteed convergence bounds for first-order stochastic and deterministic methods. In contrast to traditional methods that attempt to solve the ERM problem corresponding to the full dataset directly, adaptive sample size schemes start with a small number of samples and solve the corresponding ERM problem to its statistical accuracy. The sample size is then grown geometrically -e.g., scaling by a factor of two -and use the solution of the previous ERM as a warm start for the new ERM. Theoretical analyses show that the use of adaptive sample size methods reduces the overall computational cost of achieving the statistical accuracy of the whole dataset for a broad range of deterministic and stochastic first-order methods. The gains are specific to the choice of method. When particularized to, e.g., accelerated gradient descent and stochastic variance reduce gradient, the computational cost advantage is a logarithm of the number of training samples. Numerical experiments on various datasets confirm theoretical claims and showcase the gains of using the proposed adaptive sample size scheme.
The paper proposes an adaptive sample size strategy applied to first order methods to reduce the complexity of solving the ERM problems. By definition, the ERM problem respect to a given dataset D is to minimize the average loss over it. Instead of handling the full dataset all at once, the proposed algorithm starts with a small subset of D and first minimize the ERM problem respect to this subset. After reaching the desired statistical accuracy on this small problem, it doubles the size of the subset and update the problem with the new subset. The strategy repeats such procedure until the full dataset is included. The paper shows an improvement both in theoretical analysis and in experiments. 
The paper is very clear, the theoretical proof is correct and well presented. I find the paper very interesting and I like the idea of taking into account the statistical problem behind the ERM problem. A question I have is that the algorithm requires to predefine the statistical accuracy and uses it explicitly as a parameter in the construction of the algorithm, is there any way to adapt it by removing its dependency in the algorithm? Because it is demonstrated in the experiments that the choice of such accuracy do influence the performance. (In MNIST, the performance of taking 1/n is better than 1/sqrt{n}) The current algorithm will stop once the predefine accuracy is attained which is eventually improvable by varying it. 
Besides, I am a bit concerned about the novelty of the paper. As mentioned by the author, there is a big overlap with the reference [12]. The main strategy, including the regularized subproblem and the proposition 1, is the same as in [12]. The only difference is to replace the Newton's method by first order methods and provide the analysis of the inner loop complexity. 
Overall, I find the idea interesting but the contribution seems to be limited, therefore I vote for a weakly accept.