Let $\mathcal{X}$ and $\mathcal{Y}$ denote the domain set and label set respectively. Also let $\mathcal{D}$ be a distribution over $\mathcal{X}$ and $f:\mathcal{X} \to \mathcal{Y}$ be the true labeling function. So for generating the data, we first sample from $\mathcal{D}$ and then apply function $f$. We define the error of a prediction rule $h:\mathcal{X} \to \mathcal{Y}$ to be, $$L_{\mathcal{D} , f}(h) = \mathcal{D}(\{x:h(x) \not = f(x) \}).$$Suppose that the realizability assumption for hypothesis class $\mathcal{H}$ holds which means that there exists $h^* \in \mathcal{H}$ such that $L_{\mathcal{D} , f}(h^*) = 0$. We collect $m$ samples $S=\{(x_1,y_1),(x_2,y_2),\dots , (x_m,y_m) \}$ and compute the error of $h^*$ on $S$: $$L_S(h^*) = \frac{|i\in [m]: h^*(x_i) \not = y_i|}{m}$$ Now we have:$$\mathbb{P}[L_S(h^*) = 0] = \mathcal{D}^m(\{(x_1,x_2,\dots, x_m):h^*(x_1) = f(x_1) \ \text{and} \ h^*(x_2) = f(x_2) \ \text{and} \dots h^*(x_m) = f(x_m)\})$$ If the samples are independent then, $$\mathbb{P}[L_S(h^*) = 0] = \mathcal{D}(\{x_1: h^*(x_1) = f(x_1)\})\mathcal{D}(\{x_2: h^*(x_2) = f(x_2)\}) \dots \mathcal{D}(\{x_m: h^*(x_m) = f(x_m)\}) = 1.$$ What about the case in which samples are dependent? How can it be proved that $\mathbb{P}[L_S(h^*) = 0] = 1$?


2 Answers 2


In general you just can write \begin{eqnarray*} \mathbb{P}[L_S(h^*) = 0] &=& \mathcal{D}(\{x_1: h^*(x_1) = f(x_1)\})\\ && \mathcal{D}(\{x_2: h^*(x_2) = f(x_2)\}|h^*(x_1) = f(x_1))\\ && \mathcal{D}(\{x_3: h^*(x_3) = f(x_3)\}|h^*(x_1) = f(x_1),h^*(x_2) = f(x_2)) \dots, \end{eqnarray*} and all of the terms have to be 1.

This is because $\mathcal{D}(\{x: h^*(x) = f(x)\})=1$ by assumption, and therefore $\mathcal{D}(\{x: h^*(x) = f(x)\}|C)=1$ must hold for any $C$ with $P(C)>0$ as $P(A)=P(A|B)P(B)+P(A|B^c)P(B^c)$, which can only be 1 if $P(A|B)$ is 1 as long as $P(B)\neq 0$. (Note that there is a certain mix-up in notation between your use of ${\mathcal{D}}$ and my use of $P$ here, and I'm too lazy to fix that. The argument shouldn't be affected.)

  • $\begingroup$ Thanks. Could you explain why the conditional probabilities are equal to $1$, please? $\endgroup$
    – S.H.W
    Commented Jan 12 at 10:57
  • 1
    $\begingroup$ @S.H.W I have added that to my answer. $\endgroup$ Commented Jan 12 at 11:12
  • $\begingroup$ Great answer, thanks! Also I think this question is related. $\endgroup$
    – S.H.W
    Commented Jan 12 at 11:35
  • 1
    $\begingroup$ @S.H.W Without reading all the detail over there, I don't think the comment is incorrect. It should basically remind you that a set with probability/measure zero is still nonempty and you can find something there. But this doesn't affect the probability statement. $\endgroup$ Commented Jan 13 at 13:46
  • 1
    $\begingroup$ @S.H.W Yes. Correct. $\endgroup$ Commented Jan 13 at 16:34

tl;dr : The Assumptions Avoid the Proof

What is assumed avoids having to prove either the sample dependent or independent case. It merely follows by what is assumed. The distribution $\mathcal{D}$ is irrelevant in this case because the actual distribution involved in your $\mathbb{P}[L_S(h^*) = 0] = 1$ is a Dirac distribution with all the probability on $L_S(h^*) = 0$ as follows from assumptions of $h^*$ in "realizable" learning. Absolute certainty lies in determinism.

Note that how you wrote the equality between the expressions using $\mathcal{D}$ to define $\mathbb{P}[L_S(h^*) = 0]$ is incorrect because $\mathcal{D}$ is only about the probability of witnessing a sample $x \in \mathcal{X}$, not about the probability of error. As written $x $ ~ $ \mathcal{D}$ does not necessarily equal probability 1, but comparing if $h^*(x) = f(x)$ is independent of the probability of $x$ occurring as they are defined, and so that is 1 by def of $h^*$.

Below, I explain in detail my point without a proof because that quickly turns into an open question in research of statistical learning if you keep relaxing distribution constraints from i.i.d. to beyond ergodic and stationary process into a non-stationary stochastic processes.

Note if you were to practically find $h^*$, $\mathcal{D}$ and the dependency between its samples absolutely matters.

An Explanation Without Formal Proof

I believe the issue lies in where the probability distributions actually affect anything, in particular $L_S$ and $L_{\mathcal{D}, f}$. This is often an issue when people use $P(\cdot)$ without specifying what equals what, or which probability distribution things are relative to. To help be clear what source of uncertainty I am referring to, I will continue (as from my prior answer here) to refer to $\mathcal{D} = (X, Y)$ as a joint distribution of input $X$ and output $Y$ as random variables, and $f(X) = Y$.

