PaperlayerView exact revision on arXiv

Source-linked AI summary

Extended Comparisons of Best Subset Selection, Forward Stepwise Selection, and the Lasso

Trevor Hastie, Robert Tibshirani, Ryan J. Tibshirani

arXiv:1707.08692v2stat.MEstat.CO

TL;DR

This paper revisits whether best subset selection should be preferred over other sparse regression methods by expanding empirical comparisons across signal-to-noise regimes. Its simulations find that the relaxed lasso generally achieves the strongest out-of-sample prediction accuracy, while best subset selection and forward stepwise perform similarly and best subset selection mainly excels at high SNR.

  • Problem

    The paper examines whether best subset selection is generally superior to forward stepwise selection and the lasso for sparse regression.

  • Method

    The authors expand and refine simulations comparing best subset selection, forward stepwise selection, the lasso, and the relaxed lasso across problem settings and SNR levels.

  • Results

    The relaxed lasso generally delivers the best accuracy, while best subset selection beats the lasso mainly at high SNR and performs similarly to forward stepwise selection.

  • Takeaways & Limitations

    For out-of-sample prediction, the relaxed lasso offers the strongest overall choice across the examined scenarios, though other targets may yield different comparisons.

  • Takeaways & Limitations

    Best subset selection is computationally demanding; for n = 500 and p = 100, optimization typically takes 1 hour or longer.

Abstract

from arXiv · show

In exciting new work, Bertsimas et al. (2016) showed that the classical best subset selection problem in regression modeling can be formulated as a mixed integer optimization (MIO) problem. Using recent advances in MIO algorithms, they demonstrated that best subset selection can now be solved at much larger problem sizes that what was thought possible in the statistics community. They presented empirical comparisons of best subset selection with other popular variable selection procedures, in particular, the lasso and forward stepwise selection. Surprisingly (to us), their simulations suggested that best subset selection consistently outperformed both methods in terms of prediction accuracy. Here we present an expanded set of simulations to shed more light on these comparisons. The summary is roughly as follows: (a) neither best subset selection nor the lasso uniformly dominate the other, with best subset selection generally performing better in high signal-to-noise (SNR) ratio regimes, and the lasso better in low SNR regimes; (b) best subset selection and forward stepwise perform quite similarly throughout; (c) the relaxed lasso (actually, a simplified version of the original relaxed estimator defined in Meinshausen, 2007) is the overall winner, performing just about as well as the lasso in low SNR scenarios, and as well as best subset selection in high SNR scenarios.

1 Introduction

The introduction contrasts three established linear-model selection methods and motivates expanded empirical comparisons enabled by recent mixed integer optimization advances for best subset selection.

  • Methods: Best subset selection, forward stepwise selection, and the lasso are popular methods for parameter selection and estimation in linear models.Best subset and forward stepwise selection are classical statistical methods, while the lasso is comparatively more recent.
  • Methods: Best subset selection chooses the k-predictor subset with the lowest squared error, solving a nonconvex optimization problem.The subset size satisfies k between 0 and min{n, p}.
  • Methods: Forward stepwise selection starts with the empty model and iteratively adds the variable that best improves fit, producing a subset for every size k.Its selected subsets are not generally globally optimal.
  • Methods: The lasso replaces the ℓ0 norm with the ℓ1 norm, yielding a convex relaxation expressed in penalized form with tuning parameter λ ≥ 0.The paper focuses on this penalized formulation.
  • Motivation and contribution: Mixed integer optimization makes best subset selection problems with p in the hundreds or thousands computationally reachable, enabling expanded empirical comparisons.The authors also provide the bestsubset R package and reproducible R code using the Gurobi MIO solver.

2 Preliminary discussion

