Why non-uniform learnability does not imply PAC learnability?

Question

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

Answer 1

The following answer is based on chapter 6/7 of the book »Understanding Machine Learning: From Theory to Algorithms«, by Shalev-Shwartz and Ben-David (especially Example 7.1).

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.