  We propose a fast algorithm for computing the entire ridge regression
regularization path in nearly linear time. Our method constructs a basis on
which the solution of ridge regression can be computed instantly for any value
of the regularization parameter. Consequently, linear models can be tuned via
cross-validation or other risk estimation strategies with substantially better
efficiency. The algorithm is based on iteratively sketching the Krylov subspace
with a binomial decomposition over the regularization path. We provide a
convergence analysis with various sketching matrices and show that it improves
the state-of-the-art computational complexity. We also provide a technique to
adaptively estimate the sketching dimension. This algorithm works for both the
over-determined and under-determined problems. We also provide an extension for
matrix-valued ridge regression. The numerical results on real medium and large
scale ridge regression tasks illustrate the effectiveness of the proposed
method compared to standard baselines which require super-linear computational
time.
