Safe Feature Elimination for the LASSO and Sparse Supervised Learning Problems
arXiv:1009.4219
Abstract
We describe a fast method to eliminate features (variables) in l1 -penalized least-square regression (or LASSO) problems. The elimination of features leads to a potentially substantial reduction in running time, specially for large values of the penalty parameter. Our method is not heuristic: it only eliminates features that are guaranteed to be absent after solving the LASSO problem. The feature elimination step is easy to parallelize and can test each feature for elimination independently. Moreover, the computational effort of our method is negligible compared to that of solving the LASSO problem - roughly it is the same as single gradient step. Our method extends the scope of existing LASSO algorithms to treat larger data sets, previously out of their reach. We show how our method can be extended to general l1 -penalized convex problems and present preliminary results for the Sparse Support Vector Machine and Logistic Regression problems.
Submitted to JMLR in April 2011
References in corpus (2)
Cited by in corpus (42)
- Screening Tests for Lasso Problems
- Dynamic Screening: Accelerating First-Order Algorithms for the Lasso and Group-Lasso
- A Safe Screening Rule for Sparse Logistic Regression
- An Equivalence between the Lasso and Support Vector Machines
- Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares
- Estimating Sparse Signals Using Integrated Wideband Dictionaries
- Hybrid safe-strong rules for efficient optimization in lasso-type problems
- Supervised sequential pattern mining of event sequences in sport to identify important patterns of play: an application to rugby union
- Simultaneous Safe Screening of Features and Samples in Doubly Sparse Modeling
- Distance Metric Learning for Graph Structured Data
- Graphical Lasso and Thresholding: Equivalence and Closed-form Solutions
- Safe RuleFit: Learning Optimal Sparse Rule Model by Meta Safe Screening
- Fast non-coplanar beam orientation optimization based on group sparsity
- ExSIS: Extended Sure Independence Screening for Ultrahigh-dimensional Linear Models
- Secure Approximation Guarantee for Cryptographically Private Empirical Risk Minimization
- Natural coordinate descent algorithm for L1-penalised regression in generalised linear models
- Safe Screening for the Generalized Conditional Gradient Method
- Dynamic Sasvi: Strong Safe Screening for Norm-Regularized Least Squares
- Unbalanced Optimal Transport through Non-negative Penalized Linear Regression
- Safe Triplet Screening for Distance Metric Learning
- Balancing Statistical and Computational Precision: A General Theory and Applications to Sparse Regression
- A Fast, Principled Working Set Algorithm for Exploiting Piecewise Linear Structure in Convex Problems
- Learning Hierarchical Interactions at Scale: A Convex Optimization Approach
- Adaptive Sieving with PPDNA: Generating Solution Paths of Exclusive Lasso Models
- One to beat them all: "RYU" -- a unifying framework for the construction of safe balls
- Sparse Identification of Posynomial Models
- Smooth Bilevel Programming for Sparse Regularization
- Screening Data Points in Empirical Risk Minimization via Ellipsoidal Regions and Safe Loss Functions
- Group Invariance and Computational Sufficiency
- Interval-based Prediction Uncertainty Bound Computation in Learning with Missing Values
- Large-scale Collaborative Imaging Genetics Studies of Risk Genetic Factors for Alzheimer's Disease Across Multiple Institutions
- Learning High Order Feature Interactions with Fine Control Kernels
- Safe Sample Screening for Robust Support Vector Machine
- Safe Screening Rules for -Regression
- Nonsmoothness in Machine Learning: specific structure, proximal identification, and applications
- On Inductive Biases for Machine Learning in Data Constrained Settings
- Node-screening tests for L0-penalized least-squares problem with supplementary material
- Screening for Sparse Online Learning
- Tighter Bound Estimation of Sensitivity Analysis for Incremental and Decremental Data Modification
- On Newton Screening
- Safe preselection in lasso-type problems by cross-validation freezing
- Analytic solution and stationary phase approximation for the Bayesian lasso and elastic net