The section challenges the view that best subset selection should generally replace forward stepwise selection and the lasso. It explains that their behavior and relative accuracy depend on the noise level, predictor correlations, and differing bias–variance paths.

  • Noiseless versus noisy settings: In noiseless regression, the lasso is generally a heuristic for the sparsest ℓ0 solution, but this interpretation does not carry over to the noisy statistical setting.The noisy setting changes the comparison because the lasso and best subset selection differ in how aggressively they select and estimate coefficients.
  • Estimator differences: The lasso shrinks nonzero coefficients, whereas forward stepwise and best subset selection use least squares on their active sets without shrinkage.Shrinkage makes lasso fitted values continuous in y, while the other methods can jump across active-set decision boundaries.
  • Bias–variance behavior: At low SNR, best subset selection and forward stepwise can have high variance early in their model paths, producing worse accuracy even after tuning.This effect also depends on factors such as correlations between predictor variables.
  • Motivation: Best subset selection is not uniformly superior: neither it nor the lasso dominates across all problem settings.Different procedures traverse the bias–variance tradeoff along model paths affected differently by SNR and predictor correlations.
  • Estimator differences: Even at γ = 0, the relaxed lasso is typically less aggressive than forward stepwise and best subset selection, often having smaller effective degrees of freedom.The relaxed lasso removes lasso shrinkage to a degree controlled by γ, increasing its effective degrees of freedom relative to the lasso.

3 Simulations

Across the simulations, lasso accuracy is better at low SNR while best subset selection is better at high SNR, with forward stepwise performing similarly to best subset selection. The relaxed lasso achieves the strongest overall accuracy, while best-subset results may be limited by the MIO time cap.

  • Simulation design: The simulations extend prior setups across a wider SNR range and introduce beta-type 5 to study weak sparsity.Beta-type 5 has its first s coefficients equal to 1, with the remaining coefficients decaying exponentially to 0.
  • Simulation results: The three-minute-per-instance-per-subset-size MIO restriction may have caused best subset selection to underperform, especially at high SNR in the high-5 and high-10 settings.Optimality verification averaged 17.55 of 50 solutions in the medium setting but only 1.61 of 50 in high-5 and high-10.
  • Simulation results: Forward stepwise selection and best subset selection perform quite similarly throughout, although forward stepwise is much faster.Their comparable performance contrasts with earlier results because the earlier study tuned forward stepwise using AIC rather than a separate validation set.
  • Simulation results: The lasso performs better than best subset selection at low SNR, whereas best subset selection performs better at high SNR.The transition depends on n, p, predictor autocorrelation ρ, and beta-type.
  • Simulation results: The relaxed lasso provides the best overall accuracy, performing as well as or better than the other methods across nearly all SNR levels and configurations.Its shrinkage parameter γ can retain lasso shrinkage when helpful and reverse it when not.

4 Discussion

The paper expands large-scale simulations comparing best subset selection with forward stepwise selection, the lasso, and the relaxed lasso. It finds that forward stepwise and best subset perform similarly, while best subset often loses to the lasso except at high SNR; the accompanying bestsubset package enables replication and new comparisons.

  • 4 Discussion: The study expands and refines simulations comparing best subset selection, forward stepwise selection, the lasso, and the relaxed lasso.These simulations extend the large-scale empirical examinations enabled by Bertsimas et al. (2016).
  • 4 Discussion: Forward stepwise selection and best subset selection perform similarly throughout.
  • 4 Discussion: Best subset selection often loses to the lasso except in the high SNR range.
  • 4 Discussion: The bestsubset R package supports replicating the paper’s simulations and creating new comparisons.It is available at https://github.com/ryantibs/best-subset/.

Supplement to “Extended Comparisons of Best Subset … A.1.1 Relative risk (to null model)

The supplement presents simulation plots for the paper’s method comparisons, using validation-based tuning in Section 1 and oracle tuning in Section 2. The supplied relative-risk comparison includes best subset, forward stepwise, lasso, and relaxed lasso.

  • Supplement to “Extended Comparisons of Best Subset: The supplementary document contains plots from the simulation suite described in the paper.These plots concern comparisons among best subset selection, forward stepwise selection, the lasso, and the relaxed lasso.
  • A Validation tuning: Section 1 follows the simulation format described in the paper.The supplied passage states that the Section 1 plots precisely follow the paper’s simulation format.
  • A Validation tuning: Section 2 uses an analogous simulation format but tunes each method with an oracle rather than a validation set.This contrasts oracle tuning in Section 2 with validation-set tuning in Section 1.
  • A.1.1 Relative risk (to null model): The relative-risk comparison lists best subset, forward stepwise, lasso, and relaxed lasso as the evaluated methods.The supplied method row labels these four candidates under the comparison heading.

A.1.2 Relative test error (to Bayes) … A.2.1 Relative risk (to null model)

