 Solution

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

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

Use the empirical Rademacher convention

R (A) = \frac{1}{n} E_{σ} sup_{a \in A} \sum_{i = 1}^{n} σ_{i} a_{i} .

Because

H_{3}

is symmetric under

h \mapsto - h

, optimizing a linear functional over the positive

ℓ^{1}

hull defining

F

gives

R (F (x_{1 : n})) \leq R (H_{3} (x_{1 : n})) .

By part (c),

V C (H_{3}) \leq D = d (d + 1) /2

. Sauer--Shelah therefore bounds the number

N

of distinct label vectors on the sample by

N \leq s (H_{3}, n) \leq (n + 1)^{D} .

Massart's finite-class lemma states that for

A \subseteq {- 1, 1}^{n}

R (A) \leq \frac{2 l o g ∣ A ∣}{n} .

Applying it to the distinct label vectors of

H_{3}

gives

R (F (x_{1 : n})) \leq \frac{2 D l o g ( n + 1 )}{n} = \frac{( d ^{2} + d ) lo g ( n + 1 )}{n} .

 New to topics? Read the docs here!