One-round progress of strongly convex FedAvg

Assume the Axiom of Choice. Let $N,d,K\ge 1$ be positive integers and $1\le S\le N$. Let $f_i:{\mathbb{R}}^d\to \mathbb{R}$ be differentiable, $\mu$-strongly convex and $\beta$-smooth, with $0<\mu \le \beta$, and put $f=N^{-1}{\sum }_{i=1}^N{f}_i$. Suppose $f$ attains its minimum at $x^{\star }$ with value $f^{\star }$. At a round-start server point $x$, run the uniform-client analysis mode of FedAvg with $S$ clients sampled uniformly without replacement, $K$ local steps, local step ${\eta }_l>0$, and global scale ${\eta }_g\ge \sqrt{S}$. The client sample is independent of the fresh local-oracle randomness. Assume conditionally unbiased local stochastic gradients with within-client conditional variance at most ${\sigma }^2$. These moment conditions are conditional on the full prequery history: the round-start history, the client sample, and all earlier revealed oracle draws from every client in a fixed chronological ordering of the queries. Suppose $B\ge 1$, $G\ge 0$, and $\frac{1}{N}{\sum }_i\mathrm{\parallel }\mathrm{\nabla }{f}_i(z){\mathrm{\parallel }}_2^2\le G^2+2\beta B^2(f(z)-f^{\star })(z\in {\mathbb{R}}^d)\mathrm{.}$ Alternatively, assume the standard $(G,B)$-bounded gradient-dissimilarity condition $\frac{1}{N}{\sum }_i\mathrm{\parallel }\mathrm{\nabla }{f}_i(z){\mathrm{\parallel }}_2^2\le G^2+B^2\mathrm{\parallel }\mathrm{\nabla }f(z){\mathrm{\parallel }}_2^2(z\in {\mathbb{R}}^d)\mathrm{.}$ Either assumption gives all the conclusions below with the same $G,B$ and stepsize restrictions. Let $\tilde{\eta }=K{\eta }_l{\eta }_g$. For each client $i$, define a hypothetical local path $y_{i,0}=x,y_{i,1},\dots ,y_{i,K}$ by the same local update rule with fresh oracle draws independent of the client sample. For selected clients this path is the actual local execution; for unselected clients it is a counterfactual copy used only in the expectation below. Independence among different clients' oracle draws is not required, but the stated full-history conditional moment conditions must hold for the counterfactual queries too. Define $E=\frac{1}{KN}{\sum }_{i=1}^N{\sum }_{k=1}^K\mathbb{E}\mathrm{\parallel }{y}_{i,k-1}-x{\mathrm{\parallel }}_2^2\mathrm{.}$ If $0<\tilde{\eta }\le [32(B^2+1)\beta {]}^{-1}$, then the next server iterate $x^{+}$ satisfies $\begin{array}{rl}{\displaystyle \mathbb{E}\mathrm{\parallel }{x}^{+}-x^{\star }{\mathrm{\parallel }}_2^2}& {\displaystyle \le (1-\mu \tilde{\eta }\mathrm{/}2)\mathrm{\parallel }x-x^{\star }{\mathrm{\parallel }}_2^2-\tilde{\eta }(f(x)-f^{\star })+\frac{5{\tilde{\eta }}^2{\sigma }^2}{KS}+8(1-\frac{S}{N})\frac{{\tilde{\eta }}^2{G}^2}{S}+3\beta \tilde{\eta }E\mathrm{.}}\end{array}$ Expectation is conditional on the round-start history and averages the client sample and local stochastic-gradient draws.

Standard and gap forms of bounded client gradient dissimilarity

Standard client dissimilarity implies the gap form with unchanged parameters

Karimireddy et al., SCAFFOLD, Appendix D.3, Lemma 7 and its proof