# Uniform convergence of union of hypothesis

Let $$H_{1}$$ and $$H_{2}$$ are two hypothesis classes over some domain $$X$$1.

If both $$H_{1}$$ and $$H_{2}$$ have the uniform convergence property, then do $$H_{1}$$ U $$H_{2}$$ have uniform convergence?

• What do you think? What have you tried, and where did you get stuck? Oct 28, 2021 at 11:57
• I am thinking it in this manner. Since $H_{1}$ and $H_{2}$ have uniform convergence so each will have ε-representative and the union of such classes would also have these hypothesis that satisfy the ε-represetativeness so the union would also be uniformly converging. But I am unsure of this approach. Oct 28, 2021 at 13:01
• Have you tried writing out a formal proof? Where did you get stuck? Oct 28, 2021 at 18:03
• – D.W.
Nov 3, 2021 at 17:39

A hypothesis class $$\mathcal{H}$$ has uniform convergence if for every $$\epsilon,\delta>0$$ there exists $$m = m(\epsilon,\delta)$$ such that the following holds for all distributions $$\mathcal{D}$$ on tagged samples: If we sample at least $$m$$ elements according to $$\mathcal{D}$$, then with probability $$1-\delta$$, $$\sup_{h \in \mathcal{H}} |L_S(h) - L_{\mathcal{D}}(h)| \leq \epsilon,$$ where $$L_S(h)$$ is the empirical loss of $$h$$ on $$S$$, and $$L_{\mathcal{D}}(h)$$ is the population loss of $$h$$ with respect to $$\mathcal{D}$$.
Now suppose that $$\mathcal{H}_1$$ has uniform convergence with rate $$m_1(\epsilon,\delta)$$, and $$\mathcal{H}_2$$ has uniform convergence with rate $$m_2(\epsilon,\delta)$$. If we sample at least $$\max(m_1(\epsilon_1,\delta_1),m_2(\epsilon_2,\delta_2))$$ elements, then with probability $$1-\delta_1$$, $$\sup_{h \in \mathcal{H}_1} |L_S(h) - L_{\mathcal{D}}(h)| \leq \epsilon_1,$$ and with probability $$1-\delta_2$$, $$\sup_{h \in \mathcal{H}_2} |L_S(h) - L_{\mathcal{D}}(h)| \leq \epsilon_2.$$
Now it's your turn. Can you find $$\epsilon_1,\epsilon_2,\delta_1,\delta_2$$ such that the two statements above imply that the following holds with probability $$1-\delta$$? $$\sup_{h \in \mathcal{H}_1 \cup \mathcal{H}_2} |L_S(h) - L_{\mathcal{D}}(h)| \leq \epsilon.$$
Some authors want $$m$$ to be polynomial in $$1/\epsilon,1/\delta$$, that is, $$m(\epsilon,\delta) \leq C/(\epsilon\delta)^C$$ for some $$C>0$$. In this case you also need to show that for your choice of $$\epsilon_1,\epsilon_2,\delta_1,\delta_2$$, the value $$\max(m_1(\epsilon_1,\delta_1),m_2(\epsilon_2,\delta_2))$$ is polynomial in $$1/\epsilon,1/\delta$$ if $$m_1,m_2$$ have this property.