Source-linked AI summary
Model Selection for High Dimensional Quadratic Regression via Regularization
Ning Hao, Yang Feng, Hao Helen Zhang
TL;DR
High-dimensional quadratic regression requires selecting interactions while preserving their hierarchy with main effects, but existing regularization methods can be computationally infeasible. The paper analyzes two-stage LASSO and proposes RAMP, then reports a supermarket-data comparison in which RAMP outperforms LASSO under stringent tuning criteria.
Problem
Existing hierarchy-preserving regularization methods are infeasible at very large p because they require storing and manipulating an O(p^2) × n design matrix and solving complex constrained problems.
Source: §1 · p. 2Method
The paper studies two-stage LASSO and proposes RAMP, an efficient algorithm for computing a hierarchy-preserving regularization solution path, extending both approaches to generalized quadratic regression.
Source: §1 · p. 3Results
With GIC, RAMP selected 30 variables on average, around 3 interactions, and achieved average out-of-sample R2 of 90.08, higher than the corresponding LASSO results.
Source: §5.2 · p. 20Takeaways & Limitations
The two-stage LASSO has a variable-selection consistency result for high-dimensional QR, and the proposed procedures avoid storing the full O(p^2) × n design matrix.
Source: §1 · p. 3
Abstract
from arXiv · showhide
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.
1 Introduction
Quadratic regression adds quadratic and interaction terms to main effects, creating a hierarchy that model selection should preserve. The paper targets high-dimensional QR and GQR with scalable regularization, theoretical analysis of two-stage LASSO, and the RAMP solution-path algorithm.
1 Introduction
- Existing hierarchy-preserving regularization methods become infeasible at very large p because they require manipulating an O(p^2) × n design matrix and solving complex constrained problems.The marginality principle requires interaction terms to enter only when their parent main effects are included.Source: §1 · p. 2
- The paper studies regularization for model selection and estimation in QR and GQR, focusing on the p ≫ n regime that bottlenecks existing methods.The QR hierarchy arises because order-2 terms include both squared main effects and two-way interactions derived from main effects.Source: §1 · p. 2
- The two-stage LASSO receives a variable-selection consistency result, while RAMP computes a hierarchy-preserving regularization solution path efficiently.The authors describe this as the first selection-consistency result for high-dimensional QR.Source: §1 · p. 3
- The methods are extended to interaction selection in generalized quadratic regression models.The paper also presents numerical studies of the proposed methods.Source: §1 · p. 3
Appendix. 2 Two-stage Regularization Method
The two-stage procedure first selects main effects, then fits their quadratic and interaction terms while leaving selected main effects unpenalized. Its Stage 1 LASSO has a sign-consistency guarantee under stated conditions, supporting inclusion of important interactions in Stage 2.
Appendix. 2 Two-stage Regularization Method
- Stage 1 selects main effects alone; Stage 2 adds all order-2 terms among selected effects and leaves those main effects unpenalized to preserve hierarchy.The procedure can be implemented with existing lars and glmnet packages and avoids estimating O(p^2) parameters before dimension reduction.Source: Appendix. 2 Two-stage Regularization… · p. 5
- The theory addresses a concern specific to two-stage selection: whether Stage 1 can consistently identify important main effects despite omitting order-2 terms.The paper establishes main-effect selection consistency for two-stage LASSO under regularity conditions.Source: Appendix. 2 Two-stage Regularization… · p. 5
- The Stage 1 LASSO is sign consistent with overwhelming probability for a properly chosen tuning parameter, under the theorem's regularity conditions.The theorem assumes Gaussian design, the irrepresentable and eigenvalue conditions, dimensionality and signal-strength requirements, and centered main effects; the paper notes an extension to non-Gaussian designs in supplementary material.Source: Appendix. 2 Two-stage Regularization… · pp. 5–7
- Because the important interaction index set T is contained in S^2, identifying the important main effects at Stage 1 allows their interactions to be included at Stage 2.The paper says Stage 2 interaction-selection consistency can then be obtained under mild conditions on the reduced interaction design.Source: Appendix. 2 Two-stage Regularization… · p. 7
Principle (RAMP)
RAMP uses coordinate descent to build a solution path that selects main effects and interactions while preserving hierarchy. Its weak-heredity version can admit an interaction once either parent is selected.
Principle (RAMP)
- RAMP uses coordinate descent to select main and interaction effects simultaneously along a path that preserves hierarchy.The two-stage path depends on its Stage 1 selection, which can be made under considerably high noise when interactions are strong.Source: Principle (RAMP) · p. 8
- The coordinate descent path proceeds over decreasing λ values, using the previous solution as the next starting point and cyclically minimizing coordinates to convergence.Source: Principle (RAMP) · pp. 8–9
- At each path step, RAMP adds possible interactions among active main effects, then updates the selected sets and adds required main effects to enforce heredity.Source: Principle (RAMP) · p. 9
- Under weak heredity, an interaction can enter the candidate set after either parent is selected, including before the other parent enters.This flexibility is useful when only one parent of an important effect is strong.Source: Principle (RAMP) · p. 9
- In the toy example, strong heredity selects X1 and X6 before X1X6, while weak heredity selects X1X6 immediately after X6.The figure shows the strong-heredity path on the left and the weak-heredity path on the right.Source: Principle (RAMP) · pp. 9–10, Figure 1 · p. 10
4 Extension to Generalized Quadratic Regression Mod-
The paper extends quadratic regression to generalized linear models and presents two-stage and RAMP procedures for generalized quadratic regression. The two-stage procedure preserves hierarchy by retaining selected main effects, while RAMP replaces penalized least squares with penalized likelihood.
4.1 Generalized Quadratic Regression
- Generalized quadratic regression extends the GLM systematic component to include quadratic-regression terms, and few computational tools are available for high-dimensional GQR.Source: §4.1 · p. 11
4.2 Two-stage Regularization Methods
- For GQR, the two-stage method selects main effects first, then considers their two-way interactions while leaving the selected main effects unpenalized.Keeping the Stage 1 main effects in the final model assures hierarchy between main effects and interactions.Source: §4.2 · p. 12
4.3 New Path Algorithm for Generalized QR
- The GQR version of RAMP replaces penalized least squares with penalized likelihood and uses coordinate descent at each step.Source: §4.3 · p. 12
- During GQR path building, RAMP adds possible interactions among active main effects, updates the selected sets, and adds main effects required by heredity.Source: §4.3 · pp. 12–13
5 Numerical Studies
Simulation examples compare RAMP with two-stage regularization and other hierarchy-aware methods across varying heredity structures and error settings. In the supermarket data, RAMP with GIC achieves higher out-of-sample R2 than the corresponding LASSO results using a compact model.
5.1 Simulation Examples
- In Example 1, RAMP had high coverage of main and interaction effects and the smallest RMSE when σ = 3 and 4.The 2-LASSO tended to miss important main effects and select noise variables, while 2-SCAD had high exact selection but low coverage; iFORM had lower interaction coverage than RAMP, and iFORT performed worst in selection and estimation.Source: §5.1 · p. 14, Table 1 · p. 15
- In Example 2, RAMP performed reasonably well on both effect types with weak signals and had lower RMSE than 2-LASSO and 2-SCAD in all scenarios.With strong signals, RAMP, 2-LASSO, and 2-SCAD selected main effects similarly, while RAMP and 2-SCAD selected interactions better than 2-LASSO; iFORT and iFORM were omitted because they do not handle binary responses.Source: §5.1 · pp. 15–16, Table 2 · p. 16
- When only weak heredity held in Example 3, strong-heredity RAMP missed important interactions, while RAMP-w recovered them at high proportions, especially with small error variance.Compared with hierNet, RAMP-w generally selected smaller models with smaller RMSE, and hierNet took much longer to compute.Source: §5.1 · p. 17, Table 3 · p. 17
- Under strong heredity in Example 4, RAMP outperformed RAMP-w on interaction coverage and exact selection, and had the smallest RMSE across noise levels.Both hierNet versions had high coverage but nearly zero exact selection for main and interaction effects, selecting many noise variables; hierNet-s took over four hours per replicate.Source: §5.1 · p. 18, Table 4 · p. 18
- Under a heavy-tail error distribution, vanilla RAMP with strong heredity enforced had performance similar to Example 1, in an example designed to examine robustness to heavy-tail errors.Source: §5.1 · p. 19
5.2 Real Data Example: Supermarket Data
- With GIC, RAMP averaged out-of-sample R2 90.08 using 30 variables (about 3 interactions), much higher than the corresponding LASSO results.Across BIC, EBIC, and GIC, RAMP also had higher out-of-sample R2 than LASSO; RAMP outperformed iFORT and iFORM under every tuning method considered.Source: Table 6 · p. 20, §5.2 · p. 20
6 Discussion
The paper presents efficient hierarchy-preserving interaction selection for QR and GQR, while identifying limitations of the two-stage LASSO theory and directions for broader methods.
6 Discussion
- RAMP selects main and interaction effects simultaneously while preserving hierarchy, with computational efficiency intended for high and ultra-high dimensional data.The RAMP strategy can also extend algorithms such as LARS to build the full regularized QR solution path.Source: §6 · pp. 20–21
- Most alternative hierarchy-preserving algorithms are relatively slow when p is large, while some applications may require selecting interactions before weak main effects.The authors suggest incorporating screening-based methods into their path algorithm for such scenarios.Source: §6 · p. 21
- The two-stage LASSO theory leaves open broader penalty-function investigations for GQR, because LASSO selection consistency often relies on an irrepresentable condition considered unrealistic in applications.The discussion points to frameworks similar to Fan & Lv (2011) and Fan & Lv (2013).Source: §6 · p. 21
- An R package implementing RAMP is available from CRAN.Source: §6 · p. 21
7 Appendix
The appendix places the main results in Appendix A and a related lemma in Appendix B, with proofs using primal-dual witness arguments and concentration bounds.
7 Appendix
- The appendix identifies Appendix A as the location of the main results and Appendix B as the location of a related lemma.Source: §7 · p. 21
7.1 Appendix A
- The proof of Theorem 1 applies the primal-dual witness method and shows that, with overwhelming probability under condition (6), |Zj| < 1 holds for every j ∈ Sc.Source: §7.1 · p. 22
7.2 Appendix B
- In the proof of Lemma 1, the first summand of Mn is controlled exactly as in Wainwright (2009), with probability at least 1 −2 exp(−s/2).Source: §7.2 · p. 25
sional Quadratic Regression via Regularization”
The supplementary material extends Theorem 1 beyond Gaussian assumptions and states conditions for two-stage LASSO support containment and sign consistency. It also supplies concentration arguments used to establish these results.
Supplementary A: Theorem 2
- The supplementary material states a generalized version of Theorem 1 without a Gaussian assumption and gives concentration bounds under subgaussian conditions.Condition (C4) controls the overall interaction effect treated as noise in Stage 1.Source: sional Quadratic Regression via… · pp. 27, 29, 34
- Theorem 2 gives a unique LASSO solution whose support is contained within S with probability tending to 1 under the stated conditions.The conditions include (SG), (C1)–(C4), and a lower bound on λ_n.Source: sional Quadratic Regression via… · p. 29
- Under an additional minimum-signal condition, the LASSO solution is sign consistent, matching the signs of β_M.Source: sional Quadratic Regression via… · p. 29