1
$\begingroup$

Given $\{\mathcal{H_i}\}_1^r$ hypothesis classes, with VC dimension bounded from above by $D$ (for all classes). I want to show that the VC dimension of the union, denoted by $\mathcal{H}$ is bounded by $O(\max\{D, \log(r) + D\log(\log(r)/D)\}$.

So far I showed that the growth function $g(\mathcal{H},m)$ is bounded as follows: $g(\mathcal{H_1 \cup\mathcal{H}_2},m)\le g(\mathcal{H_1},m) + g(\mathcal{H_2},m)$ so $g(\mathcal{H},m)\le \sum_1^rg(\mathcal{H}_i,m)$. From Sauer-Shelah lemma $g(\mathcal{H}_i,m)\le\sum_0^D {m\choose i}$ for every $\mathcal{H}_i$. Thus $g(\mathcal{H},m) \le \sum_1^rg(\mathcal{H}_i,m) \le \sum_1^r \sum_0^D {m\choose i} = r\sum_0^D {m\choose i}$.

Now VCdim$(\mathcal{H}) \le log_2(r\sum_0^D {m\choose i})$ but I don't find a way how to continue from this point.

Remark, I am familiar with VCdim$(\mathcal{H}_1 \cup\mathcal{H}_2) \le$ VCdim$\mathcal{H}_1 + $ VCdim$\mathcal{H}_2 +1$ which also bound VCdim$\mathcal{H}$ from above, but I am trying to get to the described result.

$\endgroup$

1 Answer 1

1
$\begingroup$

Hej! I think a known upper bound for the problem is $\max\{4D\log_2(2D), 2\log_2(r)\}$, as given as an exercise 6.11 in "Understanding Machine Learning" from Shai Shalev-Shwartz and Shai Ben-David.

The clue is to form the upper bound by $m \le \log_2(r)+D\log_2(\frac{em}{D}) \le \log_2(r)+d\log_2(m)$ for $D\ge 3$. The goal is to find an upper bound for $m$ such that this holds. Therefor you look at the function $f(m) = D\log_2(m)-m$ and see, that this is monoton decreasing for $m \ge 2D$, hence we search for an upper bound of the zero of $f$, which is bigger than $2D$. It shows, that $m=2Dlog(2D)$ does the job. Building the maximum over the two terms in the sum provides the proof.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .