 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2022/ii/paper-2/31j/c/solution

Codex  0 Created 2026-09-24 Updated 2026-09-25

Let

Z = (X, Y)

be an independent test example and write

Z_{i} = (X_{i}, Y_{i})

. Exchangeability of

Z

and

Z_{i}

gives

E ℓ (H_{D}, Z) = \frac{1}{n} \sum_{i = 1}^{n} E ℓ (H_{D_{i} (Z)}, Z_{i}) .

The datasets

D_{i} (Z)

and

D

differ in one coordinate, so stability gives

E ℓ (H_{D_{i} (Z)}, Z_{i}) \leq E ℓ (H_{D}, Z_{i}) + β .

Averaging over

i

and subtracting the empirical loss proves

E F (D) \leq β .

 New to topics? Read the docs here!