= Solution
{c}
\b[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>:
$$
\mathbb E f(X^{j+1})\leq\mathbb E f(X^j)-\frac1{2L}\mathbb E\|\nabla f(X^j)\|^2+\frac M{2L}.
$$
Rearranging and forming a <telescoping sum> gives
$$
\frac1{2L}\sum_{j=0}^{k-1}\mathbb E\|\nabla f(X^j)\|^2
\leq f(x^0)-\mathbb E f(X^k)+\frac{kM}{2L}.
$$
Because $x^*$ is a <global minimizer>, $f(X^k)\geq f(x^*)$ for every realisation. Hence the corrected equation (4) is
$$
\boxed{\sum_{j=0}^{k-1}\frac1{2L}\mathbb E\|\nabla f(X^j)\|^2\leq f(x^0)-f(x^*)+\frac{kM}{2L}.}
$$
All <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. \b[The bound controls accumulated squared gradients], with an additive contribution from the <stochastic gradient noise floor>.
Back to article page
