Past exam of the optimisation for data science course of the University of Oxford / 2023 / 2 / c / Solution

There is a summation-index misprint. On the native PDF, paper page 3, equation (4) has $X^k$ inside a sum indexed by $j$. The intended telescoping estimate has $X^j$ inside that sum; this is the estimate proved below and used in part (d). The index mismatch is present in the original PDF, rather than being introduced by the transcription.

Take the expectation of the supplied conditional expectation bound (3), using the tower property:Rearranging and forming a telescoping sum givesBecause $x^{\ast }$ is a global minimizer, $f(X^k)\ge f(x^{\ast })$ for every realisation. Hence the corrected equation (4) isAll expectations at a finite iteration are finite here: a deterministic starting point and finitely many choices of the sampled index produce only finitely many possible iterates. The bound controls accumulated squared gradients, with an additive contribution from the stochastic gradient noise floor.