Projected SGD converges almost surely on a strongly convex objective

Since $P_C$ is the proximal map of ${\iota }_C$ by [F3], [F2] makes it nonexpansive and therefore continuous; [F3] also gives $P_C(x^{\ast })=x^{\ast }$ and $x_{k+1}\in C$. The point $x_k-{\alpha }_k{G}_k$ is ${\mathcal{F}}_{k+1}$-measurable, so continuity makes $x_{k+1}$ ${\mathcal{F}}_{k+1}$-measurable. Thus the distance process is adapted. Hence $V_{k+1}=\mathrm{\parallel }{x}_{k+1}-x^{\ast }{\mathrm{\parallel }}_2^2\le \mathrm{\parallel }{x}_k-{\alpha }_k{G}_k-x^{\ast }{\mathrm{\parallel }}_2^2\le (1+\mu {\alpha }_k)V_k+({\alpha }_k\mathrm{/}\mu +{\alpha }_k^2)\mathrm{\parallel }{G}_k{\mathrm{\parallel }}_2^2,$ where the last inequality follows by expanding the square, applying [F8], [F9], and using $2uv\le \mu u^2+{\mu }^{-1}{v}^2$. By [F6], $\mathbb{E}\mathrm{\parallel }{G}_k{\mathrm{\parallel }}_2^2\le M^2$, so induction from square-integrable $x_0$ shows each $V_k$ is integrable. By [F11] and the conditional moment bound, $\mathrm{\parallel }\mathrm{\nabla }f(x_k){\mathrm{\parallel }}_2^2=\mathrm{\parallel }\mathbb{E}[G_k\mid {\mathcal{F}}_k]{\mathrm{\parallel }}_2^2\le M^2$ almost surely. Cauchy–Schwarz therefore makes the cross products in the conditional expansion integrable.

For any $y\in C$ and $0<t\le 1$, convexity of $C$ gives $x^{\ast }+t(y-x^{\ast })\in C$. Minimality of $x^{\ast }$ implies $f(x^{\ast }+t(y-x^{\ast }))\ge f(x^{\ast })$. Divide by $t$ and let $t\downarrow 0$; [F5] makes the quotient tend to $⟨\mathrm{\nabla }f(x^{\ast }),y-x^{\ast }⟩$, which must be nonnegative because a limit of nonnegative reals is nonnegative.

By [F13], $\mathrm{dom}F=C$ and $F=f$ on $C$, so the strong-Jensen condition [F12] is exactly the hypothesis of [F4]. Apply [F4] to $x_k,x^{\ast }$ and use step 1.2 with $y=x_k$ to obtain $⟨\mathrm{\nabla }f(x_k),x_k-x^{\ast }⟩\ge \mu V_k$. Expanding the projection estimate in step 1.1 and conditioning with [F6] now gives $\mathbb{E}[V_{k+1}\mid {\mathcal{F}}_k]\le V_k-2\mu {\alpha }_k{V}_k+M^2{\alpha }_k^2\mathrm{.}$

Apply [F7] with $a_k=0$, $b_k=2\mu {\alpha }_k{V}_k$, and $c_k=M^2{\alpha }_k^2$. Step 1.1 gives integrability, and the stepsize conditions give $\sum c_k<\mathrm{\infty }$. Thus $V_k$ converges almost surely and ${\sum }_k{\alpha }_k{V}_k<\mathrm{\infty }$ almost surely. If its limit were positive, the divergent sum ${\sum }_k{\alpha }_k$ would force ${\sum }_k{\alpha }_k{V}_k=\mathrm{\infty }$, a contradiction. Therefore $V_k\to 0$ and $x_k\to x^{\ast }$ almost surely.