Sub-sampled Newton Methods with Non-uniform Sampling

We consider the problem of finding the minimizer of a convex function F: mathbb Rd rightarrow mathbb R of the form F(w) := sumi=1n fi(w) + R(w) where a low-rank factorization of nabla2 fi(w) is readily available. We consider the regime where n gg d. As second-order methods prove to be effective in finding the minimizer to a high-precision, in this work, we propose randomized Newton-type algorithms that exploit textitnon-uniform sub-sampling of nabla2 fi(w)i=1n, as well as inexact updates, as means to reduce the computational complexity. Two non-uniform sampling distributions based on it block norm squares and it block partial leverage scores are considered in order to capture important terms among nabla2 fi(w)i=1n. We show that at each iteration non-uniformly sampling at most mathcal O(d log d) terms from nabla2 fi(w)i=1n is sufficient to achieve a linear-quadratic convergence rate in w when a suitable initial point is provided. In addition, we show that our algorithms achieve a lower computational complexity and exhibit more robustness and better dependence on problem specific quantities, such as the condition number, compared to similar existing methods, especially the ones based on uniform sampling. Finally, we empirically demonstrate that our methods are at least twice as fast as Newton's methods with ridge logistic regression on several real datasets.