Federated objectives and client sampling

Let $N,d\ge 1$, let each client $i\in \{1,\dots ,N\}$ have a positive integer sample count $n_i$, and put $n={\sum }_{i=1}^N{n}_i$. For differentiable client objectives $F_i:{\mathbb{R}}^d\to \mathbb{R}$, the sample-count-weighted deployment objective is $f_{\mathrm{w}\mathrm{t}}(w)={\sum }_{i=1}^N\frac{n_i}{n}{F}_i(w)\mathrm{.}$ For differentiable client objectives $f_i:{\mathbb{R}}^d\to \mathbb{R}$, the equal-client objective is $f(w)=\frac{1}{N}{\sum }_{i=1}^N{f}_i(w)\mathrm{.}$ The symbols $F_i$ and $f_i$ denote separate families; they are not identified unless an application states $F_i=f_i$. In general, $f_{\mathrm{w}\mathrm{t}}$ and $f$ are different objectives.

For integers $1\le S\le N$, a uniform fixed-size client sample is a random subset $\mathcal{S}\subseteq \{1,\dots ,N\}$ of cardinality $S$ for which every $S$-element subset has probability ${\left(\genfrac{}{}{0px}{}{N}{S}\right)}^{-1}$. This is sampling without replacement. When several communication rounds are used, the sampled subsets are independent across rounds unless a theorem states a different sampling law.

McMahan et al., PMLR 54 (2017), §§1–4

Karimireddy et al., SCAFFOLD, §§2–3

Yuan, Optimization for Deep Learning, Lecture 14: Federated Learning, slides 7–8