Compatibility condition for the Lasso

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.

Let $\delta =\hat{\beta }-{\beta }^0$, $s=|S|>0$ and $\varphi >0$. On the score event $\Vert X^T\eta {\Vert }_{\infty }/n\le c\lambda$ with $0<c<1$, the prediction inequality from Lasso stationarity gives $Q+(1-c)\lambda \Vert {\delta }_{S^c}{\Vert }_1\le (1+c)\lambda \Vert {\delta }_S{\Vert }_1$. If the Compatibility condition for the Lasso with constant $\varphi$ holds on this cone, then $Q+(1-c)\lambda \Vert {\delta }_{S^c}{\Vert }_1\le (1+c{)}^2{\lambda }^{2}s/{\varphi }^2$. Here $Q=\Vert X\delta {\Vert }_2^2/n$ and $S$ is the true support of a vector.

With objective $\Vert Y-Xb{\Vert }_2^2/(2n)+\lambda \Vert b{\Vert }_1$, the Gaussian score event for the Lasso $\Vert X^Tϵ/n{\Vert }_{\infty }\le \lambda /2$ gives $Q+\lambda \Vert {\delta }_{S^c}{\Vert }_1\le 3\lambda \Vert {\delta }_S{\Vert }_1$, where $Q=\Vert X\delta {\Vert }_2^2/n$. The Lasso cone condition activates the Compatibility condition for the Lasso. Then $Q+\lambda \Vert \delta {\Vert }_1\le 4\lambda \sqrt{sQ}/{\varphi }_0\le Q/2+8{\lambda }^{2}s/{\varphi }_0^2$. Thus even $Q+2\lambda \Vert \delta {\Vert }_1\le 16{\lambda }^{2}s/{\varphi }_0^2$. This controls prediction and coefficient error together, including a design with correlated columns.

The fast-rate Lasso prediction bound under compatibility implies $\Vert {\hat{\beta }}_S-{\beta }_S^0{\Vert }_1\le (1+c)\lambda s/{\varphi }^2$. Each true coefficient larger in absolute value than this bound has the correct estimated sign. This conclusion alone does not ensure absence of false positives.

For a positive-semidefinite matrix $\Sigma$, an active set $S$ of size $s$, and cone factor three, one compatibility constant is defined byIt measures how strongly the quadratic form controls active-coordinate ${\ell }^1$ error on the Lasso cone condition.

If $\Vert \Theta -\Sigma {\Vert }_{\max }\le {\varphi }_{\Sigma }^2/(32s)$, then ${\varphi }_{\Theta }^2\ge {\varphi }_{\Sigma }^2/2$. Indeed, every normalized cone vector has $\Vert \delta {\Vert }_1\le 4$, so its quadratic form changes by at most $16\Vert \Theta -\Sigma {\Vert }_{\max }\le {\varphi }_{\Sigma }^2/(2s)$.

Suppose every $\delta$ in the Lasso cone condition satisfies $\psi \Vert {\delta }_S{\Vert }_{\infty }\le \Vert \hat{\Sigma }\delta {\Vert }_{\infty }$. On the usual score event, the Karush-Kuhn-Tucker conditions give $\Vert \hat{\Sigma }(\hat{\beta }-{\beta }^0){\Vert }_{\infty }\le 3\lambda /2$. Hence every active-coordinate error is at most $3\lambda /(2\psi )$, and a larger minimum nonzero signal guarantees coordinatewise sign recovery.