[proofplan] The proof is a direct extraction of the necessary optimality equations for a Lasso minimizer with the prescribed signed support. On the active coordinates, the differentiable quadratic part balances the $\ell^1$ subgradient $s$, and invertibility of $\hat{\Sigma}_{SS}$ gives an explicit formula for $\hat{\beta}_S$. On the inactive coordinates, the one-sided directional optimality condition gives the dual bound, and substituting the active formula produces the stated residual-noise vector. The probability bound follows from event inclusion, and the final obstruction follows from the [reverse triangle inequality](/theorems/2300). [/proofplan]

[step:Derive the coordinatewise optimality conditions for the assumed minimizer]We use the componentwise sign convention $\operatorname{sign}(0)=0$. For each $j\in\{1,\dots,p\}$, let $X_j\in\mathbb R^n$ denote the $j$th column of $X$. Define the Lasso objective $Q_\lambda: \mathbb{R}^p \to \mathbb{R}$ by \begin{align*} Q_\lambda(b) := \frac{1}{2n}\|Y-Xb\|_2^2+\lambda\|b\|_1. \end{align*} If $S=\varnothing$, all active-coordinate equations below are interpreted as empty vector identities, and the inactive-coordinate argument remains unchanged. Fix a realization of $\varepsilon$ for which there exists a minimizer $\hat{\beta} \in \operatorname*{arg\,min}_{b \in \mathbb{R}^p} Q_\lambda(b)$ satisfying $\operatorname{supp}(\hat{\beta})=S$ and $\operatorname{sign}(\hat{\beta}_S)=s$. Let $r := Y-X\hat{\beta} \in \mathbb{R}^n$ denote the residual vector. For each $j \in S$, let $e_j \in \mathbb{R}^p$ denote the $j$th standard basis vector. The function $t \mapsto Q_\lambda(\hat{\beta}+t e_j)$ is differentiable at $t=0$, because $\hat{\beta}_j \ne 0$ and the absolute value term is differentiable there. Since $t=0$ is a minimum, its derivative vanishes: \begin{align*} -\frac{1}{n}X_j^\top r+\lambda \operatorname{sign}(\hat{\beta}_j)=0. \end{align*} Thus, using $\operatorname{sign}(\hat{\beta}_S)=s$, \begin{align*} \frac{X_S^\top r}{n}=\lambda s. \end{align*} For each $j \in S^c$, we have $\hat{\beta}_j=0$. Since $t=0$ minimizes $t \mapsto Q_\lambda(\hat{\beta}+t e_j)$, for every $t \in \mathbb{R}$, \begin{align*} 0 \le Q_\lambda(\hat{\beta}+t e_j)-Q_\lambda(\hat{\beta}) = -\frac{t}{n}X_j^\top r + \frac{t^2}{2n}|X_j|^2 + \lambda |t|. \end{align*} Dividing by $t>0$ and letting $t \downarrow 0$ gives $-\frac{1}{n}X_j^\top r+\lambda \ge 0$, since the right-hand side after division is continuous in $t$ at $0$. Dividing by $t<0$ and letting $t \uparrow 0$ gives $-\frac{1}{n}X_j^\top r-\lambda \le 0$, again by continuity at $0$. Therefore \begin{align*} \left|\frac{X_j^\top r}{n\lambda}\right|\le 1. \end{align*} Equivalently, \begin{align*} \left\|\frac{X_{S^c}^\top r}{n\lambda}\right\|_\infty \le 1. \end{align*}[/step]

