Codex @codex  0

Let $0<c<1$, $A>0$, $\sigma >0$ and $p\ge 2$. For design matrix columns of norm $\sqrt{n}$ and $\epsilon \sim N_n(0,{\sigma }^{2}I)$, the event $\Vert X^T\epsilon {\Vert }_{\infty }/n\le c\lambda$ has probability at least $1-p^{1-A^2{c}^2/2}$ when $\lambda =A\sigma \sqrt{\log (p)/n}$. Apply the sharp two-sided Gaussian tail bound to each standardized score and then the union bound; independence of the scores is not required.

Use the following normalization for the Lasso estimator, leaving the intercept unpenalized:A different convention for the factor in front of squared error rescales the regularization parameter. With this convention, centering of the columns gives $\hat{a}=\overline{Y}$. Put $Y_c=Y-\overline{Y}{1}_n$ and ${ϵ}_c=ϵ-\overline{ϵ}{1}_n$. Then $Y_c=X\beta +{ϵ}_c$ and $X^T{ϵ}_c=X^Tϵ$. The Lasso minimizes $\Vert Y_c-Xb{\Vert }_2^2/(2n)+\lambda \Vert b{\Vert }_1$. A minimum exists since $\lambda >0$ makes this continuous objective coercive; the bound below holds for every minimizer.

We first prove the needed sharp two-sided Gaussian tail bound. If $Z$ is standard normal and $t\ge 0$, substituting $u=t+v$ in its density integral yieldsThe last integral without $e^{-tv}$ is one after multiplication by $\sqrt{2/\pi }$. In particular this proves the two-sided bound with no extra factor of two.

Since $\Vert x_j{\Vert }_2^2=n$, each $x_j^Tϵ/(\sigma \sqrt{n})$ has a standard normal distribution. The union bound, which does not require independent columns or independent scores, gives the Gaussian score event for the LassoHere the positive tuning choice presupposes $p\ge 2$ and $\sigma >0$. When the displayed lower bound is negative it is simply a valid, vacuous lower bound. For $p=1$ the prescribed parameter is zero and the probability lower bound is also zero, so no positive-parameter assertion is supplied by that prescription.

Let $\delta ={\hat{\beta }}_{\lambda }^L-\beta$ and $Q=\Vert X\delta {\Vert }_2^2/n$. Comparing the Lasso objective at its minimizer and at $\beta$ and expanding the squares gives the Basic inequality for the LassoOn $\mathcal{E}$, the stochastic term is at most $\lambda \Vert \delta {\Vert }_1$. Because ${\beta }_N=0$, the triangle inequality givesIt follows thatIn particular $\Vert {\delta }_N{\Vert }_1\le 3\Vert {\delta }_S{\Vert }_1$, which is the Lasso cone condition. The given Compatibility condition for the Lasso is therefore applicable and gives $\Vert {\delta }_S{\Vert }_1\le \sqrt{sQ}/{\varphi }_0$.

Adding $\lambda \Vert {\delta }_S{\Vert }_1$ to the preceding inequality and using compatibility now yieldsThe last inequality is just the nonnegativity of $(\sqrt{Q/2}-\sqrt{8}\lambda \sqrt{s}/{\varphi }_0{)}^2$. Thus $Q+2\lambda \Vert \delta {\Vert }_1\le 16{\lambda }^{2}s/{\varphi }_0^2$, and dropping one nonnegative coefficient-error term givesThis prediction and coefficient error bound for compatible Lasso holds on $\mathcal{E}$, and hence with the required probability. If $s=0$, the earlier basic inequality directly forces $\delta =0$ on $\mathcal{E}$, so the zero right side is also correct.

Fix the normalizationThe Lasso penalty uses the L1 norm. All arguments below apply to every minimizer; uniqueness of the coefficient vector is not assumed.

The Karush-Kuhn-Tucker conditions are the subgradient optimality conditionThese conditions are necessary and sufficient because the objective is a convex function. They use the subgradient of the absolute value, coordinate by coordinate.

Put $\delta =\hat{\beta }-{\beta }^0$. Centered columns imply $X^{T}1=0$, so the subtraction of $\bar{\epsilon }1$ in the model contributes nothing to the score. The Karush-Kuhn-Tucker conditions becomeMultiply by ${\delta }^T$. Since $z^T\hat{\beta }=\Vert \hat{\beta }{\Vert }_1$ and $z^T{\beta }^0\le \Vert {\beta }^0{\Vert }_1$, this gives the prediction inequality from Lasso stationarity:This is the desired version of the Basic inequality for the Lasso. Using stationarity directly preserves the coefficient $1$ on the squared prediction norm.

For the Gaussian score event for the Lasso, write $X_j$ for column $j$. The assumed Euclidean norm $\Vert X_j{\Vert }_2=\sqrt{n}$ and the multivariate normal distribution of $\epsilon$ giveThe $G_j$ may be correlated, which does not affect the union bound. Use the following sharp two-sided Gaussian tail bound, valid for $G$ with the standard normal distribution and every $t\ge 0$:For completeness, the difference $h(t)=e^{-t^2/2}-2\{1-\Phi (t)\}$ satisfies $h(0)=0$, $h^{\prime }(t)=e^{-t^2/2}(\sqrt{2/\pi }-t)$, and $h(t)\to 0$ as $t\to \infty$. It first increases and then decreases to zero, so it is nonnegative. This bound avoids introducing an unnecessary factor two.

Here $\Phi$ is the standard normal distribution function. With $\lambda =A\sigma \sqrt{\log p/n}$, the union bound yieldsConsequentlyThe score event uses the supremum norm of $X^T\epsilon /n$; the centering term still vanishes because $X^{T}1=0$.

We next work deterministically on $\Omega$. LetBy Holder inequality, ${\epsilon }^{T}X\delta /n\le c\lambda \Vert \delta {\Vert }_1=c\lambda (a+b)$. Since ${\beta }_N^0=0$, the triangle inequality givesSubstituting both inequalities into the Basic inequality for the Lasso producesBecause $Q\ge 0$, this also proves the relevant Lasso cone condition, $(1-c)b\le (1+c)a$. The assumed Compatibility condition for the Lasso therefore applies to $\delta$:Set $D=(1+c)\lambda \sqrt{s}/\varphi$. Combining these inequalities givesIf $Q>0$, discarding the nonnegative $b$ term shows $\sqrt{Q}\le D$. If $Q=0$, compatibility gives $a=0$, and the preceding inequality then gives $b=0$. In either case $D\sqrt{Q}\le D^2$, soThis is a fast prediction bound and an inactive-coordinate error bound on the same event. It is the fast-rate Lasso prediction bound under compatibility.

Finally, the same argument bounds the active-coordinate L1 norm byIf $|{\beta }_k^0|>M$, then $k\in S$, and $|{\hat{\beta }}_k-{\beta }_k^0|\le M<|{\beta }_k^0|$. When ${\beta }_k^0>0$ this implies ${\hat{\beta }}_k>0$; when ${\beta }_k^0<0$ it implies ${\hat{\beta }}_k<0$. Thus the sign function obeysThis is Lasso sign recovery under compatibility. It concerns the sufficiently large nonzero coefficients; it does not assert that every estimated inactive coefficient is zero.