= Solution
{c}
Condition on $X^k=x$, and set $r=x-x^*$, $g=\nabla f(x)$ and $h=\nabla f_{S_k}(x)$. Since the sampled index is independent of $X^k$ and has the <discrete uniform distribution>, $h$ is an <unbiased stochastic gradient>:
$$
\mathbb E[h\mid X^k=x]=\frac1m\sum_{i=1}^m\nabla f_i(x)=g.
$$
Write $\sigma_k^2=\mathbb E[\|h-g\|^2\mid X^k=x]\leq M$. Expanding $h=g+(h-g)$ and using the zero conditional mean of $h-g$ proves the <stochastic gradient second-moment identity>
$$
\mathbb E[\|h\|^2\mid X^k=x]=\|g\|^2+\sigma_k^2.
$$
The <stochastic gradient descent> update is $X^{k+1}=x-h/L$. Expanding the squared <Euclidean distance> and using the preceding identities gives
$$
D_k:=\frac L2\mathbb E\left[\|X^k-x^*\|^2-\|X^{k+1}-x^*\|^2\,\middle|\,X^k=x\right]
=g^Tr-\frac1{2L}(\|g\|^2+\sigma_k^2).
$$
The <subgradient inequality> for the <differentiable> <convex function> $f$ gives $f(x)-f(x^*)\leq g^Tr$. Combining this with (3),
$$
\begin{aligned}
\mathbb E[f(X^{k+1})\mid X^k=x]
&\leq f(x)-\frac1{2L}\|g\|^2+\frac M{2L}\\
&\leq f(x^*)+g^Tr-\frac1{2L}\|g\|^2+\frac M{2L}\\
&=f(x^*)+D_k+\frac{\sigma_k^2+M}{2L}\\
&\leq f(x^*)+D_k+\frac ML.
\end{aligned}
$$
Removing the temporary notation for the conditioning point yields
$$
\boxed{\mathbb E[f(X^{k+1})\mid X^k]\leq f(x^*)+\frac L2\mathbb E\left[\|X^k-x^*\|^2-\|X^{k+1}-x^*\|^2\,\middle|\,X^k\right]+\frac ML.}
$$
\b[The noise contributes twice] in this argument: once in the supplied bound (3), and once in converting the expected squared step into the squared <gradient>. Each contribution is at most $M/(2L)$.
Back to article page
