A Regularization Approach to Nonlinear Variable Selection

Lorenzo Rosasco, Matteo Santoro, Sofia Mosci, Alessandro Verri, Silvia VillaAISTATS 2010 · OpenReview

Abstract

In this paper we consider a regularization approach to variable selection when the regression function depends nonlinearly on a few input variables. The proposed method is based on a regularized least-squares estimator with a unique penalty term that encourages sparsity in the functional gradient, effectively identifying relevant input variables without requiring a pre-defined dictionary of features.

Introduction

Variable selection is a cornerstone of high-dimensional data analysis, essential for tasks like identifying disease-driving genes from thousands of candidates. While linear methods like the Lasso ($\ell_1$ regularization) are highly effective for linear models, they struggle when relationships are nonlinear. Traditional nonlinear approaches often rely on "dictionaries" (e.g., polynomial expansions), which grow exponentially with the number of variables, leading to the "curse of dimensionality." This paper introduces a method to perform variable selection directly on the original variables in a nonlinear setting, avoiding feature space explosion.

Methodology

The authors propose a regularized least-squares estimator with a penalty term focused on the partial derivatives of the learned function.

Functional Gradient Sparsity

The core insight is that if a function $f$ does not depend on the $j$-th variable, its partial derivative with respect to that variable ($\partial_j f$) should be zero. The proposed regularizer sums the empirical $L_2$ norms of these partial derivatives across all input dimensions. This encourages the model to "shut off" irrelevant inputs by forcing their corresponding functional gradients to zero.

RKHS and Optimization

The problem is framed within Reproducing Kernel Hilbert Spaces (RKHS), utilizing a generalized representer theorem to express the optimal function as a combination of kernels and their derivatives. To handle the non-smooth penalty, the authors developed an Iterative Projection Algorithm based on forward-backward splitting. Efficiency is further improved using a "continuation method" or warm restarts, where solutions for larger regularization parameters initialize the algorithm for smaller ones.

Refinement (Alg1$^{GR}$)

A two-stage process is proposed for optimal performance: first, use the algorithm to select relevant variables, then perform standard kernel ridge regression (G-ridge) using only those selected variables.

Experimental Results

The method was evaluated on synthetic data and the Boston Housing dataset.

Synthetic Data

The algorithm was tested on three nonlinear functions ($f_1, f_2, f_3$) involving interactions and exponential terms. The proposed Alg1 achieved a True Positive rate of 1.0 and a False Positive rate below 0.05. As shown in Table 1, the refined Alg1$^{GR}$ consistently outperformed standard Lasso and G-ridge across all test functions.

Table 1: Error metrics on synthetic nonlinear functions $f_1, f_2, f_3$ across different learning algorithms.

Boston Housing Dataset

On the Boston Housing benchmark (13 features, 506 samples), the method identified key drivers such as the number of rooms (RM), pupil-teacher ratio (PTRATIO), and population status (LSTAT). As shown in Table 2, the refined Alg1$^{GR}$ achieved the lowest average squared test error ($21 \pm 3$), outperforming standard Lasso ($30 \pm 4$) and non-sparse Gaussian Ridge regression ($22 \pm 5$).

Table 2: Test error comparison on the Boston Housing dataset.

Conclusion

This paper presents a novel regularization framework for nonlinear variable selection that avoids the curse of dimensionality by penalizing functional gradients. The method demonstrates superior accuracy and stability on both synthetic and real-world data. Future research will explore automated kernel selection and more formal thresholding criteria for variable exclusion.

Summary updated

Abstract

In this paper we consider a regularization approach to variable selection when the regression function depends nonlinearly on a few input variables. The proposed method is based on a regularized le...
BibTeX
@inproceedings{rosasco2010regularization,
  author = {Lorenzo Rosasco and Matteo Santoro and Sofia Mosci and Alessandro Verri and Silvia Villa},
  title = {{A Regularization Approach to Nonlinear Variable Selection}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2010},
  url = {https://openreview.net/forum?id=no_T-ODIecC},
}
Figure