Identifying a minimal class of models for high-dimensional data

Daniel Nevo, Ya’acov RitovarXiv 2015 · DOI · arXiv

Abstract

In high-dimensional regression settings where the number of predictors significantly exceeds the number of observations ($p \gg n$), achieving model selection consistency—identifying the exact "true" set of variables—requires assumptions that are rarely met in practice. This paper proposes a shift in objective: instead of seeking a single optimal model, we identify a "minimal class of models." This class comprises models that achieve comparable prediction accuracy but may consist of different variable sets. We introduce a random search algorithm utilizing simulated annealing, guided by predictor scores derived from a combination of Lasso and Elastic Net penalties. The utility of this approach is demonstrated through synthetic simulations and the analysis of genomic and environmental datasets, revealing the presence of interchangeable predictors and hidden model structures.

Introduction: The Limits of Model Selection Consistency

In modern statistical analysis, we frequently encounter "high-dimensional" data where the number of potential predictors ($p$) is much larger than the number of observations ($n$). The traditional goal in this context is model selection consistency: finding the specific subset of variables that generated the response. However, this "holy grail" is often mathematically unreachable without stringent, often unrealistic, assumptions about the sparsity and correlation structure of the data.

In the $p > n$ regime, multiple combinations of variables can often yield nearly identical predictive performance. Standard regularization techniques like the Lasso tend to select a single representative from a group of highly correlated variables, potentially leading researchers to overlook other equally valid predictors. This paper argues that a more robust approach is to identify a "minimal class" of high-performing models, providing a clearer picture of the uncertainty inherent in model selection.

The Minimal Class Framework

The authors define the Minimal Class of Models, denoted as $\mathcal{G}(\kappa, \eta)$, as the set of all models of a fixed size $\kappa$ whose Mean Squared Error (MSE) falls within a small threshold $\eta$ of the best possible model of that size.

By focusing on this class, the researcher can distinguish between:

  1. Essential Variables: Predictors that appear in every model within the minimal class.
  2. Substitutable Variables: Predictors that can be swapped for one another without significantly degrading the model's predictive power.

Methodology: Scoring and Searching

To identify the members of $\mathcal{G}(\kappa, \eta)$ without an exhaustive (and computationally impossible) search, the authors propose a two-stage approach.

1. Predictor Scoring ($\gamma$)

The algorithm begins by assigning a "score" to each variable to prioritize the search. This scoring mechanism uses a multi-step procedure involving the Lasso (to find sparse signals) and the Elastic Net (to capture groups of correlated variables). The authors provide a theoretical justification (Theorem 3.3) showing that the Elastic Net is superior to the Lasso at revealing "hidden" relevant predictors that belong to competing models.

The algorithm explores the model space using a random search based on Simulated Annealing:

  • Transition: The algorithm moves through the space by swapping one variable in the current model for a new one.
  • Acceptance: Using the Metropolis-Hastings criterion, the algorithm always accepts a swap that improves the MSE. It also occasionally accepts "worse" swaps to escape local optima.
  • Cooling: As the "temperature" parameter decreases, the search becomes more selective, eventually settling into regions of high-performance models.

Empirical Results

The framework was tested on three distinct types of data:

Synthetic Simulations

In scenarios with a high Signal-to-Noise Ratio (SNR), the algorithm successfully identified multiple "competing" models. While a standard Lasso would have reported only one "best" model, the minimal class approach revealed the full landscape of variables that could explain the data.

Riboflavin Production

The method was applied to a genomic dataset ($n=71, p=4088$) predicting vitamin B2 production in Bacillus subtilis. The analysis revealed that while 53 different genes appeared across the "good" models, only one (Gene 2564) was truly ubiquitous. Furthermore, it identified a specific cluster of four genes {4002, 4003, 4004, 4006} where at least one was always present, but they were so highly correlated that they were essentially interchangeable.

Air Pollution and Mortality

In a classic dataset expanded to 165 predictors (including interactions), the method highlighted the importance of non-linear effects. Specifically, interactions such as jant × ovr65 (January temperature and population over 65) were frequently selected over their corresponding main effects, suggesting a complex relationship between climate, demographics, and mortality.

Conclusion

The "minimal class of models" approach represents a pragmatic shift in high-dimensional statistics. By moving beyond the search for a single global optimum, researchers can better understand the stability of their findings and the potential for variable substitution. While the method requires careful parameter tuning and computational resources, it provides a more comprehensive assessment of model uncertainty than traditional single-model selection methods.

Summary updated

Abstract

Model selection consistency in the high-dimensional regression setting can be achieved only if strong assumptions are fulfilled. We therefore suggest to pursue a different goal, which we call a minimal class of models. The minimal class of models includes models that are similar in their prediction accuracy but not necessarily in their elements. We suggest a random search algorithm to reveal candidate models. The algorithm implements simulated annealing while using a score for each predictor that we suggest to derive using a combination of the Lasso and the Elastic Net. The utility of using a minimal class of models is demonstrated in the analysis of two datasets.
BibTeX
@misc{nevo2015identifying,
  author = {Daniel Nevo and Ya’acov Ritov},
  title = {{Identifying a minimal class of models for high-dimensional data}},
  year = {2015},
  eprint = {1504.00494},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1504.00494},
}
Figure