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

## 1 Answer

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.

1. Describe an algorithm that implements the ERM rule for learning $$\mathcal{H}_{Singleton}$$ in the realizable setup.
2. 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:
1. 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}$$.
2. 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:
1. $$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}$$.
2. $$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(\frac{1}{\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.