# Why non-uniform learnability does not imply PAC learnability?

PAC guarantees provide us a a learning algorithm $$A_n(\cdot)$$ and sample complexity bound $$n_{\mathcal{F}}(\epsilon,\sigma)$$ that ensures $$P\left[L_P(A(\mathcal{D}^n))-L_P(f^*)\leq \epsilon\right]\geq 1-\sigma$$ when $$n>n_{\mathcal{F}}(\epsilon,\sigma)$$.

On the other hand we say that the hypothesis class $$\mathcal{F}$$ is non-uniformly learnable if we can provide a sample complexity $$n_{\mathcal{F}}(\sigma,\epsilon,f)$$ and a learning algorithm $$A(\cdot)$$, such that $$P\left[L_P(A(\mathcal{D}^n))-L_P(f)\leq \epsilon\right]\geq 1-\sigma$$ when $$n>n_{\mathcal{F}}(\sigma,\epsilon,f)$$.

Non-uniform learnability is a relaxation of PAC learnability since $$P\left[L_P(A(\mathcal{D}^n))-L_P(f^*)\leq \epsilon\right]\geq 1-\sigma \implies P\left[L_P(A(\mathcal{D}^n))-L_P(f)\leq \epsilon\right]\geq 1-\sigma$$ but the contrary is not true, namely $$\mathcal{F}$$ may be non-uniform learnable but not PAC learnable. My question is, if we are given a non-uniformly learnable class $$\mathcal{F}$$ and we define $$n_{\mathcal{F}}(\sigma,\epsilon)=\sup_{f \in \mathcal{F}} n_{\mathcal{F}}(\sigma,\epsilon,f)$$, does it become PAC learnable? or the supremum over an uncountable set nullifies the implication? Making the complexity bound vacuous?

Thanks for any clarification

It states that the class $$\mathcal{H}$$ of all polynomial classifiers over $$\mathbb{R}$$ is not PAC learnable ($$\mathrm{VCdim}(\mathcal{H}) = \infty$$). We might rewrite $$\mathcal{H}$$ as $$\bigcup_{n \in \mathbb{N}} \mathcal{H}_n$$, where for every $$n \in \mathbb{N}$$, $$\mathcal{H}_n$$ is the class of all polynomial classifiers over $$\mathbb{R}$$ of degree $$n$$.
Each $$\mathcal{H}_n$$ is PAC learnable with $$\mathrm{VCdim}(\mathcal{H}_n) = n + 1$$, so using the fundamental theorem of statistical learning (quantified version), we know that the sample complexity of each $$h \in \mathcal{H}_n$$ is in $$\Theta\left(\frac{(d + 1) + \log(1 / \delta)}{\epsilon^2}\right)$$, so strictly increasing in $$d$$, but finite.
So for $$0< \epsilon, \delta < 1$$, the set $$\{ n_{\mathcal{H}}(\epsilon, \delta, h) \mid h \in \mathcal{H} \}$$ is not upper bounded. Yet, as a union of PAC learnable classes, $$\mathcal{H}$$ is nonuniform learnable.