Consider the class of functions $\mathcal{F}$ of the form $f_\theta(x) = \langle x,\theta \rangle$ where $\theta \in \{\theta \in R^d : ||\theta||_1 \leq r\}$ and x has support $\{x \in R^d : ||x||_\infty \leq M\}$.
Give an upper bound for the Rademacher complexity:
$$R_n(\mathcal{F}) = \frac{1}{n} E \sup_{||\theta||_1 \leq r} \left|\sum_i^n \epsilon_i \langle x_i, \theta \rangle\right|$$
where $epsilon_i$ are symmetric iid bernoullis on {-1,1}.
My approach:
Since the $\ell_1$ and $\ell_\infty$ norms are dual norms we have the bound on the inner product $\langle x_i, \theta \rangle \leq ||x||_\infty||\theta||_1 \leq Mr$
And by Jensen's inequality:
$$E\left| \sum_i^n \epsilon_i \right| \leq \sqrt{E\left( \sum_i^n \epsilon_i \right)^2} = \sqrt{n}$$
Where the equality follows by independence.
So we have the final upper bound: $Mr/\sqrt{n}$ which is better than the solution found here: http://web.stanford.edu/class/stats300b/Exercises/Solutions/ex6-sol.pdf (problem 7.3b) which contains an additional $\sqrt{\log 2d}$ factor (by an argument around subgaussianity).
I could use some feedback on my derivation.
Best Answer
In the question above: $|\sum_i \epsilon_i \langle x_i, \theta\rangle| \leq ||\theta||_1 ||x||_\infty |\sum_i \epsilon_i|$ is not valid since $\epsilon_i$ and $\langle x_i, \theta\rangle$ could be negative for some $i$.