Skip to main content
2 of 2
Scope of the outer braces
LSpice
  • 12.9k
  • 4
  • 45
  • 69

The following VC dimension bound was established in this answer to VC dimension of a certain derived class of binary functions, $$ \operatorname{VCdim}(H) \le 2\cdot \operatorname{VCdim}(\operatorname{SG}(F)), $$ where $\operatorname{SG}(F) := \{\{x \in X \mid f(x) \le 0\} \mid f \in F\}$ 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{\operatorname{VCdim}(H)}{n}}. $$

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

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

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

dohmatob
  • 6.9k
  • 1
  • 18
  • 76