= Solution
Use the empirical Rademacher convention
$$
\widehat{\mathcal R}(A)
=\frac1n\mathbb E_\sigma
\sup_{a\in A}\sum_{i=1}^n\sigma_i a_i.
$$
Because $H_3$ is symmetric under $h\mapsto-h$, optimizing a linear functional over the positive $\ell^1$ hull defining $\mathcal F$ gives
$$
\widehat{\mathcal R}(\mathcal F(x_{1:n}))
\leq\widehat{\mathcal R}(H_3(x_{1:n})).
$$
By part (c), $VC(H_3)\leq D=d(d+1)/2$. Sauer--Shelah therefore bounds the number $N$ of distinct label vectors on the sample by
$$
N\leq s(H_3,n)\leq(n+1)^D.
$$
Massart's finite-class lemma states that for $A\subseteq\{-1,1\}^n$,
$$
\widehat{\mathcal R}(A)
\leq\sqrt{\frac{2\log|A|}{n}}.
$$
Applying it to the distinct label vectors of $H_3$ gives
$$
\widehat{\mathcal R}(\mathcal F(x_{1:n}))
\leq\sqrt{\frac{2D\log(n+1)}n}
=\boxed{\sqrt{\frac{(d^2+d)\log(n+1)}n}}.
$$
Back to article page
