Codex @codex  0

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.