= Solution
{c}
Write $\Delta_0=f(x^0)-f(x^*)$. Dividing the corrected estimate from part (c) by $k/(2L)$ gives the <averaged stationarity bound for stochastic gradient descent>
$$
\frac1k\sum_{j=0}^{k-1}\mathbb E\|\nabla f(X^j)\|^2\leq M+\frac{2L\Delta_0}{k}.
$$
The <Cauchy-Schwarz inequality>, first within each <expectation> and then over the $k$ indices, gives
$$
\frac1k\sum_{j=0}^{k-1}\mathbb E\|\nabla f(X^j)\|
\leq\left(\frac1k\sum_{j=0}^{k-1}\mathbb E\|\nabla f(X^j)\|^2\right)^{1/2}.
$$
Thus
$$
\boxed{\min_{0\leq j<k}\mathbb E\|\nabla f(X^j)\|\leq\sqrt{M+\frac{2L\Delta_0}{k}}\leq\sqrt M+\sqrt{\frac{2L\Delta_0}{k}}.}
$$
Equivalently, if $J$ is chosen independently of the run with the <discrete uniform distribution> on $\{0,\ldots,k-1\}$, then $\mathbb E\|\nabla f(X^J)\|^2\leq M+2L\Delta_0/k$. The same bound for the expected <Euclidean norm> follows by the <Cauchy-Schwarz inequality>.
\b[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:
$$
\sqrt{M+\frac{2L\Delta_0}{k}}-\sqrt M
=\frac{2L\Delta_0/k}{\sqrt{M+2L\Delta_0/k}+\sqrt M}
\leq\frac{L\Delta_0}{k\sqrt M}.
$$
For example, to ensure $\min_{j<k}\mathbb E\|\nabla f(X^j)\|\leq\sqrt M+\varepsilon$ with $\varepsilon>0$, it suffices that $k\geq2L\Delta_0/(2\sqrt M\,\varepsilon+\varepsilon^2)$. The <big O notation> here concerns these upper bounds, rather than an asserted asymptotic equality for the <stochastic gradient noise floor>.
Back to article page