As per your question and the assumption of "realizable learning", the only distribution that could matter is $X$. I explain that now.

If $h^*(x) = f(x) = y$ for all $x \in \mathcal{X}$, which we are given, then the error in prediction from $h^*(x)$ wrt $f(x)$ is zero, always, regardless of any random or purposeful assortment, permutation, or poking and prodding of these functions' definitions. If given the same $x$ as input, they produce the same $y$, as that's what their equality means.

The formal theorem for this is the Data Processing Inequality, as defined in Ref. [2], Section 2.8

Theorem 2.8.1 (Data-processing inequality) If $X \rightarrow Y \rightarrow Z$ [is a markov chain of three random variables, $X,Y,Z$], then $I(X;Y) \ge I(X;Z)$.

This means that as long as there is only one source of uncertainty (as in entropy), in our case $X$ because assuming "realizable learning" means $f(X) = Y$ is a deterministic function and there is no other source of error, thus allowing zero error in the loss, then any deterministic transformation of that random variable can only have equal expected uncertainty or less. Given $h^*(X) = f(X) = Y$ by definition and "realizable learning" assumption, then all the uncertainty (probability) in $Y$ is fully determined by $X$ as transformed by $f$.

So that's the reason the loss is zero in addition to the fact that this magical $h^*$ is plucked from the imagination and not defined on how it is obtained. The curse of being too general to be useful, but yet given these properties assumed, we can reason about such an object.

This is why I stated in my last answer that if $h^*$ yields zero error on all of $\mathcal{X}$, then applying that hypothesis to any subset of $\mathcal{X}$ also yields zero error. Doesn't matter about the distribution $X$ over the space $\mathcal{X}$, because we have this magically correct $h^*$ and the $f(\cdot)$ and the losses are independent of $\mathcal{D}$ after $h^*$ is assumed.

If you want to know how to actually find $h^*$, that is an entirely different problem ripe with model assumptions including that the hypothesis space you considered even includes a correct hypothesis that could yield zero error (this is identifiability, and related is the concept of parameter or hypothesis space misspecification).

In this context, to address dependency of samples across time you need to use stochastic processes, where a process is a function over time, and a stochastic process is essentially how the random variable changes over time. There the dependency on prior states can involve either observed or latent (hidden) states. This is now a time series problem, and here be monsters. ;)

Further Reading

For more reading on finding $h^*$, I provide a snippet from this answer that is relevant after updating the reference numbers here. Recall I refer to the hypothesis space as the parameter space.

  1. identifiable [Ref. 3], meaning that the model is able to represent the observed process and is typically meant as a single parameter is point-identifiable from the information available in the observations, and
  2. "consistent" or is a "well behaved" parameter space with a "well behaved" update function that can converge to the true parameter.

This is discussed at length in [Ref. 4, Ch.6--9], specifically with regard to Bayesian modelling. Unfortunately, this is not open access.

What you are seeking in such a case is a mathematical and algorithmic formalization of inductive reasoning and inference, which has been of great interest for centuries. The Bayesian modeling approach tends to be involved in the probabilistic mathematical induction. Some relevant books of interest include Ref. 5 Ch. 5 & Ref. 6 Ch. 2.


Closed Access. = Closed Access. Open Access. = Open Access.

  1. Shalev-Shwartz, Shai and Ben-David, Shai. "Understanding Machine Learning: From Theory to Algorithms". May 2014. Cambridge University Press. ISBN 978-1-139-95274-3
  2. Cover, Thomas M. and Thomas, Joy A. "Elements of Information Theory". John Wiley & Sons, Inc. 2006. 2nd Ed. ISBN-13 978-0-471-24195-9
  3. Lewbel, Arthur. 2019. "The Identification Zoo: Meanings of Identification in Econometrics." Journal of Economic Literature, 57 (4): 835-903.
  4. Ghosal, Subhashis, and Aad Van der Vaart. Fundamentals of nonparametric Bayesian inference. Vol. 44. Cambridge University Press, 2017.
  5. Li, Ming, and Paul Vitányi. An introduction to Kolmogorov complexity and its applications. Vol. 3. New York: Springer, 2008.
  6. Hutter, Marcus. Universal artificial intelligence: Sequential decisions based on algorithmic probability. Springer Science & Business Media, 2004.
  • $\begingroup$ Note that the realizability assumption says that $$L_{\mathcal{D} , f}(h^*) = \mathcal{D}(\{x:h^*(x) \not = f(x) \}) = 0.$$ This proposition is different from $\forall x\in \mathcal{X}: h^*(x) = f(x)$. In fact the latter implies the former but not vice versa. Also the expression is correct since $L_S(h^*)=0$ occurs if and only if $$h^*(x_1) = f(x_1) \ \text{and} \ h^*(x_2) = f(x_2) \ \text{and} \dots h^*(x_m) = f(x_m)$$ occurs. Thus the events are equivalent and their probabilities the same. $\endgroup$
    – S.H.W
    Commented Jan 12 at 2:59
  • $\begingroup$ Actually the lecture notes which I referred to, have used the same argument. $\endgroup$
    – S.H.W
    Commented Jan 12 at 2:59
  • 1
    $\begingroup$ I admit i haven't yet read through those lecture notes, and this is from mostly recall besides looking up the equations in Ref 1. ATM, I am not convinced. I'd have to think on this more and reread both Ref 1 and the notes. Far too often do I find things like this in the literature on a mismatch on what distribution we're focusing on. If there are proofs for this in the notes, then as long as they're correct it does not matter whether I am convinced or not. lol ;) $\endgroup$
    – prijatelj
    Commented Jan 12 at 3:07

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.