# Problem 2 - Group A

#Hey I am Alex

## Question 1

- One intuition is that common asymptotic results rely on $D = \max ||x||_2$ to bound the excess risk. However $D$ grows with d

- Theorem 1 states that we can approximate $\hat{f}$ with a polynomial function of degree 2. This would suggest that if $f^*$ is a not a itself such a function then you will always carry a bias with you empirical optimum.

## Question 2

$$k\left(x, x^{\prime}\right)=\sum_{i=0}^{\infty} \frac{1}{i !}\left(x^{T} x^{\prime}\right)^{i}$$

$$ \mathcal{E}_{\mathbf{X}}:=\left\{\mathbf{X}\left|\max _{i, j}\right| x_{i}^{\top} x_{j}-\delta_{i, j} \mid \leq c n^{-1 / 2}(\log (n))^{(1+\epsilon) / 2}\right\} $$

2.) $$
\begin{align}
||M||_F & = \sqrt{\sum_{i \neq j} \sum_{k=0}^\infty \frac{1}{k !}\left(x_i^{T} x_j \right)^{k} } \leq \sqrt{\sum_{i \neq j} \sum_{k=0}^\infty \frac{1}{k !}\left( c n^{-1 / 2}(\log (n))^{(1+\epsilon) / 2}\right)^{k} } \\
& = n \sqrt{ \exp\left( c n^{-1 / 2}(\log (n))^{(1+\epsilon) / 2} \right) }
\end{align}
$$

$$\begin{align}
||M||_{op} \leq ||M||_F \rightarrow 0.
\end{align}$$

3.)

$$\left(\mathbf{X}^{T} \mathbf{X}\right)^{\circ 3} \rightarrow I_{d}$$

$$(K -I_n)^{\circ 3} = K^{\circ 3} -I_n^{\circ 3} = K^{\circ 3} -I_n $$
$$ || K - I_n ||_{op} = || M + D - I_n ||_{op} \leq ||M||_{op} + ||D - I_n||_{op} \rightarrow 0$$

## Scratchpad for collaboration

You can brainstorm ideas here and delete this section later (or keep it)