Exercises — Federated learning

The weight for client $k$ is the fraction $\frac{n_k}{n}$. First the total: $n=200+300+500=1000.$ Then each weight: $w_1=\frac{200}{1000}=0.2,w_2=\frac{300}{1000}=0.3,w_3=\frac{500}{1000}=\mathrm{0.5.}$ They sum to $0.2+0.3+0.5=1$, which they must — a weighted average always has weights adding to $1$. Client 3 pulls the model hardest because it holds half the data.

The client sends back its updated model weights ${\theta }_k^{(t+1)}$ (and its count $n_k$) and keeps its raw data ${\mathcal{D}}_k$ on-device. That is the whole point — "bring the model to the data," not data to the model. This is the reason federated learning is a Privacy-Preserving ML method by default.

The denominator is the total data of the selected clients only — i.e. summed over ${\mathcal{S}}_t=\{A,B\}$: $n_{{\mathcal{S}}_t}=n_A+n_B=100+300=400.$ Now the weighted average: ${\theta }^{(t+1)}=\frac{100}{400}(4.0)+\frac{300}{400}(8.0)=0.25\cdot 4.0+0.75\cdot 8.0=1.0+6.0=\mathrm{7.0.}$ Read the figure below. It draws A at $4.0$ and B at $8.0$ on a number line (cyan dots) with the aggregate as an amber square. Because B's weight is $\frac{300}{400}=\frac{3}{4}$ and A's is only $\frac{1}{4}$, the amber square does not land at the midpoint $6.0$; it lands at $7.0$, which is exactly $\frac{3}{4}$ of the way along the arrow from A to B. The picture makes concrete what the fraction $\frac{n_k}{n_{{\mathcal{S}}_t}}$ does: the bigger client literally pulls the answer toward itself.

Local steps first (each client does ${\theta }_k={\theta }^{(t)}-\eta \nabla F_k$): ${\theta }_1=10-0.5(2)=9,{\theta }_2=10-0.5(6)=7.$ Aggregate (equal weights): ${\theta }^{(t+1)}=\frac{1}{2}(9)+\frac{1}{2}(7)=8.$ Now the direct GD step on $F$. The global gradient is the weighted average of local gradients: $\nabla F=\frac{1}{2}(2)+\frac{1}{2}(6)=4,{\theta }^{(t)}-\eta \nabla F=10-0.5(4)=8.$ Same answer, $8$. This is the algebraic identity from the parent note: with $E=1$, FedAvg is one step of gradient descent on $F$. The averaging of models and the averaging of gradients commute because a step is linear in the gradient.

(a) One full model $=11\times 10^6\times 4=44\times 10^6$ bytes. Converting: $44\times 10^6÷10^6\frac{\text{bytes}}{\text{MB}}=44\text{MB}$. Down + up $=88\text{MB}=88\times 10^6$ bytes per client per round. (b) Per round for $100$ clients: $100\times 88\times 10^6=8.8\times 10^9$ bytes. Converting by dividing by $10^9$: $8.8\text{GB}$. Over $50$ rounds: $50\times 8.8\times 10^9=4.4\times 10^{11}$ bytes $=440\text{GB}$. (c) Raw data: $10^6\times 150,000=1.5\times 10^{11}$ bytes. Watch the unit conversion carefully: to read this in gigabytes we divide by $10^9$ (the number of bytes in one GB), not by $10^{12}$ (which would be terabytes): $1.5\times 10^{11}\text{bytes}÷10^9\frac{\text{bytes}}{\text{GB}}=150\text{GB}.$ (In terabytes it would be a mere $1.5\times 10^{11}÷10^{12}=0.15\text{TB}$.) So the raw dataset is $150\text{GB}$, not $150\text{TB}$ — a factor-of-1000 unit trap to avoid. (d) Ratio, both in the same unit: $\frac{150\text{GB}}{440\text{GB}}\approx \mathrm{0.341.}$ So the raw upload is actually smaller than 50 rounds of full-model federated traffic here — about $0.34\times$ the size. This is a genuine and important lesson: federated learning is not automatically cheaper on bandwidth. It pays per round in model-sized chunks, so with a large model, many clients, and many rounds the totals can exceed one-time raw upload. Federated learning's real wins are privacy and regulation; to also win on bandwidth you must cut rounds (larger $E$), sample fewer clients, or shrink each upload with Model Compression.

