True Error in Machine Learning

Question

I have read this question and I am confused by a part of the first answer, even though it is asked in the comments.

I don't understand why $$L_{(\mathcal{D}, f)}(h^{*}) = 0 \implies L_{S}(h^{*}) = 0$$

Why if the "True Error" equal to $0$ i.e. $L_{(\mathcal{D}, f)}(h^{*}) = 0$ then it's implied that the "Training Error" is also equal to $0$ i.e. $ L_{S}(h^{*}) = 0$?

After the answer to my previous question, I started understanding what is $\mathcal{D}$. Now, I think intuitively I can understand what they mean by this implication relation. So here's my intuitive explanation (please correct me if I'm wrong):

Since the classifier $h^*$ has zero error when applied to the "population" $\mathcal{X}$ (where $\mathcal{X}$ is the set of input datapoints, and where a "training" $\mathcal{X}$ is the training datapoints), this means that $h^*$ has information about all samples of $\mathcal{X}$ from the population and it has correctly classified them with $0$ error, hence when applied to one of these samples (i.e., in our case the training sample), it will clearly yield $0$ error.

I hope my intuitive explanation is understandable.

Is my understanding correct and how would I prove this more rigorously? (If it's possible to do so?)

Answer 1

The Reasoning is Correct

This reasoning is correct when the training sample $S$ is a representative sampling of the true (population) distribution $\mathcal{D}$ and there is no noise in the true labels.

Given this is the "realizable" case, which just means the loss can actually equal zero and thus the most correct hypothesis will result in a loss of zero, then if $h^*$ was the true or a correct hypothesis then there would be no error on any sampling of the distribution as long as there is no other source of uncertainty. This includes the finite sampling that is the training set.

---

Recall a random variable $R$ is always associated with a probability triple. which consists of the sample space $\Omega_R$ (really a set), the event space $\Sigma_R$ (the sigma algebra of that set), and a probability distribution $P_R$.

Note that the following proof holds without the assumption of $i.i.d.$ random variables.

In the following, I changed some of the structure and notation of the parts in hopes to aid reader's in understanding their relationships better and to emphasize explicit parts in the definitions of Ref. [1] that are left implicit in their notation as used in the question above.

Proof

We start by setting up what is given:

1. Let there be some task $\mathcal{T} \triangleq \{(\mathscr{X},\Sigma_X), (\mathscr{Y}, \Sigma_Y)\}$ that consists of the input space and output space respectively. The task of a predictor is to find some $\mathcal{H}$-parameterized function $f : \mathcal{H} \times (\mathscr{X},\Sigma_X) \mapsto (\mathscr{Y}, \Sigma_Y)$ without error, which is theoretically possible in the "realizable" case as defined in Ref. [1].
   • $\mathcal{H}$ is used to denote the parameter set of the parameter space, which is the hypothesis space. This is important to note because any function written in a formal language (as all formal math and logic is) can be represented by a parameterized function whose parameters is a string written in that formal language. Think of it as a programming language where a program performing the task by computing the function $f$ is the hypothesis.
2. Let there be a random variable $X$ whose probability triple is $(\mathscr{X}, \Sigma_X, P_X)$ and the support of $X$ is over the set of possible inputs to the task, $\mathscr{X}$.
3. Let there be another random variable $Y$ over the output space, or label space, of the task, whose corresponding probability triple is $(\mathscr{Y}, \Sigma_Y, P_Y)$
4. Let $\mathcal{D} = (X, Y)$ be the joint distribution of the two random variables simply concatenated together such that an input sample $x \in \mathscr{X}$ is paired with its correct label $y \in \mathscr{Y}$, resulting in the sample space of $\mathcal{D}$ to be $\Omega_\mathcal{D} = \{(x_i, y_i) : x_i \in \mathscr{X}, y_i \in \mathscr{Y}, i \in \mathbb{N} \}$.
   • Note that $i \in \mathbb{N}$ serves as an enumeration of all unique pairs, simply used here to emphasize they belong together and that $y_i$ is the correct label to be predicted for $x_i$. We continue to use this notation in the following.
5. Let $\mathcal{L}: \mathscr{X} \times \mathscr{Y} \mapsto [0, \infty]$ be the loss function of interest, where $[0, \infty]$ is the range of the loss as a measure.
   • Using the empirical risk as $\mathcal{L}$, the loss over some set $S \subseteq \Omega_\mathcal{D}$ is $$\mathcal{L}_S\big(x, f(h, x)\big) = \frac{1}{|S|} \sum_{(x,y) \in S} f(h,x) \neq y$$
6. Let $h^* \in \mathcal{H} : \forall\big( (x_i, y_i) \in \Omega_\mathcal{D} \big) : \Big( \mathcal{L}\big(x_i, f(h^*, x_i)\big) = 0 \Big)$ be the true hypothesis (coordinate in parameter space) or any equivalent hypothesis that solves the task in the "realizable" case, that is, without any error as measured by the loss function of interest.

As per what is given, $\forall (S \subseteq \Omega_\mathcal{D}): \Big(\mathcal{L}\big(x_i, f(h^*, x_i)\big) = 0 : (x_i, y_i) \in S \Big)$ $\blacksquare$

For the following reasons

• every pair in the support of $\mathcal{D}$ will have a loss of zero in the realizable case by definition
• any subset of that set of pairs will still have a loss of zero,
• and because $h^*$ is the correct hypothesis which yields predictions with no error, that is a loss of zero.

Clarifying Notation

Some misunderstanding may result due to Ref. [1]'s notation for the definitions of $L_\mathcal{D}(h)$ and $L_S(h)$ in Section 3.2.1, and the question's notation of $L_{\mathcal{D},f}(h^*)$, as they made the measures about the hypothesis (parameter coordinate) instead of the input and output pairs, as I wrote in my proof. I rewrote $L_S(h)$ as $\mathcal{L}_S$ above under given knowledge 5. Rewriting the definition
for the probability of the loss not equaling zero given the hypothesis $h$ is as follows using my notation $$L_\mathcal{D}(h) = P_D\Big( (X, Y) \neq \big(x, f(h,x)\big) \Big) = P\Big( Y | X \neq f(h, x) \Big)$$

Notably, as Ref. [1] wrote $L_\mathcal{D}(h)$, the conditional distribution $Y |X$ is actually non-random due to their implicit assumption that the true label $y_i$ is fully determined by $x_i$, which is why the true hypothesis $h^*$ yields a probability zero of error. This is a result of assuming "realizable" learning, that is, there is a deterministic (non-random) mapping $f(h, X) = Y$. Otherwise, there would still be some uncertainty in the labels (noise as mentioned before) even when given $X=x$. Think about trying to predict the rolled outcomes of a fair die. The probability of your predictions being correct will asymptotically follow $\frac{1}{6}$ even if you modeled it correctly as a fair die. Given $X=x$, that is the max probability of being correct following empirical risk minimization (minimizing the error).

---

References

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
   • https://www.cs.huji.ac.il/~shais/UnderstandingMachineLearning/