Randomised Lasso Consistency under Stability Selection (Theorem 2)

Summary

Assume only a sparse-eigenvalue condition on the design (Assumption 1), not the irrepresentable condition. Choose the weakness by ${\alpha }^2=\nu {\varphi }_{min}(m)/m$ with $m=C{s}^2$. Then with probability at least $1-5/(p\vee a_n)$, stability selection with the randomised Lasso selects no noise variables for every $\lambda \ge {\lambda }_{min}=2\sigma (\sqrt{2C}s+1)\sqrt{\log (p\vee a_n)/n}$. It also selects every relevant variable whose coefficient exceeds $0.3(Cs{)}^{3/2}\lambda$. With a beta-min condition this is consistent selection. Because no noise enters for any large $\lambda$, the procedure is conservative: choosing $\lambda$ too big only costs power. The proof uses five lemmas. Reweighting keeps sparse eigenvalues controlled (L3). Relevant variables are always selected (L4, via Zhang & Huang 2008). For each noise variable the irrepresentable bound holds with probability at least $p_w(1-p_w{)}^{C{s}^2}$ over the weights (L5). The noise is bounded uniformly (L6). L7 assembles these.

Overview

The theorem formalises what Fig. 1 (right) and Fig. 4 show: adding penalty randomisation to stability selection removes the need for the irrepresentable condition (12). Only the analysis for the Lasso is given in detail; OMP is “just indicated” (see Randomised Orthogonal Matching Pursuit (ROMP) for Stability Selection).

Main Content

Sparse eigenvalues

Definition 4 - Sparse eigenvalues (p. 13, eq. 14)

For $K\subseteq \{\mathrm{1..}p\}$ let $X_K$ be the columns of $X$ in $K$. For $k\le p$, the minimal sparse eigenvalue is

$${\varphi }_{min}(k)=\underset{a\in {\mathbb{R}}^{\lceil k\rceil },K\subseteq \{\mathrm{1..}p\}:|K|\le \lceil k\rceil }{\inf }\frac{\Vert X_{K}a{\Vert }_2}{\Vert a{\Vert }_2},$$

and the maximal sparse eigenvalue ${\varphi }_{max}(k)$ is defined analogously with sup. These are related to Candès & Tao (2007), van de Geer (2008), Meinshausen & Yu (2009) and Bickel et al. (2007), and to the sparse Riesz condition of Zhang & Huang (2008).

Assumption 1 - Sparse eigenvalues (p. 13, eq. 15)

There exist $C>1$ and $\kappa \ge 9$ such that, with $s=|S|$,

$$\frac{{\varphi }_{max}(C{s}^2)}{{\varphi }_{min}^{3/2}(C{s}^2)}<\sqrt{C}/\kappa .$$

Comparison (eq. 16). The sparse Riesz condition of Zhang & Huang (2008) requires some $\bar{C}>0$ with ${\varphi }_{max}((2+4\bar{C})s+1)/{\varphi }_{min}((2+4\bar{C})s+1)<\bar{C}$. (The source writes $\bar{C}$ here, a constant distinct from Assumption 1’s $C$.) That is, eigenvalues over $O(s)$-sized subsets are bounded away from $0$ and $\infty$. Assumption 1 is “significantly stronger” than (16) but “typically much weaker” than the irrepresentable condition needed for comparable results.

The theorem

Theorem 2 (p. 13, eqs 17-18)

Consider model (10).

• Weakness: ${\alpha }^2=\nu {\varphi }_{min}(m)/m$ for any $\nu \in ((7/\kappa {)}^2,1/\sqrt{2})$, with $m=C{s}^2$.
• Sequence: $a_n\to \infty$ as $n\to \infty$.
• Penalty floor: ${\lambda }_{min}=2\sigma (\sqrt{2C}s+1)\sqrt{\log (p\vee a_n)/n}$.
• Conditions: $p>10$, $s\ge 7$, and Assumption 1 holds.
• Weights: $W_k=\alpha$ w.p. $p_w$, else $1$, independently.

Then there is $\delta ={\delta }_s\in (0,1)$ such that for all ${\pi }_{thr}\ge 1-\delta$, stability selection with the randomised Lasso satisfies, on a set ${\Omega }_A$ with $P({\Omega }_A)\ge 1-5/(p\vee a_n)$:

