Safe Feature Elimination in Sparse Supervised Learning

2010/09/17 by Laurent El Ghaoui, Vivian Viallon, Ghaoui, Laurent El +3 · 178 citations
Computer Science · Mathematics · #Artificial intelligence #Artificial neural network #Computer science #Curse of dimensionality #Dimensionality reduction #FOS: Computer and information sciences #FOS: Mathematics #Face and Expression Recognition #Feature (linguistics) #Feature vector #Heuristic #Machine Learning (cs.LG) #Machine Learning and Algorithms #Machine Learning and Data Classification #Machine learning #Optimization and Control (math.OC) #Pattern recognition (psychology) #Semi-supervised learning #Supervised learning #Support vector machine #cs.LG #math.OC

paper · pdf · doi:10.48550/arxiv.1009.3515

published in arXiv (Cornell University) (Cornell University) · New version is on arXiv:1009.4219

openalex publication_date 2010/09/17 · arxiv created 2010/10/26 · arxiv updated 2010/10/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We investigate fast methods that allow to quickly eliminate variables (features) in supervised learning problems involving a convex loss function and a l₁-norm penalty, leading to a potentially substantial reduction in the number of variables prior to running the supervised learning algorithm. The methods are not heuristic: they only eliminate features that are \em guaranteed to be absent after solving the learning problem. Our framework applies to a large class of problems, including support vector machine classification, logistic regression and least-squares. The complexity of the feature elimination step is negligible compared to the typical computational effort involved in the sparse supervised learning problem: it grows linearly with the number of features times the number of examples, with much better count if data is sparse. We apply our method to data sets arising in text classification and observe a dramatic reduction of the dimensionality, hence in computational effort required to solve the learning problem, especially when very sparse classifiers are sought. Our method allows to immediately extend the scope of existing algorithms, allowing us to run them on data sets of sizes that were out of their reach before.

Citations

• Safe Feature Elimination for the LASSO and Sparse Supervised Learning Problems
• Pathwise coordinate optimization
• Least angle regression
• Large-Scale Bayesian Logistic Regression for Text Categorization

Cited by

• From STLS to Projection-based Dictionary Selection in Sparse Regression for System Identification
• Safe Screening Rules for Group SLOPE
• Non-null Shrinkage Regression and Subset Selection via the Fractional Ridge Regression
• Safe screening rules for portfolio optimization with linear and cardinality constraints
• Safe Squeezing for Antisparse Coding
• Adaptive sieving with semismooth Newton proximal augmented Lagrangian algorithm for multi-task Lasso problems
• GAP Safe screening rules for sparse multi-task and multi-class models
• Learning step sizes for unfolded sparse coding
• Accurate Genomic Prediction Of Human Height
• Accurate Genomic Prediction of Human Height

Related

• Safe Feature Elimination for the LASSO and Sparse Supervised Learning Problems
• Direct l_(2,p)-Norm Learning for Feature Selection
• Safe Screening Rules for Generalized Double Sparsity Learning
• Algorithms for Sparse Support Vector Machines
• SLM: End-to-end Feature Selection via Sparse Learnable Masks