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.

考虑使用面向低秩分解的凸函数 F (w) 最小化问题，提出一种基于不均匀子采样和不精确更新的随机牛顿型算法来降低计算复杂度，研究了两个基于块范数平方和块部分杠杆分数的非均匀采样分布，理论和实验都表明此类算法具有线性 - 二次收敛率，相较于现有方法，具有更低的计算复杂度和更好的计算鲁棒性。