# Question 4.1 in Understanding Machine Learning: From Theory To Algorithms

For any learning algorithm $$A$$, probability distribution $$D$$, and a loss function $$L$$ whose range is $$[0,1]$$, show that the following 2 statements are equivalent.

1. For every $$\epsilon, \delta > 0$$ there exist $$m(\epsilon,\delta)$$ such that $$\forall m \geq m(\epsilon, \delta)$$ $$\mathbb{P}_{S \sim D^m}[L_D(A(S))> \epsilon] < \delta$$

2. $$\lim_{m \to \infty}\mathbb{E}_{S \sim D^m}[L_D(A(S))]= 0$$

where $$D^m$$ is distribution over samples $$S$$ of size $$m$$ and $$A(S)$$ is hypothesis that $$A$$ returns after receiving sample $$S$$.

I'm stuck at proving $$1 \rightarrow 2$$. Pick $$\epsilon, \delta > 0$$. Assume $$B = \{S: L(A(S)) > 0 \}$$ - collection of samples such that the learner returns a hypothesis with nonzero loss over true $$D^m$$.

We have $$\mathbb{E}_{S \sim D^m}[L_D(A(S))] = \sum_{S \in B} L_D(A(S))P_{S \sim D^m}(S)$$ Now, we can also define $$B_{\epsilon} = \{S: L(A(S)) > \epsilon \}$$, and so we get, by (1), $$\sum_{S \in B} L_D(A(S))P_{S \sim D^m}(S) = \sum_{S \in B - B_\epsilon} L_D(A(S))P_{S \sim D^m}(S) + \sum_{S \in B_{\epsilon}} L_D(A(S))P_{S \sim D^m}(S)$$ $$\leq \epsilon + \delta\sum_{S \in B_{\epsilon}} L_D(A(S))$$

I am not sure how to bound the sum at this point. You can probably say that $$B_{\epsilon} \to \emptyset$$ since $$m \to \infty$$ (more datapoints to learn over), but I don't see how to make this more rigorous.

• Downvoter: please explain. May 9, 2018 at 4:07

Write $X:=L_D(A(S))$ and let $E_m$ be shorthand for $E_{S\sim D^m}$. You want to show $E_m[X]\to0$. To do this, consider the cases $X\le\epsilon$ and $X>\epsilon$. (In fact the event $X>\epsilon$ is your event $B_\epsilon$.) Then $$E_m[X]=E_m[XI(X\le\epsilon)]+E_m[XI(X>\epsilon)].\tag1$$ The first term on the RHS of (1) is at most $\epsilon$, as you've done. For the second term, use the fact that $L$ has range $[0,1]$ to see that $$E_m[XI(X>\epsilon)]\le E_m[I(X>\epsilon)]=P_m(X>\epsilon).\tag2$$ By assumption, the RHS of (2) can be made arbitrarily small for large enough $m$.
To add more rigor to the proof $E_m[X]\to0$, replace $\epsilon$ above with $\epsilon/2$ and choose $\delta:=\epsilon/2$. The argument then shows $E_m[X]\le \epsilon/2+\epsilon/2$ for all $m$ exceeding $m(\epsilon/2,\epsilon/2)$.