  We introduce single-set spectral sparsification as a deterministic sampling
based feature selection technique for regularized least squares classification,
which is the classification analogue to ridge regression. The method is
unsupervised and gives worst-case guarantees of the generalization power of the
classification function after feature selection with respect to the
classification function obtained using all features. We also introduce
leverage-score sampling as an unsupervised randomized feature selection method
for ridge regression. We provide risk bounds for both single-set spectral
sparsification and leverage-score sampling on ridge regression in the fixed
design setting and show that the risk in the sampled space is comparable to the
risk in the full-feature space. We perform experiments on synthetic and
real-world datasets, namely a subset of TechTC-300 datasets, to support our
theory. Experimental results indicate that the proposed methods perform better
than the existing feature selection methods.
