  Kernel logistic regression (KLR) is a conventional nonlinear classifier in
machine learning. With the explosive growth of data size, the storage and
computation of large dense kernel matrices is a major challenge in scaling KLR.
Even the nystr\"{o}m approximation is applied to solve KLR, it also faces the
time complexity of $O(nc^2)$ and the space complexity of $O(nc)$, where $n$ is
the number of training instances and $c$ is the sampling size. In this paper,
we propose a fast Newton method efficiently solving large-scale KLR problems by
exploiting the storage and computing advantages of multilevel circulant matrix
(MCM). Specifically, by approximating the kernel matrix with an MCM, the
storage space is reduced to $O(n)$, and further approximating the coefficient
matrix of the Newton equation as MCM, the computational complexity of Newton
iteration is reduced to $O(n \log n)$. The proposed method can run in
log-linear time complexity per iteration, because the multiplication of MCM (or
its inverse) and vector can be implemented the multidimensional fast Fourier
transform (mFFT). Experimental results on some large-scale
binary-classification and multi-classification problems show that the proposed
method enables KLR to scale to large scale problems with less memory
consumption and less training time without sacrificing test accuracy.
