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)