if H is Pac learnable according to

Definition 3.1 (PAC Learnability) A hypothesis class H is PAC learnable if there exist a function $m_H\colon(0,1)^2 \mapsto N$ and a learning algorithm with the following property: For every $\varepsilon, \delta \in (0,1)$, for every distribution $D$ over $X$, and for every labeling function $f \colon X \mapsto \{0,1\}$, if the realizability assumption holds with respect to $H,D,f$, then when running the learning algorithm on $m \geq m_H(\varepsilon, \delta)$ i.i.d. samples generated by $D$ and labeled by $f$, the algorithm returns a hypothesis $h$ such that, with probability of at least $1 - \delta$ (over the choice of the examples), $$L_{(D,f)}(h) \leq \varepsilon.$$

and the algorithm returns h* (for specific S of size $m_H(\varepsilon, \delta$) and distribution D) , I can define a distribution D' that gives 0 for each x s.t. h*(x)=f(x) and that will give me $L_{D'}(h*)=1$. I am trying to understand why this is ok (not a contradiction for H being PAC), so I have 2 questions on this: $$$$ 1. my guess is that since the algorithm does not depend on the distribution but does on S (that depends on it), we will probably get with the new distribution D' a different S that will return a different h that keeps us with $L_{(D',f)}(h) \leq \varepsilon.$ with probability $1 - \delta$. Is this the right explanation? $$$$ 2. After defining the new distribution D' is it right to say that (D',f,H) still hold the realizability assumption? I don't see why not but want to be sure.

definition 2.1 (The Realizability Assumption) There exists $h* \in H$ s.t. $L_{(D,f)}(h*) = 0.$. Note that this assumption implies that with probability 1 over random samples, S, where the instances of S are sampled according to D and are labeled by f, we have $L_S(h*) = 0$.

Thank you

  • 1
    $\begingroup$ The usual rule is one question per post. $\endgroup$ Jun 7, 2017 at 19:46
  • $\begingroup$ @YuvalFilmus but it is on the same example, should i copy paste it? $\endgroup$
    – Ayelet
    Jun 7, 2017 at 20:05
  • $\begingroup$ You can wait for the answers. If they answer both questions, then it's ok. $\endgroup$ Jun 7, 2017 at 20:18

1 Answer 1


I think the definitions in that book are unclear. If you note, the realisability assumption is not stated as an assumption on anything, nor as a standalone definition, so that already is a bit confusing. I have struggled to find one anywhere that is clear actually.

It appears to me that The Realisability Assumption is also dependent on the distribution $D$ and the labelling function $f$. That is the trio ($H, D, f$) can be realisable. $H$ in and of itself cannot be realisable.

It took me some sleuthing to come to this conclusion, and I hope it is the right one. I think you are nearly on the right lines of thinking. Here is my thinking:

As you say, if we choose a distribution that causes problems then perhaps we can prove that $L(h) = Err(h) > 0$. If you assume $H$ is finite, and $f$ is not in $H$, then we can find problematic points $x$s and put positive probabilities on them. Then for every $h$ in $H$, $L(h) > 0$; i.e. $H$ is not actually realisable with respect to any distribution.

We have made an assumption that $H$ is finite, but given that the book later on goes on demonstrate results with realisability, and finite $H$, I think we should assume that realisability and finite $H$ together are a valid consideration, and therefore, we cannot assume that realisability holds across any distribution over the domain set $X$. I think therefore we should assume that that is what they meant when defining realisability.

Similarly for the labelling function $f$. If $H$ and $D$ are realisable, independently of $f$, then in the case where $H$ is finite and contains only one hypothesis $h$, we can choose an $f$ that is different to h on the whole domain, which would result in $Err(h) = 1$.

So here's how I would state the Realisability Assumption:

Definition (The Realisability Assumption) Given a learning problem with distribution $D$ over the domain set, and labelling function $f$, then a set of hypotheses, $H$, is Realisable if there exists $h* \in H$ s.t. $L_{(D,f)}(h*) = 0$.

Note that you do not need to know what $D$ and $f$ are to assume that $H$ is realisable with respect to them. We can just assume that $H$ is realisable with respect to them, whatever they may be.

So, assuming realisability in PAC Learnability also restricts $D$ and $f$ to be those which are realisable w.r.t. $H$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.