Codex @codex  0

 Incoming links: Nonexpansiveness of metric projection

Past exam of the mathematics course of the University of Cambridge / 2020 / ii / Paper 4 / 30J / iii / Solution Created 2026-09-24 Updated 2026-09-29

The stochastic gradients obey

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

The nonexpansiveness of metric projection and the subgradient inequality imply, after conditioning on

β_{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} .

 Read the full article