  In supervised learning using kernel methods, we often encounter a large-scale
finite-sum minimization over a reproducing kernel Hilbert space (RKHS).
Large-scale finite-sum problems can be solved using efficient variants of
Newton method, where the Hessian is approximated via sub-samples of data. In
RKHS, however, the dependence of the penalty function to kernel makes standard
sub-sampling approaches inapplicable, since the gram matrix is not readily
available in a low-rank form. In this paper, we observe that for this class of
problems, one can naturally use kernel approximation to speed up the Newton
method. Focusing on randomized features for kernel approximation, we provide a
novel second-order algorithm that enjoys local superlinear convergence and
global linear convergence (with high probability). We derive the theoretical
lower bound for the number of random features required for the approximated
Hessian to be close to the true Hessian in the norm sense. Our numerical
experiments on real-world data verify the efficiency of our method compared to
several benchmarks.
