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.

  • $\begingroup$ Downvoter: please explain. $\endgroup$ – Franck Dernoncourt May 9 '18 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)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.