SCAFFOLD with client and server control variates

The inputs are positive integers $N,d,R,K,S$ with $1\le S\le N$, objective functions $f_i:{\mathbb{R}}^d\to \mathbb{R}$, an initial server model $x_0\in {\mathbb{R}}^d$, client controls $c_i^0\in {\mathbb{R}}^d$, positive step sizes ${\eta }_l,{\eta }_g$, a local stochastic-gradient oracle $g_i$, and a control-update option from $\{\mathrm{I},\mathrm{I}\mathrm{I}\}$. Set $c^0=N^{-1}{\sum }_i{c}_i^0$. The random client sample in each round is independent of that round's fresh local-oracle randomness; no independence among distinct clients' oracle draws is required here.

For each round $r=1,\dots ,R$, independently sample a uniform fixed-size subset ${\mathcal{S}}_r$ of $S$ clients. At the start of this round, write $x=x_{r-1}$, $c=c^{r-1}$, and $c_i=c_i^{r-1}$. For every selected client $i$, initialize $y_{i,0}=x$ and, for $k=1,\dots ,K$, call $g_i$ at $y_{i,k-1}$ and update $y_{i,k}=y_{i,k-1}-{\eta }_l(g_i(y_{i,k-1})-c_i+c)\mathrm{.}$ After its $K$ local steps, a selected client updates its control using either

• Option I: call $g_i$ at the round-start model $x_{r-1}$ and set $c_i^{+}=g_i(x)$; or
• Option II: set $c_i^{+}=c_i-c+(K{\eta }_l{)}^{-1}(x-y_{i,K})$.

The client sends $\mathrm{\Delta }{x}_i=y_{i,K}-x$ and $\mathrm{\Delta }{c}_i=c_i^{+}-c_i$. Unselected clients retain their controls. The server forms $\mathrm{\Delta }x=\frac{1}{S}{\sum }_{i\in {\mathcal{S}}_r}\mathrm{\Delta }{x}_i,\mathrm{\Delta }c=\frac{1}{S}{\sum }_{i\in {\mathcal{S}}_r}\mathrm{\Delta }{c}_i$ and updates $x_r=x+{\eta }_g\mathrm{\Delta }x,c^r=c^{r-1}+\frac{S}{N}\mathrm{\Delta }c\mathrm{.}$ The selected clients set $c_i^r=c_i^{+}$ and unselected clients set $c_i^r=c_i^{r-1}$. Thus $c^r=N^{-1}{\sum }_i{c}_i^r$ whenever $c^{r-1}=N^{-1}{\sum }_i{c}_i^{r-1}$ held before the round. The general procedure permits zero initial controls; the convergence rates stated below use the explicitly stated gradient-consistent initialization $c_i^0=\mathrm{\nabla }{f}_i(x_0)$. Repeat through round $R$ and return the model and control trajectories $((x_r,c^r,(c_i^r{)}_{i=1}^N){)}_{r=0}^R$.

The following schematic records only the communication flow. Its vertices are the server and the selected clients; the arrow labels are exactly the quantities sent in each direction. The local updates and server equations above, not the schematic, define the procedure.

Equal-client objective and fixed-size client sampling

Karimireddy et al., SCAFFOLD, §§4–5 and Algorithm 1

Gorbunov et al., Local SGD: Unified Theory and New Efficient Methods, §4.2

Chi and Li, Advances in Federated Optimization, slides 34–35

Yuan, Optimization for Deep Learning, Lecture 14: Federated Learning, slides 24–30

Theorem III's rates below do not assume bounded gradient dissimilarity. The separate Hessian-dissimilarity improvement in Theorem IV is proved only for quadratic client functions and is not asserted here for general smooth losses. The procedure transmits model and control updates but supplies no differential-privacy guarantee.

Karimireddy et al., SCAFFOLD, Theorems III–IV and §4