One-step progress of the virtual local-SGD iterate

Averaging the proposals in [F1] gives their mean ${\bar{x}}_t-{\eta }_t{g}_t$. Synchronization preserves that mean, so ${\bar{x}}_{t+1}={\bar{x}}_t-{\eta }_t{g}_t$, whether or not this step synchronizes. Fix any past tuple of sampled indices. The current independent uniform indices have finite conditional average ${\bar{g}}_t$ by [F2]. Expanding after adding and subtracting ${\eta }_t{\bar{g}}_t$, then averaging over the current indices, removes the cross term and gives $\mathbb{E}\mathrm{\parallel }{\bar{x}}_{t+1}-x^{\star }{\mathrm{\parallel }}_2^2=\mathbb{E}\mathrm{\parallel }{\bar{x}}_t-x^{\star }-{\eta }_t{\bar{g}}_t{\mathrm{\parallel }}_2^2+{\eta }_t^2\mathbb{E}\mathrm{\parallel }{g}_t-{\bar{g}}_t{\mathrm{\parallel }}_2^2$.

Fix the past tuple and write $x_k=x_t^k$. Jensen's inequality [F4] gives $\mathrm{\parallel }{\bar{g}}_t{\mathrm{\parallel }}_2^2\le K^{-1}{\sum }_k\mathrm{\parallel }\mathrm{\nabla }f(x_k){\mathrm{\parallel }}_2^2$. Applying [F3] at $x_k$ with $y=x_k-L^{-1}\mathrm{\nabla }f(x_k)$ and using $f(x^{\star })\le f(y)$ yields $\mathrm{\parallel }\mathrm{\nabla }f(x_k){\mathrm{\parallel }}_2^2\le 2L(f(x_k)-f^{\star })$. Strong convexity [A1] gives $-⟨x_k-x^{\star },\mathrm{\nabla }f(x_k)⟩\le -(f(x_k)-f^{\star })-(\mu \mathrm{/}2)\mathrm{\parallel }{x}_k-x^{\star }{\mathrm{\parallel }}_2^2$. Young's inequality, in the form $-2⟨u,v⟩\le 2L\mathrm{\parallel }u{\mathrm{\parallel }}_2^2+(2L{)}^{-1}\mathrm{\parallel }v{\mathrm{\parallel }}_2^2$, therefore gives $-2⟨{\bar{x}}_t-x_k,\mathrm{\nabla }f(x_k)⟩\le 2L\mathrm{\parallel }{\bar{x}}_t-x_k{\mathrm{\parallel }}_2^2+f(x_k)-f^{\star }$. In the expansion $\mathrm{\parallel }{\bar{x}}_t-x^{\star }-{\eta }_t{\bar{g}}_t{\mathrm{\parallel }}_2^2=\mathrm{\parallel }{\bar{x}}_t-x^{\star }{\mathrm{\parallel }}_2^2-2{\eta }_t⟨{\bar{x}}_t-x^{\star },{\bar{g}}_t⟩+{\eta }_t^2\mathrm{\parallel }{\bar{g}}_t{\mathrm{\parallel }}_2^2$, decompose ${\bar{x}}_t-x^{\star }=({\bar{x}}_t-x_k)+(x_k-x^{\star })$ and average the preceding bounds over $k$. The function-gap coefficient is $-2{\eta }_t+{\eta }_t+2{\eta }_t^{2}L=2{\eta }_t({\eta }_{t}L-\frac{1}{2})$; the strong- convexity term is $-\mu {\eta }_t{K}^{-1}{\sum }_k\mathrm{\parallel }{x}_k-x^{\star }{\mathrm{\parallel }}_2^2$. Hence $\mathrm{\parallel }{\bar{x}}_t-x^{\star }-{\eta }_t{\bar{g}}_t{\mathrm{\parallel }}_2^2\le \mathrm{\parallel }{\bar{x}}_t-x^{\star }{\mathrm{\parallel }}_2^2+\frac{2{\eta }_{t}L}{K}{\sum }_k\mathrm{\parallel }{\bar{x}}_t-x_k{\mathrm{\parallel }}_2^2+2{\eta }_t({\eta }_{t}L-\frac{1}{2})\frac{1}{K}{\sum }_k(f(x_k)-f^{\star })-\frac{\mu {\eta }_t}{K}{\sum }_k\mathrm{\parallel }{x}_k-x^{\star }{\mathrm{\parallel }}_2^2\mathrm{.}$

Since ${\eta }_{t}L\le 1\mathrm{/}4$, the coefficient $2{\eta }_t({\eta }_{t}L-\frac{1}{2})\le -{\eta }_t\mathrm{/}2$. Convexity of $f$ follows from $\mu$-strong convexity in [A1]. Jensen [F4] gives $K^{-1}{\sum }_{k}f(x_k)\ge f({\bar{x}}_t)$ and $K^{-1}{\sum }_k\mathrm{\parallel }{x}_k-x^{\star }{\mathrm{\parallel }}_2^2\ge \mathrm{\parallel }{\bar{x}}_t-x^{\star }{\mathrm{\parallel }}_2^2$. Thus step 1.2 is at most $(1-\mu {\eta }_t)\mathrm{\parallel }{\bar{x}}_t-x^{\star }{\mathrm{\parallel }}_2^2-({\eta }_t\mathrm{/}2)(f({\bar{x}}_t)-f^{\star })+(2{\eta }_{t}L\mathrm{/}K){\sum }_k\mathrm{\parallel }{\bar{x}}_t-x_k{\mathrm{\parallel }}_2^2$. Average over the past and substitute into step 1.1 to obtain the claim.