Skip to main content
1 of 2
dohmatob
  • 6.9k
  • 1
  • 18
  • 76

The following VC dimension bound was established in this MO post, $$ \mathrm{VCdim}(H) \le 2\cdot \mathrm{VCdim}(\mathrm{SG}(F)), $$ where $\mathrm{SG}(F) := \{\{x \in X \mid f(x) \le 0\}\}$ is the subgraph of $F$.

On the other, hand it's well-known that Rademacher complexity can be bounded via VC dimension like so. $$ \mathbb E\, R_n(H) \lesssim\sqrt{\dfrac{\mathrm{VCdim}(H)}{n}}. $$

We conclude that $$ \mathbb E\,R_n(H) \lesssim \sqrt{\frac{\mathrm{VCdim}(\mathrm{SG}(F))}{n}}. $$

In particular, because $\mathrm{VCdim}(\mathrm{SG}(F_{\mathrm{lin}})) = d$, we conclude that

$$ \mathbb E\,\widetilde R_n(F_{\mathrm{lin}}) \lesssim \sqrt{\frac{d}{n}}. $$

dohmatob
  • 6.9k
  • 1
  • 18
  • 76