Define a set $C\_3(S):=\{\Delta\in R^d: \|\Delta\_{S^c}\|\_1\le 3\|\Delta\_S\|\_1\}$. Suppose we form a random design matrix $X\in R^{n\times d}$ with rows drawn iid from a $N(0,\Sigma)$ distribution and that for all $\Delta \in C\_3(S)$,
$$
\|\Sigma\Delta\|\_{\infty}\ge \gamma\|\Delta\|\_{\infty}
$$



Sparse linear regression model
The result is completely independent of the regression model ($y, w$ have no role and need not be involved). $\alpha$ in the definition of $C\_3(S)$ is not defined, I will assume it is $\alpha=3$.


For each $\Delta\in C\_3(S)$, there exists $k=1,...,p$ such that
$$|e\_k^TX^TX/n \Delta| - |e\_k^T\Sigma\Delta| + |e\_k^T\Sigma\Delta|
\ge \gamma |\Delta|\_\infty - |e\_k^T(X^TX/n-\Sigma)\Delta|.$$
Now, using $|u^Tv|\le \|u\|\_\infty\|v\|\_1$,
$$
|e\_k^T(X^TX/n-\Sigma)\Delta|
\le \max\_{j=1,...,p} |e\_k^T(X^TX/n -\Sigma)e\_j| \|\Delta\|\_1
\le \max\_{j=1,...,p} |e\_k^T(X^TX/n -\Sigma)e\_j| ~ 6 \|\Delta\_S\|\_1
$$
and $\|\Delta\_S\|\_1 \le s\|\Delta\|\_\infty$. By the Hanson-Wright inequality, for each $j,k$, assuming $\max\_{i}\Sigma\_{ii}\le 1$,
$$
P(|e\_k^T(X^TX/n -\Sigma)e\_j| > c(\sqrt{x/n} + {x/n})) ) < e^{-x}.
$$
By the union bound over all pairs $i,k$ and taking $x=\log(p^3)$, we obtain that
$$
\max\_{j=1,...,p} |e\_k^T(X^TX/n -\Sigma)e\_j| \le C \sqrt{\log (p)/n}
$$
with probability at least $1/p$. This provides the desired bound when
$s\sqrt{\log(p)/n}$ is smaller than a constant.


