Source-linked AI summary
Least squares after model selection in high-dimensional sparse models
Alexandre Belloni, Victor Chernozhukov
TL;DR
The paper asks whether applying OLS after penalized model selection can improve on Lasso in high-dimensional sparse regression. It derives generic rate and sparsity results for post-selection estimators, including thresholded procedures, and finds that OLS post-Lasso matches or improves Lasso while reducing bias under the stated selection conditions.
Problem
High-dimensional sparse regression needs estimators that remain accurate when the number of regressors is very large and first-step Lasso selection may omit parts of the oracle model.
Method
The paper analyzes OLS applied after Lasso or other rate-controlled, sparsity-controlled first-step estimators, including traditional and data-driven fitness thresholding.
Results
OLS post-Lasso performs at least as well as Lasso in convergence rate with smaller bias, can achieve a strictly faster rate under sufficient inclusion and sparsity, and becomes oracle OLS under perfect selection.
Takeaways & Limitations
Post-model-selection OLS can preserve Lasso’s near-oracle performance while improving it when model selection includes the oracle components with sufficient sparsity.
Takeaways & Limitations
Perfect model selection is special, requiring strong coefficient separation from zero and near-perfect empirical Gram-matrix orthogonality.
Abstract
from arXiv · showhide
In this article we study post-model selection estimators that apply ordinary least squares (OLS) to the model selected by first-step penalized estimators, typically Lasso. It is well known that Lasso can estimate the nonparametric regression function at nearly the oracle rate, and is thus hard to improve upon. We show that the OLS post-Lasso estimator performs at least as well as Lasso in terms of the rate of convergence, and has the advantage of a smaller bias. Remarkably, this performance occurs even if the Lasso-based model selection "fails" in the sense of missing some components of the "true" regression model. By the "true" model, we mean the best s-dimensional approximation to the nonparametric regression function chosen by the oracle. Furthermore, OLS post-Lasso estimator can perform strictly better than Lasso, in the sense of a strictly faster rate of convergence, if the Lasso-based model selection correctly includes all components of the "true" model as a subset and also achieves sufficient sparsity. In the extreme case, when Lasso perfectly selects the "true" model, the OLS post-Lasso estimator becomes the oracle estimator. An important ingredient in our analysis is a new sparsity bound on the dimension of the model selected by Lasso, which guarantees that this dimension is at most of the same order as the dimension of the "true" model. Our rate results are nonasymptotic and hold in both parametric and nonparametric models. Moreover, our analysis is not limited to the Lasso estimator acting as a selector in the first step, but also applies to any other estimator, for example, various forms of thresholded Lasso, with good rates and good sparsity properties. Our analysis covers both traditional thresholding and a new practical, data-driven thresholding scheme that induces additional sparsity subject to maintaining a certain goodness of fit. The latter scheme has theoretical guarantees similar to those of Lasso or OLS post-Lasso, but it dominates those procedures as well as traditional thresholding in a wide variety of experiments.
1. Introduction
The article studies post-model-selection OLS estimators for high-dimensional sparse regression and shows that they retain Lasso’s rate while potentially reducing bias and improving performance. It develops sparsity guarantees and extends the analysis to thresholded and other first-step estimators, supported by theoretical and computational results.
- High-dimensional sparse models contain many regressors but only s = o(n) regressors capture most of the response’s impact.
- The results are developed for high-dimensional sparse models with asymptotic regimes allowing p and s to grow with n, and include computational experiments.The article addresses applications of high-dimensional data analysis and reports experiments summarized through estimator performance under varying signal strength.
- OLS post-Lasso performs at least as well as Lasso in convergence rate and has smaller bias, even when selection omits components of the oracle’s best s-dimensional model.If selection includes the oracle model and is sufficiently sparse, OLS post-Lasso can achieve a strictly faster rate; perfect selection yields the oracle estimator.
- The theoretical framework applies to Lasso, thresholded Lasso, the Dantzig selector, and other first-step estimators with suitable rate and sparsity bounds.A data-driven fitness-thresholding scheme induces additional sparsity while maintaining a specified goodness of fit.
- OLS post-Lasso and OLS post-fit Lasso perform at least as well as Lasso and can perform substantially better across signal strengths.At intermediate signals, both outperform Lasso and OLS post-t Lasso; at large signals, OLS post-fit Lasso and OLS post-t Lasso perform very well.
- The analysis establishes a new Lasso sparsity bound ensuring that the selected model dimension is no larger in order than the oracle model dimension.The bounds improve on analogous results and rely on sparse-eigenvalue inequalities and maximal inequalities.
2. Setting, estimators, and conditions
The paper defines an oracle benchmark for sparse regression, then estimates the selected model with Lasso-type procedures and applies OLS after selection. It also develops thresholding choices and conditions for near-oracle performance while allowing imperfect model selection.
- Oracle benchmark: The oracle program chooses the sparsity dimension that balances approximation bias and estimation variance, defining the oracle target, model, and risk benchmark.The oracle model has dimension s and uses the best s-sparse approximation to the regression function.
- First-step estimators: Because p can exceed n, Lasso uses ℓ1 penalization for regularization and covariate selection, with thresholded Lasso removing coefficients below a chosen level.Thresholded Lasso includes ordinary Lasso as the special case t = 0.
- Thresholding choices: The proposed fitness-thresholding scheme preserves a specified goodness of fit while inducing additional sparsity, addressing risks from aggressive thresholding when oracle coefficients are small.Traditional thresholding can cause goodness-of-fit losses, slow convergence, or inconsistency in such settings.
- Post-model selection estimators: Post-model selection estimators apply OLS to models selected by Lasso, thresholded Lasso, or fitness-thresholded Lasso.The paper studies OLS post-Lasso, OLS post-t Lasso, and OLS post-fit Lasso.
- Selection conditions: The analysis targets imperfect selection as the general case, while perfect selection yields oracle estimators only under special circumstances.The results provide near-oracle rates when selection is imperfect, whereas perfect selection requires restrictive conditions.
- Penalty choice: The penalty level is chosen as the smallest value that dominates the effective noise gradient, using a design-dependent quantile and a possibly data-driven variance estimate.The proposed data-driven choice is sharper than the commonly used c′bσ^2(2n)^-1 log(p/α) expression.
3. Results on Lasso as an estimator and model selector
The section establishes Lasso’s near-oracle estimation properties, model-selection conditions, and a new sparsity bound showing that selected models can remain close to oracle size.
- Estimation properties of Lasso: Theorem 1 extends earlier Lasso results to data-driven penalty levels and derives rates in the ℓ1-norm.These bounds support subsequent results on post-model selection estimators.
- Estimation properties of Lasso: Lower bounds derived from Lasso’s Karush–Kuhn–Tucker conditions characterize limits on its rate of convergence.The bound involves the number of incorrectly selected regressors, bm = |bT \ T|.
- Estimation properties of Lasso: Lasso with a data-driven penalty estimates the regression function at a near-oracle rate when κ(¯c) is bounded away from 0.The results also show that this rate cannot generally be improved.
- Model selection properties of Lasso: Perfect selection requires coefficient separation from zero and near-perfect empirical Gram-matrix orthogonality, making it a special, nongeneral phenomenon.Under these conditions, thresholded Lasso can recover the true model as a subset or exactly.
- Sparsity properties of Lasso: The new sparsity analysis shows that Lasso’s selected-model dimension is of the same order as the oracle dimension, bs := |bT| ≤ s + bm ≲ s.The result improves earlier bounds and requires a smaller penalty level than comparable bounds.
- Sparsity properties of Lasso: The earlier sparsity bound is not sharp when φ(n) diverges, while sublinearity of restricted sparse eigenvalues enables a sharper bound.This issue arises, for example, in Gaussian designs with p ≥ 2n.
4. Performance of post-model selection estimators with a generic model selector
The section gives generic performance results for OLS post-model selection estimators, linking their prediction error to first-step estimation, model sparsity, and whether the selected model contains the oracle model.
- Generic performance result: The generic post-model selection estimator applies a second-step procedure to the model selected by any first-step estimator with support size at most n.The framework is not restricted to Lasso.
- Generic performance result: Theorem 4 bounds prediction performance using the first-step loss Bn, truncation loss Cn, and the number bm of incorrectly selected regressors.The result also controls empirical error through sparsity-dependent logarithmic terms.
- Implications: When the selected model contains the true model, Bn and Cn do not affect the rate, which is instead determined by the selector’s sparsity.If the true model is missed, performance depends on both sparsity and the smaller of Bn and Cn.
- Proof ingredients: The empirical-error control used in the theorem is based on sparsity and relies on maximal inequalities for collections of empirical processes.The auxiliary results hold uniformly over sparse deviations and omitted subsets of the true model.
5. Performance of least squares after Lasso-based model selection
Applying OLS after Lasso-based selection yields rates at least as good as Lasso in general, with strict improvements when selection includes the oracle model and is sufficiently sparse. Fitness-based thresholding can further improve sparsity, whereas traditional thresholding may lose goodness of fit.
- OLS post-Lasso: OLS post-Lasso applies generic post-selection rate results using Lasso’s convergence and sparsity bounds in parametric and nonparametric models.The resulting performance bound depends on Lasso’s sparsity, rate, and model-selection ability.
- OLS post-Lasso: In general, OLS post-Lasso matches Lasso’s rate despite Lasso potentially missing components of the oracle model.It also has a smaller regularization bias.
- OLS post-Lasso: OLS post-Lasso strictly improves on Lasso when oracle coefficients are well separated, approximation error is non-dominant, bm = oP(s), and the selected model includes the oracle model with probability approaching one.Perfect model selection makes the post-Lasso estimator the oracle estimator.
- OLS post-fit Lasso: OLS post-fit Lasso matches the near-oracle rate of Lasso and OLS post-Lasso while selecting a model that is sparser than the OLS post-Lasso model.Its data-driven threshold is chosen subject to maintaining a certain goodness of fit.
- OLS post-fit Lasso: OLS post-fit Lasso strictly improves on Lasso when its selected model is sufficiently sparse and contains the oracle model, and it outperforms OLS post-Lasso when its sparsity is smaller.Under perfect model selection, it achieves oracle performance.
- OLS post-thresholded Lasso: Traditional thresholding can strictly improve rates under well-separated coefficients, but excessive thresholding can cause large goodness-of-fit losses and make its bound worse than Lasso’s.The threshold must balance sparsity gains against the thresholding-induced loss γt.
A.1. Proofs for Section 3
The proofs establish Lasso rate and sparsity controls from optimality conditions, restricted eigenvalue arguments, and maximal inequalities. These controls yield the stated bounds under data-driven penalty choices.
- Data-driven penalty: The data-driven penalty analysis establishes lower and upper penalty bounds with high probability before invoking the prediction-norm bound.This transfers the rate result to the specified data-driven choice of λ.
- Lasso rate bounds: The proof bounds estimation error using restricted eigenvalue conditions and separates cases according to the relationship between support and nonsupport ℓ1 errors.The resulting bounds control both prediction and ℓ1 errors.
- Lasso rate bounds: Lasso optimality conditions provide correlation bounds that are combined with noise inequalities and the Cauchy–Schwarz inequality.These steps produce the basic rate control used later in the model-selection analysis.
- Sparsity bound: The sparsity proof bounds the number of selected variables by combining optimality conditions with restricted sparse eigenvalue sublinearity.It minimizes the resulting bound over admissible model-size values.
A.2. Proofs for Section 4
The proofs derive generic post-model-selection bounds by comparing the second-step empirical criterion with both the first-step estimator and the oracle-restricted fit. Empirical-process control handles the selected sparse model class.
- Generic post-selection bound: The second-step estimator’s criterion is bounded by the smaller of the first-step criterion and the oracle-restricted criterion.This comparison supplies the deterministic starting point for the post-selection error bound.
- Generic post-selection bound: Combining criterion comparisons, empirical-process bounds, and approximation terms yields the post-selection prediction-error inequality.The final step solves the resulting quadratic inequality for the estimation error.
- Empirical-process control: Empirical-process deviations are controlled over sparse model classes using covering numbers and the Samorodnitsky–Talagrand inequality.The covering-number bound depends on the model’s excess dimension m and sparsity s.
- Empirical-process control: Restricted sparse eigenvalue conditions bound the radius of each function class, which yields the required covering-number inequality.The proof applies a standard covering bound after setting the radius using RSE(m).
A.3. Proofs for Section 5
The proof of the OLS post-Lasso theorem combines the generic post-selection result with Lasso’s optimality and rate bounds. When the oracle model is selected as a subset, the additional approximation term vanishes.
- Theorem 5 proof: If the selected Lasso model contains the oracle model, the proof sets the corresponding approximation term Cn to zero.Otherwise, the term is controlled by an indicator for failure to include the oracle model.
- Theorem 5 proof: Lasso optimality conditions bound the first-step criterion according to whether the estimation error’s nonsupport ℓ1 norm exceeds its support norm.Restricted eigenvalue arguments then control the resulting prediction error.
- Theorem 5 proof: Applying the Lasso error bound together with the generic post-selection theorem produces the stated OLS post-Lasso rate.The proof concludes by invoking Theorem 1 and Theorem 4 under the required restricted eigenvalue condition.