Federated averaging (FedAvg)

The inputs are positive integers $N,d,R,K,S$ with $1\le S\le N$, an initial server model $x_0\in {\mathbb{R}}^d$, client objectives for the chosen mode and their local oracle procedures $g_i$, positive step sizes ${\eta }_l,{\eta }_g$, and one aggregation mode from the two modes below. In count-weighted deployment mode the objectives are $F_i$ and the inputs also include positive integer record counts $n_1,\dots ,n_N$, with $n={\sum }_i{n}_i$. A call to $g_i$ returns a gradient vector according to its supplied deterministic or stochastic local-oracle rule; the client-sample randomness in a round is independent of that round's fresh oracle randomness. In uniform-client analysis mode the objectives are $f_i$.

For each round $r=1,\dots ,R$, independently draw a uniform fixed-size subset ${\mathcal{S}}_r$ of $S$ clients from $\{1,\dots ,N\}$. For every selected client $i$, initialize $y_{i,0}=x_{r-1}$ and for $k=1,\dots ,K$ call $g_i$ at $y_{i,k-1}$ and update $y_{i,k}=y_{i,k-1}-{\eta }_l{g}_i(y_{i,k-1}),1\le k\le K,$ The client sends its model difference $y_{i,K}-x_{r-1}$ to the server. Use one of the following aggregation branches in every round:

1. Count-weighted deployment mode. With positive client record counts $n_i$ and $n={\sum }_i{n}_i$, set $x_r=x_{r-1}+{\eta }_g{\sum }_{i\in {\mathcal{S}}_r}\frac{n_i}{n}(y_{i,K}-x_{r-1})\mathrm{.}$ Equivalently, each unselected client contributes its unchanged model $x_{r-1}$ to the full count-weighted average.

2. Uniform-client analysis mode. Set $x_r=x_{r-1}+\frac{{\eta }_g}{S}{\sum }_{i\in {\mathcal{S}}_r}(y_{i,K}-x_{r-1})\mathrm{.}$ The equal-client convergence result on this page uses this mode and the objective $f=N^{-1}{\sum }_i{f}_i$.

After the selected clients finish the round, apply the chosen branch to obtain $x_r$. Repeat through round $R$. Return the finite server trajectory $x_0,\dots ,x_R$.

Federated objectives and uniform client sampling

McMahan et al., PMLR 54 (2017), §2 and Algorithm 1

Karimireddy et al., SCAFFOLD, Algorithm 2

Chi and Li, Advances in Federated Optimization, slides 29–31

Yuan, Optimization for Deep Learning, Lecture 14: Federated Learning, slides 7–16 and 28–30

The count-weighted deployment mode and uniform-client analysis mode are different update rules when the $n_i$ are unequal. The strongly convex rate proved on this page applies only to the uniform-client mode and the equal-client objective. McMahan et al. give the algorithm and empirical experiments; those experiments do not prove a general convergence rate or a differential-privacy guarantee.

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