The supplied excerpts identify the methods compared across relative test error, variance explained, coefficient sparsity, and relative risk analyses. They list best subset, forward stepwise, lasso, and relaxed lasso as the candidate methods.

  • A.1.2 Relative test error (to Bayes): The relative test error (to Bayes) comparison lists best subset, forward stepwise, lasso, and relaxed lasso.The excerpt provides method labels but no numerical test-error results.
  • Cross-section comparison: Across the supplied comparison excerpts, the same four methods recur: best subset, forward stepwise, lasso, and relaxed lasso.This summarizes the repeated method labels across the listed subsections without adding performance claims.
  • A.1.3 Proportion of variance explained: The proportion of variance explained comparison lists best subset, forward stepwise, lasso, and relaxed lasso.The excerpt provides method labels but no variance-explained results.
  • A.1.4 Number of nonzero coefficients: The number of nonzero coefficients comparison lists best subset, forward stepwise, lasso, and relaxed lasso.The excerpt provides method labels but no coefficient-count results.
  • A.2.1 Relative risk (to null model): The relative risk (to null model) comparison lists best subset, forward stepwise, lasso, and relaxed lasso.The excerpt provides method labels but no relative-risk values.

A.2.2 Relative test error (to Bayes) … A.3.1 Relative risk (to null model)

This section block compares best subset selection, forward stepwise selection, the lasso, and the relaxed lasso across test error, explained variance, model size, and relative risk. The supplied excerpt identifies the comparison methods but provides no numerical results for these subsections.

  • A.2.2 Relative test error (to Bayes): A.2.2 compares best subset selection, forward stepwise selection, the lasso, and the relaxed lasso on relative test error to Bayes.The supplied passage contains method labels but no error values or comparative outcomes.
  • Comparison scope: Across the listed subsections, the recurring candidate set is best subset selection, forward stepwise selection, the lasso, and the relaxed lasso.This method set appears in each supplied subsection passage.
  • A.2.3 Proportion of variance explained: A.2.3 compares best subset selection, forward stepwise selection, the lasso, and the relaxed lasso on proportion of variance explained.The supplied passage lists the candidate methods without reporting explained-variance values.
  • A.2.4 Number of nonzero coefficients: A.2.4 compares best subset selection, forward stepwise selection, the lasso, and the relaxed lasso by number of nonzero coefficients.The supplied passage identifies the methods but does not provide model-size counts.
  • A.3.1 Relative risk (to null model): A.3.1 compares best subset selection, forward stepwise selection, the lasso, and the relaxed lasso on relative risk to the null model.The supplied passage lists the comparison methods but contains no relative-risk values.

A.3.2 Relative test error (to Bayes) … A.4.1 Relative risk (to null model)

The paper compares best subset, forward stepwise, lasso, and relaxed lasso across relative test error, variance explained, sparsity, and relative risk. Best subset tends to excel at high SNR, lasso at low SNR, while relaxed lasso performs strongly across both regimes.

  • A.3.2 Relative test error (to Bayes): Four methods—best subset, forward stepwise, lasso, and relaxed lasso—are compared using relative test error to Bayes.This comparison appears under subsection A.3.2.
  • A.3.2 Relative test error (to Bayes): Best subset generally performs better in high-SNR regimes, whereas the lasso performs better in low-SNR regimes.The paper states that neither method uniformly dominates the other.
  • A.3 Comparisons: Best subset and forward stepwise perform quite similarly throughout the simulations.Their similarity is stated as a general comparison across the reported settings.
  • A.3 Comparisons: The relaxed lasso is the overall winner, performing about as well as the lasso at low SNR and as well as best subset at high SNR.The relaxed estimator is described as a simplified version of Meinshausen’s original relaxed estimator.
  • A.4.1 Relative risk (to null model): Relative risk to the null model is reported for best subset, forward stepwise, lasso, and relaxed lasso.This comparison appears under subsection A.4.1.

A.4.2 Relative test error (to Bayes) … B.1.1 Relative risk (to null model)

The supplied section compares best subset selection, forward stepwise selection, the lasso, and the relaxed lasso across relative test error, variance explained, coefficient sparsity, and relative risk. The excerpt provides method labels but no numerical results for these comparisons.

  • A.4.2 Relative test error (to Bayes): Relative test error to Bayes is reported for best subset, forward stepwise, lasso, and relaxed lasso.No values are included in the supplied passage.
  • B Oracle tuning: The oracle-tuning portion concerns method comparisons under the reported simulation framework.The supplied passages do not provide an oracle-tuning result or method-specific value.
  • A.4.3 Proportion of variance explained: Proportion of variance explained is reported for best subset, forward stepwise, lasso, and relaxed lasso.No values are included in the supplied passage.
  • A.4.4 Number of nonzero coefficients: Number of nonzero coefficients is reported for best subset, forward stepwise, lasso, and relaxed lasso.No values are included in the supplied passage.
  • B.1.1 Relative risk (to null model): Relative risk to the null model is reported for best subset, forward stepwise, lasso, and relaxed lasso.No values are included in the supplied passage.

