0
$\begingroup$

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?

$\endgroup$
4
  • 2
    $\begingroup$ What do you think? What have you tried, and where did you get stuck? $\endgroup$ Oct 28, 2021 at 11:57
  • $\begingroup$ 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. $\endgroup$
    – baxter8
    Oct 28, 2021 at 13:01
  • $\begingroup$ Have you tried writing out a formal proof? Where did you get stuck? $\endgroup$ Oct 28, 2021 at 18:03
  • 1
    $\begingroup$ Cross-posted: cs.stackexchange.com/q/145188/755, stats.stackexchange.com/q/550073/2921. Please do not post the same question on multiple sites. $\endgroup$
    – D.W.
    Nov 3, 2021 at 17:39

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.