Model Selection for High Dimensional Quadratic Regression via Regularization

Ning Hao, Yang Feng, Hao Helen ZhangJournal of the American Statistical Association 2014

Abstract

Quadratic regression (QR) models naturally extend linear models by considering interaction effects between the covariates. To conduct model selection in QR, it is important to maintain the hierarchical model structure between main effects and interaction effects. Existing regularization methods generally achieve this goal by solving complex optimization problems, which usually demands high computational cost and hence are not feasible for high dimensional data. This paper focuses on scalable regularization methods for model selection in high dimensional QR. We first consider two-stage regularization methods and establish theoretical properties of the two-stage LASSO. Then, a new regularization method, called Regularization Algorithm under Marginality Principle (RAMP), is proposed to compute a hierarchy-preserving regularization solution path efficiently. Both methods are further extended to solve generalized QR models. Numerical results are also shown to demonstrate performance of the methods.

Introduction

In modern statistical learning, high-dimensional data—where the number of predictors ($p$) significantly exceeds the number of observations ($n$)—is increasingly common. While linear models serve as a foundational tool for analyzing such data, they often fail to capture complex dependencies, specifically interaction effects. Quadratic Regression (QR) addresses this by incorporating squared terms ($X_j^2$) and cross-products ($X_jX_k$).

However, the transition from linear to quadratic models introduces a massive computational burden. For a dataset with $p$ variables, the number of potential interaction terms grows at a rate of $O(p^2)$. For instance, a model with 1,000 variables results in over 500,000 potential predictors. Beyond the computational cost, unconstrained selection methods like the standard LASSO often select interaction terms without their corresponding main effects, resulting in models that lack interpretability and violate the "marginality principle."

The Marginality Principle and Hierarchy

The marginality principle suggests that an interaction term should only be included in a model if its "parent" main effects are also present. This is categorized into two types of hierarchy:

  1. Strong Hierarchy: Both main effects (e.g., $X_j$ and $X_k$) must be present for the interaction ($X_jX_k$) to be included.
  2. Weak Hierarchy: At least one of the main effects must be present for the interaction to be included.

Enforcing these structures is essential for scientific interpretability, yet existing methods like hierNet are often computationally prohibitive for ultra-high dimensional data due to the need to store and process the full $O(p^2)$ design matrix.

Proposed Methodologies

1. Two-Stage LASSO

The authors first examine a simple two-stage heuristic. In the first stage, a standard LASSO is performed on the main effects only. In the second stage, the model is expanded to include interactions only between those variables selected in the first stage. While often viewed as a practical "hack," this paper provides a landmark theoretical contribution by proving the selection consistency (or sign consistency) of this two-stage approach under high-dimensional settings, justifying its use in specific contexts.

2. RAMP: Regularization Algorithm under Marginality Principle

The primary innovation of this work is RAMP, a coordinate descent algorithm designed to build a hierarchy-preserving solution path efficiently. RAMP offers several advantages:

  • Active Set Strategy: Instead of searching the entire $O(p^2)$ space, RAMP only considers adding interaction terms if their parents are already in the active set. This drastically reduces the memory bottleneck.
  • Scalability: By avoiding the storage of the full design matrix, RAMP can fit models with tens of thousands of variables in seconds.
  • Generalized Framework: The authors extend RAMP to Generalized Quadratic Regression (GQR), making it applicable to non-Gaussian data, such as binary outcomes in logistic regression.

Numerical Results and Real-World Application

Simulation Studies

Extensive simulations were conducted with $p$ ranging from 100 to 5,000. RAMP consistently outperformed two-stage LASSO and SCAD in terms of Root Mean Squared Error (RMSE) and "coverage" (the ability to identify true underlying variables), particularly in scenarios with low signal-to-noise ratios.

In terms of computational speed, the difference was stark. For a relatively small problem ($p=200$), the existing hierNet method required over 4 hours for a single replicate. In contrast, RAMP completed the same task in approximately 30 seconds. For $p=10,000$, RAMP remained feasible on a standard desktop, fitting the model in under half a minute.

Supermarket Case Study

The researchers applied RAMP to a real-world dataset from a major supermarket in China ($n = 464$, $p = 6,398$). The objective was to predict daily customer volume based on the sales of various product categories. RAMP achieved an out-of-sample $R^2$ of approximately 90-91%. This significantly outperformed the standard LASSO, which achieved only 72-75% when using stringent tuning criteria. This result underscores the importance of capturing interaction effects to achieve high predictive accuracy in real-world economic data.

Conclusion and Future Work

RAMP represents a significant advancement in high-dimensional variable selection by balancing theoretical rigor with extreme computational efficiency. While the method relies on the marginality principle—and may miss "hidden" interactions where main effects are zero—it reflects the structural reality of most physical and biological systems.

Future research may involve integrating RAMP with "sure independence screening" (SIS) to handle datasets where $p$ reaches the millions. To support the research community, the authors have released the RAMP R package, providing a scalable tool for practitioners to implement these hierarchical models.

Summary updated

Abstract

Quadratic regression (QR) models naturally extend linear models by considering interaction effects between the covariates. To conduct model selection in QR, it is important to maintain the hierarchical model structure between main effects and interaction effects. Existing regularization methods generally achieve this goal by solving complex optimization problems, which usually demands high computational cost and hence are not feasible for high dimensional data. This paper focuses on scalable regularization methods for model selection in high dimensional QR. We first consider two-stage regularization methods and establish theoretical properties of the two-stage LASSO. Then, a new regularization method, called Regularization Algorithm under Marginality Principle (RAMP), is proposed to compute a hierarchy-preserving regularization solution path efficiently. Both methods are further extended to solve generalized QR models. Numerical results are also shown to demonstrate performance of the methods.
BibTeX
@article{hao2014model,
  author = {Ning Hao and Yang Feng and Hao Helen Zhang},
  title = {{Model Selection for High Dimensional Quadratic Regression via Regularization}},
  journal = {Journal of the American Statistical Association},
  year = {2014},
}
Figure