 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2020/ii/paper-4/30j/iii/solution

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

∥ G_{s} ∥_{2} \leq G := \frac{M}{l o g 2} .

β_{s}

2 η E [f (β_{s}) - f (β)] \leq E ∥ β_{s} - β ∥_{2}^{2} - E ∥ β_{s + 1} - β ∥_{2}^{2} + η^{2} G^{2} .

Summing telescopes. Since both

β_{1}

and

β

lie in the radius-

R

C

, their distance is at most

2 R

. By the Jensen inequality and convexity of

f

E f (\overset{ˉ}{β}) - f (β) \leq \frac{2 R ^{2}}{η k} + \frac{η M ^{2}}{2 { l o g 2 } ^{2}} .

Choose

η = \frac{2 R lo g 2}{M k} .

The two terms are then equal, and

E f (\overset{ˉ}{β}) - f (β) \leq \frac{2 MR}{lo g ( 2 ) k} .

 New to topics? Read the docs here!