Minimax estimation rate of sparse vector $w_\star$, w.r.t to mixed norm $\|\hat w_n-w_\star\| := \|\hat w_n - w_\star\|_2 + \|\hat w_n-w_\star\|_q$

Question

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 Theorem 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.

Answer 1

For any $c \ge 0$, define $\theta(s,c)$ by \begin{eqnarray} \theta(X,s,c) := \inf_{\delta \in \mathrm{CRE}(s,c)}\dfrac{\|X\delta\|_2}{\sqrt{n}\|\delta\|_2}, \end{eqnarray}

where $\mathrm{CRE}(s,c) := \{\delta \in \mathbb R^d \mid 0 < \|\delta\|_1 \le (1+c)\sqrt{s}\|\delta\|_2\}$.

Using corollary 4.3 of Bellec et al., one can easily establish that

Theorem. If $\overline \theta(X,1) \le 1$ and $\theta(X,s,7) > 0$, then the lower-bound obtained in the original question is tight: it is obtained by a Lasso estimator with the usual tuning $\lambda \asymp \sigma \sqrt{\dfrac{\log(2ed/s)}{n}}$.

This solves my problem completely.