1
$\begingroup$

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?

$\endgroup$

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.