SCAFFOLD trajectories, client drift, control lag and tracking error

Let $N,d,K,R\ge 1$ be positive integers and let $1\le S\le N$. Let $f_i:{\mathbb{R}}^d\to \mathbb{R}$ be differentiable client objectives and $f=N^{-1}{\sum }_{i=1}^N{f}_i$. Run SCAFFOLD for $R$ rounds with local step count $K$, client sample size $S$, server iterates $x_0,\dots ,x_R$, and client controls $c_i^r$ after round $r$. In each round, extend the local trajectory $y_{i,0}^r=x_{r-1},y_{i,1}^r,\dots ,y_{i,K}^r$ to every client using the same local update rule, including hypothetical paths for clients not selected in that round. Generate these counterfactual paths using fresh local oracle randomness independently of the fresh client sample, so a selected path agrees with its actual local execution. Local paths use only the round-start model and controls and their own successive oracle draws. Oracle moment conditions in the results below are conditional on the full prequery history, including any earlier revealed draws in the current round. All expectations below are over client samples and local stochastic-gradient draws.

The round-$r$ client drift at gradient-query points is $E_r=\frac{1}{KN}{\sum }_{i=1}^N{\sum }_{k=1}^K\mathbb{E}\mathrm{\parallel }{y}_{i,k-1}^r-x_{r-1}{\mathrm{\parallel }}_2^2\mathrm{.}$ For every client and local-step index, initialize a stored anchor ${\alpha }_{i,k}^0=x_0$ and stored gradient ${\gamma }_{i,k}^0=\mathrm{\nabla }{f}_i(x_0)$. After round $r$, if client $i$ was selected, set ${\alpha }_{i,k}^r=y_{i,k-1}^r$ and let ${\gamma }_{i,k}^r$ be the actual stochastic gradient draw used at that local query. If client $i$ was not selected, retain both previous stored values. Thus the anchors and stored gradients record the most recent query and its realized oracle output for each local-step index.

When $f$ is convex with minimizer $x^{\star }$, the round-$r$ convex control lag is the average second moment of the mean full-gradient error at the stored anchors: $C_r=\frac{1}{N}{\sum }_{i=1}^N\mathbb{E}{\parallel \frac{1}{K}{\sum }_{k=1}^K\mathrm{\nabla }{f}_i({\alpha }_{i,k}^r)-\mathrm{\nabla }{f}_i(x^{\star })\parallel }_2^2\mathrm{.}$ For the nonconvex analysis, the round-$r$ control-tracking error is ${\mathrm{\Xi }}_r=\frac{1}{KN}{\sum }_{i=1}^N{\sum }_{k=1}^K\mathbb{E}\mathrm{\parallel }{\alpha }_{i,k}^r-x_r{\mathrm{\parallel }}_2^2\mathrm{.}$ Thus ${\mathrm{\Xi }}_0=0$ and each stored anchor records the point at which that client's corresponding control-gradient sample was evaluated.

The query-point indexing in $E_r$ is deliberate: the gradient-difference terms in the variance and drift recurrences are evaluated at $y_{i,k-1}^r$. It is not interchangeable with an average over the post-update endpoints $y_{i,k}^r$.

SCAFFOLD local updates, control updates and server update

Equal-client objective and fixed-size client sampling

Karimireddy et al., SCAFFOLD, Appendix E.1–E.2, equations (23)–(27)

The local $C_r$ retains the randomness of the stored anchors inside the squared norm. Source equation (24) instead prints the squared norm of an expected control; the two quantities are different. The local definition above is the interface used in every local control-lag, drift and progress argument.