The two terms tell opposite stories. The first term $c_1/T$ shrinks as you run more rounds — pure "keep talking, keep improving." The second term $c_2{E}^2{\eta }^2{\sigma }^2$ is the local-drift error floor: when clients do many local epochs $E$, each one wanders toward its own optimum before the server can re-sync them, and the gradient noise $\sigma$ amplifies that wandering. It grows like $E^2$, so it punishes large $E$ hard. Bigger $E$ means you need fewer rounds $T$ (less communication) but you sit on a higher floor.

Numbers. Drift floor $=c_2{E}^2{\eta }^2{\sigma }^2=0.001\cdot E^2\cdot (0.1{)}^2\cdot (2{)}^2=0.001\cdot E^2\cdot 0.01\cdot 4=4\times 10^{-5}{E}^2$.

• $(T=100,E=1)$: $\frac{1}{100}+4\times 10^{-5}(1{)}^2=0.01+0.00004=0.01004$.
• $(T=25,E=10)$: $\frac{1}{25}+4\times 10^{-5}(100)=0.04+0.004=0.044$.

Read the figure below. It plots the bound as a function of rounds $T$ for the two choices of $E$. The cyan curve ($E=1$) hugs a nearly-zero dashed floor and, by $T=100$ (cyan dot), has dropped to $0.01004$. The amber curve ($E=10$) sits on a visibly higher dashed floor (the $E^2$ term is 100× bigger), and even at $T=25$ (amber square) the $1/T$ term hasn't shrunk much, landing at $0.044$. The eye sees the trade instantly: the second setup uses 4× fewer rounds but its bound is $\approx 4.4\times$ larger — the $1/T$ term ballooned (fewer rounds) and the drift floor jumped 100× (because $E^2$ went $1\to 100$). So fewer rounds isn't free.

(a) Un-weighted (each of 100 clients gets weight $1/100$): $\theta =\frac{1}{100}(99\cdot 5.0+1\cdot 100.0)=\frac{495+100}{100}=\frac{595}{100}=\mathrm{5.95.}$ The outlier — with almost no data — dragged the answer nearly a whole unit off the true $5.0$. (b) Data-weighted FedAvg. Total data $n=99\cdot 1000+10=99,010$. $\theta =\frac{99\cdot 1000\cdot 5.0+10\cdot 100.0}{99,010}=\frac{495,000+1000}{99,010}=\frac{496,000}{99,010}\approx \mathrm{5.0096.}$ The weighted answer is essentially $5.01$ — the outlier's influence is $\frac{10}{99010}\approx 0.0001$, i.e. $0.01\%$, so it barely moves the result. Takeaway: data-weighting is the built-in defense against low-data noisy clients. (For malicious high-data clients you need a different tool — Byzantine Robust Learning with median/trimmed aggregation, since weighting alone won't stop an attacker who fakes a large $n_k$.)

(a) Noise std $=\sigma S=0.05\times 1.0=0.05$. (b) Averaging $m$ independent noises with equal weight divides variance by $m$, so the std divides by $\sqrt{m}$: ${\text{std}}_{\text{avg}}=\frac{\sigma S}{\sqrt{m}}=\frac{0.05}{\sqrt{400}}=\frac{0.05}{20}=\mathrm{0.0025.}$ So it shrinks by a factor of $\sqrt{400}=20$. This is why federated DP scales: each client can add just enough noise for its own privacy (its own $ϵ$), yet after aggregating hundreds of clients the global model is barely perturbed. Clipping to $S$ is what makes the required noise finite — an un-clipped update could be arbitrarily large and would need infinite noise to hide, i.e. no achievable $ϵ$.

