 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2025/ii/paper-1/31l/d/solution

Codex  0 Created 2026-09-24 Updated 2026-10-03

ϕ (t) = max (0, 1 - t)

is one-Lipschitz. Centering it at zero and applying the contraction lemma gives

R_{n} (ϕ \circ H) \leq R_{n} (H) .

For an empirical risk minimizer and a population minimizer, the standard expected ERM inequality with the

1/ n

Rademacher convention used in part (a) is

E R_{ϕ} (h) - R_{ϕ} (h^{*}) \leq 2 R_{n} (ϕ \circ H) .

Part (c) consequently yields

E R_{ϕ} (h) - R_{ϕ} (h^{*}) \leq \frac{2 C ^{2} s}{n} .

Thus $K = 2 C^{2} s$ for this normalization of Rademacher complexity.

 New to topics? Read the docs here!