Post-selection inference with HSIC-Lasso

Tobias Freidling, Benjamin Poignard, Héctor Climente-González, Makoto YamadaICML 2021 · OpenReview

Detecting influential features in non-linear and/or high-dimensional data is a challenging and increasingly important task in machine learning. This paper introduces a rigorous statistical framework for performing inference after using HSIC-Lasso, a powerful non-linear feature selection method. By leveraging the "polyhedral lemma" and asymptotic normality, the authors provide a way to calculate valid p-values that account for the fact that features were chosen based on the data, ensuring tight control over false positives (Type-I error) even in high-dimensional, non-linear settings.

The "Double-Dipping" Problem

In modern machine learning, we often face a "double-dipping" problem: we use a dataset to select the most important features (variable selection) and then use that same data to test if those features are actually significant (inference).

Standard statistical tests assume your model was chosen before looking at the data. When the model is data-driven (like using Lasso to pick features), classical p-values become biased and over-optimistic, leading to a high rate of false discoveries. This is known as the post-selection inference (PSI) problem.

While solutions exist for linear models (like the standard Lasso), many real-world relationships are non-linear. The HSIC-Lasso is a popular kernel-based method for non-linear feature selection, but until now, there was no formal way to perform valid inference on its results without resorting to wasteful techniques like sample splitting or computationally expensive bootstrapping.

Bridging Non-Linear Kernels and Selective Inference

The authors bridge the gap between non-linear kernel methods and selective inference through several key steps:

  1. Asymptotic Framework: They replace biased HSIC estimators with asymptotically normal ones (specifically block and incomplete U-statistics). This allows them to treat the HSIC estimates as a Gaussian random vector in the limit.
  2. The Polyhedral Lemma: The core "trick" of PSI is recognizing that selecting a specific set of features via Lasso-style optimization is equivalent to the data falling into a specific polyhedron (a high-dimensional shape defined by linear inequalities).
  3. Tailored Pivot: They prove that for HSIC-Lasso, the selection event can be characterized as $\{AH \le b\}$. By conditioning on this event, the distribution of their test statistic becomes a truncated Gaussian. They derive a "pivot"—a quantity that follows a Uniform(0,1) distribution under the null hypothesis—allowing for the calculation of exact p-values.
  4. Algorithmic Efficiency: To handle high-dimensional data ($p > n$), they propose a practical pipeline:
  5. Split the data into two folds.
  6. Use the first fold for an initial screening and hyper-parameter ($\lambda$) selection.
  7. Use the second fold for the formal HSIC-Lasso selection and the subsequent PSI testing.

Key Insights and Results

The authors evaluated their method on synthetic data (ranging from categorical responses to complex non-linear interactions) and real-world datasets, including a Turkish student evaluation dataset and high-dimensional Single-Cell RNAseq data.

Type-I Error Control

In all simulations, the proposed method successfully maintained a false positive rate very close to the target significance level ($\alpha = 0.05$), even with small sample sizes.

Type-I error control across different sample sizes

Power and the "Cubic" Advantage

Most PSI methods are tied to linear regression. By using kernels (HSIC), this method can find significant features even when the relationship is highly non-linear or involves complex interactions that linear Lasso would miss entirely.

A standout insight is demonstrated in their "M4" toy model. When a feature influences the outcome through a cubic term ($x - x^3$), linear PSI methods have zero power to detect it, while the HSIC-Lasso approach succeeds. Overall, the method showed statistical power comparable to "Multi-scale bootstrapping" (a state-of-the-art but much slower method) while being significantly faster and more automated.

Power comparison showing the advantage over linear methods

Biological Discovery

On the RNAseq data ($>26,000$ genes, $\sim1,000$ samples), the method correctly identified well-known marker genes (like CD14 for monocytes) and provided p-values that helped rank the importance of other genes, filtering out those that provided redundant information. By using block estimators for HSIC, the authors made the method computationally feasible for these massive datasets where $p \gg n$.

Limitations and Future Work

  • Data Splitting: The current algorithm still requires a data split to choose the regularization parameter $\lambda$ and perform initial screening. Incorporating the choice of $\lambda$ directly into the PSI framework (to use 100% of the data for inference) is an open challenge.
  • Kernel Approximation: To scale to even larger datasets, the authors suggest exploring Random Fourier Features to speed up kernel computations, though the theoretical guarantees for PSI in that setting still need to be proven.
  • Hyper-parameter Heuristics: Finding the optimal "split ratio" between the screening fold and the inference fold remains a heuristic process that could be refined.

Summary updated

Abstract

Detecting influential features in non-linear and/or high-dimensional data is a challenging and increasingly important task in machine learning. Variable selection methods have thus been gaining muc...
BibTeX
@inproceedings{freidling2021post,
  author = {Tobias Freidling and Benjamin Poignard and Héctor Climente-González and Makoto Yamada},
  title = {{Post-selection inference with HSIC-Lasso}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=BU5ZTnHYLgc},
}
Figure