  Kernel methods are a popular class of nonlinear predictive models in machine
learning. Scalable algorithms for learning kernel models need to be iterative
in nature, but convergence can be slow due to poor conditioning. Spectral
preconditioning is an important tool to speed-up the convergence of such
iterative algorithms for training kernel models. However computing and storing
a spectral preconditioner can be expensive which can lead to large
computational and storage overheads, precluding the application of kernel
methods to problems with large datasets. A Nystrom approximation of the
spectral preconditioner is often cheaper to compute and store, and has
demonstrated success in practical applications. In this paper we analyze the
trade-offs of using such an approximated preconditioner. Specifically, we show
that a sample of logarithmic size (as a function of the size of the dataset)
enables the Nystrom-based approximated preconditioner to accelerate gradient
descent nearly as well as the exact preconditioner, while also reducing the
computational and storage overheads.
