 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2023/ii/paper-1/31j/f/solution

 Top articles  Latest articles New article in topic

Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 1 / 31J / f / Solution by

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

Using the harmless normalization

1/ (2 n)

, the squared-loss empirical risk for linear prediction is

R_{n} (β) = \frac{1}{2 n} \sum_{i = 1}^{n} (β^{T} X_{i} - Y_{i})^{2},

with explicit gradient

\nabla R_{n} (β) = \frac{1}{n} i = 1 \sum n (β^{T} X_{i} - Y_{i}) X_{i} .

Starting from any

β_{0} \in C

, projected gradient descent with step sizes

η_{k} > 0

is

β_{k + 1} = β_{k} - η_{k} \nabla R_{n} (β_{k}), β_{k + 1} = π_{C} (β_{k + 1}) .

For a fully explicit update, write

β_{k + 1} = (u_{k}, t_{k})

and

ρ_{k} = ∥ u_{k} ∥_{2}

. The projection from part (e) is

π_{C} (u_{k}, t_{k}) = ⎩ ⎨ ⎧ (u_{k}, t_{k}), (0, 0), \frac{1}{2} (1 + \frac{t _{k}}{ρ _{k}}) (u_{k}, ρ_{k}), ρ_{k} \leq t_{k}, ρ_{k} \leq - t_{k}, ρ_{k} > ∣ t_{k} ∣.

Every iterate therefore lies in the prescribed hypothesis class, and any convergent run under the standard convex-optimization step-size conditions targets its empirical-risk minimizer.

 Read the full article

 New to topics? Read the docs here!