Standard client dissimilarity implies the gap form with unchanged parameters

Let $N,d\ge 1$ be positive integers, let $\beta >0$, and let $f_i:{\mathbb{R}}^d\to \mathbb{R}$ be differentiable with $\beta$-Lipschitz gradients. Put $f=N^{-1}{\sum }_i{f}_i$, and suppose $f(x)\ge f^{\star }$ for all $x$, where $f^{\star }\in \mathbb{R}$ is finite. Then $\mathrm{\parallel }\mathrm{\nabla }f(x){\mathrm{\parallel }}_2^2\le 2\beta (f(x)-f^{\star })(x\in {\mathbb{R}}^d)\mathrm{.}$ Consequently, if the clients satisfy standard $(G,B)$-bounded gradient dissimilarity, with $G\ge 0$ and $B\ge 1$, they satisfy the gap-form condition with exactly the same $G,B,\beta ,f^{\star }$: $\frac{1}{N}{\sum }_i\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{.}$ No convexity or attainment of the lower bound is required for this implication.

Standard and gap forms of bounded client gradient dissimilarity

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

The reverse implication with the same parameters need not hold, even for strongly convex clients. For example, on $\mathbb{R}$ take $f_1(x)=x^2\mathrm{/}2$ and $f_2(x)=3x^2\mathrm{/}2$. Their equal-client mean is $f(x)=x^2$, its minimum is $0$, and both clients are $1$-strongly convex and $3$-smooth. The population gradient second moment is $5x^2$, while $\mathrm{\parallel }\mathrm{\nabla }f(x){\mathrm{\parallel }}_2^2=4x^2$. The gap form holds with $G=0,B=1,\beta =3$ because $5x^2\le 6x^2$, whereas the standard form with the same $G,B$ would require $5x^2\le 4x^2$. Keeping the gap branch therefore retains instances beyond the same-parameter standard condition.