$$N\cap {\hat{S}}_{\lambda }^{stable}=\varnothing ,\text{\hspace{1em}(17)}$$ $$(S\setminus S_{small;\lambda })\subseteq {\hat{S}}_{\lambda }^{stable},\text{\hspace{1em}(18)}$$

where ${\hat{S}}_{\lambda }^{stable}=\{k:{\hat{\Pi }}_k^{\lambda }\ge {\pi }_{thr}\}$ for any $\lambda \ge {\lambda }_{min}$, and $S_{small;\lambda }=\{k:|{\beta }_k|\le 0.3(Cs{)}^{3/2}\lambda \}$.

In words: no noise variable is selected, and all variables with large enough coefficients are selected.

The text layer of the PDF loses the extent of the square roots in $\nu$‘s range and in ${\lambda }_{min}$. The forms above were checked against the rendered page (p. 13): $\nu \in ((7/\kappa {)}^2,1/\sqrt{2})$ and ${\lambda }_{min}=2\sigma (\sqrt{2C}s+1)\sqrt{\log (p\vee a_n)/n}$, with the radical over $2C$ only. This equals Lemma 6’s bound $2\sigma (\sqrt{2m}+1)\sqrt{\log (p\vee a_n)/n}$ at $m=C{s}^2$, since $\sqrt{2C{s}^2}=\sqrt{2C}s$.

Remark 2 - Consistency under beta-min (p. 14)

If ${\min }_{k\in S}|{\beta }_k|\ge (Cs{)}^{3/2}(0.3\lambda )$, then

$$P(S={\hat{S}}_{\lambda }^{stable})\ge 1-1/(p\vee a_n).$$

This is consistent variable selection in the sense of (11) as $p\vee a_n\to \infty$, even if the irrepresentable condition (12) is violated. Without the lower bound, variables with too-small coefficients (those in $S_{small;\lambda }$) may be missed.

The bound stated in Remark 2 is $1-1/(p\vee a_n)$, whereas the theorem gives $1-5/(p\vee a_n)$. This is recorded as printed.

Remark 3 - Conservativeness for any large $\lambda$ (p. 14)

Theorem 2 holds for all $\lambda \ge {\lambda }_{min}$. If $\lambda$ is chosen too large, (17) still guarantees no noise variables; only some important variables may be missed. This matches the empirical insensitivity to $\lambda$. By contrast, a hard-thresholded Lasso with $\lambda$ too large includes noise variables. In the paper’s words, stability selection with the randomised Lasso has “an important property of being conservative and guarding against false positive selections.”

Remark 4 - Adding subsampling (p. 14)

Theorem 2 randomises only the weights. Combining this with subsampling $n/2$ of $n$ works better empirically, and the theory extends. Let ${\tilde{\Pi }}_k^{\lambda }$ be the selection probability under both weights and subsampling, for $k\in S\setminus S_{small;\lambda }$. A Markov-type inequality gives

$$P({\tilde{\Pi }}_k^{\lambda }\ge {\pi }_{thr})\ge \frac{E({\tilde{\Pi }}_k^{\lambda })-{\pi }_{thr}}{1-{\pi }_{thr}}\ge 1-\frac{5}{(p\vee a_{n/2})(1-{\pi }_{thr})},$$

using $E({\tilde{\Pi }}_k^{\lambda })\ge 1-5/(p\vee a_{n/2})$ from Theorem 2. If $5/(p\vee a_{n/2})\ll 1-{\pi }_{thr}$, important variables are still selected w.h.p. A similar argument keeps noise variables out. Recommendation: “combining random weight perturbations with subsampling yields very competitive results and this is what we recommend to use.”

Proof architecture (App. §6.3, pp. 23-27)

Work with the equivalent formulation where columns are rescaled by their weights.

Definition 6 - Reweighted design (p. 23)

$X_k^w=X_k\cdot W_k$ for each $k$; i.e. $X^w=XW$ with $W=\mathrm{diag}(W_1..W_p)$. ${\varphi }_{max}^w,{\varphi }_{min}^w$ are the sparse eigenvalues (14) of $X^w$.

A weakness $\alpha <1$ has two effects. (i) It distorts the design’s singular values, which gives a lower bound on useful $\alpha$ (Lemma 3). (ii) It makes the irrepresentable condition hold sometimes for each noise variable (Lemma 5).

