Parametric Programming Approach for More Powerful and General Lasso Selective Inference

Vo Nguyen Le Duy, Ichiro TakeuchiAISTATS 2021 · OpenReview

Abstract

Selective Inference (SI) has been actively studied in the past few years for conducting inference on the features of linear models that are adaptively selected by feature selection methods such as Lasso. The basic idea of SI is to make inference conditional on the selection event. Unfortunately, the main limitation of the original SI approach for Lasso is that the inference is conducted not only conditional on the selected features but also on their signs—this leads to loss of power because of over-conditioning. Although this limitation can be circumvented by considering the union of such selection events for all possible combinations of signs, this is only feasible when the number of selected features is sufficiently small. To address this computational bottleneck, we propose a parametric programming-based method that can conduct SI without conditioning on signs even when we have thousands of active features. The main idea is to compute the continuum path of Lasso solutions in the direction of a test statistic, and identify the subset of the data space corresponding to the feature selection event by following the solution path. The proposed parametric programming-based method not only avoids the aforementioned computational bottleneck but also improves the performance and practicality of SI for Lasso in various respects. We conduct several experiments to demonstrate the effectiveness and efficiency of our proposed method.

Introduction

In modern data science, the practice of using the same dataset for both feature selection (e.g., via Lasso) and subsequent significance testing—often called "double dipping"—introduces significant selection bias. Features can appear statistically significant simply because they were chosen by the model. Selective Inference (SI) addresses this by calculating p-values and confidence intervals conditional on the selection event.

The current "gold standard" for Lasso SI, established by Lee et al. (2016), conditions inference on both the selected features and their specific signs (positive or negative). While this simplifies the geometry of the selection event into a "polytope," it results in over-conditioning. By restricting analysis to a narrow subset of the data space, statistical power is sacrificed, leading to wider confidence intervals. Until now, avoiding this sign-conditioning was computationally prohibitive for models with many features, as it required evaluating an exponential number of sign combinations ($2^{|A|}$).

Methodology: Parametric Programming-based SI

We propose a Parametric Programming (PP) approach that bypasses the exponential explosion of sign combinations. Instead of characterizing the entire selection event geometrically, the method focuses on a "parametrized line" in the data space that aligns with the direction of the test statistic.

Conceptual overview of the proposed parametric programming approach for Lasso selective inference.

The core algorithm relies on several key technical insights:

  1. Piecewise Linear Homotopy: The Lasso solution is shown to be a piecewise linear function along the parametrized line.
  2. Transition Points: By moving along this line, the algorithm identifies "transition points" where the active feature set changes.
  3. Truncation Region Identification: Following this solution path allows for the exact identification of the "truncation region"—the subset of the data space where the features of interest are selected, regardless of their signs.
  4. Handling Cross-Validation: This path-following approach can also characterize complex selection events, such as when the regularization parameter ($\lambda$) is determined via Cross-Validation (CV), a scenario that was previously a major computational bottleneck.

Experimental Evaluation

The effectiveness of the proposed method was evaluated using both synthetic and real-world datasets.

Synthetic Data

Synthetic experiments were used to verify False Positive Rate (FPR) control and compare True Positive Rates (TPR) across varying sample sizes ($n$) and feature counts ($p$). As shown in Figure 2, the proposed method (TN-A) consistently outperforms the standard sign-conditioned method (TN-As) in terms of power and precision.

Comparison of statistical performance (FPR, TPR, and CI length) between the proposed method (TN-A) and the standard sign-conditioned method (TN-As).

Real-World Bioinformatics Datasets

The method was applied to three high-dimensional datasets from the CoEPrA (Comparative Evaluation of Prediction Methodologies) competition. These datasets involve thousands of descriptors ($p \approx 5,800$) for peptides. The proposed method demonstrated remarkable efficiency, computing p-values in approximately 0.34 to 0.37 seconds per feature.

Key Results and Insights

  • Increased Statistical Power: By conditioning only on the selected features and not their signs, the method utilizes more data information, resulting in higher TPR and significantly shorter confidence intervals.
  • Computational Efficiency and Scalability: The method avoids the $2^{|A|}$ bottleneck by only visiting relevant parts of the solution path. It successfully handled thousands of active features, whereas previous sign-free attempts failed beyond 15 features.
  • Robustness: The method maintained strict control over the FPR even under non-normal noise distributions, such as Laplace or Skew-normal distributions.

Discussion and Future Work

While the proposed method offers significant advantages, it does have limitations. The worst-case computational complexity could theoretically be high, although this was not observed in practice. Additionally, the current theory assumes a unique Lasso solution (general position), though this can be mitigated using elastic net or ridge penalties.

Future research may extend this path-following approach to other selection models beyond Lasso, potentially enabling robust Selective Inference for a wider array of complex machine learning pipelines.

Summary updated

Abstract

Selective Inference (SI) has been actively studied in the past few years for conducting inference on the features of linear models that are adaptively selected by feature selection methods such as Lasso. The basic idea of SI is to make inference conditional on the selection event. Unfortunately, the main limitation of the original SI approach for Lasso is that the inference is conducted not only conditional on the selected features but also on their signs—this leads to loss of power because of over-conditioning. Although this limitation can be circumvented by considering the union of such selection events for all possible combinations of signs, this is only feasible when the number of selected features is sufficiently small. To address this computational bottleneck, we propose a parametric programming-based method that can conduct SI without conditioning on signs even when we have thousands of active features. The main idea is to compute the continuum path of Lasso solutions in the direction of a test statistic, and identify the subset of the data space corresponding to the feature selection event by following the solution path. The proposed parametric programming-based method not only avoids the aforementioned computational bottleneck but also improves the performance and practicality of SI for Lasso in various respects. We conduct several experiments to demonstrate the effectiveness and efficiency of our proposed method.
BibTeX
@inproceedings{duy2021parametric,
  author = {Vo Nguyen Le Duy and Ichiro Takeuchi},
  title = {{Parametric Programming Approach for More Powerful and General Lasso Selective Inference}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2021},
  url = {https://openreview.net/forum?id=R5bGebowSYJ},
}
Figure