Local SGD with periodic synchronization

Let $n,d,K,T,b,m$ be positive integers, let $f_j:{\mathbb{R}}^d\to \mathbb{R}$ be differentiable for $1\le j\le n$, and define $f(x)=n^{-1}{\sum }_{j=1}^n{f}_j(x)$. The inputs are a starting point $x_0\in {\mathbb{R}}^d$, positive step sizes ${\eta }_0,\dots ,{\eta }_{T-1}$, and integer synchronization times $0<t_1<\cdots <t_m=T,{\mathcal{I}}_T=\{t_1,\dots ,t_m\}\mathrm{.}$ Set $t_0=0$ and $H={\max }_{1\le j\le m}(t_j-t_{j-1})\mathrm{.}$ Initialize $x_0^k=x_0$ for each worker $k\in \{1,\dots ,K\}$. For each $t=0,\dots ,T-1$, each worker $k$ and each within-step draw $q=1,\dots ,b$, draw $i_{t,q}^k$ uniformly from $\{1,\dots ,n\}$, with all draws mutually independent, and form $g_t^k(x)=\frac{1}{b}{\sum }_{q=1}^b\mathrm{\nabla }{f}_{i_{t,q}^k}(x),z_{t+1}^k=x_t^k-{\eta }_t{g}_t^k(x_t^k)\mathrm{.}$ For $b=1$ this is a single stochastic gradient. If $t+1\mathrm{\notin }{\mathcal{I}}_T$, set $x_{t+1}^k=z_{t+1}^k$ for every worker. If $t+1\in {\mathcal{I}}_T$, set $x_{t+1}^k=\frac{1}{K}{\sum }_{\mathrm{\ell }=1}^K{z}_{t+1}^{\mathrm{\ell }}\text{for every }k\mathrm{.}$ The procedure returns the worker trajectories $(x_t^k{)}_{0\le t\le T,1\le k\le K}$. The common initialization at time $0$ is included when measuring the largest synchronization gap, and a convergence statement must specify any particular average or iterate it analyzes.

Independent random elements

Stich, Local SGD Converges Fast and Communicates Little, Algorithm 1 and Definition 2.1

Gorbunov et al., Local SGD: Unified Theory and New Efficient Methods, equation (4)