Lemma 3 - Eigenvalue ratio under reweighting (p. 23, eq. 22)

Define $\bar{C}$ by $(2+4\bar{C})s+1=C{s}^2$ and assume $s\ge 7$. ($\bar{C}$ is a second constant, determined by Assumption 1’s $C$ and $s$: $\bar{C}=(C{s}^2-2s-1)/(4s)$.) For weights in $[\alpha ,1]$ with ${\alpha }^2\ge \nu {\varphi }_{min}(C{s}^2)/(C{s}^2)$, $\nu \in {\mathbb{R}}^{+}$, under Assumption 1, for all realisations $W$:

$$\frac{{\varphi }_{max}^w(C{s}^2)}{{\varphi }_{min}^w(C{s}^2)}\le \frac{7\bar{C}}{\kappa \sqrt{\nu }}.$$

Sketch.

1. The source’s explicit chain (p. 23) is $$\frac{{\varphi }_{max}(C{s}^2)}{{\varphi }_{min}^{3/2}(C{s}^2)}<\frac{\sqrt{C}}{\kappa }=(C{s}^2{)}^{-1/2}\frac{((2+4\bar{C})s+1)/s}{\kappa }\le (C{s}^2{)}^{-1/2}\frac{3+4\bar{C}}{\kappa }.$$
   • The first inequality is Assumption 1, eq. (15).
   • The equality uses the definition $(2+4\bar{C})s+1=C{s}^2$: $\sqrt{C}=(C{s}^2{)}^{1/2}/s=(C{s}^2{)}^{-1/2}\cdot C{s}^2/s=(C{s}^2{)}^{-1/2}((2+4\bar{C})s+1)/s$.
   • The second inequality is “by $s\ge 1$” (source wording): $((2+4\bar{C})s+1)/s=2+4\bar{C}+1/s\le 3+4\bar{C}$.
   • Multiplying through by ${\varphi }_{min}^{1/2}(C{s}^2)$ gives eq. (23): ${\varphi }_{max}(C{s}^2)/{\varphi }_{min}(C{s}^2)\le \frac{3+4\bar{C}}{\kappa }\sqrt{{\varphi }_{min}(C{s}^2)/(C{s}^2)}$.
2. Reweighting cannot increase ${\varphi }_{max}$, since ${\sup }_W{\sup }_v{v}^{\top }{W}^{\top }{X}^{\top }XWv/v^{\top }v\le {\varphi }_{max}^2$.
3. Reweighting shrinks ${\varphi }_{min}$ by at most a factor $\alpha$: ${\varphi }_{min}^w\ge \alpha {\varphi }_{min}$. This uses $\tilde{v}=Wv$, with ${\tilde{v}}^{\top }\tilde{v}\le v^{\top }v\le {\alpha }^{-2}{\tilde{v}}^{\top }\tilde{v}$.
4. Combine with $3+4\bar{C}\le 7\bar{C}$. The source argues ”$\bar{C}\ge 1$ for $s\ge 7$, since $C\ge 1$ by Assumption 1”; e.g. $s=7$, $C=1$ gives $\bar{C}=34/28\approx 1.21$.

Lemma 4 - Relevant variables always selected (p. 24, eqs 24-26)

Let ${\hat{A}}^{\lambda ,W}=\{k:{\hat{\beta }}_k^{\lambda ,W}\ne 0\}$. Suppose ${\alpha }^2\ge (7/\kappa {)}^2{\varphi }_{min}(C{s}^2)/(C{s}^2)$. Under Theorem 2’s assumptions there is ${\Omega }_0$ with $P(Y\in {\Omega }_0)\ge 1-3/(p\vee a_n)$ such that for all weight realisations $w$, $p\ge 5$, and $Y\in {\Omega }_0$:

$$|{\hat{A}}^{\lambda ,w}\cup S|\le C{s}^2\text{and}(S\setminus S_{small;\lambda })\subseteq {\hat{A}}^{\lambda ,w}.\text{\hspace{1em}(24)}$$

Proof (pp. 24).

