# 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?

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

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