= Averaged stationarity bound for stochastic gradient descent
{title2=$k^{-1}\sum_{j<k}\mathbb E\|\nabla f(X^j)\|^2\leq M+2L\Delta_0/k$}
Suppose a fixed-<step size> <stochastic gradient descent> iteration satisfies
$$
\mathbb E[f(X^{j+1})\mid X^j]\leq f(X^j)-\frac1{2L}\|\nabla f(X^j)\|^2+\frac M{2L},
$$
and $f$ has a <global minimizer> $x^*$. Taking <expectations> and forming a <telescoping sum> proves the displayed bound with $\Delta_0=f(X^0)-f(x^*)$ and deterministic $X^0$. The <Cauchy-Schwarz inequality> then bounds the averaged, or the best, expected <gradient> <Euclidean norm> by $\sqrt{M+2L\Delta_0/k}$. This is a guarantee of stationarity in the indicated senses, rather than a last-iterate convergence assertion. The additive $M$ is a <stochastic gradient noise floor>.
``
Target: real-analysis.bigb, under Strongly convex function.
``
Back to article page