B.1.2 Relative test error (to Bayes) … B.2.1 Relative risk (to null model)

The supplied passages identify four compared methods across relative test error, variance explained, nonzero coefficients, and relative risk, but provide no numerical results or rankings.

  • B.1.2 Relative test error (to Bayes): The relative test error subsection compares best subset, forward stepwise, lasso, and relaxed lasso.The passage lists these four methods without reporting values or performance ordering.
  • Methods compared: Across the supplied metric subsections, the candidate methods are consistently best subset, forward stepwise, lasso, and relaxed lasso.This synthesis draws on all four passages, which repeat the same method set.
  • Scope of supplied evidence: The supplied excerpts do not support quantitative comparisons among the methods for any listed metric.Only method labels are present; values, baselines, and rankings are absent.
  • B.1.3 Proportion of variance explained: The proportion of variance explained subsection uses the same four-method comparison: best subset, forward stepwise, lasso, and relaxed lasso.No variance-explained values are supplied in the passage.
  • B.1.4 Number of nonzero coefficients: The number of nonzero coefficients subsection compares best subset, forward stepwise, lasso, and relaxed lasso.The passage provides method labels but no coefficient-count results.
  • B.2.1 Relative risk (to null model): The relative risk subsection also lists best subset, forward stepwise, lasso, and relaxed lasso as the compared methods.No relative-risk values or rankings appear in the supplied passage.

B.2.2 Relative test error (to Bayes) … B.3.1 Relative risk (to null model)

The supplied passages identify the compared methods across five consecutive subsections but provide no numerical results or substantive findings for those comparisons.

  • B.2.2 Relative test error (to Bayes): The relative test error subsection lists best subset, forward stepwise, lasso, and relaxed lasso as the compared methods.No relative test-error values are supplied in the passage.
  • Cross-section comparison: Across the supplied method listings, best subset, forward stepwise, lasso, and relaxed lasso are the recurring candidates.The excerpts contain method labels only, without comparative metrics.
  • B.2.3 Proportion of variance explained: The proportion of variance explained subsection lists best subset, forward stepwise, lasso, and relaxed lasso.No variance-explained values are supplied in the passage.
  • B.2.4 Number of nonzero coefficients: The number of nonzero coefficients subsection lists best subset, forward stepwise, lasso, and relaxed lasso.No coefficient-count values are supplied in the passage.
  • B.3.1 Relative risk (to null model): The relative risk to the null model subsection lists best subset, forward stepwise, lasso, and relaxed lasso as the compared methods.No relative-risk values are supplied in the passage.

B.3.2 Relative test error (to Bayes) … B.4.4 Number of nonzero coefficients

The supplied excerpts identify comparisons among best subset, forward stepwise, lasso, and relaxed lasso across relative error, variance explained, coefficient sparsity, and relative risk. They cover both the B.3 metric subsections and the B.4.1–B.4.4 metrics, including the high-10 setting.

  • B.3.2 Relative test error (to Bayes): The B.3.2 subsection lists best subset, forward stepwise, lasso, and relaxed lasso for relative test error to Bayes.
  • B.3.3 Proportion of variance explained: The B.3.3 subsection lists best subset, forward stepwise, lasso, and relaxed lasso for proportion of variance explained.
  • B.3.4 Number of nonzero coefficients: The B.3.4 subsection lists best subset, forward stepwise, lasso, and relaxed lasso by number of nonzero coefficients.
  • B.4.2 Relative test error (to Bayes): The B.4.2 subsection lists best subset, forward stepwise, lasso, and relaxed lasso for relative test error to Bayes.
  • B.4.3 Proportion of variance explained: The B.4.3 subsection lists best subset, forward stepwise, lasso, and relaxed lasso for proportion of variance explained.
  • B.4.4 Number of nonzero coefficients: The B.4.4 subsection lists best subset, forward stepwise, lasso, and relaxed lasso by number of nonzero coefficients.
Loading 1707.08692v2…