[proofplan]
Set $\Delta := \hat{\beta}-\beta^*$ and use the [Lasso](/page/Lasso) optimality inequality at $\beta^*$ to compare the empirical prediction loss of $\hat{\beta}$ to the stochastic [inner product](/page/Inner%20Product) $\varepsilon^\top X\Delta$. On the event $\mathcal{E}_\lambda$, this stochastic term is controlled by $\lambda\|\Delta\|_1$, and the support decomposition over $S$ yields both the cone condition $\|\Delta_{S^c}\|_1 \le 3\|\Delta_S\|_1$ and the sharper prediction bound by $3\lambda\|\Delta_S\|_1$. If $s=0$, the same inequality forces $\Delta=0$; otherwise, the [compatibility constant](/page/Compatibility%20Condition) converts $\|\Delta_S\|_1$ into $|X\Delta|/\sqrt n$, after which a one-line algebraic rearrangement gives the stated fast-rate prediction bound.
[/proofplan]
[step:Derive the basic inequality from Lasso optimality]
Let $p \in \mathbb{N}$ denote the number of columns of $X$, so that $X \in \mathbb{R}^{n \times p}$ and $\beta^*,\hat{\beta} \in \mathbb{R}^p$. Define the error vector $\Delta \in \mathbb{R}^p$ by
\begin{align*}
\Delta := \hat{\beta}-\beta^*.
\end{align*}
Since $\hat{\beta}$ minimizes the Lasso objective over $\mathbb{R}^p$, comparison with $\beta^*$ gives
\begin{align*}
\frac{1}{n}|Y-X\hat{\beta}|^2 + 2\lambda\|\hat{\beta}\|_1
\le
\frac{1}{n}|Y-X\beta^*|^2 + 2\lambda\|\beta^*\|_1.
\end{align*}
Using $Y=X\beta^*+\varepsilon$ and $X\hat{\beta}=X\beta^*+X\Delta$, we have
\begin{align*}
Y-X\hat{\beta}=\varepsilon-X\Delta,
\qquad
Y-X\beta^*=\varepsilon.
\end{align*}
Substituting these identities and expanding the Euclidean square gives
\begin{align*}
\frac{1}{n}|\varepsilon-X\Delta|^2 + 2\lambda\|\hat{\beta}\|_1
\le
\frac{1}{n}|\varepsilon|^2 + 2\lambda\|\beta^*\|_1.
\end{align*}
After expanding $|\varepsilon-X\Delta|^2$, cancelling $n^{-1}|\varepsilon|^2$ from both sides, and moving the cross term to the right-hand side, we obtain
\begin{align*}
\frac{1}{n}|X\Delta|^2
\le
\frac{2}{n}\varepsilon^\top X\Delta
+2\lambda\bigl(\|\beta^*\|_1-\|\hat{\beta}\|_1\bigr).
\end{align*}
[/step]
[step:Use the event $\mathcal{E}_\lambda$ and the support decomposition]
Recall that $\mathcal{E}_\lambda$ denotes the event
\begin{align*}
\mathcal{E}_\lambda
:=
\left\{\left\|\frac{1}{n}X^\top\varepsilon\right\|_\infty \le \frac{\lambda}{2}\right\}.
\end{align*}
On $\mathcal{E}_\lambda$, the [dual norm inequality](/page/Dual%20Norm) for $\ell^\infty$ and $\ell^1$ gives
\begin{align*}
\left|\frac{2}{n}\varepsilon^\top X\Delta\right|
=
2\left|\left(\frac{1}{n}X^\top\varepsilon\right)^\top \Delta\right|
\le
2\left\|\frac{1}{n}X^\top\varepsilon\right\|_\infty \|\Delta\|_1
\le
\lambda\|\Delta\|_1.
\end{align*}
Because $\beta^*_{S^c}=0$, we have $\hat{\beta}_{S^c}=\Delta_{S^c}$ and $\hat{\beta}_S=\beta^*_S+\Delta_S$. The [reverse triangle inequality](/page/Reverse%20Triangle%20Inequality) on the coordinates in $S$ gives
\begin{align*}
\|\beta^*\|_1-\|\hat{\beta}\|_1
=
\|\beta^*_S\|_1-\|\beta^*_S+\Delta_S\|_1-\|\Delta_{S^c}\|_1.
\end{align*}
Using $\|\beta^*_S\|_1-\|\beta^*_S+\Delta_S\|_1\le \|\Delta_S\|_1$, this becomes
\begin{align*}
\|\beta^*\|_1-\|\hat{\beta}\|_1
\le
\|\Delta_S\|_1-\|\Delta_{S^c}\|_1.
\end{align*}
Combining this estimate with the basic inequality gives
\begin{align*}
\frac{1}{n}|X\Delta|^2
\le
\lambda\|\Delta\|_1
+
2\lambda\bigl(\|\Delta_S\|_1-\|\Delta_{S^c}\|_1\bigr).
\end{align*}
Since $\|\Delta\|_1=\|\Delta_S\|_1+\|\Delta_{S^c}\|_1$, the right-hand side equals
\begin{align*}
3\lambda\|\Delta_S\|_1-\lambda\|\Delta_{S^c}\|_1.
\end{align*}
In particular,
\begin{align*}
\frac{1}{n}|X\Delta|^2
\le
3\lambda\|\Delta_S\|_1.
\end{align*}
[guided]
The purpose of this step is to turn the random quantity involving $\varepsilon$ into a deterministic norm bound and then separate the active coordinates $S$ from the inactive coordinates $S^c$.
On the event $\mathcal{E}_\lambda$, the vector $\frac{1}{n}X^\top\varepsilon \in \mathbb{R}^p$ has $\ell^\infty$ norm at most $\lambda/2$. Applying the [dual norm inequality](/page/Dual%20Norm) between $\ell^\infty$ and $\ell^1$ to the vectors $\frac{1}{n}X^\top\varepsilon$ and $\Delta$ gives
\begin{align*}
\left|\frac{2}{n}\varepsilon^\top X\Delta\right|
=
2\left|\left(\frac{1}{n}X^\top\varepsilon\right)^\top \Delta\right|
\le
2\left\|\frac{1}{n}X^\top\varepsilon\right\|_\infty \|\Delta\|_1
\le
\lambda\|\Delta\|_1.
\end{align*}
This is exactly where the event $\mathcal{E}_\lambda$ is used.
Next we exploit sparsity. Since $S=\operatorname{supp}(\beta^*)$, the inactive coordinates satisfy $\beta^*_{S^c}=0$. Hence
\begin{align*}
\hat{\beta}_{S^c}
=
\beta^*_{S^c}+\Delta_{S^c}
=
\Delta_{S^c}.
\end{align*}
On the active coordinates, we also have
\begin{align*}
\hat{\beta}_S
=
\beta^*_S+\Delta_S.
\end{align*}
Therefore
\begin{align*}
\|\hat{\beta}\|_1
=
\|\beta^*_S+\Delta_S\|_1+\|\Delta_{S^c}\|_1.
\end{align*}
By the [reverse triangle inequality](/page/Reverse%20Triangle%20Inequality) on $\mathbb{R}^S$,
\begin{align*}
\|\beta^*_S\|_1-\|\beta^*_S+\Delta_S\|_1
\le
\|\Delta_S\|_1.
\end{align*}
Since $\|\beta^*\|_1=\|\beta^*_S\|_1$, it follows that
\begin{align*}
\|\beta^*\|_1-\|\hat{\beta}\|_1
=
\|\beta^*_S\|_1-\|\beta^*_S+\Delta_S\|_1-\|\Delta_{S^c}\|_1.
\end{align*}
Combining this identity with the [reverse triangle inequality](/theorems/2300) gives
\begin{align*}
\|\beta^*\|_1-\|\hat{\beta}\|_1
\le
\|\Delta_S\|_1-\|\Delta_{S^c}\|_1.
\end{align*}
Substituting the stochastic bound and this support estimate into the basic inequality yields
\begin{align*}
\frac{1}{n}|X\Delta|^2
\le
\lambda\|\Delta\|_1
+
2\lambda\bigl(\|\Delta_S\|_1-\|\Delta_{S^c}\|_1\bigr).
\end{align*}
Using the support decomposition $\|\Delta\|_1=\|\Delta_S\|_1+\|\Delta_{S^c}\|_1$, the right-hand side is
\begin{align*}
\lambda\bigl(\|\Delta_S\|_1+\|\Delta_{S^c}\|_1\bigr)
+
2\lambda\|\Delta_S\|_1
-
2\lambda\|\Delta_{S^c}\|_1.
\end{align*}
Collecting the active and inactive terms gives
\begin{align*}
3\lambda\|\Delta_S\|_1-\lambda\|\Delta_{S^c}\|_1.
\end{align*}
Dropping the non-positive term $-\lambda\|\Delta_{S^c}\|_1$ gives the sharper prediction estimate
\begin{align*}
\frac{1}{n}|X\Delta|^2
\le
3\lambda\|\Delta_S\|_1.
\end{align*}
[/guided]
[/step]
[step:Place the error vector in the compatibility cone]
From the inequality just obtained,
\begin{align*}
0
\le
\frac{1}{n}|X\Delta|^2
\le
3\lambda\|\Delta_S\|_1-\lambda\|\Delta_{S^c}\|_1.
\end{align*}
Since $\lambda>0$ by the Lasso tuning-parameter hypothesis, this implies
\begin{align*}
\|\Delta_{S^c}\|_1 \le 3\|\Delta_S\|_1.
\end{align*}
Thus $\Delta$ belongs to the cone on which the [compatibility constant](/page/Compatibility%20Condition) $\phi_0(S,3)$ is defined, unless $\|\Delta_S\|_1=0$. If $\|\Delta_S\|_1=0$, then the displayed inequality above gives $\|\Delta_{S^c}\|_1=0$, hence $\Delta=0$, and therefore $|X(\hat{\beta}-\beta^*)|=0$. This proves the asserted $s=0$ case and also handles the degenerate case $s\ge 1$ with $\|\Delta_S\|_1=0$. We may therefore assume $s\ge 1$ and $\|\Delta_S\|_1>0$.
[/step]
[step:Apply compatibility to convert the active $\ell^1$ error into prediction error]
Since $\Delta \in \mathbb{R}^p$ satisfies
\begin{align*}
\|\Delta_{S^c}\|_1 \le 3\|\Delta_S\|_1
\qquad\text{and}\qquad
\|\Delta_S\|_1>0,
\end{align*}
the definition of $\phi_0(S,3)$ gives
\begin{align*}
\phi_0(S,3)^2
\le
\frac{s\,|X\Delta|^2}{n\|\Delta_S\|_1^2}.
\end{align*}
Equivalently,
\begin{align*}
\|\Delta_S\|_1
\le
\frac{\sqrt{s}\,|X\Delta|}{\sqrt{n}\,\phi_0(S,3)}.
\end{align*}
Combining this with the prediction estimate from the previous step gives
\begin{align*}
\frac{1}{n}|X\Delta|^2
\le
3\lambda
\frac{\sqrt{s}\,|X\Delta|}{\sqrt{n}\,\phi_0(S,3)}.
\end{align*}
[guided]
The compatibility condition is designed precisely to convert a sparse $\ell^1$ quantity into a prediction norm quantity. We have already proved that $\Delta$ lies in the cone
\begin{align*}
\|\Delta_{S^c}\|_1 \le 3\|\Delta_S\|_1,
\end{align*}
and in this step we are in the non-degenerate case $s \ge 1$ and $\|\Delta_S\|_1>0$. Therefore the defining inequality for the [compatibility constant](/page/Compatibility%20Condition) $\phi_0(S,3)$ applies to the vector $\Delta \in \mathbb{R}^p$ and gives
\begin{align*}
\phi_0(S,3)^2
\le
\frac{s\,|X\Delta|^2}{n\|\Delta_S\|_1^2}.
\end{align*}
Multiplying by $\|\Delta_S\|_1^2$ and then taking square roots is valid because all quantities are non-negative and $\phi_0(S,3)>0$ by hypothesis. Hence
\begin{align*}
\|\Delta_S\|_1
\le
\frac{\sqrt{s}\,|X\Delta|}{\sqrt{n}\,\phi_0(S,3)}.
\end{align*}
The previous prediction estimate was
\begin{align*}
\frac{1}{n}|X\Delta|^2
\le
3\lambda\|\Delta_S\|_1.
\end{align*}
Substituting the compatibility bound for $\|\Delta_S\|_1$ into this estimate yields
\begin{align*}
\frac{1}{n}|X\Delta|^2
\le
3\lambda
\frac{\sqrt{s}\,|X\Delta|}{\sqrt{n}\,\phi_0(S,3)}.
\end{align*}
This is the key fast-rate inequality: the prediction loss now appears on both sides, so the final step is only algebra.
[/guided]
[/step]
[step:Divide by the prediction norm and square the resulting bound]
If $|X\Delta|=0$, then
\begin{align*}
\frac{1}{n}|X\Delta|^2=0
\le
\frac{9\lambda^2 s}{\phi_0(S,3)^2},
\end{align*}
so the result holds. Assume now that $|X\Delta|>0$. Dividing the inequality
\begin{align*}
\frac{1}{n}|X\Delta|^2
\le
3\lambda
\frac{\sqrt{s}\,|X\Delta|}{\sqrt{n}\,\phi_0(S,3)}
\end{align*}
by the positive quantity $|X\Delta|/\sqrt n$ gives
\begin{align*}
\frac{|X\Delta|}{\sqrt n}
\le
\frac{3\lambda\sqrt{s}}{\phi_0(S,3)}.
\end{align*}
Squaring both sides yields
\begin{align*}
\frac{1}{n}|X\Delta|^2
\le
\frac{9\lambda^2 s}{\phi_0(S,3)^2}.
\end{align*}
Since $\Delta=\hat{\beta}-\beta^*$, this is precisely
\begin{align*}
\frac{1}{n}|X(\hat{\beta}-\beta^*)|^2
\le
\frac{9\lambda^2 s}{\phi_0(S,3)^2}.
\end{align*}
[guided]
There are two cases. If $|X\Delta|=0$, then the prediction loss is already zero:
\begin{align*}
\frac{1}{n}|X\Delta|^2=0
\le
\frac{9\lambda^2 s}{\phi_0(S,3)^2},
\end{align*}
so the desired estimate holds.
Assume instead that $|X\Delta|>0$. From the compatibility step we have
\begin{align*}
\frac{1}{n}|X\Delta|^2
\le
3\lambda
\frac{\sqrt{s}\,|X\Delta|}{\sqrt{n}\,\phi_0(S,3)}.
\end{align*}
The factor $|X\Delta|/\sqrt n$ is positive in this case, so division by it preserves the inequality and gives
\begin{align*}
\frac{|X\Delta|}{\sqrt n}
\le
\frac{3\lambda\sqrt{s}}{\phi_0(S,3)}.
\end{align*}
Both sides are non-negative, so squaring preserves the inequality:
\begin{align*}
\frac{1}{n}|X\Delta|^2
\le
\frac{9\lambda^2 s}{\phi_0(S,3)^2}.
\end{align*}
Finally, substituting the definition $\Delta=\hat{\beta}-\beta^*$ gives
\begin{align*}
\frac{1}{n}|X(\hat{\beta}-\beta^*)|^2
\le
\frac{9\lambda^2 s}{\phi_0(S,3)^2}.
\end{align*}
This is exactly the theorem's claimed prediction bound.
[/guided]
[/step]
