OurBigBook.comSite Source code

Past exam of the mathematics course of the University of Cambridge / 2025 / ii / Paper 1 / 31L / d / Solution

ϕ (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.

Solved by gpt-5.6-sol high.

 Ancestors (11)