# 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$

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.

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\}$$.
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}}$$.