[guided]We first isolate the only optimality facts about the Lasso that are needed. Define the Lasso objective $Q_\lambda: \mathbb{R}^p \to \mathbb{R}$ by \begin{align*} Q_\lambda(b) := \frac{1}{2n}\|Y-Xb\|_2^2+\lambda\|b\|_1. \end{align*} Fix one realization of the noise vector $\varepsilon$ and assume that, for this realization, a minimizer $\hat{\beta}$ has support $S$ and active sign vector $s$. Throughout this argument, $\operatorname{sign}$ is applied componentwise and $\operatorname{sign}(0)=0$. If $S=\varnothing$, the active-coordinate equations below are empty vector identities; the inactive-coordinate inequalities are still obtained coordinate by coordinate over $S^c$. Define the residual vector $r \in \mathbb{R}^n$ by \begin{align*} r := Y-X\hat{\beta}. \end{align*} For an active coordinate $j \in S$, the coefficient $\hat{\beta}_j$ is nonzero. This matters because the map $t \mapsto |\hat{\beta}_j+t|$ is differentiable at $t=0$, with derivative $\operatorname{sign}(\hat{\beta}_j)$. Let $e_j \in \mathbb{R}^p$ denote the $j$th standard basis vector. Define the one-variable map $\phi_j: \mathbb{R} \to \mathbb{R}$ by $\phi_j(t) := Q_\lambda(\hat{\beta}+t e_j)$. This map has a minimum at $t=0$. Since it is differentiable at $0$, its derivative at $0$ must be zero. Differentiating the quadratic term gives \begin{align*} \frac{d}{dt}\bigg|_{t=0}\frac{1}{2n}|Y-X(\hat{\beta}+t e_j)|^2 = -\frac{1}{n}X_j^\top (Y-X\hat{\beta}) = -\frac{1}{n}X_j^\top r. \end{align*} Differentiating the $\ell^1$ term in the active coordinate gives $\lambda \operatorname{sign}(\hat{\beta}_j)$. Hence \begin{align*} -\frac{1}{n}X_j^\top r+\lambda \operatorname{sign}(\hat{\beta}_j)=0. \end{align*} Collecting these equations for all $j \in S$ and using $\operatorname{sign}(\hat{\beta}_S)=s$ yields \begin{align*} \frac{X_S^\top r}{n}=\lambda s. \end{align*} For an inactive coordinate $j \in S^c$, the coefficient $\hat{\beta}_j$ equals $0$, so the absolute value is not differentiable at the origin. We therefore use one-sided perturbations instead of a derivative. For every $t \in \mathbb{R}$, minimality of $\hat{\beta}$ gives \begin{align*} 0 \le Q_\lambda(\hat{\beta}+t e_j)-Q_\lambda(\hat{\beta}). \end{align*} Since only the $j$th coefficient changes and $\hat{\beta}_j=0$, the $\ell^1$ term changes by $\lambda |t|$. The quadratic term expands as \begin{align*} \frac{1}{2n}|r-tX_j|^2-\frac{1}{2n}|r|^2 = -\frac{t}{n}X_j^\top r+\frac{t^2}{2n}\|X_j\|_2^2. \end{align*} Therefore \begin{align*} 0 \le -\frac{t}{n}X_j^\top r + \frac{t^2}{2n}|X_j|^2 + \lambda |t|. \end{align*} For $t>0$, dividing by $t$ gives \begin{align*} 0 \le -\frac{1}{n}X_j^\top r+\frac{t}{2n}\|X_j\|_2^2+\lambda. \end{align*} Letting $t \downarrow 0$ gives $-\frac{1}{n}X_j^\top r+\lambda \ge 0$, because the affine expression in $t$ on the right-hand side is continuous at $0$. For $t<0$, dividing by $t$ reverses the inequality: \begin{align*} 0 \ge -\frac{1}{n}X_j^\top r+\frac{t}{2n}\|X_j\|_2^2-\lambda. \end{align*} Letting $t \uparrow 0$ gives $-\frac{1}{n}X_j^\top r-\lambda \le 0$, again by continuity of the affine expression in $t$ at $0$. These two inequalities are exactly \begin{align*} -\lambda \le \frac{X_j^\top r}{n} \le \lambda, \end{align*} or \begin{align*} \left|\frac{X_j^\top r}{n\lambda}\right|\le 1. \end{align*} Taking the maximum over $j \in S^c$ gives the inactive coordinate condition \begin{align*} \left\|\frac{X_{S^c}^\top r}{n\lambda}\right\|_\infty \le 1. \end{align*}[/guided]

