Safe Feature Elimination in Sparse Supervised Learning

Abstract

We investigate fast methods that allow to quickly eliminate variables (features) in supervised learning problems involving a convex loss function and a $l_1$-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.

New version is on arXiv:1009.4219

References in corpus (11)

• Rejoinder to "Least angle regression" by Efron et al
• Least Angle Regression
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Pathwise coordinate optimization

Cited by in corpus (48)

• Lasso Screening Rules via Dual Polytope Projection
• Fixed Point Strategies in Data Science
• Screening Tests for Lasso Problems
• Dynamic Screening: Accelerating First-Order Algorithms for the Lasso and Group-Lasso
• Safe Screening With Variational Inequalities and Its Application to LASSO
• Mind the duality gap: safer rules for the Lasso
• Scaling SVM and Least Absolute Deviations via Exact Data Reduction
• GAP Safe Screening Rules for Sparse-Group-Lasso
• Scaling Up Sparse Support Vector Machines by Simultaneous Feature and Sample Reduction
• Efficient Smoothed Concomitant Lasso Estimation for High Dimensional Regression
• Screening Sinkhorn Algorithm for Regularized Optimal Transport
• GAP Safe screening rules for sparse multi-task and multi-class models
• Two-Layer Feature Reduction for Sparse-Group Lasso via Decomposition of Convex Sets
• Concise comparative summaries (CCS) of large text corpora with a human experiment
• On the Distribution, Model Selection Properties and Uniqueness of the Lasso Estimator in Low and High Dimensions
• Gap Safe screening rules for sparsity enforcing penalties
• WHInter: A Working set algorithm for High-dimensional sparse second order Interaction models
• Screening Rules for Overlapping Group Lasso
• Safe squeezing for antisparse coding
• Safe Screening for Multi-Task Feature Learning with Multiple Data Matrices
• Dual Extrapolation for Sparse Generalized Linear Models
• From safe screening rules to working sets for faster Lasso-type solvers
• Safe Sample Screening for Support Vector Machines
• Fast OSCAR and OWL Regression via Safe Screening Rules
• Efficient Mixed-Norm Regularization: Algorithms and Safe Screening Methods
• Safe Grid Search with Optimal Complexity
• The Statistics of Streaming Sparse Regression
• Stable safe screening and structured dictionaries for faster L1 regularization
• The Geometry of Uniqueness, Sparsity and Clustering in Penalized Estimation
• Regularization Path of Cross-Validation Error Lower Bounds
• A scalable hierarchical lasso for gene-environment interactions
• Learning step sizes for unfolded sparse coding
• Feedback-Controlled Sequential Lasso Screening
• The Strong Screening Rule for SLOPE
• Screening Rules and its Complexity for Active Set Identification
• Safe Feature Pruning for Sparse High-Order Interaction Models
• Tuning parameter selection rules for nuclear norm regularized multivariate linear regression
• The Symmetry of a Simple Optimization Problem in Lasso Screening
• Quick sensitivity analysis for incremental data modification and its application to leave-one-out CV in linear classification problems
• An Algorithmic Framework for Computing Validation Performance Bounds by Using Suboptimal Models
• Safe Active Feature Selection for Sparse Learning
• Safe Screening for Sparse Conditional Random Fields
• Safe Feature Elimination for Non-Negativity Constrained Convex Optimization
• Accelerated Sparse Bayesian Learning via Screening Test and Its Applications
• Regularization parameter selection for low rank matrix recovery
• Successive Ray Refinement and Its Application to Coordinate Descent for LASSO
• l1-norm quantile regression screening rule via the dual circumscribed sphere
• Persistent Reductions in Regularized Loss Minimization for Variable Selection