1. The proof “follows mostly from Theorem 1 in Zhang and Huang (2008)” (Annals of Statistics 36:1567-1594), with $c_0=0$ in their notation. By definition $(2+4\bar{C})s+1=C{s}^2$, as in Lemma 3, so $C{s}^2\le (2+4\bar{C})s+1$.
2. Their quantity $c^{\ast }/c_{\ast }$ equals ${\varphi }_{max}^w(C{s}^2)/{\varphi }_{min}^w(C{s}^2)$ here. For every realisation $W=w$, as long as ${\alpha }^2\ge (7/\kappa {)}^2{\varphi }_{min}(C{s}^2)/(C{s}^2)$, Lemma 3 gives ${\varphi }_{max}^w((2+4\bar{C})s+1)/{\varphi }_{min}^w((2+4\bar{C})s+1)\le \bar{C}$. So all assumptions of their Theorem 1 hold with ${\eta }_1=0$, for every weight realisation.
3. By their (2.20)-(2.24) there is ${\Omega }_0$ with $P(Y\in {\Omega }_0)\ge 2-\exp (2/(p\vee a_n))-2/(p\vee a_n{)}^2\ge 1-3/(p\vee a_n)$ for all $p\ge 5$.
4. On ${\Omega }_0$, their (2.21) gives $|{\hat{A}}^{\lambda ,w}\cup S|\le (2+4\bar{C})s\le C{s}^2$ (eq. 25).
5. Their (2.23) gives (eq. 26)

$$\sum _{k\in S}|{\beta }_k{|}^{2}1\{k\notin {\hat{A}}^{\lambda ,w}\}\le (\frac{2}{3}\bar{C}+\frac{28}{9}{\bar{C}}^2+\frac{16}{9}{\bar{C}}^3)s{\lambda }^2\le 5.6{\bar{C}}^3{s}^3{\lambda }^2\le (0.3(Cs{)}^{3/2}\lambda {)}^2.$$

• First inequality: in Zhang & Huang’s notation, $1/(c_{\ast }{c}^{\ast })\le c^{\ast }/c_{\ast }$. Their $n^{-2}$ factor is omitted because of the different normalisation of $X$ (unit-norm columns here).
• Second inequality: the paper says it uses $4\bar{C}\le Cs$ (true, since $4\bar{C}s=C{s}^2-2s-1<C{s}^2$). A direct check: with $\bar{C}\ge 1$ the bracket is at most $(\frac{2}{3}+\frac{28}{9}+\frac{16}{9}){\bar{C}}^3\approx 5.56{\bar{C}}^3\le 5.6{\bar{C}}^3$, and $s\le s^3$.
• Last inequality: this is what defines $S_{small;\lambda }$. Squared, the right side is $0.09C^3{s}^3{\lambda }^2$, so read literally the step needs $5.6{\bar{C}}^3\le 0.09C^3$, i.e. $\bar{C}\le 0.25C$. But $\bar{C}=Cs/4-(2s+1)/(4s)\ge 1.2C$ for $s\ge 7$, $C>1$, so the step fails. See the note after this callout.

6. Any $k\in S$ missed by ${\hat{A}}^{\lambda ,w}$ therefore has $|{\beta }_k|\le 0.3(Cs{)}^{3/2}\lambda$, i.e. it lies in $S_{small;\lambda }$. This gives $(S\setminus S_{small;\lambda })\subseteq {\hat{A}}^{\lambda ,w}$.

Constant check in eq. (26)

As printed, (26) ends with $5.6{\bar{C}}^3{s}^3{\lambda }^2\le (0.3(Cs{)}^{3/2}\lambda {)}^2=0.09C^3{s}^3{\lambda }^2$. With $\bar{C}=(C{s}^2-2s-1)/(4s)$ this needs $\bar{C}\le 0.25C$, which fails for every $s\ge 7$, $C>1$ (there $\bar{C}\ge 1.2C$). Since $\bar{C}<Cs/4$, a bound of the form $5.6{\bar{C}}^3{s}^3\le 0.09C^3{s}^6$, i.e. $S_{small;\lambda }$ defined with $(C{s}^2{)}^{3/2}$-type scaling, or a larger leading constant, would make the chain valid. Alternatively, the normalisation change mentioned in the proof (dropping the $n^{-2}$ factor) may also rescale $\lambda$. This affects only the numerical constant in the definition of $S_{small;\lambda }$ (and hence in Remark 2’s beta-min condition), not the structure of Theorem 2. The paper does not flag it; this is an ingester arithmetic check of the arXiv v2 text, and the JRSS-B version may differ.

