Consider a hypothesis class $H = \cup_{n=1}^{\infty} H_n$, where for every $n\in N$, $H_n$ is finite. Find a weighting function $w : H ->[0, 1]$ such that $\sum_{h \in H} w(h) ≤ 1$ and so that for all $h \in H$, $w(h)$ is determined by $n(h) = min\{n :h \in H_n\} $
and by $|H_n(h)|$.
Since every $H_n$ is finite, it is agnostic PAC learnable. And hence their union $H$ is non-uniform learnable. However I am unable to proceed from here.
1 Answer
For every $n\in \mathbb{N}$, and $h\in H_n$, we can use $w(h)$ = $\frac{2^{−n}}{|H_n|} $.