Proving $\mathcal{H}_{Singleton}$ is PAC-learnable I'm referring to Section 3.5, ex. 2 in Understanding machine learning.
To my understanding, given $\varepsilon, \delta$, I need to find minimum sample size $n$ s.t.
$$P[e_P(ERM(S_n) > \varepsilon] < \delta$$
Where $S_n$ is a sample of size $n$. and $ERM$ is an algorithm that given the sample return an hypothesis with minimum empirical error.
I tried to count the number of hypotheses that are "bad", in a way that their true error is more then $\varepsilon$, and to show that the the probability that the $ERM$ algorithm will choose one of those is less than $\delta$, but that wasn't successful.
I also tried doing the opposite - count all possible hypotheses that the $ERM$ algorithm can output and show that the probability that any of them has true error which is larger then $\varepsilon$ is less then $\delta$. That wasn't successful either.
Is there a way proving it without using VC-dimension-arguments?
 A: For completeness, the complete question is:

Let $X$ be a discrete domain, and let $\mathcal{H}_{Singleton} = \{h_z : z \in X\} \cup \{h_−\}$, where for each $z \in X$, $h_z$ is the function defined by $h_z(x) = 1$ iff $x = z$ and $0$ otherwise.
$h_−$ is simply the all-negative hypothesis, namely, for all $x \in X, h_−(x) = 0$.


The realizability assumption here implies that the true hypothesis $f$ labels
negatively all examples in the domain, perhaps except one.

*

*Describe an algorithm that implements the ERM rule for learning $\mathcal{H}_{Singleton}$
in the realizable setup.

*Show that $\mathcal{H}_{Singleton}$ is PAC learnable. Provide an upper bound on the
sample complexity.


I will first describe a learning algorithm for $\mathcal{H}_{Singleton}$, and then show that this learning algorithm outputs a hypothesis that satisfies the requirements of PAC learning.
Assume an arbitrary distribution $D$ over $X$.
Given the training set $S$ consisting of $m$ samples independently sampled from $D$ and labelled by the true hypothesis $f$, ie, $S = \{(x_1, f(x_1)) \ldots (x_m, f(x_m))\}$,
our learning algorithm is:

*

*Suppose $y_i = 1$ for some $(x_i, y_i) \in S$. Note that this can happen for exactly one $i$, if it does, because of the realizability condition. Then, output $h_{x_i}$.

*Otherwise, all $y_i = 0$. Then, output $h_-$.

Note that in both cases, if the output hypothesis is $h_S$, the loss over the training set for this hypothesis, $L_S(h_S)$, is $0$ always. Thus, this is an ERM rule, because $0$ is the lowest possible loss.
This concludes part 1. We will now analyse the error of this learning algorithm.
For $S = \{(x_1, f(x_1)) \ldots (x_m, f(x_m))\}$, define $S_x = \{ x_1, x_2, \ldots x_m \},$ the list of unlabelled samples obtained from $X$ through sampling from $D$ exactly $m$ times. Note that $S_x$ completely determines $S$.
We wish to bound the probability of a bad sample (parametrised by the accuracy $\epsilon$) by the confidence parameter $\delta$.
More precisely, given some $\epsilon, \delta$ in $(0, 1)$, we want to show that there is an $m$, such that when our learning algorithm is trained on $m$ samples, we have,
$$ P(\{S_x|L_{(D, f)}(h_S) > \epsilon\}) < \delta $$
Note that $m$ will be a function of $\epsilon$ and $\delta$. $P$ above is the probability measure given by the distribution $D^m$ over $X^m.$
The true error $L_{(D, f)}$ is defined as,
$$ L_{(D, f)}(h) = P(\{h(x) \neq f(x)\}) $$
Now, suppose the true hypothesis (or, the actual labelling function) $f$ is $h_-$. Then, our learning algorithm outputs $h_-$ as well. The true error of the error hypothesis will be $0$, and hence, will be greater than any $\epsilon > 0$ with probability $0$, which is less than $\delta$. In this case, our learning algorithm outputs a suitable hypothesis.
Otherwise, the true hypothesis $f$ is $h_{x_0}$ for some $x_0$ in $X$. Here, we have two cases:

*

*$x_0 \in S_x$  : Our learning algorithm will output $h_{x_0}$ here, and hence, will have zero true error as $f = h_{x_0}$.

*$x_0 \not\in S_x$ : This is the only case where we can have a non-zero true error, because our algorithm will output $h_-$. Thus,
$$ P(\{S_x|L_{(D, f)}(h_S) > \epsilon\}) \leq P(\{x_0 \not\in S_x\}) $$
Note that, as the samples in $S$ are identically and independently sampled from $D$, the probability that $x_0 \not \in S_x$ is the same as the probability that we never sample $x_0$ in $m$ independent trials from the distribution $D$, which is $(1 - P(\{x_0\}))^m$.
Note that, $f$ and $h_-$ differ only at one point, $x_0$. Thus,
$$ \epsilon < L_{(D, f)}(h_-) = P(\{h_-(x) \neq f(x)\}) = P(\{x_0\}) $$
It follows that, $$ P(\{x_0 \not\in S_x\}) = (1 -  P(\{x_0\}))^m < (1 - \epsilon)^m .$$
Thus, if we have, $(1 - \epsilon)^m \leq \delta$, we are done. This is equivalent to,
$$ m \geq \left\lceil{\frac{\ln(\delta)}{\ln(1 - \epsilon)}}\right\rceil $$
and, the righthand-side is an upper bound on the sample complexity of the hypothesis class $\mathcal{H}_{Singleton}$ by definition of the sample complexity.
This shows that the output hypothesis satisfies the PAC learning requirements, given a sufficiently large but finite $m$. Thus, $\mathcal{H}_{Singleton}$ is PAC-learnable.

A: Yes that's right. The singleton class is precisely PAC-learnable and it can be proven by showing that it so happens that this class of classifiers under its discrete domain will satisfy the PAC-learning requirements, i.e. finding $\epsilon$ and $\delta$. But would it be true to say that this class of classifiers is also PAC-learnable under a continuous domain (eg. real numbers)?
