Sparse Hilbert-Schmidt Independence Criterion Regression

Benjamin Poignard, Makoto Yamada

Abstract

Feature selection is a fundamental problem for machine learning and statistics, and it has been widely studied over the past decades. However, the majority of feature selection algorithms are based on linear assumptions or simple correlation rankings. This paper introduces Sparse Hilbert-Schmidt Independence Criterion (SpHSIC) regression, a framework that transforms the "minimum redundancy maximum relevance" (mRMR) approach into a continuous optimization problem, enabling effective nonlinear feature selection with theoretical guarantees.

Introduction

Identifying relevant variables in high-dimensional datasets is critical for both interpretability and predictive performance. While linear methods like the Lasso are standard, they often fail when relationships between features and outputs are nonlinear, such as multiplicative effects or complex biological pathways. Furthermore, many nonlinear alternatives either assume additive independence (like Sparse Additive Models) or fail to account for feature redundancy, leading to the selection of "copycat" variables that provide no new information. The mRMR algorithm was designed to address redundancy but historically lacked a continuous optimization framework and a rigorous theoretical foundation. SpHSIC regression bridges this gap.

Methodology

The authors propose SpHSIC, which treats feature selection as a regression problem within a "kernelized" space.

The Loss Function and Optimization

The algorithm utilizes the Hilbert-Schmidt Independence Criterion (HSIC) to measure independence between variables using kernels. By minimizing the difference between the similarity matrix of the output and a weighted sum of the similarity matrices of the features, the method naturally identifies features that are highly relevant to the output while minimizing redundancy among selected features. Unlike traditional discrete mRMR, SpHSIC is a continuous problem, allowing for the use of efficient gradient-based solvers.

Regularization and Penalties

To induce sparsity and ensure the selection of only the most relevant features, the framework incorporates several regularization terms:

  • Lasso: The standard linear L1 penalty.
  • Non-convex penalties (MCP, SCAD, Bridge): These penalties avoid over-shrinking large coefficients. The authors demonstrate that using these penalties allows the model to satisfy the "oracle property," meaning it can perfectly recover the true underlying features as the sample size grows.

Theoretical Foundations

A significant contribution of this work is re-casting the loss function as a "U-statistic of degree four." This sophisticated statistical tool allows the authors to derive the asymptotic behavior of the estimator, providing a much-needed theoretical justification for mRMR-style selection. This proves that the heuristic mRMR algorithm can be viewed as a specific type of V-statistic-based M-estimation.

Empirical Results

The authors evaluated SpHSIC on both synthetic and real-world data, demonstrating its superiority in feature recovery and predictive accuracy.

Synthetic Data Performance

In simulations with high-dimensional data ($d=400$ and $d=800$), non-convex SpHSIC (using MCP or SCAD) almost perfectly recovered the true number of zero and non-zero coefficients, whereas standard Lasso selected many redundant "false positive" features.

Table 1: Simulation results comparing feature recovery (C) and error (MSE) for various penalties across two high-dimensional scenarios.

Real-World Applications

The method was tested on datasets from the UCI Machine Learning Repository, including speech recognition (Isolet), image recognition (Coil), and medical diagnosis (ILPD).

Table 2: Mean Squared Error (MSE) comparison on real-world datasets across different regularization methods.

As shown in the table above, SpHSIC variants consistently achieved lower MSE than non-penalized or standard Lasso versions. For example, on the Isolet dataset, the MCP penalty reduced the error from 2.085 to 1.829. The method remained effective even when the number of features significantly exceeded the number of observations.

Conclusion and Future Work

SpHSIC regression provides a robust, theoretically grounded approach to nonlinear feature selection. While the current method optimizes memory usage to $O(dn^2)$, future work may focus on further reducing computational complexity for extremely large-scale datasets and developing automated methods for kernel parameter selection. The authors also suggest extending the theory to "double-asymptotic" settings where the number of parameters grows faster relative to the sample size.

Summary updated

Abstract

Feature selection is a fundamental problem for machine learning and statistics, and it has been widely studied over the past decades. However, the majority of feature selection algorithms are based...
BibTeX
@inproceedings{poignard2020sparse,
  author = {Benjamin Poignard and Makoto Yamada},
  title = {{Sparse Hilbert-Schmidt Independence Criterion Regression}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2020},
  url = {https://openreview.net/forum?id=H3zWanBFUe9},
}
Figure