Question 4.1 in Understanding Machine Learning: From Theory To Algorithms

Question

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.

Answer 1

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)$.