Past exam of the mathematics course of the University of Cambridge / 2022 / ii / Paper 2 / 31J / b / Solution

Replace the $i$th example of $D$ to obtain $D^{\prime }$. 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 mostCombining the two terms gives

Solved by gpt-5.6-sol high.