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


1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.