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)

1) Binary Classification : Prove that $\mathbb{E}_{\mathcal{D}_n}\left[R_e(h)\right] = R(h)$

2) Why is the risk equal to the empirical risk when taking the expectation over the samples?

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.


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.



Your Answer

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