The following I believe is a direct proof of this fact. If a learner is tasked to be $\epsilon$-competitive with a hypothesis $h \in \mathcal H_n$, where $\mathcal H_n$ is agnostic PAC learnable, it should be sufficient to just agnostic PAC learn on $\mathcal H$.

Suppose $\mathcal H = \bigcup_n \mathcal H_n$ where each $\mathcal H_n$ is PAC learnable.

Fix $\epsilon,\delta,h \in \mathcal H$ where $h \in \mathcal H_n$. (The textbook Understanding Machine Learning implicitly assumes it's efficiently computable to assign $h$ to a $\mathcal H_n$, which I'm fine with.) $\mathcal H_n$ has the uniform convergence property with bound $m_{\mathcal H_n}(\cdot,\cdot)$ by hypothesis. Let m = $m(\epsilon/2, \delta, h) = m_\mathcal {H_n}(\epsilon, \delta)$. Take $S \sim \mathcal D^m$ and run ERM over $\mathcal H_n$ to return an $\epsilon/2$-accurate, $\delta$-confident PAC hypothesis $h'$ in $\mathcal H_n$. In particular $|L_S(h') - L_{\mathcal D}(h')| < \epsilon/2$ and $|L_S(h) - L_{\mathcal D}(h)| < \epsilon /2 $ with probability $1-\delta$ by uniform convergence. $L_S(h') \leq L_S(h)$ by the definition of ERM. Putting this together with triangle inequality and we have $L_{\mathcal D}(h') \leq L_{\mathcal D}(h) + \epsilon$ with probability $1-\delta$ as desired.

I think this proof is correct. I'm working through Chapter 7 of Understanding Machine Learning which prefers using the SRM paradigm to prove this result. It seems like a direct proof is possible, and perhaps SRM is important but it's certainly not needed in this chapter to prove this theorem.

Is this correct?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.