# Bound the VC dimension of a union of hypothesis classes with bounded VC dimension

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.

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.