Uniform convergence of union of hypothesis

Question

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?

Answer 1

Let's start with the definition.

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.