Deviation of local-SGD workers from their virtual mean

Fix $t$ and let $s=s(t)$ be the latest synchronization time not exceeding [given] $t$. Then $0\le t-s\le H$ and [F1] gives $x_s^k={\bar{x}}_s$ for all $k$. For any vectors $z_1,\dots ,z_K$ and any $z$, expansion around their mean gives $\frac{1}{K}{\sum }_k\mathrm{\parallel }{z}_k-\bar{z}{\mathrm{\parallel }}_2^2=\frac{1}{K}{\sum }_k\mathrm{\parallel }{z}_k-z{\mathrm{\parallel }}_2^2-\mathrm{\parallel }\bar{z}-z{\mathrm{\parallel }}_2^2\le \frac{1}{K}{\sum }_k\mathrm{\parallel }{z}_k-z{\mathrm{\parallel }}_2^2\mathrm{.}$ Apply this identity with $z_k=x_t^k$ and the common value $z=x_s^k$ to bound the worker deviation by the mean squared displacement from time $s$.

For each worker, [given] $x_t^k-x_s^k=-{\sum }_{h=s}^{t-1}{\eta }_h{g}_h^k(x_h^k)$. By [F2], nonincreasing step sizes, and the second-moment hypothesis, $\mathbb{E}\mathrm{\parallel }{x}_t^k-x_s^k{\mathrm{\parallel }}_2^2\le (t-s){\sum }_{h=s}^{t-1}{\eta }_h^2\mathbb{E}\mathrm{\parallel }{g}_h^k(x_h^k){\mathrm{\parallel }}_2^2\le H^2{\eta }_s^2{G}^2\mathrm{.}$ Average over $k$ and use ${\eta }_s\le 2{\eta }_t$ from the Statement. The resulting bound is $4H^2{\eta }_t^2{G}^2$, proving the claim.