The second section of these notes points explains how one might PAC learn the concept class of intervals of all positive half-lines in $\mathbb{R}$. If we restricted our attention to $\mathbb{N}$ instead of $\mathbb{R}$, is this concept class still PAC learnable?
1 Answer
$\begingroup$
$\endgroup$
Yes, it's trivial. The learning algorithm consists of choosing the smallest positive example $x_0$, and taking the hypothesis to be $h(x)=1[x\ge x_0]$. All of the generalization guarantees proved for $\mathbb{R}$ hold here as well. In particular, it's a proper PAC learner for a VC-class of VC-dim 1. You can also use the specialized structure (of the class and algorithm) to shave off the superfluous $\log(n)$ factor you'd get from generic VC-based bounds.
