  We consider the problem of finding the minimizer of a convex function $F:
\mathbb R^d \rightarrow \mathbb R$ of the form $F(w) := \sum_{i=1}^n f_i(w) +
R(w)$ where a low-rank factorization of $\nabla^2 f_i(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 \textit{non-uniform}
sub-sampling of $\{\nabla^2 f_i(w)\}_{i=1}^{n}$, 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 $\{\nabla^2
f_i(w)\}_{i=1}^{n}$. We show that at each iteration non-uniformly sampling at
most $\mathcal O(d \log d)$ terms from $\{\nabla^2 f_i(w)\}_{i=1}^{n}$ 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.
