Safe Screening With Variational Inequalities and Its Application to LASSO

Abstract

Sparse learning techniques have been routinely used for feature selection as the resulting model usually has a small number of non-zero entries. Safe screening, which eliminates the features that are guaranteed to have zero coefficients for a certain value of the regularization parameter, is a technique for improving the computational efficiency. Safe screening is gaining increasing attention since 1) solving sparse learning formulations usually has a high computational cost especially when the number of features is large and 2) one needs to try several regularization parameters to select a suitable model. In this paper, we propose an approach called "Sasvi" (Safe screening with variational inequalities). Sasvi makes use of the variational inequality that provides the sufficient and necessary optimality condition for the dual problem. Several existing approaches for Lasso screening can be casted as relaxed versions of the proposed Sasvi, thus Sasvi provides a stronger safe screening rule. We further study the monotone properties of Sasvi for Lasso, based on which a sure removal regularization parameter can be identified for each feature. Experimental results on both synthetic and real data sets are reported to demonstrate the effectiveness of the proposed Sasvi for Lasso screening.

Accepted by International Conference on Machine Learning 2014

References in corpus (1)

• Safe Feature Elimination in Sparse Supervised Learning

Cited by in corpus (25)

• Screening Tests for Lasso Problems
• Scaling SVM and Least Absolute Deviations via Exact Data Reduction
• Estimating Sparse Signals Using Integrated Wideband Dictionaries
• Two-Layer Feature Reduction for Sparse-Group Lasso via Decomposition of Convex Sets
• Simultaneous Safe Screening of Features and Samples in Doubly Sparse Modeling
• Screening Rules for Overlapping Group Lasso
• Fast OSCAR and OWL Regression via Safe Screening Rules
• Expanding boundaries of Gap Safe screening
• Stable safe screening and structured dictionaries for faster L1 regularization
• Safe Pattern Pruning: An Efficient Approach for Predictive Pattern Mining
• Secure Approximation Guarantee for Cryptographically Private Empirical Risk Minimization
• Dynamic Sasvi: Strong Safe Screening for Norm-Regularized Least Squares
• Regularization Path of Cross-Validation Error Lower Bounds
• A Fast, Principled Working Set Algorithm for Exploiting Piecewise Linear Structure in Convex Problems
• Safe Feature Pruning for Sparse High-Order Interaction Models
• Group Invariance and Computational Sufficiency
• One to beat them all: "RYU" -- a unifying framework for the construction of safe balls
• On Newton Screening
• Safe Adaptive Importance Sampling
• Screening for Sparse Online Learning
• Tighter Bound Estimation of Sensitivity Analysis for Incremental and Decremental Data Modification
• Quick sensitivity analysis for incremental data modification and its application to leave-one-out CV in linear classification problems
• Interval-based Prediction Uncertainty Bound Computation in Learning with Missing Values
• Successive Ray Refinement and Its Application to Coordinate Descent for LASSO
• An Algorithmic Framework for Computing Validation Performance Bounds by Using Suboptimal Models