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}$)


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?
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?
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&gt;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.