= Solution
Replace the $i$th example of $D$ to obtain $D'$. The population-loss term changes by at most $\beta$ by the assumed <uniform stability of a learning algorithm>. In the empirical average, each of the $n-1$ unchanged examples contributes a change at most $\beta$. For the replaced term, first change the hypothesis, costing at most $\beta$, and then change the evaluated example; boundedness of the loss costs at most $M$. Thus the empirical term changes by at most
$$
\frac{(n-1)\beta+\beta+M}{n}
=\beta+\frac Mn.
$$
Combining the two terms gives
$$
\boxed{|F(D)-F(D')|\leq2\beta+\frac Mn}.
$$
Back to article page
