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.


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.