Feature Selection for Ridge Regression with Provable Guarantees.

Area of Science:

• Machine Learning
• Statistical Learning Theory

Background:

• Feature selection is crucial for efficient and generalizable machine learning models.
• Regularized least-squares classification and ridge regression are widely used for regression and classification tasks.

Purpose of the Study:

• To introduce novel unsupervised feature selection methods for regularized least-squares classification and ridge regression.
• To provide theoretical guarantees on the generalization performance of the selected features.
• To compare the proposed methods with existing feature selection techniques.

Main Methods:

• Single-set spectral sparsification: a deterministic sampling-based feature selection for regularized least-squares classification.
• Leverage-score sampling: an unsupervised randomized feature selection for ridge regression.
• Derivation of risk bounds in the fixed design setting for both methods.

Main Results:

• Both single-set spectral sparsification and leverage-score sampling provide worst-case generalization guarantees.
• The risk in the sampled feature space is comparable to the risk in the full-feature space.
• Experimental results on synthetic and real-world datasets (TechTC-300) show superior performance compared to existing methods.

Conclusions:

• The proposed feature selection methods are effective for regularized least-squares classification and ridge regression.
• These unsupervised methods offer theoretical advantages and practical improvements in performance.
• The findings support the use of spectral sparsification and leverage-score sampling for efficient and accurate machine learning.