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

Write ${\Delta }_0=f(x^0)-f(x^{\ast })$. Dividing the corrected estimate from part (c) by $k/(2L)$ gives the averaged stationarity bound for stochastic gradient descentThe Cauchy-Schwarz inequality, first within each expectation and then over the $k$ indices, givesThusEquivalently, if $J$ is chosen independently of the run with the discrete uniform distribution on $\{0,\dots ,k-1\}$, then $\mathbb{E}\Vert \nabla f(X^J){\Vert }^2\le M+2L{\Delta }_0/k$. The same bound for the expected Euclidean norm follows by the Cauchy-Schwarz inequality.

The guarantee is averaged or best-iterate stationarity. It does not assert that every last iterate converges, or that the limiting Euclidean norm equals $\sqrt{M}$. The squared gradient bound has excess $O(k^{-1})$ above $M$; the displayed expected Euclidean norm bound is within $O(k^{-1/2})$ of $\sqrt{M}$, including the zero-noise case. For fixed $M>0$, it is sharper:For example, to ensure ${\min }_{j<k}\mathbb{E}\Vert \nabla f(X^j)\Vert \le \sqrt{M}+\epsilon$ with $\epsilon >0$, it suffices that $k\ge 2L{\Delta }_0/(2\sqrt{M}\epsilon +{\epsilon }^2)$. The big O notation here concerns these upper bounds, rather than an asserted asymptotic equality for the stochastic gradient noise floor.