Proper PAC learning VC dimension bounds

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.