  We propose a fast proximal Newton-type algorithm for minimizing regularized
finite sums that returns an $\epsilon$-suboptimal point in
$\tilde{\mathcal{O}}(d(n + \sqrt{\kappa d})\log(\frac{1}{\epsilon}))$ FLOPS,
where $n$ is number of samples, $d$ is feature dimension, and $\kappa$ is the
condition number. As long as $n > d$, the proposed method is more efficient
than state-of-the-art accelerated stochastic first-order methods for non-smooth
regularizers which requires $\tilde{\mathcal{O}}(d(n + \sqrt{\kappa
n})\log(\frac{1}{\epsilon}))$ FLOPS. The key idea is to form the subsampled
Newton subproblem in a way that preserves the finite sum structure of the
objective, thereby allowing us to leverage recent developments in stochastic
first-order methods to solve the subproblem. Experimental results verify that
the proposed algorithm outperforms previous algorithms for $\ell_1$-regularized
logistic regression on real datasets.
