title: Feature Selection for Ridge Regression with Provable Guarantees.
abstract: We introduce single-set spectral sparsification as a deterministic sampling-based feature selection technique for regularized least-squares classification, which is the classification analog 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 data sets; a subset of TechTC-300 data sets, to support our theory. Experimental results indicate that the proposed methods perform better than the existing feature selection methods.
authors.affiliation: Global Risk Sciences, Paypal, San Jose, CA 95112, U.S.A. saupaul@paypal.com.
authors.forename: Saurabh
authors.initials: S
authors.lastname: Paul
authors.affiliation: Computer Science Department, Rensselaer Polytechnic Institute, Troy, NY 12180, U.S.A. drinep@cs.rpi.edu.
authors.forename: Petros
authors.initials: P
authors.lastname: Drineas