⧼exchistory⧽
6 exercise(s) shown, 0 hidden
BBy Bot
May 21'24

Show that the least-squares estimator $\thetals$ defined in equation satisfies the following exact oracle inequality:

[$] \E\MSE(\varphi_{\thetals})\le \inf_{\theta \in \R^M}\MSE(\varphi_\theta) +C\sigma^2 {\frac{M}{n}} [$]

for some constant $C$ to be specified.

BBy Bot
May 21'24

Assume that $\eps\sim \sg_n(\sigma^2)$ and the vectors $\varphi_j$ are normalized in such a way that $\max_j|\varphi_j|_2\le \sqrt{n}$. Show that there exists a choice of $\tau$ such that the Lasso estimator $\thetalasso$ with regularization parameter $2\tau$ satisfies the following exact oracle inequality:

[$] \MSE(\varphi_{\thetalasso})\le \inf_{\theta \in \R^M}\Big\{ \MSE(\varphi_\theta) +C\sigma|\theta|_1 \sqrt{\frac{\log M}{n}}\Big\} [$]

with probability at least $1-M^{-c}$ for some positive constants $C,c$.

BBy Bot
May 21'24

Let $\{\varphi_1, \dots, \varphi_M\}$ be a dictionary normalized in such a way that $\max_j|\varphi_j|_2\le D \sqrt{n}$. Show that for any integer $k$ such that $1\le k \le M$, we have

[$] \min_{\substack{\theta \in \R^M\\ |\theta|_0\le 2k}}\MSE(\varphi_\theta) \le \min_{\substack{\theta \in \R^M\\ |\theta|_{w\ell_q}\le 1}} \MSE(\varphi_\theta) + C_qD^2 \frac{\big(M^\frac{1}{\bar q}-k^\frac{1}{\bar q}\big)^2}{k}\,, [$]

where $|\theta|_{w\ell_q}$ denotes the weak $\ell_q$ norm and $\bar q$ is such that $\frac1q+\frac1{\bar q}=1$, for $q \gt 1$.

BBy Bot
May 21'24

Show that the trigonometric basis and the Haar system indeed form an orthonormal system of $L_2([0,1])$.

BBy Bot
May 21'24

Consider the $n \times d$ random matrix $\Phi=\{\varphi_j(X_i)\}_{\substack{1\le i \le n\\1\le j \le d}}$ where $X_1, \ldots, X_n$ are i.i.d uniform random variables on the interval $[0,1]$ and $\phi_j$ is the trigonometric basis as defined in Example. Show that $\Phi$ satisfies $\textsf{INC(k)}$ with probability at least $.9$ as long as $n \ge Ck^2 \log (d)$ for some large enough constant $C \gt 0$.

BBy Bot
May 21'24

If $f \in \Theta(\beta, Q)$ for $\beta \gt 1/2$ and $Q \gt 0$, then $f$ is continuous.