Source-linked AI summary
Exact Post-Selection Inference for Sequential Regression Procedures
Ryan J. Tibshirani, Jonathan Taylor, Richard Lockhart, Robert Tibshirani
TL;DR
The paper addresses valid inference after adaptive variable selection without assuming a true linear model. It uses truncated-Gaussian inference on polyhedral selection events for forward stepwise regression, LAR, and the lasso, producing finite-sample exact null p-values and confidence intervals. The approach yields implemented post-selection tools, while rigorous p-value-based stopping rules remain unresolved.
Problem
Adaptive regression inference must account for variable-selection decisions, without requiring that the true model be linear in X.
Method
The paper characterizes selection events for forward stepwise regression, LAR, and the lasso as polyhedral constraints and applies truncated-Gaussian conditional tests.
Results
The resulting null p-values are exactly conditionally uniform in finite samples under Gaussian errors, without restrictions on X or linearity of the underlying model.
Takeaways & Limitations
The framework provides exact post-selection p-values and confidence intervals for the considered adaptive regression procedures, with a spacing-test approximation for LAR.
Takeaways & Limitations
The paper does not yet provide a complete understanding or theory for converting these p-values into rigorous model-selection stopping rules.
Abstract
from arXiv · showhide
We propose new inference tools for forward stepwise regression, least angle regression, and the lasso. Assuming a Gaussian model for the observation vector y, we first describe a general scheme to perform valid inference after any selection event that can be characterized as y falling into a polyhedral set. This framework allows us to derive conditional (post-selection) hypothesis tests at any step of forward stepwise or least angle regression, or any step along the lasso regularization path, because, as it turns out, selection events for these procedures can be expressed as polyhedral constraints on y. The p-values associated with these tests are exactly uniform under the null distribution, in finite samples, yielding exact type I error control. The tests can also be inverted to produce confidence intervals for appropriate underlying regression parameters. The R package "selectiveInference", freely available on the CRAN repository, implements the new inference tools described in this paper.
1 Introduction
The paper develops exact post-selection inference for adaptive regression procedures, focusing on forward stepwise, least angle regression, and the lasso while avoiding a true-linear-model assumption.
- The framework targets variable selection and estimation in adaptive linear regression without assuming the true model is linear in X.
- Naive forward-stepwise p-values can overstate significance because they ignore greedy variable selection, whereas selection-adjusted truncated Gaussian tests account for the active set.In the prostate cancer example, four variables appear significant naively, compared with two under the adjusted test at the 0.05 level.
- The paper applies analogous inference tools to LAR and the lasso path, including truncated Gaussian and spacing tests for LAR.The LAR and lasso paths coincide in the prostate cancer example because no variables were deleted.
- The truncated Gaussian tests require Gaussian errors but no assumptions about predictors or linearity, and their null p-values are exact in finite samples.The spacing test for LAR is computationally efficient and asymptotically equivalent to the covariance test.
- Implementations are provided in the selectiveInference R package, with an additional Python implementation.The R package is available through CRAN and GitHub; the Python implementation is hosted on GitHub.
- The paper does not resolve how to combine post-selection p-values into a rigorous stopping or model-selection rule.It identifies rigorous model selection as important and leaves it for future work.
2 Summary of results
The paper develops exact conditional inference after polyhedral selection events, applying it to sequential regression procedures and obtaining valid tests and confidence intervals for selected effects. The framework also clarifies that rigorous model-selection stopping rules remain an open problem addressed only partially.
- General framework: The framework tests a fixed linear contrast v^Tθ conditional on y falling in a polyhedral set P, requiring only Gaussian errors.The resulting statistic is exactly uniform under the null for finite n and p, without restrictions on P.
- Polyhedral selection events: FS selection events can be represented as Γy ≥ 0, so the framework conditions on the variables and signs selected by the procedure.For first-step FS selecting variable 3 with a positive coefficient, Γ contains four inequalities formed from normalized predictor columns.
- Sequential procedures: Conditioning on the selection event accounts for FS's adaptive, greedy nature by evaluating v^Ty only among responses producing the observed selection.The same construction applies across steps of FS and essentially the same framework applies to LAR and the lasso.
- Inference targets: The tests can target arbitrary linear contrasts, with partial regression coefficients of the last selected variable providing the principal concrete example.The contrast need only be fixed by the conditioning event; the displayed choice tests the significance of variables as they enter the model.
- Confidence intervals: Inverting the tests yields conditional confidence intervals with 1 − α coverage for the last selected variable's projected coefficient, given the selected variables and signs.Unconditionally, the corresponding selection interval covers a moving target because the selected variables depend on y.
- Model selection limits: The paper does not yet provide a complete, extensively evaluated theory for converting these p-values into rigorous model-selection rules.It presents possible strategies, including inference at an adaptively selected step when the stopping event is polyhedral, but leaves model selection for future work.
3 Conditional Gaussian inference after polyhedral selection
Under Gaussian sampling, conditioning on a polyhedral selection event turns a contrast into a normally distributed quantity truncated by selection-dependent bounds. This yields exact conditional p-values and confidence intervals for the contrast.
- For y ∼ N(θ, Σ) and P = {y : Γy ≥ u}, inference targets the contrast vTθ conditional on y ∈ P.
- Under normality, the truncation quantities are independent of vT y, so the conditional distribution of vT y is truncated Gaussian.
- Polyhedral selection traps vT y between bounds Vlo and Vup determined by the orthogonal projection Pv⊥y, with additional feasibility checked by V0.
- One-sided conditional inference: The truncated-normal CDF produces a pivotal statistic and valid conditional p-values for testing H0: vTθ = 0.
- One-sided conditional inference: The one-sided construction tests H0: vTθ = 0 against H1: vTθ > 0 and can be inverted into a valid interval I = [δα, ∞).
- Two-sided conditional inference: For two-sided alternatives, 2·min{U, 1−U} applied to the truncated-normal CDF yields a valid p-value with power against vTθ ≠ 0.
4 Exact selection-adjusted tests for FS, LAR, lasso
Forward stepwise, LAR, and lasso selection events can be represented as polyhedral constraints on y, enabling exact conditional inference after their adaptive selections. The procedures differ in their selection conditions and conditioning burden, which affects computational complexity and power.
- Assuming X is in general position, FS, LAR, and lasso model-selection events are polyhedra, indeed cones, of the form {y : Γy ≥ 0}.
- Forward stepwise: Forward stepwise repeatedly adds the variable producing the largest fit improvement, recomputes active coefficients by least squares, and encodes each selected variable and sign through linear inequalities.
- Forward stepwise: After k FS steps, the selection matrix Γ has 2pk − k^2 − k rows when k < p.
- LAR: LAR selects variable-sign pairs through sequential competition and conditions additionally on the sets of pairs eligible to enter at each step.
- Lasso: The lasso regularization path is traced by modifying LAR to delete active variables when their coefficients pass through zero.
- One-sided or two-sided tests: The sign-aligned one-sided null tests whether the last selected variable has a nonzero population coefficient with the same sign as its fitted sample coefficient, gaining power under that alternative.
- Models with intercept: With an intercept, centering y and X incorporates the intercept while preserving the polyhedral construction and conditional inference under the resulting known covariance.
- How much to condition on?: Extra conditioning is computationally convenient but generally reduces power and widens intervals; unions of polyhedra can remove unnecessary conditioning at higher computational cost.
5 The spacing test for LAR
The spacing test simplifies LAR post-selection inference by applying the polyhedral framework to a compact selection representation. It is exact under orthogonal predictors, often approximates the exact selection event for general predictors, and yields conditional tests for selected coefficients.
- Refined characterization: The exact LAR selection event after k steps is represented by linear inequalities Γy ≥ 0, with up to 4pk − 2k^2 − k rows.The representation combines sequential active-variable and sign constraints with additional conditions.
- Orthogonal predictors: For orthogonal predictors, the additional conditions are vacuous, reducing the representation to Γy ≥ U with only k + 1 rows.This compact form uses the constraints in (34) and (35), with random lower bounds U.
- Approximation: For general nonorthogonal predictors, dropping the additional conditions gives a computationally favorable approximation with k + 1 rows, supported by empirical evidence.The omitted constraints are often inactive, so the approximation may preserve the geometry of the selection set in practice.
- Conditional inference: When v lies in the span of the active LAR variables, random-U polyhedral inference applies to v^Tθ conditional on Γy ≥ U.The required independence condition holds under the Gaussian regression model for such contrasts.
- Spacing test: The spacing test targets the latest selected LAR coefficient and is an exact conditional p-value for H0: v^Tθ = 0.Its one-sided alternative follows the sign of the latest selected sample coefficient.
- Scope and limitations: The spacing test requires no extra computation for truncation limits, but the compact representation is restricted to contrasts in the active-variable span.For general predictors, the approximation is not exactly equivalent to the full LAR selection event, although empirical p-values are often close or more powerful.
6 Empirical examples
Simulations compare post-selection tests for FS and LAR, showing exact TG tests alongside spacing and covariance alternatives across early selection steps. The experiments also evaluate LAR confidence-interval coverage and compare TG tests with the max-|t|-test.
- Conditional size and power: At step 1, all tests achieve about 73% power at a 10% nominal type I error cutoff.
- Conditional size and power: At step 2, covariance and spacing tests for LAR reach about 82% power, versus 35% for exact TG tests for FS and LAR.
- Conditional size and power: At step 3, TG and spacing tests produce uniform p-values, while covariance-test p-values are super-uniform and conservative under the null.
- Conditional size and power: Spacing can have greater power because it removes some LAR conditioning constraints and therefore uses a larger portion of the sample space.
- Coverage of LAR conditional confidence intervals: LAR’s 90% confidence intervals have miscoverage proportions of 12/100, 11/100, and 11/100 at steps 1, 2, and 3.
- Comparison to the max-|t|-test: Under an entirely null signal, the max-|t|-test becomes increasingly conservative, whereas the exact TG test continues to produce uniform p-values.
7 Relationship to the covariance test
The section relates the LAR spacing and covariance tests through an asymptotic equivalence. This connection explains their similar empirical behavior while distinguishing their assumptions and finite-sample guarantees.
- Covariance test: The covariance test targets the significance of variables entering at step k and later under an underlying linear model.
- Covariance test: The covariance statistic has a conservative Exp(1) limiting distribution under the null under predictor-correlation restrictions and other conditions.
- Asymptotic equivalence: This equivalence explains why covariance and spacing tests show similar behavior in the empirical plots.
- Asymptotic equivalence: The spacing p-value and covariance statistic are asymptotically equivalent after a fixed number k of LAR steps.
- Interpretation: The covariance test is implicitly aligned to have power when the selected variable’s sign matches its projected population effect.
8 Discussion
The framework provides exact post-selection inference for FS, LAR, and the lasso when selection events are polyhedral under Gaussian errors.
- Polyhedral representations of FS, LAR, and lasso selection events enable exact p-values and confidence intervals after model selection.
A.1 Proof of Lemma 5
The proof constructs linear constraints characterizing LAR’s selected variables and signs through step k by intersecting iteration-specific conditions.
- LAR optimality is characterized separately for candidate variables and signs at each iteration.
- The construction uses inequalities involving candidate-specific linear functions of y and covariance-related ratios.
- A key independence result separates the selected contrast from the remaining constrained quantities for fixed variable-sign pairs.
- Intersecting the conditions from iterations ℓ = 1 through k yields constraints equivalent to selecting the active variables A_k and signs s_Ak.
A.2 Proof of Lemma 6
The proof uses the fact that a key quantity is a maximum over linear functions of y orthogonal to the active-variable span, yielding the stated certification condition.
- M_k^+ is characterized as a maximum over linear functions of y orthogonal to col(X_Ak).
- When v lies in col(A_k), the orthogonality structure simplifies the characterization of M_k^+.
- The resulting calculation certifies condition (39).
A.3 Proof of Theorem 1
The proof derives the truncation limits V_lo and V_up from the rows of Γ and identifies their values using the active-step geometry.
- The proof reduces V_lo and V_up to extrema of linear quantities indexed by the signs of (Γv)_j.
- The first k−2 rows of Γ contribute zero because they lie in col(X_Ak−1).
- The (k−1)st row has (Γv)_{k−1} = −∥v∥2, while the kth and (k+1)st rows equal ∥v∥2.
- V_up is determined by the (k−1)st row and equals λ_{k−1}.
- V_lo is determined by the kth and (k+1)st rows and equals M_k^+.
- The proof also establishes ∥v∥2 = 1/ω_k by direct calculation, using a result from Lockhart et al. (2014).
A.4 Proof of Theorem 2
The proof compares modified and original spacing statistics through their truncation limits, while the simulation shows that full conditioning preserves exact TG behavior and avoids later-step conservatism.
- λ_{k+1} ≥ M_k^+ implies that the modified spacing statistic is at least as large as the original statistic.
- Because the truncated Gaussian survival function increases with its lower truncation limit, the modified statistic is super-uniform under the null.
- Under an entirely null model, both TG and max-|t|-tests behave well at step 1, but max-|t|-test p-values become increasingly conservative over six FS steps.
- The TG test conditions on all selection events through step k, whereas max-|t|-test at step 2 ignores that the observed statistic is second largest.
- The proof begins with a lemma based on Mills’ inequalities for asymptotic normal-tail comparisons.
- Assuming λ_k/λ_{k+1} → 1 in probability, the asymptotic expression follows after terms converging to zero in probability are controlled.