Lemma 5 - Irrepresentability holds with positive probability over weights (p. 25, eqs 27-28)

Let $m=C{s}^2$, $k\in \{\mathrm{1..}p\}$, and let $K(w)\subseteq \{\mathrm{1..}p\}$ depend on the weights, with $|K(w)|\le m$ and $k\notin K(w)$. Suppose a monotonicity property holds: $K(w)=A$ implies $K(v)=A$ whenever $v_j\le w_j$ for all $j$ with equality on $A$. Then for ${\alpha }^2\le {\varphi }_{min}(m)/(\sqrt{2}m)$ (this matches Theorem 2’s upper limit $\nu <1/\sqrt{2}$):

$$P_w(\Vert ((X_{K(w)}^w{)}^{\top }{X}_{K(w)}^w{)}^{-1}(X_{K(w)}^w{)}^{\top }{X}_k^w{\Vert }_1\le 2^{-1/4})\ge p_w(1-p_w{)}^m.\text{\hspace{1em}(27)}$$

Proof (p. 25).

1. Let $\tilde{w}$ be the realisation with ${\tilde{w}}_k=\alpha$ and ${\tilde{w}}_j=1$ for all $j\ne k$. Under the weight-sampling scheme it has probability $P(W=\tilde{w})=p_w(1-p_w{)}^{p-1}$. This is tiny, so the proof does not use this single point.
2. Let $A:=K(\tilde{w})$. Define $\mathcal{W}\subseteq \{\alpha ,1{\}}^p$ as all weights with $w_k=\alpha$, $w_j=1$ for $j\in A$, and arbitrary values for $j\notin A\cup \{k\}$. Then $P_w(w\in \mathcal{W})=p_w(1-p_w{)}^{|A|}\ge p_w(1-p_w{)}^m$.
3. Every $w\in \mathcal{W}$ satisfies $w_j\le {\tilde{w}}_j$ for all $j$, with equality on $A$. By the monotonicity assumption, $K(w)=A$ for all $w\in \mathcal{W}$.
4. For $w\in \mathcal{W}$, the columns in $A$ are unscaled and column $k$ is scaled by $\alpha$, so

$$((X_A^w{)}^{\top }{X}_A^w{)}^{-1}(X_A^w{)}^{\top }{X}_k^w=\alpha (X_A^{\top }{X}_A{)}^{-1}{X}_A^{\top }{X}_k.$$

5. With ${\alpha }^2\le {\varphi }_{min}(m)/(\sqrt{2}m)$, the result follows once one shows, for unit-norm columns,

$$\underset{A:|A|\le m}{\sup }\underset{k\notin A}{\sup }\Vert (X_A^{\top }{X}_A{)}^{-1}{X}_A^{\top }{X}_k{\Vert }_1^2\le m/{\varphi }_{min}(m).\text{\hspace{1em}(28)}$$

Then $\Vert \cdot {\Vert }_1^2\le {\alpha }^{2}m/{\varphi }_{min}(m)\le 1/\sqrt{2}$, i.e. $\Vert \cdot {\Vert }_1\le 2^{-1/4}$. 6. Proof of (28).

• Let $\gamma :=(X_A^{\top }{X}_A{)}^{-1}{X}_A^{\top }{X}_k$. Since $\Vert \gamma {\Vert }_1\le \sqrt{|A|}\Vert \gamma {\Vert }_2$, it suffices to show $\sup \Vert \gamma {\Vert }_2^2\le 1/{\varphi }_{min}(m)$.
• $X_A\gamma$ is the projection of $X_k$ onto the span of $X_A$, and $\Vert X_k{\Vert }_2^2=1$, so $\Vert X_A\gamma {\Vert }_2^2\le 1$.
• Also $\Vert X_A\gamma {\Vert }_2^2={\gamma }^{\top }{X}_A^{\top }{X}_A\gamma \ge {\varphi }_{min}(|A|)\Vert \gamma {\Vert }_2^2$. The source writes $X_S$ here, evidently meaning $X_A$, and uses ${\varphi }_{min}$ as the minimal eigenvalue of the Gram matrix in this step.
• Hence $\Vert \gamma {\Vert }_2^2\le 1/{\varphi }_{min}(|A|)\le 1/{\varphi }_{min}(m)$, which proves (28).

