Iterative Feature Selection In Least Square Regression Estimation

Pierre Alquier

Abstract

In this paper, we focus on regression estimation in both the inductive and the transductive case. We assume that we are given a set of features (which can be a base of functions, but not necessarily). We begin by giving a deviation inequality on the risk of an estimator in every model defined by using a single feature. These models are too simple to be useful by themselves, but we then show how this result motivates an iterative algorithm that performs feature selection in order to build a suitable estimator. We prove that every selected feature actually improves the performance of the estimator. We give all the estimators and results at first in the inductive case, which requires the knowledge of the distribution of the design, and then in the transductive case, in which we do not need to know this distribution.

Introduction

Regression estimation typically involves constructing a model from a dictionary of features, such as wavelets or polynomials. While iterative methods like boosting or greedy algorithms offer computational efficiency, they often lack robust statistical guarantees against overfitting without the addition of complex penalization terms. Furthermore, traditional theory predominantly addresses the inductive setting—optimizing for any future data point. However, many practical applications, such as batch image labeling, are transductive, focusing on performance over a specific, known test set.

This work introduces an iterative algorithm that is both computationally efficient and statistically rigorous. By leveraging PAC-style deviation inequalities to define confidence regions for each feature, the proposed method provides a clear "guarantee of improvement" at every step without requiring the target function to belong to a specific predefined class.

Methodology: Projections onto Confidence Regions

The core of the proposed approach is an iterative algorithm based on projections onto statistically defined confidence regions.

1. The Dictionary and Confidence Regions

The algorithm begins with a finite family of features $\Theta_0 = \{\theta_1, \dots, \theta_m\}$. For each feature, a deviation inequality is derived to define a "confidence region" ($CR$). This region represents the space where the optimal coefficient for that specific feature is likely to reside, given the observed data.

2. The Iterative Update and Stopping Rule

Starting from an initial estimate $\theta^{(0)} = 0$, the algorithm proceeds sequentially. At each step $n$, a feature $k$ is selected from the dictionary. The current model is updated by projecting it onto the confidence region of that feature: $$\theta^{(n)} = \Pi_{k, \epsilon} \theta^{(n-1)}$$ This projection acts as an implicit form of regularization. Instead of a global penalty (like the $\ell_1$ norm in Lasso), the estimate is constrained to stay within statistically valid regions for each feature. The algorithm terminates based on a concrete stopping criterion related to the magnitude of the update, ensuring statistical guarantees are maintained.

3. Inductive vs. Transductive Settings

The paper distinguishes between two scenarios:

  • Inductive Case: Requires knowledge of the marginal distribution of the inputs ($X$).
  • Transductive Case: Does not require knowledge of the distribution of $X$, making it highly practical for scenarios where test features are available but their underlying density is unknown. The author argues that transduction is a more natural fit for this framework as it bypasses the hurdle of input distribution estimation.

4. Extensions and Adaptivity

The framework is inherently adaptive, reaching optimal convergence rates without prior knowledge of the target function's smoothness. Furthermore, the approach can be extended to Support Vector Machines (SVMs) and multiscale kernels, potentially leading to "multiscale SVMs" that automatically select appropriate kernel scales.

Theoretical Results

The primary contribution of this work is the formal proof of performance improvement and convergence.

Guaranteed Improvement

Theorem 2.3 establishes that, with high probability, the risk of the model decreases with every projection: $$R(\theta^{(n)}) \le R(\theta^{(n-1)}) - d_P^2(\theta^{(n)}, \theta^{(n-1)})$$ This ensures that every step moving the estimate actually reduces the risk.

Minimax Optimality

The estimator is evaluated on functional spaces, specifically Sobolev and Besov spaces. It is proven to reach the minimax rate of convergence $N^{-2\beta/(2\beta+1)}$ (up to a logarithmic factor). This confirms that the algorithm achieves the best possible theoretical speed of convergence for these classes of functions.

Discussion and Future Work

While the framework provides strong guarantees, several areas for further exploration remain. The current implementation relies on a confidence level $\epsilon$, which influences convergence speed. Additionally, while the theory allows for any feature selection at each step, maximizing the projection distance is a common heuristic that may become computationally expensive for very large dictionaries. Finally, extending these iterative projections beyond least-squares regression to other loss functions, such as logistic loss, represents a significant avenue for future research.

Summary updated

Abstract

In this paper, we focus on regression estimation in both the inductive and the transductive case. We assume that we are given a set of features (which can be a base of functions, but not necessarily). We begin by giving a deviation inequality on the risk of an estimator in every model defined by using a single feature. These models are too simple to be useful by themselves, but we then show how this result motivates an iterative algorithm that performs feature selection in order to build a suitable estimator. We prove that every selected feature actually improves the performance of the estimator. We give all the estimators and results at first in the inductive case, which requires the knowledge of the distribution of the design, and then in the transductive case, in which we do not need to know this distribution.
BibTeX
@inproceedings{alquier2008iterative,
  author = {Pierre Alquier},
  title = {{Iterative Feature Selection In Least Square Regression Estimation}},
  booktitle = {Annales},
  year = {2008},
  doi = {10.1214/07-aihp106},
}
Figure