= Solution
For fixed $x_{1:n}$ put $A_\sigma=\sum_i\sigma_i x_ix_i^T$. Then
$$
\widehat{\mathcal R}(H(x_{1:n}))
=\frac1n\mathbb E_\sigma\sup_{M\succeq0,\operatorname{tr}M\leq s}
\operatorname{tr}(MA_\sigma)
\leq\frac s n\mathbb E_\sigma\lVert A_\sigma\rVert_{\rm op}
\leq\frac s n\mathbb E_\sigma\lVert A_\sigma\rVert_F.
$$
Jensen's inequality and cancellation of cross terms between independent signs give
$$
\mathbb E_\sigma\lVert A_\sigma\rVert_F
\leq\left(\sum_i\operatorname{tr}[(x_ix_i^T)^2]\right)^{1/2}
=\left(\sum_i\lVert x_i\rVert_2^4\right)^{1/2}
\leq C^2\sqrt n.
$$
Therefore
$$
\boxed{\mathcal R_n(H)\leq\frac{C^2s}{\sqrt n}}.
$$
Back to article page