Intuition. Down-weighting the noise variable alone (which happens with positive probability) shrinks its representability by $\alpha$, enough to fall below 1.

Lemma 6 - Uniform noise bound (p. 25, eqs 29-30)

Let $P_A=X_A(X_A^{\top }{X}_A{)}^{-1}{X}_A^{\top }$. For $p>10$ there is ${\Omega }_1$ with $P({\Omega }_1)\ge 1-2/(p\vee a_n)$ on which

$$\underset{|A|\le m}{\sup }\underset{k\notin A}{\sup }|X_k^{\top }(1-P_A)\epsilon |<2\sigma (\sqrt{2m}+1)\sqrt{\log (p\vee a_n)/n}.$$

Proof (pp. 25-26).

1. Split. For $k\notin A$, $|X_k^{\top }(1-P_A)\epsilon |\le |X_k^{\top }\epsilon |+|X_k^{\top }{P}_A\epsilon |$ and $|X_k^{\top }{P}_A\epsilon |\le \Vert P_A\epsilon {\Vert }_2$ (unit-norm $X_k$).
2. Event ${\Omega }_1^{\prime }$: ${\max }_k|X_k^{\top }\epsilon |\le 2\sigma \sqrt{\log (p\vee a_n)/n}$. Since ${\epsilon }_i$ are i.i.d. $\mathcal{N}(0,{\sigma }^2)$, the Gaussian tail gives $P({\Omega }_1^{\prime })\ge 1-1/(p\vee a_n)$.
3. Event ${\Omega }_1^{\prime \prime }$: ${\sup }_{|A|\le m}\Vert P_A\epsilon {\Vert }_2\le 2\sigma \sqrt{2m\log (p\vee a_n)/n}$ (eq. 30). The goal is $P({\Omega }_1^{\prime \prime })\ge 1-1/(p\vee a_n)$. The argument follows a bound in Zhang & Huang (2008).
4. ${\chi }^2$ tail. If $X_A$ has full rank $|A|$, then $n\Vert P_A\epsilon {\Vert }_2^2/{\sigma }^2\sim {\chi }_{|A|}^2$. The standard tail bound used in the proof of Zhang & Huang’s Theorem 3 gives

$$P(n\Vert P_A\epsilon {\Vert }_2^2/{\sigma }^2\ge |A|(1+4\log (p\vee a_n)\left)\right)\le ((p\vee a_n{)}^{-4}(1+4\log (p\vee a_n)){)}^{|A|/2}\le (p\vee a_n{)}^{-3|A|/2}.$$

The last step uses $1+4\log (p\vee a_n)\le p\vee a_n$, which holds for all $p>10$. The paper does not spell out how the threshold $|A|(1+4\log (p\vee a_n))$ maps onto the radius in (30). 5. Union bound. Using $\left(\genfrac{}{}{0ex}{}{p}{|A|}\right)\le p^{|A|}/|A|!$ and summing over subset sizes $|A|=2,\dots ,m$:

$$P({\Omega }_1^{\prime \prime })\ge 1-\sum _{|A|=2}^m\left(\genfrac{}{}{0ex}{}{p}{|A|}\right)(p\vee a_n{)}^{-3|A|/2}\ge 1-\sum _{|A|=2}^m\frac{(p\vee a_n{)}^{-|A|/2}}{|A|!}\ge 1-\frac{1}{p\vee a_n}.$$

6. Set ${\Omega }_1={\Omega }_1^{\prime }\cap {\Omega }_1^{\prime \prime }$, so $P({\Omega }_1)\ge 1-2/(p\vee a_n)$ for all $p>10$. On ${\Omega }_1$ the two bounds add to $2\sigma (\sqrt{2m}+1)\sqrt{\log (p\vee a_n)/n}$.

The source text says $P({\Omega }_1^{\prime })\ge 1-1/(p\vee a_n)$ “for all $\delta \in (0,1)$”, although no $\delta$ appears. The sum starts at $|A|=2$ as printed.

Lemma 7 - Separation of selection probabilities (pp. 26-27, eqs 31-34)

