EPR-C3: A Deterministic Constraint-Aware Heuristic for High-Dimensional Subset Selection in Multiple Linear Regression

Technical Summary: EPR-C3 for High-Dimensional Subset Selection in Multiple Linear Regression

Problem Statement
Feature subset selection in Multiple Linear Regression (MLR) presents a dual challenge in high-dimensional data regimes: a combinatorial explosion of possible predictor subsets and the risk of generating statistically inadmissible models due to multicollinearity, overfitting, or coefficient insignificance. While exhaustive "all-subsets" regression guarantees the identification of the globally optimal model under a chosen criterion, its computational cost grows exponentially with the number of predictors ($d$) and the maximum model size ($w$), rendering it infeasible for large $d$. Conversely, existing alternatives—such as greedy stepwise procedures, penalized regression (Lasso, Ridge, Elastic Net), filter-wrapper screening, and stochastic metaheuristics (e.g., Genetic Algorithms)—often suffer from limitations including local optima entrapment, sensitivity to early decisions, modification of the Ordinary Least Squares (OLS) objective, or a lack of reproducibility. There is a practical need for a method that operates within the native OLS framework, enforces statistical and multicollinearity constraints directly during the search, and remains computationally tractable in high-dimensional settings without relying on exhaustive enumeration.

Methodology: The EPR-C3 Algorithm
The paper introduces EPR-C3, a deterministic, multi-start, neighborhood-search heuristic designed for constraint-aware subset selection in OLS-based MLR. The algorithm does not modify the OLS objective function (unlike penalized regression) nor does it enumerate all combinations. Instead, it relies on a structured search trajectory defined by four core components:

1. Multi-Start Initialization: The search begins from multiple small predictor subsets (seeds). While seed generation can be randomized, the subsequent trajectory is fully deterministic given a fixed seed list and random state, ensuring reproducibility.
2. Neighborhood Operators: Each trajectory iterates through a sequence of local modifications:
   • Expand: Adds the inactive predictor that yields the largest improvement in the target metric (e.g., $R^2$), subject to model size limits.
   • Perturb: Performs one-for-one exchanges between active and inactive predictors to escape local optima.
   • Reduce: Tests one-variable removals, accepting them if they maintain or improve the target score, thereby favoring parsimony.
3. C3 Constraint-Aware Refinement: A unique feature of the algorithm is the integration of admissibility constraints directly into the search workflow rather than as post-hoc filters. This block comprises:
   • Correlation Cleanup: Identifies active predictor pairs exceeding a user-defined correlation threshold ($\tau_r$) and removes the one that results in a better screened target score.
   • Replacement Recovery: Re-evaluates predictors removed during correlation cleanup to test if screened replacement moves can recover or improve the target score.
   • VIF Pruning: Iteratively removes predictors with high Variance Inflation Factors (VIF) exceeding a threshold ($\tau_{VIF}$) if their exclusion improves the screened score.
4. Admissibility Filtering: Candidate models are evaluated using standard OLS estimation. A subset is stored as a "reportable" model only if it satisfies a strict set of constraints: maximum model size ($w$), target metric threshold ($\tau_f$), pairwise correlation limits ($\tau_r$), VIF limits ($\tau_{VIF}$), and coefficient significance levels ($\alpha$).

Key Contributions
The paper outlines six primary contributions:

1. Algorithmic Formulation: The introduction of EPR-C3 as a deterministic, multi-start heuristic that embeds statistical admissibility constraints (correlation, VIF, significance) directly into the neighborhood search.
2. Explicit Search Operators: The definition of specific expansion, perturbation, reduction, and C3 refinement operators within an OLS subset selection framework.
3. Benchmarking Against Exhaustive Search: An evaluation of EPR-C3's ability to recover top-ranked subsets identified by all-subsets regression across varying levels of combinatorial complexity ($d$ and $w$).
4. Comparative Analysis: A demonstration that EPR-C3 achieves a superior recovery-efficiency trade-off compared to stepwise procedures, penalized-regression preselection, filter-wrapper screening, genetic algorithms, and branch-and-bound methods (Leaps).
5. Empirical Utility Threshold: The proposal of an empirical threshold ($U$) to guide analysts on when heuristic search becomes computationally preferable to exhaustive enumeration. The threshold is approximated by $U = (8.2w - 31) \times 10^6$ for $w \geq 4$, representing the number of candidate subsets above which EPR-C3 outperforms exhaustive search in CPU time.
6. Applied Validation: A case study on a published pKa modeling dataset demonstrating the reproducible recovery of a known MLR equation with reduced runtime compared to the original exhaustive approach.

Results

• Recovery Performance: In benchmark scenarios with predictor counts up to $d=60$ and model sizes up to $w=10$ (search spaces exceeding $2.8 \times 10^8$ subsets), EPR-C3 with 1,000 seeds recovered over 95% of the top 100 reference subsets identified by exhaustive all-subsets regression.
• Computational Efficiency: EPR-C3 becomes computationally advantageous over exhaustive enumeration when the number of candidate subsets exceeds the empirical utility threshold. For example, at $d=35$ and $w=10$, EPR-C3 was approximately 12.7 times faster than exhaustive search while maintaining high recovery rates.
• Comparative Superiority:
  • Stepwise/Filter Methods: Forward stepwise and filter-wrapper screening (CSR-AS) failed to recover any of the top 100 reference subsets, highlighting the limitations of greedy or marginal screening approaches in complex multivariate landscapes.
  • Penalized Regression: Methods like Lasso, Ridge, and Elastic Net provided modest recovery (10–23%) but required significant computational overhead for preselection and subsequent OLS re-fitting.
  • Stochastic/Branch-and-Bound: While Genetic Algorithms and the Leaps algorithm (branch-and-bound) achieved higher recovery (65–68%), they were either computationally expensive (Genetic Algorithms) or suffered from "post-hoc admissibility loss" (Leaps), where high-ranking subsets were discarded after search because they violated constraints not enforced during the search. EPR-C3 achieved the highest recovery (95%) with a lower relative CPU time than both the Genetic Algorithm and Leaps.
• Case Study: In the pKa dataset ($d=53$), EPR-C3 recovered the exact published predictor set and equation in approximately 2.5 times less time than the all-subsets regression used in the original study.

Significance and Claims
The paper positions EPR-C3 not as a replacement for exhaustive enumeration when that is feasible, but as a necessary, deterministic alternative for high-dimensional regimes where exhaustive search is computationally prohibitive. Its significance lies in bridging the gap between the interpretability and statistical rigor of OLS and the computational feasibility required for high-dimensional data.

By embedding constraint-aware decisions (correlation cleanup, VIF pruning, significance filtering) directly into the search trajectory, EPR-C3 avoids the "post-hoc admissibility loss" common in branch-and-bound or stochastic methods. The authors claim that this approach allows for the recovery of statistically defensible, interpretable, and reproducible MLR models without the full combinatorial burden of exhaustive enumeration. The method is presented as a practical tool for data science workflows where model transparency and adherence to statistical assumptions are as critical as predictive performance. The paper remains modest, acknowledging that EPR-C3 is a heuristic whose recovery guarantees are validated only within regimes where exhaustive search is still computationally feasible, and that larger seed budgets may be required for even more extreme combinatorial spaces.