Basic inequality for the Lasso

Comparing the Lasso objective at an estimate $\hat{\beta }$ and a target ${\beta }^0$, then expanding the squared loss, bounds the prediction error by a noise-score term and the decrease in the ${\ell }^1$ penalty.

On an event where the noise-score infinity norm is at most half the penalty, the Lasso error $\delta$ obeys $\Vert {\delta }_{S^c}{\Vert }_1\le 3\Vert {\delta }_S{\Vert }_1$.

A design matrix satisfies a restricted eigenvalue condition with constant $\gamma >0$ on a cone $C$ when $\Vert X\delta {\Vert }_2^2/n\ge \gamma \Vert \delta {\Vert }_2^2$ for every nonzero $\delta \in C$.

A compatibility condition lower-bounds prediction norm by a scaled ${\ell }^1$ norm on a Lasso cone condition. One convention requires $|S|\Vert X\delta {\Vert }_2^2/n\ge {\varphi }^2\Vert {\delta }_S{\Vert }_1^2$ throughout the cone.