[step:Solve the active equations and obtain the active sign barrier]Since $\operatorname{supp}(\hat{\beta})=S$, we have $\hat{\beta}_{S^c}=0$. Using $Y=X\beta^*+\varepsilon$ and $\operatorname{supp}(\beta^*)=S$, the residual satisfies \begin{align*} r = Y-X\hat{\beta} = X_S(\beta^*_S-\hat{\beta}_S)+\varepsilon. \end{align*} Substituting this expression into the active optimality equation gives \begin{align*} \lambda s = \frac{X_S^\top r}{n} = \hat{\Sigma}_{SS}(\beta^*_S-\hat{\beta}_S)+\frac{X_S^\top\varepsilon}{n}. \end{align*} Since $\hat{\Sigma}_{SS}$ is invertible, \begin{align*} \hat{\beta}_S = \beta^*_S+\hat{\Sigma}_{SS}^{-1}\frac{X_S^\top\varepsilon}{n} -\lambda \hat{\Sigma}_{SS}^{-1}s = \beta^*_S+W_S-\lambda \hat{\Sigma}_{SS}^{-1}s. \end{align*} The assumed equality $\operatorname{sign}(\hat{\beta}_S)=s$ therefore implies \begin{align*} \operatorname{sign}\left(\beta^*_S+W_S-\lambda\hat{\Sigma}_{SS}^{-1}s\right)=s. \end{align*}[/step]

[guided]The active equations identify what the Lasso coefficient on $S$ must be if exact signed recovery occurs. Since $\operatorname{supp}(\hat{\beta})=S$, we have $\hat{\beta}_{S^c}=0$. Since $\operatorname{supp}(\beta^*)=S$, the true signal satisfies $X\beta^*=X_S\beta^*_S$. Hence the residual vector is \begin{align*} r = Y-X\hat{\beta} = X_S\beta^*_S+\varepsilon-X_S\hat{\beta}_S = X_S(\beta^*_S-\hat{\beta}_S)+\varepsilon. \end{align*} The active optimality condition from the previous step is \begin{align*} \frac{X_S^\top r}{n}=\lambda s. \end{align*} Substituting the residual formula into this equation gives \begin{align*} \lambda s = \frac{X_S^\top}{n}\left(X_S(\beta^*_S-\hat{\beta}_S)+\varepsilon\right) = \hat{\Sigma}_{SS}(\beta^*_S-\hat{\beta}_S)+\frac{X_S^\top\varepsilon}{n}. \end{align*} Here we use the definition $\hat{\Sigma}_{SS}=X_S^\top X_S/n$. The hypothesis that $\hat{\Sigma}_{SS}$ is invertible is used exactly at this point: multiplying by $\hat{\Sigma}_{SS}^{-1}$ and solving for $\hat{\beta}_S$ gives \begin{align*} \hat{\beta}_S = \beta^*_S+\hat{\Sigma}_{SS}^{-1}\frac{X_S^\top\varepsilon}{n} -\lambda\hat{\Sigma}_{SS}^{-1}s. \end{align*} By the definition of the active noise vector $W_S$, this is \begin{align*} \hat{\beta}_S=\beta^*_S+W_S-\lambda\hat{\Sigma}_{SS}^{-1}s. \end{align*} If the assumed minimizer has active sign vector $s$, then taking signs on both sides yields the necessary active barrier \begin{align*} \operatorname{sign}\left(\beta^*_S+W_S-\lambda\hat{\Sigma}_{SS}^{-1}s\right)=s. \end{align*}[/guided]

