= Solution
{c}
\b[The printed distance needs a square.] The native PDF, paper page 3, prints $\|x^0-x^*\|$ in the final bound, but the general conclusion from (5) contains $\|x^0-x^*\|^2$. We first prove the corrected statement and then show that the printed version can fail.
Take the <expectation> in (5), use the <tower property>, and sum over $j=0,\ldots,k-1$. The squared <Euclidean distances> form a <telescoping sum>:
$$
\sum_{j=0}^{k-1}\big(\mathbb E f(X^{j+1})-f(x^*)\big)
\leq\frac L2\left(\|x^0-x^*\|^2-\mathbb E\|X^k-x^*\|^2\right)+\frac{kM}{L}.
$$
Discard the final nonnegative squared <Euclidean distance>. The smallest of $k$ numbers is at most their <arithmetic mean>, so
$$
\boxed{\min_{0\leq j<k}\mathbb E f(X^{j+1})-f(x^*)\leq\frac L{2k}\|x^0-x^*\|^2+\frac ML.}
$$
This is an $O(k^{-1})$ bound above the <stochastic gradient noise floor> $M/L$ for the best expected <objective function> value. By <Jensen's inequality>, it also bounds $\mathbb E f(\bar X^k)-f(x^*)$ for the averaged iterate $\bar X^k=k^{-1}\sum_{j=0}^{k-1}X^{j+1}$, because $f$ is a <convex function>.
To test the printed version, take one component function, $f_1(x)=f(x)=x^2/4$, with $L=1$, $x^*=0$ and $x^0=10$. This <convex quadratic function> has $\nabla f(x)=x/2$, hence it has a $1$-<Lipschitz gradient>. The <stochastic gradient descent> update is deterministic, its conditional <variance> is zero, and the assumed positive bound $M=1/10$ is valid. At $k=1$, the new iterate is $X^1=5$, so
$$
f(X^1)-f(x^*)=\frac{25}{4}>5+\frac1{10}
=\frac L2\|x^0-x^*\|+\frac ML.
$$
Thus the printed inequality is false under its stated assumptions. The squared <Euclidean distance> in the corrected bound resolves the defect.
Back to article page
