Past exam of the mathematics course of the University of Cambridge / 2022 / ii / Paper 2 / 31J (Mathematics of Machine Learning)

A function has the bounded-differences property with constants
$L_1,\dots ,L_n$ when replacing only coordinate $i$ changes its value by at most $L_i$. The Bounded differences inequality states that, for independent inputs,and the analogous lower-tail bound also holds.

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

Let $Z=(X,Y)$ be an independent test example and write $Z_i=(X_i,Y_i)$. Exchangeability of $Z$ and $Z_i$ givesThe datasets $D_i(Z)$ and $D$ differ in one coordinate, so stability givesAveraging over $i$ and subtracting the empirical loss proves

Apply the bounded-differences inequality with every
$L_i=2\beta +M/n$. With probability at least $1-\delta$,Using part (c) and substituting the definition of $F$ gives