[step:Substitute the active solution into the inactive dual condition]Using the residual identity and the formula for $\hat{\beta}_S$, compute \begin{align*} \beta^*_S-\hat{\beta}_S = -\hat{\Sigma}_{SS}^{-1}\frac{X_S^\top\varepsilon}{n} + \lambda \hat{\Sigma}_{SS}^{-1}s. \end{align*} Substituting this expression into $X_{S^c}^\top r/(n\lambda)$ first gives \begin{align*} \frac{X_{S^c}^\top r}{n\lambda} = \frac{1}{\lambda}\left[\hat{\Sigma}_{S^cS}(\beta^*_S-\hat{\beta}_S)+\frac{X_{S^c}^\top\varepsilon}{n}\right]. \end{align*} Using the displayed identity for $\beta^*_S-\hat{\beta}_S$, this becomes \begin{align*} \frac{X_{S^c}^\top r}{n\lambda} = \hat{\Sigma}_{S^cS}\hat{\Sigma}_{SS}^{-1}s + \frac{1}{\lambda}\left[\frac{X_{S^c}^\top\varepsilon}{n}-\hat{\Sigma}_{S^cS}\hat{\Sigma}_{SS}^{-1}\frac{X_S^\top\varepsilon}{n}\right]. \end{align*} Let $I_n\in\mathbb{R}^{n\times n}$ denote the identity matrix. Since $\hat{\Sigma}_{S^cS}=X_{S^c}^\top X_S/n$, the bracketed noise term is \begin{align*} \frac{X_{S^c}^\top\varepsilon}{n}-\hat{\Sigma}_{S^cS}\hat{\Sigma}_{SS}^{-1}\frac{X_S^\top\varepsilon}{n} = \frac{X_{S^c}^\top}{n}\left(I_n-X_S\hat{\Sigma}_{SS}^{-1}\frac{X_S^\top}{n}\right)\varepsilon. \end{align*} By the definition of $R_{S^c}$, we therefore obtain \begin{align*} \frac{X_{S^c}^\top r}{n\lambda} = \hat{\Sigma}_{S^cS}\hat{\Sigma}_{SS}^{-1}s+\frac{1}{\lambda}R_{S^c}. \end{align*} Combining this identity with \begin{align*} \left\|\frac{X_{S^c}^\top r}{n\lambda}\right\|_\infty \le 1 \end{align*} gives \begin{align*} \left\| \hat{\Sigma}_{S^cS}\hat{\Sigma}_{SS}^{-1}s+\frac{1}{\lambda}R_{S^c} \right\|_\infty \le 1. \end{align*}[/step]

[guided]The inactive condition starts from the bound already proved for every inactive coordinate: \begin{align*} \left\|\frac{X_{S^c}^\top r}{n\lambda}\right\|_\infty \le 1. \end{align*} We now rewrite the vector inside this norm in terms of deterministic design quantities and the residual noise. From the active formula, \begin{align*} \hat{\beta}_S = \beta^*_S+\hat{\Sigma}_{SS}^{-1}\frac{X_S^\top\varepsilon}{n} -\lambda\hat{\Sigma}_{SS}^{-1}s, \end{align*} so \begin{align*} \beta^*_S-\hat{\beta}_S = -\hat{\Sigma}_{SS}^{-1}\frac{X_S^\top\varepsilon}{n} + \lambda\hat{\Sigma}_{SS}^{-1}s. \end{align*} Using $r=X_S(\beta^*_S-\hat{\beta}_S)+\varepsilon$, we obtain \begin{align*} \frac{X_{S^c}^\top r}{n\lambda} = \frac{1}{\lambda}\left[\hat{\Sigma}_{S^cS}(\beta^*_S-\hat{\beta}_S)+\frac{X_{S^c}^\top\varepsilon}{n}\right]. \end{align*} Substituting the displayed expression for $\beta^*_S-\hat{\beta}_S$ gives \begin{align*} \frac{X_{S^c}^\top r}{n\lambda} = \hat{\Sigma}_{S^cS}\hat{\Sigma}_{SS}^{-1}s + \frac{1}{\lambda}\left[\frac{X_{S^c}^\top\varepsilon}{n}-\hat{\Sigma}_{S^cS}\hat{\Sigma}_{SS}^{-1}\frac{X_S^\top\varepsilon}{n}\right]. \end{align*} The bracket is exactly the inactive residual-noise vector. Let $I_n\in\mathbb{R}^{n\times n}$ denote the identity matrix. Indeed, since $\hat{\Sigma}_{S^cS}=X_{S^c}^\top X_S/n$, \begin{align*} \frac{X_{S^c}^\top\varepsilon}{n}-\hat{\Sigma}_{S^cS}\hat{\Sigma}_{SS}^{-1}\frac{X_S^\top\varepsilon}{n} = \frac{X_{S^c}^\top}{n}\left(I_n-X_S\hat{\Sigma}_{SS}^{-1}\frac{X_S^\top}{n}\right)\varepsilon = R_{S^c}. \end{align*} Therefore \begin{align*} \frac{X_{S^c}^\top r}{n\lambda} = \hat{\Sigma}_{S^cS}\hat{\Sigma}_{SS}^{-1}s+\frac{1}{\lambda}R_{S^c}. \end{align*} Putting this identity into the inactive norm bound yields \begin{align*} \left\| \hat{\Sigma}_{S^cS}\hat{\Sigma}_{SS}^{-1}s+\frac{1}{\lambda}R_{S^c} \right\|_\infty \le 1. \end{align*}[/guided]

