Question in Wainwright's paper about signed support recovery in lasso

Question

Sharp thresholds for high dimensional and noisy sparsity recovery using $l_1$ constrained quadratic programming (Lasso)

This paper is about support recovery guarantees of the Lasso.

I have an issue with Lemma 2b. Wainwright claims that if the primal-dual witness 1-4 conditions are met, we get correct signed support. What if one of the elements in $S$ has $\hat{\beta}$ value $0$ i.e. $\exists\, i\in S \,s.t.\, \hat{\beta}_i=0$, while $\beta^*_i>0$? Now $\hat{z}_i$ could still be 1 (because 1 lies in the subdifferential of the $l_1$ norm at 0), so $\hat{z}_i=\text{sign}(\hat{\beta}_i^*)=1$ and the primal dual witness conditions are all met, and yet $\text{ sign}(\hat{\beta}_i)=0\neq 1=\text{sign}(\beta_S^*)$, so we do not have signed support recovery.

Why can this not happen?

Answer 1

It seems you are right that there is a gap in the argument.

With this example: $n=p=2$, design $X=I_2$ (identity), support of $\beta^*$ and its complement $S=\{1 \}, S^c=\{2\}$, unknown $\beta^*= (2, 0)$, noise $w=(-1,0)$ and tuning parameter $\lambda_n=1/n$, the unique solution is $\hat\beta=(0,0)$ but the subgradient has $\hat z_1=1$ since $$ \partial \|\hat\beta\|_1 \ni \hat z = X^T(w + X\beta^* - X\hat\beta)/(n\lambda_n) = (1, 0). $$ This setup passes steps 1-4 of the primal dual witness method with strict dual feasibility in step 3, but the sign of $\hat\beta$ in the first coordinate is incorrect.