ET-Lasso: A New Efficient Tuning of Lasso-type Regularization for High-Dimensional Data

Songshan Yang, Jiawei Wen, Xiang Zhan, Daniel Kifer

TL;DR

This paper introduces ET-Lasso, a novel method for efficiently selecting relevant features in high-dimensional datasets. It tackles the challenge of choosing the right regularization parameter in Lasso models by cleverly using "pseudo-features" to create a clear separation between truly important and irrelevant variables, leading to more accurate and interpretable models.

What Problem Does This Paper Address?

High-dimensional data, where the number of features (p) far exceeds the number of observations (n), is increasingly common in fields like genomics, finance, and medical imaging. The Lasso (Least Absolute Shrinkage and Selection Operator) is a popular technique for simultaneously selecting relevant features and estimating model coefficients in such settings. However, a critical challenge with Lasso is selecting the optimal "tuning parameter" (λ), which controls the sparsity of the model. Traditional methods like cross-validation or BIC can be computationally expensive and may not consistently identify the true set of active features, especially when p is extremely large. Existing methods like "Knockoff" offer feature selection with controlled false discovery rates but can be sensitive to hyperparameter choices and computationally demanding. This paper aims to provide an efficient and consistent method for tuning Lasso in high-dimensional scenarios.

Methods

The core innovation of ET-Lasso lies in its use of "pseudo-features" to guide the selection of the tuning parameter. The authors construct these pseudo-features by permuting the original data features. These permuted features are designed to be inactive and uncorrelated with the response variable, serving as a benchmark.

The ET-Lasso algorithm works in two stages:

  1. Pseudo-feature Generation and Initial Selection: Two sets of permuted features are generated. The first set is combined with the original features to form an augmented design matrix. Lasso is then applied to this augmented matrix, and a cutoff value (Cp) is determined based on the tuning parameters at which these permuted features enter the model. This cutoff helps to separate active from inactive features.
  2. Refined Selection: The features identified in the first stage are then combined with the second set of permuted features. Lasso is applied again to this new augmented matrix, and a final set of features is selected using a similar cutoff mechanism.

This two-stage approach aims to balance precision and recall, improving the robustness of the feature selection. The theoretical underpinnings suggest that this method can achieve a clear separation between active and inactive features with high probability.

Datasets

The paper evaluates ET-Lasso on several datasets:

  • Simulated Data: The authors generate synthetic data with varying sample sizes (n=500), numbers of predictors (p=1000, 2000), and covariance structures (independent, AR(1), compound symmetric). The number of active features (k) is also varied (k=10, 15).
  • FIFA 2019 Dataset: A real-world dataset used for predicting player wages, containing 84 attributes for 1500 players.
  • Stock Price Prediction: Data from four major companies (GOOG, IBM, AMZN, WFC) is used to predict stock prices, incorporating lagged stock prices as features.
  • Chinese Supermarket Data: A dataset recording customer numbers and sales volumes for 6398 products, used for prediction.
  • Human Activity Recognition (HAR) Data: A UCI dataset used for a binary classification task (walking vs. standing) with 561 extracted features.

Key Insights and Ideas

  • Pseudo-features as a "Gold Standard": The core idea of using permuted, inactive features as a benchmark to identify truly active features is a clever way to overcome the limitations of traditional tuning parameter selection methods.
  • Guaranteed Separation: The theoretical analysis suggests that ET-Lasso can achieve a statistically significant separation between the importance scores of active and inactive features, which is crucial for reliable selection.
  • Efficiency and Scalability: Unlike some existing methods that require extensive computation (e.g., cross-validation, Knockoff), ET-Lasso is designed to be computationally efficient, making it suitable for very high-dimensional problems.
  • Robustness to Hyperparameters: ET-Lasso aims to be less sensitive to hyperparameter choices compared to methods like Knockoff, which require careful tuning of the false discovery rate threshold.

Key Results

  • Simulation Studies: ET-Lasso consistently achieved higher precision and F1-scores compared to Lasso+BIC, Lasso+CV, and Lasso+ESCV across various simulation settings. It also demonstrated superior recall in many cases. Knockoff methods sometimes struggled with low recall or were computationally very expensive.
  • Real-World Data:
    • On the FIFA 2019 dataset, ET-Lasso achieved the best Mean Squared Error (MSE) with a significantly smaller number of selected features compared to CV and BIC.
  • For stock price prediction, ET-Lasso outperformed other methods in terms of MSE and model complexity, often selecting a fraction of the features chosen by CV and ESCV.
  • In the Chinese supermarket data experiment, ET-Lasso again showed the smallest prediction MSE and a more parsimonious model than CV and BIC.
  • For the Human Activity Recognition classification task, ET-Lasso demonstrated the best classification accuracy.
  • Computational Efficiency: ET-Lasso was consistently faster than Knockoff methods and often more efficient than cross-validation-based approaches.

Limitations and Future Work

  • Two-Stage Approach: While the two-stage approach aims to balance precision and recall, the paper notes that more iterations could potentially offer better control over false discoveries.
  • Extension to Classification: The paper demonstrates ET-Lasso's performance in a classification setting (logistic regression) but acknowledges that its theoretical foundation is primarily for linear regression. Further theoretical investigation into its classification capabilities might be warranted.
  • Hyperparameter Sensitivity (Knockoff): The paper highlights the sensitivity of Knockoff methods to FDR thresholds, suggesting ET-Lasso's advantage in this regard. However, ET-Lasso itself might have implicit sensitivities that could be explored.

Summary updated

Abstract

The $L_1 $ regularization (Lasso) has proven to be a versatile tool to select relevant features and estimate the model coefficients simultaneously and has been widely used in many research areas such as genomes studies, finance, and biomedical imaging. Despite its popularity, it is very challenging to guarantee the feature selection consistency of Lasso especially when the dimension of the data is huge. One way to improve the feature selection consistency is to select an ideal tuning parameter. Traditional tuning criteria mainly focus on minimizing the estimated prediction error or maximizing the posterior model probability, such as cross-validation and BIC, which may either be time-consuming or fail to control the false discovery rate (FDR) when the number of features is extremely large. The other way is to introduce pseudo-features to learn the importance of the original ones. Recently, the Knockoff filter is proposed to control the FDR when performing feature selection. However, its performance is sensitive to the choice of the expected FDR threshold. Motivated by these ideas, we propose a new method using pseudo-features to obtain an ideal tuning parameter. In particular, we present the E fficient T uning of Lasso (ET-Lasso ) to separate active and inactive features by adding permuted features as pseudo-features in linear models. The pseudo-features are constructed to be inactive by nature, which can be used to obtain a cutoff to select the tuning parameter that separates active and inactive features. Experimental studies on both simulations and real-world data applications are provided to show that ET-Lasso can effectively and efficiently select active features under a wide range of scenarios.
BibTeX
@inproceedings{yang2019et,
  author = {Songshan Yang and Jiawei Wen and Xiang Zhan and Daniel Kifer},
  title = {{ET-Lasso: A New Efficient Tuning of Lasso-type Regularization for High-Dimensional Data}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2019},
  doi = {10.1145/3292500.3330910},
}
Figure