= Solution
The stochastic gradients obey
$$
\lVert G_s\rVert_2\leq G:=\frac{M}{\log2}.
$$
The <nonexpansiveness of metric projection> and the <subgradient inequality> imply, after conditioning on $\beta_s$,
$$
2\eta\,\mathbb E[f(\beta_s)-f(\widehat\beta)]
\leq\mathbb E\lVert\beta_s-\widehat\beta\rVert_2^2
-\mathbb E\lVert\beta_{s+1}-\widehat\beta\rVert_2^2
+\eta^2G^2.
$$
Summing telescopes. Since both $\beta_1$ and $\widehat\beta$ lie in the radius-$R$ set $C$, their distance is at most $2R$. By the <Jensen inequality> and convexity of $f$,
$$
\mathbb E f(\bar\beta)-f(\widehat\beta)
\leq\frac{2R^2}{\eta k}+\frac{\eta M^2}{2\{\log2\}^2}.
$$
Choose
$$
\boxed{\eta=\frac{2R\log2}{M\sqrt k}}.
$$
The two terms are then equal, and
$$
\boxed{\mathbb E f(\bar\beta)-f(\widehat\beta)
\leq\frac{2MR}{\log(2)\sqrt k}}.
$$
Back to article page
