# Proper PAC learning VC dimension bounds

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?

## 3 Answers

My thanks to 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.

Daniely and Shalev-Shwartz (2014). Optimal Learners for Multiclass Problems. In Proceedings of the 27th Conference on Learning Theory.

Hanneke (2016a). The Optimal Sample Complexity of PAC Learning. Journal of Machine Learning Research, Vol. 17 (38), pp. 1-15.

Hanneke (2016b). Refined Error Bounds for Several Learning Algorithms. Journal of Machine Learning Research, Vol. 17 (135), pp. 1-55.

• 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. Jul 11 '19 at 18:20
• @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 Jul 12 '19 at 17:31
• Thank you! ${}{}$ – Clement C. Jul 12 '19 at 17:33

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.

• 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 Feb 11 '18 at 9:41
• 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 Feb 11 '18 at 12:18
• 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. Feb 12 '18 at 22:33
• 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. Feb 13 '18 at 16:05
• @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 Feb 14 '18 at 10:11

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] S. Hanneke. 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.

• Is it conjectured that the 1-inclusion graph of Haussler et al. is such an optimal PAC learner? – Aryeh Feb 14 '18 at 21:59
• @Aryeh I am not sure. From what I could find, Warmuth conjectured so in 2004. I don't know more than that. – Clement C. Feb 14 '18 at 22:19