<p>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).</p>

<p>It states that the class <span class="math-container">$\mathcal{H}$</span> of all polynomial classifiers over <span class="math-container">$\mathbb{R}$</span> is not PAC learnable (<span class="math-container">$\mathrm{VCdim}(\mathcal{H}) = \infty$</span>). We might rewrite <span class="math-container">$\mathcal{H}$</span> as <span class="math-container">$\bigcup_{n \in \mathbb{N}} \mathcal{H}_n$</span>, where for every <span class="math-container">$n \in \mathbb{N}$</span>, <span class="math-container">$\mathcal{H}_n$</span> is the class of all polynomial classifiers over <span class="math-container">$\mathbb{R}$</span> of degree <span class="math-container">$n$</span>.</p>

<p>Each <span class="math-container">$\mathcal{H}_n$</span> is PAC learnable with <span class="math-container">$\mathrm{VCdim}(\mathcal{H}_n) = n + 1$</span>, so using the fundamental theorem of statistical learning (quantified version), we know that the sample complexity of each <span class="math-container">$h \in \mathcal{H}_n$</span> is in <span class="math-container">$\Theta\left(\frac{(d + 1) + \log(1 / \delta)}{\epsilon^2}\right)$</span>, so strictly increasing in <span class="math-container">$d$</span>, but finite.</p>

<p>So for <span class="math-container">$0&lt; \epsilon, \delta &lt; 1$</span>, the set <span class="math-container">$\{ n_{\mathcal{H}}(\epsilon, \delta, h) \mid h \in \mathcal{H} \}$</span> is not upper bounded. Yet, as a union of PAC learnable classes, <span class="math-container">$\mathcal{H}$</span> is nonuniform learnable.</p>

CC BY-SA 4.0
2020-05-14T07:21:05.020Z
2020-05-14T07:21:05.020Z
user3389669
<p>PAC guarantees provide us a a learning algorithm <span class="math-container">$A_n(\cdot)$</span> and sample complexity bound <span class="math-container">$n_{\mathcal{F}}(\epsilon,\sigma)$</span> that ensures
<span class="math-container">$
P\left[L_P(A(\mathcal{D}^n))-L_P(f^*)\leq \epsilon\right]\geq 1-\sigma
$</span>
when <span class="math-container">$n&gt;n_{\mathcal{F}}(\epsilon,\sigma)$</span>.</p>

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

<p>Non-uniform learnability is a relaxation of PAC learnability since 
<span class="math-container">$
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
$</span>
but the contrary is not true, namely <span class="math-container">$\mathcal{F}$</span> may be non-uniform learnable but not PAC learnable. My question is, if we are given a non-uniformly learnable class <span class="math-container">$\mathcal{F}$</span> and we define <span class="math-container">$n_{\mathcal{F}}(\sigma,\epsilon)=\sup_{f \in \mathcal{F}} n_{\mathcal{F}}(\sigma,\epsilon,f)$</span>, does it become PAC learnable? or the supremum over an uncountable set nullifies the implication? Making the complexity bound vacuous?</p>

<p>Thanks for any clarification</p>

<machine-learning><st.statistics><pac-learning>
Why non-uniform learnability does not imply PAC learnability?
CrispyMcDiarmid
# Why non-uniform learnability does not imply PAC learnability?

(Asked by: username_0 on 2020-04-02)

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

**Tags:** machine-learning, st.statistics, pac-learning


---

## 1 answers

### Answer by username_1 on 2020-05-14. Score: 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.


---