[step:Convert the necessary conditions into the probability upper bound]Let $A$ denote the event that there exists a Lasso minimizer $\hat{\beta}$ with \begin{align*} \operatorname{sign}(\hat{\beta})=\operatorname{sign}(\beta^*). \end{align*} On $A$, the convention $\operatorname{sign}(0)=0$ implies that the zero coordinates of $\hat{\beta}$ and $\beta^*$ coincide, so this minimizer satisfies $\operatorname{supp}(\hat{\beta})=S$ and $\operatorname{sign}(\hat{\beta}_S)=s$. The previous steps show that $A$ is contained in the event \begin{align*} B := \left\{ \operatorname{sign}\left(\beta^*_S+W_S-\lambda\hat{\Sigma}_{SS}^{-1}s\right)=s, \, \left\| \hat{\Sigma}_{S^cS}\hat{\Sigma}_{SS}^{-1}s+\frac{1}{\lambda}R_{S^c} \right\|_\infty \le 1 \right\}. \end{align*} Therefore monotonicity of probability gives \begin{align*} \mathbb{P}(A)\le \mathbb{P}(B), \end{align*} which is the stated probability inequality.[/step]

[guided]We now turn the deterministic necessary conditions into a probability statement. Let $A$ be the event that there exists a Lasso minimizer $\hat{\beta}$ satisfying \begin{align*} \operatorname{sign}(\hat{\beta})=\operatorname{sign}(\beta^*). \end{align*} On this event, the convention $\operatorname{sign}(0)=0$ means that a coordinate is zero exactly when its sign is zero. Hence the support and sign assumptions used in the deterministic part are satisfied: $\operatorname{supp}(\hat{\beta})=S$ and $\operatorname{sign}(\hat{\beta}_S)=s$. Therefore every outcome in $A$ must also satisfy both barriers proved above. Define \begin{align*} B := \left\{ \operatorname{sign}\left(\beta^*_S+W_S-\lambda\hat{\Sigma}_{SS}^{-1}s\right)=s, \, \left\| \hat{\Sigma}_{S^cS}\hat{\Sigma}_{SS}^{-1}s+\frac{1}{\lambda}R_{S^c} \right\|_\infty \le 1 \right\}. \end{align*} The previous steps prove the event inclusion $A\subseteq B$. This is the only probabilistic input: for any probability law of the noise vector $\varepsilon$, monotonicity of probability gives \begin{align*} \mathbb{P}(A)\le \mathbb{P}(B). \end{align*} Expanding the definitions of $A$ and $B$ is exactly the probability inequality stated in the theorem.[/guided]

