Probability Bounds Behind Post-Double Selection
The selected controls depend on the data, so a probability bound for one fixed regression does not suffice for post-double selection. The proof in (Belloni, Chernozhukov, and Hansen 2014) constructs events that control all relevant scores and sparse submodels at once. On those events, the selected model has both a small prediction error and a controlled size.
1. The bounds we need
Write \(Y_i=f(Z_i)+\epsilon_i\) and approximate \(f\) by \(X_i'\beta_0\), with at most \(s\) nonzero coefficients. Under the paper’s regularity conditions, feasible Lasso and post-Lasso give
with approximation error included at the same order. A restricted eigenvalue condition converts prediction control into coefficient control on the relevant sparse sets. It does not control arbitrary dense directions.
2. Why the penalty contains a Gaussian quantile
For coordinate \(j\), the relevant random score is a sum of \(U_{ij}=X_{ij}\epsilon_i\). Studentizing it gives
Self-normalized moderate deviations approximate each tail by a Gaussian tail over a range determined by the third moments. With \(z=\Phi^{-1}(1-\gamma/(2p))\) in that range, a union bound yields
The denominator adapts to heteroskedasticity. The union bound explains the \(\log p\) cost: \(z\) is of order \(\sqrt{\log(p/\gamma)}\). This approximation is not valid for unrestricted growth of \(p\); its moment-dependent range must cover that quantile.
3. From the score event to prediction error
On the event that the penalty dominates all noise scores, the basic Lasso inequality compares the fitted objective with the objective at \(\beta_0\). Splitting the coefficient error into the true support and its complement gives a cone restriction. The restricted eigenvalue then changes an \(\ell_1\) error bound into
Prediction control does not by itself bound the selected size. A separate argument using the first-order optimality equations does that. Least-squares refitting can then remove shrinkage while retaining the prediction rate.
4. Work through the basic inequality
First take an exact sparse model \(Y=X\beta_0+\epsilon\), with support \(T\) of size \(s\), and unweighted columns normalized to empirical second moment one. Define Lasso by
Let \(\delta=\widehat\beta-\beta_0\). Comparing the objective at \(\widehat\beta\) and \(\beta_0\), then cancelling \(\|\epsilon\|^2/(2n)\), gives
On the score event \(\|X'\epsilon/n\|_\infty\le\lambda/2\), Hölder’s inequality bounds the first term by \(\lambda\|\delta\|_1/2\). Since \(\beta_{0,T^c}=0\), the penalty difference is at most \(\|\delta_T\|_1-\|\delta_{T^c}\|_1\). Therefore
Dropping the nonnegative prediction term yields the cone \(\|\delta_{T^c}\|_1\le3\|\delta_T\|_1\). Define a restricted eigenvalue \(\kappa>0\) by requiring \(\|X\delta\|_{2,n}\ge\kappa\|\delta_T\|_2\) on that cone. Cauchy–Schwarz now gives
If the prediction norm is positive, divide both sides by it to obtain \(3\lambda\sqrt s/\kappa\). If it is zero, the bound already holds. The score event supplies the cone, sparsity supplies the square-root factor, and the restricted eigenvalue connects coefficient error to prediction error.
With approximation error \(r=f-X\beta_0\), the basic inequality gains \(r'X\delta/n\), bounded by \(\|r\|_{2,n}\|X\delta\|_{2,n}\). For an oracle approximation with \(\|r\|_{2,n}\) of the target prediction order, the paper’s approximate-sparsity argument absorbs this term at that order. The exact-model cone calculation alone is not a proof for unrestricted approximation errors.
5. Why the selected model stays small
For every selected coordinate, the KKT equations give \(|X_j'(Y-X\widehat\beta)/n|=\lambda\). If \(\widehat s\) coordinates are selected, the Euclidean norm of these selected scores is \(\lambda\sqrt{\widehat s}\). On the score event, at least half of that norm must be explained by the fitted-error component. Thus, in the exact model,
where \(\phi_{\max}(q)\) is the largest empirical eigenvalue among \(q\)-column submodels. Substituting the prediction bound gives
The inequality contains the selected size on both sides. A suitable sparse-eigenvalue assumption must resolve it before concluding \(\widehat s=O_p(s)\). Assuming a bound only at size \(s\) would leave the random selected size uncontrolled.
6. A loading calculation
To see the maximum-over-coordinates issue explicitly, let \(V_{ij}\) be independent across observations and centered, and let \(\varepsilon_i\) be independent random signs. Symmetrization gives
Conditional on the data, \(\mathbb{E}_\varepsilon e^{t\sum_i\varepsilon_iV_{ij}}\le\exp(t^2\sum_iV_{ij}^2/2)\). Apply the exponential bound to both signs and all \(p\) coordinates, then optimize \(t\) to obtain
This conditional bound still contains a random scale, which must be bounded using moments or an envelope. For penalty loadings, squared regressor–error products require more moment control than a single score mean. The empirical-process symmetrization argument develops the same random-sign method more generally.
The logarithm comes from summing exponential bounds over coordinates. To derive it directly, set \(V=\max_j\sum_iV_{ij}^2\) and \(M=\max_j|\sum_i\varepsilon_iV_{ij}|\). For \(t>0\), the two signs of every coordinate give
When \(V>0\), the derivative of the right side vanishes at \(t=\sqrt{2\log(2p)/V}\), yielding \(\sqrt{2V\log(2p)}\). For \(V=0\), every summand vanishes. Independence across dictionary coordinates is unnecessary: only the conditional sign bound for each coordinate and the sum over coordinates were used.
This separates two effects of correlated dictionary columns. The maximum-score bound uses a sum over coordinates, with a logarithmic cost in their number; it does not require independent columns. Distinguishing sparse coefficient vectors from their predictions is the separate task of the restricted-eigenvalue condition.
7. Two less visible steps
Estimated penalty loadings involve averages of \(X_{ij}^2\epsilon_i^2\). Symmetrization introduces independent random signs; conditional maximal inequalities then bound the largest fluctuation across coordinates. Fourth moments or suitable tail restrictions keep the resulting random envelope under control.
For a single mean, much less is needed. If independent centered \(V_i\) satisfy \(n^{-1}\sum_i\mathbb{E}|V_i|^r\le C\), \(1\le r\le2\), the von Bahr–Esseen inequality and Markov’s inequality give
A law of large numbers for one mean and a uniform bound over a growing dictionary solve different problems. The double-selection proof uses the latter when a data-dependent choice of regressors must be covered.