= Solution
With the convention matching the constants below, the <Lasso> estimator is any minimizer
$$
\widehat\beta\in\underset{\beta\in\mathbb R^p}{\operatorname{argmin}}
\left\{\frac1n\|Y-X\beta\|_2^2+2\lambda\|\beta\|_1\right\}.
$$
Because $X^T\mathbf1=0$, the centered noise has the same score as $\varepsilon$: $X^T(\varepsilon-\overline\varepsilon\mathbf1)=X^T\varepsilon$. Each $X_j^T\varepsilon/n$ is sub-Gaussian with scale $1/\sqrt n$, so
$$
\mathbb P\!\left(\frac{2|X_j^T\varepsilon|}{n}>\lambda\right)
\leq2e^{-n\lambda^2/8}.
$$
For $\lambda=A\sqrt{\log p/n}$, a <union bound> over the $p$ columns yields
$$
\mathbb P\!\left(\frac{2\|X^T\varepsilon\|_\infty}{n}\leq\lambda\right)
\geq1-2p^{-(A^2/8-1)}.
$$
Call this event $\mathcal T$.
The <Karush-Kuhn-Tucker conditions> for the Lasso say that there is $\widehat z\in\mathbb R^p$ such that
$$
\frac1nX^T(Y-X\widehat\beta)=\lambda\widehat z,
\qquad
\widehat z_j=
\begin{cases}
\operatorname{sgn}(\widehat\beta_j),&\widehat\beta_j\ne0,\\
[-1,1],&\widehat\beta_j=0.
\end{cases}
$$
Equivalently, $\widehat z$ belongs to the <subdifferential> of the $\ell^1$ norm at $\widehat\beta$.
Back to article page