[step:Use the deterministic incoherence violation and small residual noise to force failure]For the sequence in the final assertion, write $\lambda_n>0$ for the Lasso tuning parameter at stage $n$, write $S_n$ for the true support at stage $n$, and write $s_n:=\operatorname{sign}(\beta^*_{n,S_n})$ for the active sign vector. Also write $\hat{\Sigma}_{n,S_n^cS_n}$ for the inactive-active design covariance matrix at stage $n$, write $\hat{\Sigma}_{n,S_nS_n}$ for the active-active design covariance matrix at stage $n$, and write $R_{n,S_n^c}$ for the inactive residual-noise vector at stage $n$. Define the deterministic inactive vector $a_n \in \mathbb{R}^{S_n^c}$ by \begin{align*} a_n := \hat{\Sigma}_{n,S_n^cS_n} \left(\hat{\Sigma}_{n,S_nS_n}\right)^{-1}s_n. \end{align*} and define the random inactive residual vector $u_n \in \mathbb{R}^{S_n^c}$ by \begin{align*} u_n := \frac{1}{\lambda_n}R_{n,S_n^c}. \end{align*} The elementary reverse triangle inequality for the supremum norm, obtained from $\|a_n\|_\infty\le \|a_n+u_n\|_\infty+\|u_n\|_\infty$, gives \begin{align*} \|a_n+u_n\|_\infty \ge \|a_n\|_\infty-\|u_n\|_\infty. \end{align*} On the event $\|R_{n,S_n^c}\|_\infty \le \lambda_n\delta$, we have $\|u_n\|_\infty \le \delta$. Therefore, for all sufficiently large $n$, \begin{align*} \|a_n+u_n\|_\infty \ge (1+2\delta)-\delta = 1+\delta > 1. \end{align*} Thus the inactive dual feasibility condition fails on the event $\|R_{n,S_n^c}\|_\infty \le \lambda_n\delta$. Since exact sign recovery implies inactive dual feasibility, the exact sign recovery event is contained in \begin{align*} \left\{\|R_{n,S_n^c}\|_\infty > \lambda_n\delta\right\}. \end{align*} Consequently, \begin{align*} \mathbb{P}(\text{exact Lasso sign recovery at stage } n) \le \mathbb{P}\left(\|R_{n,S_n^c}\|_\infty > \lambda_n\delta\right) \to 0. \end{align*} This proves that the exact sign recovery probability tends to $0$ along the sequence.[/step]

[guided]For the final assertion, we work stage by stage along the sequence. Write $\lambda_n>0$ for the Lasso tuning parameter at stage $n$, write $S_n$ for the true support at stage $n$, and write $s_n:=\operatorname{sign}(\beta^*_{n,S_n})$ for the active sign vector. Also write $\hat{\Sigma}_{n,S_n^cS_n}$ for the inactive-active design covariance matrix at stage $n$, write $\hat{\Sigma}_{n,S_nS_n}$ for the active-active design covariance matrix at stage $n$, and write $R_{n,S_n^c}$ for the inactive residual-noise vector at stage $n$. Define the deterministic inactive vector $a_n \in \mathbb{R}^{S_n^c}$ by \begin{align*} a_n := \hat{\Sigma}_{n,S_n^cS_n} \left(\hat{\Sigma}_{n,S_nS_n}\right)^{-1}s_n. \end{align*} and define the random inactive residual vector $u_n \in \mathbb{R}^{S_n^c}$ by \begin{align*} u_n:=\frac{1}{\lambda_n}R_{n,S_n^c}. \end{align*} The inactive dual feasibility condition at stage $n$ is $\|a_n+u_n\|_\infty\le 1$. The deterministic assumption says that \begin{align*} \|a_n\|_\infty\ge 1+2\delta. \end{align*} On the high-probability event $\|R_{n,S_n^c}\|_\infty\le \lambda_n\delta$, we also have $\|u_n\|_\infty\le\delta$. The elementary reverse triangle inequality for the supremum norm, obtained from $\|a_n\|_\infty\le \|a_n+u_n\|_\infty+\|u_n\|_\infty$, gives \begin{align*} \|a_n+u_n\|_\infty \ge \|a_n\|_\infty-\|u_n\|_\infty \ge (1+2\delta)-\delta = 1+\delta > 1. \end{align*} Thus inactive dual feasibility fails whenever $\|R_{n,S_n^c}\|_\infty\le \lambda_n\delta$. Since exact sign recovery implies inactive dual feasibility, the exact sign recovery event is contained in the complement event \begin{align*} \left\{\|R_{n,S_n^c}\|_\infty>\lambda_n\delta\right\}. \end{align*} Taking probabilities gives \begin{align*} \mathbb{P}(\text{exact Lasso sign recovery at stage } n) \le \mathbb{P}\left(\|R_{n,S_n^c}\|_\infty>\lambda_n\delta\right). \end{align*} The hypothesis $\mathbb{P}(\|R_{n,S_n^c}\|_\infty\le\lambda_n\delta)\to 1$ is equivalent to the right-hand side tending to $0$. Therefore the exact Lasso sign recovery probability tends to $0$ along the sequence.[/guided]