 Solution

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

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

With varying positive step sizes, the same one-step inequality is

2 η_{s} E [f (β_{s}) - f (β)] \leq E ∥ β_{s} - β ∥_{2}^{2} - E ∥ β_{s + 1} - β ∥_{2}^{2} + η_{s}^{2} \frac{M ^{2}}{{ l o g 2 } ^{2}} .

Sum from

s = 1

k

, use

∥ β_{1} - β ∥_{2} \leq 2 R

, and divide by

2 A_{1}

β = A_{1}^{- 1} \sum_{s} η_{s} β_{s}

gives

E f (β) - f (β) \leq \frac{A _{2} M ^{2}}{2 A _{1} { lo g ( 2 ) } ^{2}} + \frac{2 R ^{2}}{A _{1}},

where

A_{1} = \sum_{s} η_{s}

and

A_{2} = \sum_{s} η_{s}^{2}

 New to topics? Read the docs here!