<p>Suppose <span class="math-container">$\mathcal{F} \subset \{0, 1\}^\mathcal{X}$</span> be a class of functions and denote by <span class="math-container">$D_m(f) := \{(X_i, f(X_i))\}_{i=1}^m$</span> a dataset. Here, <span class="math-container">$X_i$</span> are iid samples from distribution <span class="math-container">$P$</span> on <span class="math-container">$\mathcal{X}$</span>.</p>
<p>We can define the optimal sample complexity, assuming realizability <span class="math-container">$f \in \mathcal{F}$</span> as follows:
<span class="math-container">$$
m_{P, \mathcal{F}}^{\rm opt}(\epsilon, \delta) = \min\{m \geq 1 : \exists \hat f~\text{s.t.}~\text{Pr}_{D_m(f)}[\text{err}_P(\hat f, f) &gt; \epsilon] \leq \delta~\text{for all}~f\in \mathcal{F}\}.
$$</span>
Above, <span class="math-container">$\text{err}_P(g, f) = P(g(X) \neq f(X))$</span>.</p>
<p>Thus, <span class="math-container">$m^{\rm opt}_{P, \mathcal{F}}(\epsilon, \delta)$</span> is the smallest number of samples for which there exists an algorithm under which I can <span class="math-container">$(\epsilon,\delta)$</span>-PAC-learn <span class="math-container">$f$</span> with access to samples <span class="math-container">$D_m(f)$</span>.</p>
<p>It is possible to show that ERM can <span class="math-container">$(\epsilon, \delta)$</span>-PAC learn with <span class="math-container">$m &gt; \frac{\log(|\mathcal{F}|/\delta)}{\epsilon}$</span> many samples.
Hence, <span class="math-container">$m^{\rm opt}_{P, \mathcal{F}}(\epsilon, \delta) \leq O(\tfrac{\log(|\mathcal{F}|/\delta)}{\epsilon})$</span>.</p>
<p><strong>Question:</strong>
Is there a reference showing this is sharp? In other words what is a reference that demonstrates that for every integer <span class="math-container">$M \geq 2$</span>, there exists an problem instance <span class="math-container">$(P, \mathcal{F})$</span> with <span class="math-container">$|\mathcal{F}| = M$</span> for which <span class="math-container">$m^{\rm opt}_{P, \mathcal{F}}(\epsilon, \delta) \geq \Omega(\tfrac{\log(|\mathcal{F}|/\delta)}{\epsilon})$</span>?</p>

CC BY-SA 4.0
2024-10-31T01:46:21.457Z
VC-dimension is a lower bound, so just take any class with VCdim equal to log size. One such class is the class of all functions on a finite set $\mathcal{X}$.
mathworker21
CC BY-SA 4.0
2024-10-31T01:51:02.887Z
Sure, even in that case, I am asking what reference actually proves this result?
Drew Brady
CC BY-SA 4.0
2024-10-31T01:51:36.560Z
If there are any pedagogical sources too, that would be great. Most places I looked either didn't have the result, or if they did, they only consider $\delta = O(1)$.
Drew Brady
CC BY-SA 4.0
2024-10-31T02:53:38.220Z
have u checked "understanding machine learning" and "foundations of machine learning"?
mathworker21
CC BY-SA 4.0
2024-10-31T16:32:02.037Z
See Chapter 5 of Neural Network Learning: Theoretical Foundations by Anthony and Bartlett.
Recursion
<reference-request><pac-learning>
Reference for lower bound for realizable PAC learning sample complexity?
Drew Brady
# Reference for lower bound for realizable PAC learning sample complexity?

(Asked by: username_0 on 2024-10-31)

Suppose $\mathcal{F} \subset \{0, 1\}^\mathcal{X}$ be a class of functions and denote by $D\_m(f) := \{(X\_i, f(X\_i))\}\_{i=1}^m$ a dataset. Here, $X\_i$ are iid samples from distribution $P$ on $\mathcal{X}$.

We can define the optimal sample complexity, assuming realizability $f \in \mathcal{F}$ as follows:
$$
m\_{P, \mathcal{F}}^{\rm opt}(\epsilon, \delta) = \min\{m \geq 1 : \exists \hat f~\text{s.t.}~\text{Pr}\_{D\_m(f)}[\text{err}\_P(\hat f, f) > \epsilon] \leq \delta~\text{for all}~f\in \mathcal{F}\}.
$$
Above, $\text{err}\_P(g, f) = P(g(X) \neq f(X))$.

Thus, $m^{\rm opt}\_{P, \mathcal{F}}(\epsilon, \delta)$ is the smallest number of samples for which there exists an algorithm under which I can $(\epsilon,\delta)$-PAC-learn $f$ with access to samples $D\_m(f)$.

It is possible to show that ERM can $(\epsilon, \delta)$-PAC learn with $m > \frac{\log(|\mathcal{F}|/\delta)}{\epsilon}$ many samples.
Hence, $m^{\rm opt}\_{P, \mathcal{F}}(\epsilon, \delta) \leq O(\tfrac{\log(|\mathcal{F}|/\delta)}{\epsilon})$.

**Question:**
Is there a reference showing this is sharp? In other words what is a reference that demonstrates that for every integer $M \geq 2$, there exists an problem instance $(P, \mathcal{F})$ with $|\mathcal{F}| = M$ for which $m^{\rm opt}\_{P, \mathcal{F}}(\epsilon, \delta) \geq \Omega(\tfrac{\log(|\mathcal{F}|/\delta)}{\epsilon})$?

**Tags:** reference-request, pac-learning

> **Comments:**
> **username_1**: VC-dimension is a lower bound, so just take any class with VCdim equal to log size. One such class is the class of all functions on a finite set $\mathcal{X}$.  
> **username_0**: Sure, even in that case, I am asking what reference actually proves this result?  
> **username_0**: If there are any pedagogical sources too, that would be great. Most places I looked either didn't have the result, or if they did, they only consider $\delta = O(1)$.  
> **username_1**: have u checked "understanding machine learning" and "foundations of machine learning"?  
> **username_2**: See Chapter 5 of Neural Network Learning: Theoretical Foundations by Anthony and Bartlett.  

---

## 0 answers

