Standard and gap forms of bounded client gradient dissimilarity

Let $N,d\ge 1$ be positive integers, let $f_i:{\mathbb{R}}^d\to \mathbb{R}$ be differentiable, and put $f=N^{-1}{\sum }_{i=1}^N{f}_i$. For constants $G\ge 0$ and $B\ge 1$, the clients have standard $(G,B)$-bounded gradient dissimilarity if $\frac{1}{N}{\sum }_{i=1}^N\mathrm{\parallel }\mathrm{\nabla }{f}_i(x){\mathrm{\parallel }}_2^2\le G^2+B^2\mathrm{\parallel }\mathrm{\nabla }f(x){\mathrm{\parallel }}_2^2(x\in {\mathbb{R}}^d)\mathrm{.}$

For $\beta >0$ and a finite global lower bound $f^{\star }\in \mathbb{R}$ for $f$, the gap-form condition with parameters $(G,B,\beta ,f^{\star })$ is $\frac{1}{N}{\sum }_{i=1}^N\mathrm{\parallel }\mathrm{\nabla }{f}_i(x){\mathrm{\parallel }}_2^2\le G^2+2\beta B^2(f(x)-f^{\star })(x\in {\mathbb{R}}^d)\mathrm{.}$ In the convex-client FedAvg results, $\beta$ is a common gradient Lipschitz constant and $f^{\star }$ is the attained minimum of $f$; this is the relaxed convex form of the source's assumption. These conditions bound the population second moment of deterministic client gradients. They are separate from the within-client stochastic-gradient noise bound $\mathbb{E}\mathrm{\parallel }{g}_i(x)-\mathrm{\nabla }{f}_i(x){\mathrm{\parallel }}_2^2\le {\sigma }^2$.

Karimireddy et al., SCAFFOLD, Section 2 (A1)

Karimireddy et al., SCAFFOLD, Appendix D.1, equations (13)–(14)