# We know that The empirical risk is an unbiased estimate of the risk. Then why Is the training error biased ? (How does to proof for the former break)

Setting:

Let $$S$$ be a set of $$m$$ samples from a set $$Z$$ and $$w^{*}$$ be an arbitrary vector. (Samples Are I.I.D and we are operating in a binary classification setting)

Then $$\mathbb{E}_{S \sim D^{m}}\left[L_{S}\left(w^{*}\right)\right]=L_{D}\left(w^{*}\right)$$

Where: $$L_{S}\left(w^{*}\right) \equiv \frac{1}{m} \sum_{i=1}^{m} l\left(w^{*}, z_{i}\right)$$ and $$z_{i} \in S, L_{D}\left(w^{*}\right) \equiv \mathbb{E}_{z \sim D}\left[l\left(w^{*}, z\right)\right], D$$ is a distribution on $$Z,$$ and $$l(\ldots)$$ is a loss function.

When proving that the empirical risk is an unbiased estimate of the risk we usually argue that.

\begin{aligned} \mathbb{E}_{S} L_{n}(h) &=\mathbb{E}_{S} \frac{1}{n} \sum_{i=1}^{n} \mathbf{1}\left[h\left(X_{i}\right) \neq Y_{i}\right] \\ &=\frac{1}{n} \sum_{i=1}^{n} \mathbb{E}_{S} \mathbf{1}\left[h\left(X_{i}\right) \neq Y_{i}\right] \\ &=\frac{1}{n} \sum_{i=1}^{n} \mathbb{E}_{(X, Y)} \mathbf{1}[h(X) \neq Y] \\ &=\frac{1}{n} \sum_{i=1}^{n} L(h) \\ &=L(h) \end{aligned}

or something along these lines. (Thorough proofs can be seen at)

After this, we can pose a Claim that there exists a distribution $$P$$ and a learner, such that for all $$n$$ we have $$L_{n}\left(h_{n}\right)=0 \text { and } L\left(h_{n}\right)=1$$

Meaning that we can create a model that overfits on the Training Data $$S$$.

As: $$E\left[L\left(f^{*}\left(S\right)\right)-\hat{L}\left(f^{*}\left(S\right), S\right)\right] \geq 0$$.

Meaning that the training error actually IS a biased estimate of the risk. On a high level, we are told that this happens because $$h_n$$ depends on the data and that at any given sample size, there exist functions, for which true and empirical risk are arbitrarily far apart.

Question:

Now I want to know how does $$h_n$$ being dependent on the data $$S$$ breaks the proof that the empirical risk is an unbiased estimate of the risk. Is the IID assumption broken or what exactly happens mathematically.