<p>Your questions (1) and (2) are related. First, let's talk about proper PAC learning. It is known that there are proper PAC learners that achieve zero sample error, and yet require $\Omega(\frac{d}{\epsilon}\log\frac1\epsilon)$ examples. For a simple proof of the $\epsilon$ dependence, consider the concept class of intervals $[a,b]\subseteq[0,1]$ under the uniform distribution. If we choose the <em>smallest</em> consistent interval, we indeed get a sample complexity of $O(1/\epsilon)$. Suppose, however, we choose the <em>largest</em> consistent interval, and the target concept is a point interval such as $[0,0]$. Then a simple coupon-collector argument shows that unless we receive roughly $\frac{1}{\epsilon}\log\frac1\epsilon$ examples, we'll get fooled by the spacing between the negative examples (the only kind we'll see) -- which has characteristic behavior of $1/$[sample size] under the uniform distribution. More general lower bounds of this type are given in </p>

<p>P. Auer, R. Ortner. A new PAC bound for intersection-closed concept classes. Machine Learning 66(2-3): 151-163 (2007)
<a href="http://personal.unileoben.ac.at/rortner/Pubs/PAC-intclosed.pdf" rel="nofollow noreferrer">http://personal.unileoben.ac.at/rortner/Pubs/PAC-intclosed.pdf</a></p>

<p>The thing about proper PAC is that for positive results in the abstract case, one cannot specify an algorithm beyond ERM, which says "find a concept consistent with the labeled sample". When you have additional structure, such as intervals, you can examine two different ERM algorithms, as above: a minimal vs. maximal consistent segment. And these have different sample complexities!</p>

<p>The power of improper PAC is that you get to design various voting schemes (Hanneke's is such a result) -- and this additional structure lets you prove improved rates. (The story is simpler for agnostic PAC, where ERM gives you the best possible worst-case rate, up to constants.)</p>

<p>Edit. It now occurs to me that the 1-inclusion graph prediction strategy of 
D. Haussler, N. Littlestone, M.d K. Warmuth.
Predicting {0,1}-Functions on Randomly Drawn Points. Inf. Comput. 115(2): 248-292 (1994)
might be a natural candidate for universal $O(d/\epsilon)$ proper PAC learner.</p>

CC BY-SA 3.0
2018-02-11T09:41:36.600Z
Thanks! Ok, so if i understand you correctly, the sample complexity of improper PAC learning is $\Theta(d/\epsilon)$ and for proper PAC learning it is $\Theta(d/\epsilon\log (1/\epsilon))$, the lower bound for the latter  being achieved for the example you give. Is that right?
Annonymous
CC BY-SA 3.0
2018-02-11T12:18:19.593Z
Yes, with the slight reservation that for improper PAC you need to use a specific algorithm (Hanneke's) -- not just any old ERM. Feel free to accept the answer :)
Aryeh
CC BY-SA 3.0
2018-02-12T22:33:10.680Z
I'm late to the party, but isn't the above-mentioned Proper-PAC lower bound a sample complexity lower bound for a specific learning algorithm (or restricted class thereof) only? I mean, without such restriction there is information-theoretically no separation between proper and improper PAC, right? (And thus no separation without computational assumptions, such as $NP\neq RP$ or similar)?)
Clement C.
CC BY-SA 3.0
2018-02-13T06:55:03.440Z
There is no separation in the sense that, computational considerations aside, a concept class is properly PAC learnable iff it’s improperly learning. Even the sample complexity is the same—up to log factors, which cannot be removed.
Aryeh
CC BY-SA 3.0
2018-02-13T14:54:45.413Z
That's my point: information-theoretically, I cannot see the reason for a difference even by a log factor. If you have a non-proper hypothesis eps-close to the true concept, then (information-theoretically) you can find (without any new sample) a proper hypothesis eps-close to what you have. This proper hypothesis you get is then 2eps-close to the true concept.
Clement C.
CC BY-SA 3.0
2018-02-13T15:36:43.270Z
So you’re saying that even for proper PAC, for each concept class, there exists a proper learner (not necessarily ERM) that achieves the optimal rate.  This is probably true (your argument plus Hanneke’s result) but not terribly useful since I don’t think we can say anything constructive about this learner.
Aryeh
CC BY-SA 3.0
2018-02-13T15:52:23.463Z
Oh, I agree. It's non constructive and most likely terribly inefficient (under standard computational assumptions). But there is no proof that a computationally efficient proper learning algorithm with same optimal  sample complexity cannot exist (even though it's widely believed).
Clement C.
CC BY-SA 3.0
2018-02-13T15:55:11.800Z
So, maybe I am not understanding something then. If @ClementC. s comment is true, then we should be able to show that the sample complexity of proper PAC learning is $\Theta(d/\epsilon)$ right, without the log-factor? Since, we don't care about efficiency, run Hanneke's algorithm and then find a 2eps-close proper hypothesis which is proper.
Annonymous
CC BY-SA 3.0
2018-02-13T16:02:08.407Z
@ClementC.  I think we may be confusing computational efficiency with *constructive description*. For example, 3-term DNF is not properly PAC learnable in polynomial time, unless NP=RP, but it is efficiently improperly learnable by 3-CNF.
Aryeh
CC BY-SA 3.0
2018-02-13T16:02:49.027Z
I don't understand what "computationally efficient proper learning algorithm with same optimal sample complexity cannot exist" means. For rectangles and intervals, we do have efficient propert algorithms with optimal sample complexity.
Aryeh
CC BY-SA 3.0
2018-02-13T16:05:44.293Z
The usual definition of PAC learnability asks for poly time algorithms. My points are that (i) relaxing that, proper and improper have same sample complexity; (ii) with this requirement, we cannot prove an unconditional separation between proper and improper (as it would essentially prove something like NP not equal to RP). (We can prove lower bounds on the sample complexity of *specific* proper learning algorithms, though, which as far as I understand is what Aryeh's reference does.)
Clement C.
CC BY-SA 3.0
2018-02-14T10:11:11.893Z
@ClementC. In one of your earlier comments, you mentioned after running an improper PAC algorithm, a learner obtains a possibly improper hypothesis and the learner can then find the closest proper hypothesis from the concept class (without any more samples). But how could the learner do this without knowing the distribution under which it is being given samples? Isn't the closest being measured according to an unknown distribution?
Annonymous
CC BY-SA 3.0
2018-02-14T21:10:03.290Z
@Annonymous You are right, I was very sloppy. The above only works if one knows the ambient distribution. Based on what I have searched since, without this (arguably unrealistic) assumption it is still open. Thank you!
Clement C.
CC BY-SA 3.0
2018-02-14T21:16:58.397Z
@ClementC. Thanks! I agree its still open, and its not totally clear to me if the paper Aryeh mentioned shows that $\log(1/\epsilon)$ is necessary, becaust it seems to look at specific proper learning algorithms like you mentioned.
Annonymous
CC BY-SA 3.0
2018-02-10T18:46:32.620Z
2018-02-14T21:58:49.560Z
2018-02-14T21:58:49.560Z
Aryeh
<p>To add to the currently accepted answer:</p>

<ol>
<li><p><strong>Yes.</strong> The $$O\left(\frac{d}{\varepsilon}\log\frac{1}{\varepsilon}\right)$$
sample complexity upper bound holds for proper PAC learning as well <em>(although it is important to note that it may not lead to a computationally efficient learning algorithm. Which is normal, since unless $\mathsf{NP}=\mathsf{RP}$ is it known that some classes are not efficiently proper PAC learnable. Cf. e.g. Theorem 1.3 in the Kearns—Vazirani book you mention).</em>
This is actually shown in the Kearns—Vazirani book (Theorem 3.3), since $L$ there is a consistent hypothesis finder with hypothesis class $\mathcal{H}=\mathcal{C}$. See also [1].</p></li>
<li><p><strong>Unknown.</strong> Hanneke's algorithm [2] is an improper learning algorithm. Whether this extra $\log(1/\varepsilon)$ factor in the sample complexity can be removed for proper PAC learning <em>(information theoretically, i.e. setting aside any computational efficiency requirement)</em>  is still an open question. Cf. the open questions at the end of [3]: </p>

<blockquote>
  <p>Classically, it is still an open question whether the $\log(1/\varepsilon)$-factor in the upper bound of [1]
  for $(\varepsilon, \delta)$-proper PAC learning is necessary.</p>
</blockquote>

<p>(Footnote 1 in the same paper is also relevant)</p></li>
</ol>

<hr>

<p>[1] A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth. <em>Learnability and the
Vapnik-Chervonenkis dimension.</em> Journal of the ACM, 36(4):929–965, 1989.</p>

<p>[2] S. Hanneke. <em>The optimal sample complexity of PAC learning.</em> J. Mach. Learn. Res. 17, 1, 1319-1333, 2016.</p>

<p>[3] S. Arunachalam and R. de Wolf. <em>Optimal quantum sample complexity of learning algorithms.</em> In Proceedings of the 32nd Computational Complexity Conference (CCC), 2017.</p>

CC BY-SA 3.0
2018-02-14T21:59:37.963Z
Is it conjectured that the 1-inclusion graph of Haussler et al. is such an optimal PAC learner?
Aryeh
CC BY-SA 3.0
2018-02-14T22:19:30.920Z
@Aryeh I am not sure. From what I could find, Warmuth conjectured so in 2004. I don't know more than that.
Clement C.
CC BY-SA 3.0
2018-02-14T21:30:38.583Z
2018-02-14T21:40:14.820Z
2018-02-14T21:40:14.820Z
Clement C.
<p>My thanks to <a href="https://cstheory.stackexchange.com/users/1746/aryeh">Aryeh</a> for bringing this question to my attention.</p>

<p>As others have mentioned, the answer to (1) is <strong>Yes</strong>, and the 
simple method of Empirical Risk Minimization in <span class="math-container">$\mathcal{C}$</span> achieves 
the <span class="math-container">$O((d/\varepsilon)\log(1/\varepsilon))$</span> sample complexity (see Vapnik and Chervonenkis, 1974; Blumer, Ehrenfeucht, Haussler, and Warmuth, 1989).</p>

<p>As for (2), it is in fact known that there exist spaces <span class="math-container">$\mathcal{C}$</span> 
where <strong>no</strong> proper learning algorithm achieves better than <span class="math-container">$\Omega((d/\varepsilon)\log(1/\varepsilon))$</span> sample complexity, and hence proper learning cannot achieve the optimal <span class="math-container">$O(d/\varepsilon)$</span> sample complexity. To my knowledge, this fact has never actually been published, but is rooted in a related argument of Daniely and Shalev-Shwartz (COLT 2014) (originally formulated for a different, but related, question in multiclass learning).</p>

<p>Consider the simple case <span class="math-container">$d=1$</span>, and put the space <span class="math-container">$\mathcal{X}$</span> as <span class="math-container">$\{1,2,...,1/\varepsilon\}$</span>, and <span class="math-container">$\mathcal{C}$</span> is singletons <span class="math-container">$f_z(x) := \mathbb{I}[x = z], z \in \mathcal{X}$</span>: that is, each classifier in <span class="math-container">$\mathcal{C}$</span> classifies exactly one point from <span class="math-container">$\mathcal{X}$</span> as <span class="math-container">$1$</span> and the others as <span class="math-container">$0$</span>. For the lower bound, take the target function as a random singleton <span class="math-container">$f_{x^*}$</span>, where <span class="math-container">$x^{*} \sim {\rm Uniform}(\mathcal{X})$</span>, and <span class="math-container">$P$</span>, the marginal distribution of <span class="math-container">$X$</span>, is uniform on <span class="math-container">$\mathcal{X}\setminus\{x^*\}$</span>.  Now the learner never sees any examples labeled <span class="math-container">$1$</span>, 
but it must choose a point <span class="math-container">$z$</span> to <strong>guess</strong> is labeled <span class="math-container">$1$</span> (importantly, the 
``all zero'' function is <strong>not</strong> in <span class="math-container">$\mathcal{C}$</span>, so any proper learner <strong>must</strong> guess some <span class="math-container">$z$</span>), and until it has seen every point in <span class="math-container">$\mathcal{X}\setminus\{x^*\}$</span> it has at least <span class="math-container">$1/2$</span> chance of guessing wrong (i.e., the posterior probability of its <span class="math-container">$f_z$</span> having <span class="math-container">$z \neq x^*$</span> is at least <span class="math-container">$1/2$</span>).  The coupon collector argument implies it would require <span class="math-container">$\Omega((1/\varepsilon)\log(1/\varepsilon))$</span> samples to see every point in <span class="math-container">$\mathcal{X} \setminus \{x^*\}$</span>. So this proves a lower bound of <span class="math-container">$\Omega((1/\varepsilon)\log(1/\varepsilon))$</span> for all proper learners.</p>

<p>For general <span class="math-container">$d&gt;1$</span>, we take <span class="math-container">$\mathcal{X}$</span> as <span class="math-container">$\{1,2,...,d/(4\varepsilon)\}$</span>, take <span class="math-container">$\mathcal{C}$</span> as classifiers <span class="math-container">$\mathbb{I}_{A}$</span> for sets <span class="math-container">$A \subset \mathcal{X}$</span> of size exactly <span class="math-container">$d$</span>, choose the target function at random from <span class="math-container">$\mathcal{C}$</span>, and take <span class="math-container">$P$</span> again as uniform on just the points the target function classifies <span class="math-container">$0$</span> (so the learner never sees a point labeled <span class="math-container">$1$</span>). Then a generalization of the coupon-collector argument implies we need <span class="math-container">$\Omega((d/\varepsilon)\log(1/\varepsilon))$</span> samples to see at least <span class="math-container">$|\mathcal{X}| - 2d$</span> distinct points from <span class="math-container">$\mathcal{X}$</span>, and without seeing this many distinct points any proper learner has at least <span class="math-container">$1/3$</span> chance of getting greater than <span class="math-container">$d/4$</span> of its guess <span class="math-container">$A$</span> of <span class="math-container">$d$</span> points wrong in its chosen hypothesis <span class="math-container">$h_{A}$</span>, meaning its error rate is greater than <span class="math-container">$\varepsilon$</span>.  So in this case, there is no proper learner with sample complexity smaller than <span class="math-container">$\Omega((d/\varepsilon)\log(1/\varepsilon))$</span>, which means no proper learner achieves the optimal sample complexity <span class="math-container">$O(d/\varepsilon)$</span>.</p>

<p>Note that the result is quite specific to the space <span class="math-container">$\mathcal{C}$</span> constructed. There do exist spaces <span class="math-container">$\mathcal{C}$</span> where proper learners can achieve the <span class="math-container">$O(d/\varepsilon)$</span> optimal sample complexity, and indeed even the exact full expression <span class="math-container">$O((d/\varepsilon)+(1/\varepsilon)\log(1/\delta))$</span> from (Hanneke, 2016a). Some upper and lower bounds for general ERM learners have been developed in (Hanneke, 2016b), quantified in terms of properties of the space <span class="math-container">$\mathcal{C}$</span>, as well as discussing some more specialized cases where specific proper learners can sometimes achieve the optimal sample complexity.</p>

<p>References: </p>

<p>Vapnik and Chervonenkis (1974). Theory of Pattern Recognition. Nauka, Moscow, 1974.</p>

<p><a href="https://doi.org/10.1145/76359.76371" rel="noreferrer">Blumer, Ehrenfeucht, Haussler, and Warmuth (1989). Learnability and the Vapnik-Chervonenkis dimension. Journal of the Association for Computing Machinery, 36(4):
929–965.</a></p>

<p><a href="http://proceedings.mlr.press/v35/daniely14b.html" rel="noreferrer">Daniely and Shalev-Shwartz (2014). Optimal Learners for Multiclass Problems. In Proceedings of the 27th Conference on Learning Theory.</a></p>

<p><a href="http://www.jmlr.org/papers/v17/15-389.html" rel="noreferrer">Hanneke (2016a). The Optimal Sample Complexity of PAC Learning. Journal of Machine Learning Research, Vol. 17 (38), pp. 1-15.</a></p>

<p><a href="http://www.jmlr.org/papers/v17/15-655.html" rel="noreferrer">Hanneke (2016b). Refined Error Bounds for Several Learning Algorithms. Journal of Machine Learning Research, Vol. 17 (135), pp. 1-55.</a></p>

CC BY-SA 4.0
2019-07-11T18:20:19.857Z
Interesting... Is there a combinatorial characterization of classes $\mathcal{C}$ for which proper PAC learning is sample-optimal? Or at least sufficient conditions (closure under intersection, union?)
Clement C.
CC BY-SA 4.0
2019-07-12T17:31:04.807Z
@ClementC. There is no known complete characterization of which classes have optimal rates achievable by proper learners in general.  The referenced paper "Refined error bounds..." gives a combinatorial characterization of which classes admit optimal rates for all ERM learners (Corollary 14).  The relevant quantity is the "star number": the largest number of points such that one can flip any single point's label without changing the others (Definition 9).  Intersection-closed classes have an optimal proper learner: the "closure" alg (Theorem 5 in the paper, and also proven by Darnstädt, 2015).
S. Hanneke
CC BY-SA 4.0
2019-07-12T17:33:58.833Z
Thank you! ${}{}$
Clement C.
CC BY-SA 4.0
2019-07-11T04:27:10.863Z
2019-07-11T04:27:10.863Z
S. Hanneke
<p>It is well known that for a concept class $\mathcal{C}$ with VC dimension $d$, it suffices to obtain $O\left(\frac{d}{\varepsilon}\log\frac{1}{\varepsilon}\right)$ labelled examples to PAC learn $\mathcal{C}$. It is not clear to me if the PAC learning algorithm (which uses these many samples) is proper or improper? In the textbooks of Kearns and Vazirani as well as Anthony and Biggs it seems like the PAC learning algorithm is improper (i.e., the output hypothesis does not lie in $\mathcal{C}$)</p>

<ol>
<li><p>Could someone clarify if a similar upper bound holds for the proper PAC learning setting as well?  If so, could you give me a reference where this is explicitly mentioned and also contains a self-contained proof?</p></li>
<li><p>Recently Hanneke improved this bound by getting rid of the $\log(1/\varepsilon)$ factor. Could someone clarify if the $\log(1/\varepsilon)$ is known to be removable for the Proper PAC learning setting? Or is it an open question still? </p></li>
</ol>

CC BY-SA 3.0
2018-02-13T17:05:34.660Z
Which is this Hanneke paper that you are referring to?
gradstudent
CC BY-SA 3.0
2018-02-13T17:53:35.020Z
@gradstudent https://arxiv.org/abs/1507.00473
Clement C.
<machine-learning><boolean-functions><lg.learning><vc-dimension><pac-learning>
Proper PAC learning VC dimension bounds
Annonymous
# Proper PAC learning VC dimension bounds

(Asked by: username_0 on 2018-02-10)

It is well known that for a concept class $\mathcal{C}$ with VC dimension $d$, it suffices to obtain $O\left(\frac{d}{\varepsilon}\log\frac{1}{\varepsilon}\right)$ labelled examples to PAC learn $\mathcal{C}$. It is not clear to me if the PAC learning algorithm (which uses these many samples) is proper or improper? In the textbooks of Kearns and Vazirani as well as Anthony and Biggs it seems like the PAC learning algorithm is improper (i.e., the output hypothesis does not lie in $\mathcal{C}$)

1. Could someone clarify if a similar upper bound holds for the proper PAC learning setting as well? If so, could you give me a reference where this is explicitly mentioned and also contains a self-contained proof?
2. Recently Hanneke improved this bound by getting rid of the $\log(1/\varepsilon)$ factor. Could someone clarify if the $\log(1/\varepsilon)$ is known to be removable for the Proper PAC learning setting? Or is it an open question still?

**Tags:** machine-learning, boolean-functions, lg.learning, vc-dimension, pac-learning

> **Comments:**
> **username_1**: Which is this Hanneke paper that you are referring to?  
> **username_2**: @username_1 https://arxiv.org/abs/1507.00473  

---

## 3 answers

### Answer by username_4 on 2019-07-11. Score: 11 | Accepted answer

My thanks to [username_3](https://cstheory.stackexchange.com/users/1746/aryeh) for bringing this question to my attention.

As others have mentioned, the answer to (1) is **Yes**, and the
simple method of Empirical Risk Minimization in $\mathcal{C}$ achieves
the $O((d/\varepsilon)\log(1/\varepsilon))$ sample complexity (see Vapnik and Chervonenkis, 1974; Blumer, Ehrenfeucht, Haussler, and Warmuth, 1989).

As for (2), it is in fact known that there exist spaces $\mathcal{C}$
where **no** proper learning algorithm achieves better than $\Omega((d/\varepsilon)\log(1/\varepsilon))$ sample complexity, and hence proper learning cannot achieve the optimal $O(d/\varepsilon)$ sample complexity. To my knowledge, this fact has never actually been published, but is rooted in a related argument of Daniely and Shalev-Shwartz (COLT 2014) (originally formulated for a different, but related, question in multiclass learning).

Consider the simple case $d=1$, and put the space $\mathcal{X}$ as $\{1,2,...,1/\varepsilon\}$, and $\mathcal{C}$ is singletons $f\_z(x) := \mathbb{I}[x = z], z \in \mathcal{X}$: that is, each classifier in $\mathcal{C}$ classifies exactly one point from $\mathcal{X}$ as $1$ and the others as $0$. For the lower bound, take the target function as a random singleton $f\_{x^\*}$, where $x^{\*} \sim {\rm Uniform}(\mathcal{X})$, and $P$, the marginal distribution of $X$, is uniform on $\mathcal{X}\setminus\{x^\*\}$. Now the learner never sees any examples labeled $1$,
but it must choose a point $z$ to **guess** is labeled $1$ (importantly, the
``all zero'' function is **not** in $\mathcal{C}$, so any proper learner **must** guess some $z$), and until it has seen every point in $\mathcal{X}\setminus\{x^\*\}$ it has at least $1/2$ chance of guessing wrong (i.e., the posterior probability of its $f\_z$ having $z \neq x^\*$ is at least $1/2$). The coupon collector argument implies it would require $\Omega((1/\varepsilon)\log(1/\varepsilon))$ samples to see every point in $\mathcal{X} \setminus \{x^\*\}$. So this proves a lower bound of $\Omega((1/\varepsilon)\log(1/\varepsilon))$ for all proper learners.

For general $d>1$, we take $\mathcal{X}$ as $\{1,2,...,d/(4\varepsilon)\}$, take $\mathcal{C}$ as classifiers $\mathbb{I}\_{A}$ for sets $A \subset \mathcal{X}$ of size exactly $d$, choose the target function at random from $\mathcal{C}$, and take $P$ again as uniform on just the points the target function classifies $0$ (so the learner never sees a point labeled $1$). Then a generalization of the coupon-collector argument implies we need $\Omega((d/\varepsilon)\log(1/\varepsilon))$ samples to see at least $|\mathcal{X}| - 2d$ distinct points from $\mathcal{X}$, and without seeing this many distinct points any proper learner has at least $1/3$ chance of getting greater than $d/4$ of its guess $A$ of $d$ points wrong in its chosen hypothesis $h\_{A}$, meaning its error rate is greater than $\varepsilon$. So in this case, there is no proper learner with sample complexity smaller than $\Omega((d/\varepsilon)\log(1/\varepsilon))$, which means no proper learner achieves the optimal sample complexity $O(d/\varepsilon)$.

Note that the result is quite specific to the space $\mathcal{C}$ constructed. There do exist spaces $\mathcal{C}$ where proper learners can achieve the $O(d/\varepsilon)$ optimal sample complexity, and indeed even the exact full expression $O((d/\varepsilon)+(1/\varepsilon)\log(1/\delta))$ from (Hanneke, 2016a). Some upper and lower bounds for general ERM learners have been developed in (Hanneke, 2016b), quantified in terms of properties of the space $\mathcal{C}$, as well as discussing some more specialized cases where specific proper learners can sometimes achieve the optimal sample complexity.

References:

Vapnik and Chervonenkis (1974). Theory of Pattern Recognition. Nauka, Moscow, 1974.

[Blumer, Ehrenfeucht, Haussler, and Warmuth (1989). Learnability and the Vapnik-Chervonenkis dimension. Journal of the Association for Computing Machinery, 36(4):
929–965.](https://doi.org/10.1145/76359.76371)

[Daniely and Shalev-Shwartz (2014). Optimal Learners for Multiclass Problems. In Proceedings of the 27th Conference on Learning Theory.](http://proceedings.mlr.press/v35/daniely14b.html)

[Hanneke (2016a). The Optimal Sample Complexity of PAC Learning. Journal of Machine Learning Research, Vol. 17 (38), pp. 1-15.](http://www.jmlr.org/papers/v17/15-389.html)

[Hanneke (2016b). Refined Error Bounds for Several Learning Algorithms. Journal of Machine Learning Research, Vol. 17 (135), pp. 1-55.](http://www.jmlr.org/papers/v17/15-655.html)

> **Comments:**
> **username_2**: Interesting... Is there a combinatorial characterization of classes $\mathcal{C}$ for which proper PAC learning is sample-optimal? Or at least sufficient conditions (closure under intersection, union?)  
> **username_4**: @ClementC. There is no known complete characterization of which classes have optimal rates achievable by proper learners in general.  The referenced paper "Refined error bounds..." gives a combinatorial characterization of which classes admit optimal rates for all ERM learners (Corollary 14).  The relevant quantity is the "star number": the largest number of points such that one can flip any single point's label without changing the others (Definition 9).  Intersection-closed classes have an optimal proper learner: the "closure" alg (Theorem 5 in the paper, and also proven by Darnstädt, 2015).  
> **username_2**: Thank you! ${}{}$  

---

### Answer by username_3 on 2018-02-10. Score: 6

Your questions (1) and (2) are related. First, let's talk about proper PAC learning. It is known that there are proper PAC learners that achieve zero sample error, and yet require $\Omega(\frac{d}{\epsilon}\log\frac1\epsilon)$ examples. For a simple proof of the $\epsilon$ dependence, consider the concept class of intervals $[a,b]\subseteq[0,1]$ under the uniform distribution. If we choose the *smallest* consistent interval, we indeed get a sample complexity of $O(1/\epsilon)$. Suppose, however, we choose the *largest* consistent interval, and the target concept is a point interval such as $[0,0]$. Then a simple coupon-collector argument shows that unless we receive roughly $\frac{1}{\epsilon}\log\frac1\epsilon$ examples, we'll get fooled by the spacing between the negative examples (the only kind we'll see) -- which has characteristic behavior of $1/$[sample size] under the uniform distribution. More general lower bounds of this type are given in

P. Auer, R. Ortner. A new PAC bound for intersection-closed concept classes. Machine Learning 66(2-3): 151-163 (2007)
<http://personal.unileoben.ac.at/rortner/Pubs/PAC-intclosed.pdf>

The thing about proper PAC is that for positive results in the abstract case, one cannot specify an algorithm beyond ERM, which says "find a concept consistent with the labeled sample". When you have additional structure, such as intervals, you can examine two different ERM algorithms, as above: a minimal vs. maximal consistent segment. And these have different sample complexities!

The power of improper PAC is that you get to design various voting schemes (Hanneke's is such a result) -- and this additional structure lets you prove improved rates. (The story is simpler for agnostic PAC, where ERM gives you the best possible worst-case rate, up to constants.)

Edit. It now occurs to me that the 1-inclusion graph prediction strategy of
D. Haussler, N. Littlestone, M.d K. Warmuth.
Predicting {0,1}-Functions on Randomly Drawn Points. Inf. Comput. 115(2): 248-292 (1994)
might be a natural candidate for universal $O(d/\epsilon)$ proper PAC learner.

> **Comments:**
> **username_0**: Thanks! Ok, so if i understand you correctly, the sample complexity of improper PAC learning is $\Theta(d/\epsilon)$ and for proper PAC learning it is $\Theta(d/\epsilon\log (1/\epsilon))$, the lower bound for the latter  being achieved for the example you give. Is that right?  
> **username_3**: Yes, with the slight reservation that for improper PAC you need to use a specific algorithm (Hanneke's) -- not just any old ERM. Feel free to accept the answer :)  
> **username_2**: I'm late to the party, but isn't the above-mentioned Proper-PAC lower bound a sample complexity lower bound for a specific learning algorithm (or restricted class thereof) only? I mean, without such restriction there is information-theoretically no separation between proper and improper PAC, right? (And thus no separation without computational assumptions, such as $NP\neq RP$ or similar)?)  
> **username_3**: There is no separation in the sense that, computational considerations aside, a concept class is properly PAC learnable iff it’s improperly learning. Even the sample complexity is the same—up to log factors, which cannot be removed.  
> **username_2**: That's my point: information-theoretically, I cannot see the reason for a difference even by a log factor. If you have a non-proper hypothesis eps-close to the true concept, then (information-theoretically) you can find (without any new sample) a proper hypothesis eps-close to what you have. This proper hypothesis you get is then 2eps-close to the true concept.  
> **username_3**: So you’re saying that even for proper PAC, for each concept class, there exists a proper learner (not necessarily ERM) that achieves the optimal rate.  This is probably true (your argument plus Hanneke’s result) but not terribly useful since I don’t think we can say anything constructive about this learner.  
> **username_2**: Oh, I agree. It's non constructive and most likely terribly inefficient (under standard computational assumptions). But there is no proof that a computationally efficient proper learning algorithm with same optimal  sample complexity cannot exist (even though it's widely believed).  
> **username_0**: So, maybe I am not understanding something then. If @ClementC. s comment is true, then we should be able to show that the sample complexity of proper PAC learning is $\Theta(d/\epsilon)$ right, without the log-factor? Since, we don't care about efficiency, run Hanneke's algorithm and then find a 2eps-close proper hypothesis which is proper.  
> **username_3**: @ClementC.  I think we may be confusing computational efficiency with *constructive description*. For example, 3-term DNF is not properly PAC learnable in polynomial time, unless NP=RP, but it is efficiently improperly learnable by 3-CNF.  
> **username_3**: I don't understand what "computationally efficient proper learning algorithm with same optimal sample complexity cannot exist" means. For rectangles and intervals, we do have efficient propert algorithms with optimal sample complexity.  
> **username_2**: The usual definition of PAC learnability asks for poly time algorithms. My points are that (i) relaxing that, proper and improper have same sample complexity; (ii) with this requirement, we cannot prove an unconditional separation between proper and improper (as it would essentially prove something like NP not equal to RP). (We can prove lower bounds on the sample complexity of *specific* proper learning algorithms, though, which as far as I understand is what username_3's reference does.)  
> **username_0**: @ClementC. In one of your earlier comments, you mentioned after running an improper PAC algorithm, a learner obtains a possibly improper hypothesis and the learner can then find the closest proper hypothesis from the concept class (without any more samples). But how could the learner do this without knowing the distribution under which it is being given samples? Isn't the closest being measured according to an unknown distribution?  
> **username_2**: @username_0 You are right, I was very sloppy. The above only works if one knows the ambient distribution. Based on what I have searched since, without this (arguably unrealistic) assumption it is still open. Thank you!  
> **username_0**: @ClementC. Thanks! I agree its still open, and its not totally clear to me if the paper username_3 mentioned shows that $\log(1/\epsilon)$ is necessary, becaust it seems to look at specific proper learning algorithms like you mentioned.  

---

### Answer by username_2 on 2018-02-14. Score: 5

To add to the currently accepted answer:

1. **Yes.** The $$O\left(\frac{d}{\varepsilon}\log\frac{1}{\varepsilon}\right)$$
   sample complexity upper bound holds for proper PAC learning as well *(although it is important to note that it may not lead to a computationally efficient learning algorithm. Which is normal, since unless $\mathsf{NP}=\mathsf{RP}$ is it known that some classes are not efficiently proper PAC learnable. Cf. e.g. Theorem 1.3 in the Kearns—Vazirani book you mention).*
   This is actually shown in the Kearns—Vazirani book (Theorem 3.3), since $L$ there is a consistent hypothesis finder with hypothesis class $\mathcal{H}=\mathcal{C}$. See also [1].
2. **Unknown.** Hanneke's algorithm [2] is an improper learning algorithm. Whether this extra $\log(1/\varepsilon)$ factor in the sample complexity can be removed for proper PAC learning *(information theoretically, i.e. setting aside any computational efficiency requirement)* is still an open question. Cf. the open questions at the end of [3]:

   > Classically, it is still an open question whether the $\log(1/\varepsilon)$-factor in the upper bound of [1]
   > for $(\varepsilon, \delta)$-proper PAC learning is necessary.

   (Footnote 1 in the same paper is also relevant)

---

[1] A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth. *Learnability and the
Vapnik-Chervonenkis dimension.* Journal of the ACM, 36(4):929–965, 1989.

[2] username_4. *The optimal sample complexity of PAC learning.* J. Mach. Learn. Res. 17, 1, 1319-1333, 2016.

[3] S. Arunachalam and R. de Wolf. *Optimal quantum sample complexity of learning algorithms.* In Proceedings of the 32nd Computational Complexity Conference (CCC), 2017.

> **Comments:**
> **username_3**: Is it conjectured that the 1-inclusion graph of Haussler et al. is such an optimal PAC learner?  
> **username_2**: @username_3 I am not sure. From what I could find, Warmuth conjectured so in 2004. I don't know more than that.  

---

