Let $n,d,s$ be positive integers with $s \le d$, and let $B_0(d,s)$ be the set of all (real) $d$-dimensional vectors with at most $s$ nonzero components. Given an $n \times d$ matrix $X$ with rows $x_1,\ldots,x_n$, a vector $w_\star \in \mathbb R^d$, and iid $\epsilon_1,\ldots,\epsilon_n \sim N(0,\sigma^2)$, form labels
$$ y_i := x_i^\top w + \epsilon,\text{ for }i=1,2,\ldots,n, $$
and consider a dataset $D_n := \{(x_1,y_1),\ldots,(x_n,y_n)\}$. Note that $D_n$ is random due to randomness in the $\epsilon_i$'s. The goal is to estimate $w_\star$ from the dataset $D_n$. Let $\hat A$ be any algorithm which consumes this dataset an outputs a possible random vector $\hat w_n := \hat A(D_n) \in \mathbb R^d$. Finally, let $\alpha \ge 0$ and $q \ge 1$, and define
$$ \Delta(n,d,s,q,\alpha,X) := \inf_{\hat A}\sup_{w_\star \in B_0(d,s)}\mathbb E\,\alpha \|\hat w_n - w_\star\|_2 + \|\hat w_n-w_\star\|_q. $$
Question. What is a good lower-bound for $\Delta(n,d,s,q,\alpha,X)$ ?
I'm particularly interested in the case $q=1$.
Very rough estimate
Define $\theta(X,s) \ge 0$ by
$$ \theta(X,s) := \sup_{\delta \in B_0(d,s),\,\delta \ne 0} \frac{\|X\delta\|_2}{\sqrt{n}\|\delta\|_2}. $$
It was shown in BellecTheorem 7.1, Bellec et al. 2018 that if $s \le d/2$, then
$$ \Delta(n,d,s,q,0,X) \gtrsim \frac{\psi(n,d,s,q)}{\theta(X,1)},\text{ with }\psi(n,d,s,q) := \sigma s^{1/q}\sqrt{\dfrac{\log(ed/s)}{n}}. $$ We deduce that
$$ \begin{split} \Delta(n,d,s,q,\alpha,X) &\ge \max(\alpha\Delta(n,d,s,2,0,X), \Delta(n,d,s,q,0,X))\\ & \gtrsim \frac{\max(\alpha\psi(n,d,s,2),\psi(n,d,s,q))}{\theta(X,1)}\\ &\asymp \frac{\sigma}{\theta(X,1)}\sqrt{\frac{\log(ed/s)}{n}}\cdot \begin{cases} \alpha \sqrt{s},&\mbox{ if }\alpha = \Omega(1),\\ s^{1/q},&\mbox{ else.} \end{cases} \end{split} $$
However, by construction, the dependence on $\alpha$ and $q$ in the above is likely to be very sub-optimal in general.