 Solution

Condition on $X^k=x$, and set $r=x-x^{\ast }$, $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:Write ${\sigma }_k^2=\mathbb{E}[\Vert h-g{\Vert }^2\mid X^k=x]\le M$. Expanding $h=g+(h-g)$ and using the zero conditional mean of $h-g$ proves the stochastic gradient second-moment identityThe stochastic gradient descent update is $X^{k+1}=x-h/L$. Expanding the squared Euclidean distance and using the preceding identities givesThe subgradient inequality for the differentiable convex function $f$ gives $f(x)-f(x^{\ast })\le g^{T}r$. Combining this with (3),Removing the temporary notation for the conditioning point yieldsThe 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)$.