Let ${\delta }_w=p_w(1-p_w{)}^{C{s}^2}$ and ${\hat{\Pi }}_k^{\lambda }=P_w(k\in {\hat{A}}^{\lambda ,W})$. Under Theorem 2’s assumptions, with $p>10$, on ${\Omega }_A={\Omega }_0\cap {\Omega }_1$ ($P\ge 1-5/(p\vee a_n)$), for all $\lambda \ge {\lambda }_{min}$:

$$\underset{k\in N}{\max }{\hat{\Pi }}_k^{\lambda }<1-{\delta }_w,\text{\hspace{1em}(31)}$$ $$\underset{k\in S\setminus S_{small;\lambda }}{\min }{\hat{\Pi }}_k^{\lambda }\ge 1-{\delta }_w.\text{\hspace{1em}(32)}$$

Sketch of (31).

1. A noise variable $k$ enters only if the KKT condition $|(X_k^w{)}^{\top }(Y-X_{-k}^w{\hat{\beta }}^{\lambda ,W,-k})|\ge \lambda$ holds (eq. 33). Here ${\hat{\beta }}^{\lambda ,W,-k}$ is the fit with ${\beta }_k$ forced to 0.
2. Let $\hat{B}={\hat{A}}^{\lambda ,W,-k}\cup S$ and split the residual into a $(1-P_{\hat{B}})$ part and a $P_{\hat{B}}$ part (eq. 34).
3. Projection invariance. For every $w$, $P_{\hat{B}}^w=X_{\hat{B}}^w((X_{\hat{B}}^w{)}^{\top }{X}_{\hat{B}}^w{)}^{-1}(X_{\hat{B}}^w{)}^{\top }=X_{\hat{B}}(X_{\hat{B}}^{\top }{X}_{\hat{B}}{)}^{-1}{X}_{\hat{B}}^{\top }=P_{\hat{B}}$. Rescaling columns does not change their span, so the projection does not depend on the weights.
4. Left term of (34). On ${\Omega }_0$, Lemma 4 gives $|\hat{B}|\le C{s}^2$, and $S\subseteq \hat{B}$ by definition. So $(1-P_{\hat{B}})X\beta =0$ and the left term is pure noise:

$$(X_k^w{)}^{\top }(1-P_{\hat{B}}^w)\epsilon \le \underset{A:|A|\le C{s}^2}{\sup }\underset{k\notin A}{\sup }|X_k^{\top }(1-P_A)\epsilon |\cdot \frac{\Vert X_k^w{\Vert }_2}{\Vert X_k{\Vert }_2}<{\lambda }_{min}\frac{\Vert X_k^w{\Vert }_2}{\Vert X_k{\Vert }_2},$$

by Lemma 6 with $m=C{s}^2$. This matches ${\lambda }_{min}=2\sigma (\sqrt{2C}s+1)\sqrt{\log (p\vee a_n)/n}$, because $\sqrt{2m}=\sqrt{2C}s$. 5. Right term of (34). Using the KKT conditions of the restricted fit,

$$(X_k^w{)}^{\top }{P}_{\hat{B}}^w(Y-X_{-k}^w{\hat{\beta }}^{\lambda ,W,-k})\le (X_k^w{)}^{\top }{X}_{\hat{B}}^w((X_{\hat{B}}^w{)}^{\top }{X}_{\hat{B}}^w{)}^{-1}\mathrm{sign}({\hat{\beta }}^{\lambda ,W,-k})\lambda \le \Vert ((X_{\hat{B}}^w{)}^{\top }{X}_{\hat{B}}^w{)}^{-1}(X_{\hat{B}}^w{)}^{\top }{X}_k^w{\Vert }_1\lambda .$$

6. Applying Lemma 5 with $K(w)=\hat{B}$. Check its three conditions:
   • $|\hat{B}|\le C{s}^2$.
   • $k\notin \hat{B}$ for all $w$, by construction.
   • Monotonicity. By the Lasso KKT conditions, ${\hat{\beta }}^{\lambda ,w,-k}$ and ${\hat{\beta }}^{\lambda ,v,-k}$ have the same non-zero set whenever $v_j=w_j$ on ${\hat{A}}^{\lambda ,W,-k}$ and $v_j\le w_j$ off it. In the paper’s words, “increasing the penalty on zero coefficients will leave them at zero, if the penalty for non-zero coefficients is kept constant”; a smaller weight means a larger effective penalty $\lambda /w_j$.
   So there is a weight event ${\Omega }_w$ with $P_w({\Omega }_w)\ge {\delta }_w$ on which the ${\ell }_1$ term is $\le 2^{-1/4}$. (The source prints "$\ge 1-{\delta }_w$" at this point. Lemma 5 gives $\ge p_w(1-p_w{)}^m={\delta }_w$, which is what (31) needs.)
