Problem 4 - Group B

# Problem 4 - Group B ## Presentation Write your presentation here if you like (you can also use your ipad if one of you has one) Dummy formula: $$R(f) - R(f^\star) \leq \mathcal{R}(\mathcal{H}) - \gamma$$ Dummy align environment \begin{align} R(f) - R(f^\star) &\leq \alpha \beta \\ &\leq c\tau \end{align} ``` Some code ``` ## Scratchpad for collaboration You can brainstorm ideas here and delete this section later (or keep it) ## Question 1 - Classical statistics - empirical distribution converges to true one - degeree of freedomm is fixed - more data helps - High dimensional - more data does not necessarily help - average distance between data points grows as $\mathcal{O}(\sqrt{d})$ - In modern image datasets, $n$ and $d$ roughly grow together, hence high-dimensional statistics provide better intuition - ex: MNIST -> CIFAR10 -> ImageNet - more features and also more data available - Thm 1 says that the learned function converges to a polynomial of deg. 2 - => everything which is not representable by a deg-2 poly. has some error - we can only interpolate what is interpolateable by a deg-2 poly. - We do not expect the bias to vanish as $d \to \infty$ since the problem also becomes harder - but shouldn't it actually become *easier* when we increase $d$ and get more degrees of freedom? ## Question 2 ### 1) - Trivial since $x_i^T x_i = 1$ ### 2) we use $k(x,x')=(x^Tx')^3$ Condition on $\mathcal{E}_\mathbf{X}$ (for some $\epsilon > 0$). $$ \begin{align} \|M\| &\leq \|M\|_{fro} \\ &= \sqrt{2\sum_{x\neq x'}k(x,x')^2} \\ &\leq n\sqrt{2}\max_{i\neq j} |x_i^Tx_j|^3\\ &\leq ncn^{\frac{-3}{2}}(\log{n})^\frac{3 (1+\epsilon)}{2} \\ &= c\frac{(\log{n})^\frac{3(1+\epsilon)}{2}}{\sqrt{n}}\to 0 \end{align} $$ for some $c > 0$.