= Lasso support bound from sparse eigenvalues
{c}
{title2=$|\widehat S|\le64\kappa_p^2s/\phi^2$}
For $\lambda>0$ and $\phi>0$, use the <Lasso> objective $\|Y-X\beta\|_2^2/(2n)+\lambda\|\beta\|_1$. Suppose the noise score has maximum <norm> at most $\lambda/2$, the true support has size $s$, and $\|X(\widehat\beta-\beta^0)\|_2^2/n\le16\lambda^2s/\phi^2$. For any nonempty $B\subseteq\widehat S$, the <Karush-Kuhn-Tucker conditions> imply
$$
\lambda|B|/2\le n^{-1}\operatorname{sgn}(\widehat\beta_B)^TX_B^TX(\beta^0-\widehat\beta)\le4\lambda\kappa_{|B|}\sqrt{|B|s}/\phi.
$$
The upper bound is the <Cauchy-Schwarz inequality>. Hence $|B|\le64\kappa_{|B|}^2s/\phi^2$. A finite first index $m_*$ violating this inequality must exceed $|\widehat S|$. Its minimality also gives $|\widehat S|\le64\kappa_{m_*}^2s/\phi^2$. If no such index exists within $1,\ldots,p$, use the always defined bound $|\widehat S|\le64\kappa_p^2s/\phi^2$.
Back to article page