7. Weight ratio. On ${\Omega }_w$, $w_k=\alpha$, so $\Vert X_k^w{\Vert }_2/\Vert X_k{\Vert }_2=\alpha \le 1/s\le 1/7$. This is where $s\ge 7$ enters. The paper states $\alpha \le 1/s$ without derivation. It follows (ingester’s check) from ${\alpha }^2=\nu {\varphi }_{min}(m)/m$ with $\nu <1$, ${\varphi }_{min}\le 1$ (unit-norm columns) and $m=C{s}^2\ge s^2$.
8. Conclusion. For $\omega \in {\Omega }_0\cap {\Omega }_1$ and weights in ${\Omega }_w$, the left side of (33) is $\le {\lambda }_{min}/7+2^{-1/4}\lambda <\lambda$, since $\lambda \ge {\lambda }_{min}$ and $1/7+2^{-1/4}\approx 0.98<1$. So $k\notin {\hat{A}}^{\lambda ,W}$, and ${\max }_{\lambda }{\hat{\Pi }}_k^{\lambda }<1-{\delta }_w$ for every $k\notin S$.

(32) follows from Lemma 4: on ${\Omega }_0$, $S\setminus S_{small;\lambda }\subseteq {\hat{A}}^{\lambda ,W}$ for every $w$, so ${\hat{\Pi }}_k^{\lambda }=1$.

Lemma 7 is a reformulation of Theorem 2, with $\delta ={\delta }_w$, which completes its proof.

Proof map

Step	Lemma	What it buys
Reweighting keeps the design well-conditioned	L3	Lower bound on usable $\alpha$
Relevant variables always in, model size $\le C{s}^2$	L4 (Zhang & Huang 2008)	(18); support size for L5-L6
Each noise variable “irrepresentable” with prob $\ge {\delta }_w$ over weights	L5	Selection probability of noise $<1-{\delta }_w$
Noise correlations uniformly small	L6	Sets ${\lambda }_{min}$
Assemble on ${\Omega }_0\cap {\Omega }_1$	L7	(17) with ${\pi }_{thr}\ge 1-{\delta }_w$

The threshold needed, ${\pi }_{thr}\ge 1-{\delta }_w$ with ${\delta }_w=p_w(1-p_w{)}^{C{s}^2}$, is extremely close to 1 for moderate $s$. The theorem is a qualitative statement about why randomisation helps, not a calibration rule. Practical thresholds come from Theorem 1 (Stability Selection PFER Bound (Theorem 1) and Its Proof).

Examples

Size of ${\delta }_w$

With $p_w=0.5$, $s=7$ and $C=1.1$, $C{s}^2\approx 54$ and ${\delta }_w=0.5\cdot 0.5^{54}\approx 3\times 10^{-17}$. The theorem’s threshold $1-{\delta }_w$ is essentially 1. This shows the gap between the asymptotic guarantee and the practical recommendation ${\pi }_{thr}\in (0.6,0.9)$ and $\alpha \in (0.2,0.8)$, which is backed instead by §4’s simulations.

Connections

• Sparse-eigenvalue / restricted-eigenvalue conditions also underlie Lasso nuisance estimation in DML (DML Estimators for ATE and the Interactive Model, Regularization Bias and the Partially Linear Model).
• The conservativeness of Remark 3 (wrong $\lambda$ costs power, not false positives) is the property a validation reviewer wants when selection feeds into reported drivers. Compare SR 11-7 - Model Risk Management Guidance - Overview on effective challenge.

See Also

• Meinshausen Buhlmann 2010 - Stability Selection - Overview
• Randomised Lasso and the Irrepresentable Condition
• Randomised Orthogonal Matching Pursuit (ROMP) for Stability Selection