1. Objective & weighting. Minimize $F(\theta )={\sum }_k\frac{n_k}{n}{F}_k(\theta )$, weighting each phone by its keystroke count $n_k$ (L1.1, L4.1 show why: it neutralizes low-data noisy clients — the outlier's pull dropped to $0.01\%$).

2. Client sampling (and the empty-set edge case). Never touch all $2\times 10^9$ phones per round — sample a set ${\mathcal{S}}_t$ of a few hundred to a few thousand devices, and only those that are idle, charging, on Wi-Fi (edge constraints). Random diverse sampling also averages over label skew (different languages/users). Degenerate case — what if ${\mathcal{S}}_t=\varnothing$? If no eligible device responds (all offline / a dead network window), the FedAvg denominator $n_{{\mathcal{S}}_t}={\sum }_{j\in {\mathcal{S}}_t}{n}_j=0$, and the update ${\theta }^{(t+1)}=\frac{1}{0}(\cdots )$ is undefined — a division by zero. The safe rule: detect ${\mathcal{S}}_t=\varnothing$ (or too few responders below a quorum) and skip the round entirely, keeping ${\theta }^{(t+1)}={\theta }^{(t)}$ unchanged, then retry later. Never let the aggregator run with an empty or below-quorum set.

3. Local epochs $E$. Choose a moderate $E\approx 5$. From L3.2, the drift floor grows like $E^2{\eta }^2{\sigma }^2$; on highly non-IID typing data (each user a different vocabulary) large $E$ makes clients over-fit their own text before sync, so keep $E$ small-to-moderate rather than maxing it.

4. Communication budget. Cost per round $\approx |{\mathcal{S}}_t|\times 2\times (\text{model bytes})$ (L3.1). Because L3.1 showed federated traffic is not automatically cheaper than raw upload, this must be budgeted deliberately: shrink each uploaded delta with Model Compression (quantize to fewer bits), sample fewer devices, and cut rounds using a moderate $E$ — but not so large that L3.2's error floor dominates. This is the round-count vs drift trade-off, spent on purpose.

5. Privacy. Raw text never leaves the phone, but that alone is not private (recall the L1 trap: gradient-inversion attacks reconstruct typed text from a single update). So layer on Differential Privacy with an explicit budget, e.g. $ϵ\approx 2.7$, $\delta =10^{-9}$ (small $ϵ$ = strong privacy, tiny $\delta$ = negligible failure probability, per the L4 definition). On each device, clip the update to norm $S$ then add Gaussian noise scaled to $S$. This works at scale precisely because of L4.2: each phone adds enough noise for its own $(ϵ,\delta )$ guarantee, but when the server averages $m$ contributions the injected noise shrinks like $\sigma S/\sqrt{m}$ — with $m=400$ that is $0.05\to 0.0025$, negligible against real gradient magnitudes. Net result: provable per-user privacy at almost no accuracy cost. This is the Privacy-Preserving ML backbone of the whole design.

6. Non-IID handling. Typing data is extremely heterogeneous — different languages, slang, names — so the per-client divergence ${\delta }_k=\Vert {\theta }_k^{\ast }-{\theta }^{\ast }{\Vert }^2$ is large and clients pull in conflicting directions (slower convergence, higher L3.2 drift). Three concrete mitigations: (i) keep $E$ modest so clients don't over-commit to their own optimum before syncing; (ii) sample a diverse ${\mathcal{S}}_t$ each round so the aggregate averages over language/skew; (iii) split the model into a shared federated backbone plus a small per-user personalized head kept on-device — a Multi-Task Learning view where the common trunk trains federated while each user's head adapts locally. This preserves one global model of shared language structure while respecting each user's idiosyncratic vocabulary.

Sanity number tying it together: with the L4.2 setup, averaging $m=400$ noisy clients cuts the injected std from $0.05$ to $0.0025$ — confirming the privacy layer (5) is affordable, so the design meets all six requirements at once. (Note: DP handles privacy but not malicious clients faking a huge $n_k$; that orthogonal threat needs Byzantine Robust Learning — see the L5 trap.)

FedAvg denominator ::: sum of the selected clients' $n_k$, i.e. $n_{{\mathcal{S}}_t}$ over the set ${\mathcal{S}}_t$ — never the client count $N$. Empty selected set ${\mathcal{S}}_t=\varnothing$ ::: denominator is $0$, update undefined — skip the round and keep ${\theta }^{(t+1)}={\theta }^{(t)}$. Why $E=1$ FedAvg equals GD ::: averaging models and averaging gradients commute because one SGD step is linear in the gradient. The two convergence terms ::: $c_1/T$ shrinks with more rounds; $c_2{E}^2{\eta }^2{\sigma }^2$ is the local-drift floor (${\sigma }^2$ = stochastic-gradient variance) that grows with $E$. Federated bandwidth ::: NOT automatically cheaper — L3.1 gave ratio $\approx 0.34$ (raw upload smaller); wins are privacy/regulation, bandwidth needs compression/fewer rounds. DP budget $(ϵ,\delta )$ ::: small $ϵ$ = strong privacy (output barely reacts to one person); $\delta$ = tiny failure slack. DP noise after averaging $m$ clients ::: std shrinks by $\sqrt{m}$ (from $\sigma S$ to $\sigma S/\sqrt{m}$). Weighting vs robustness ::: data-weighting stops low-data noisy clients; malicious clients need Byzantine-robust aggregation.