Exercises

1. Data location. Data-center SGD: data shuffled across workers. FL: data stays on user devices.
2. Participation. Data-center: all workers participate every iteration. FL: a subset ($C \cdot n$) per round.
3. Heterogeneity. Data-center: homogeneous GPUs, fast network. FL: heterogeneous devices, slow / unreliable uplinks.

$C n = 100$ users upload. $100 \cdot 10^7 \cdot 32 = 3.2 \cdot 10^{10}$ bits per round = 4 GB.

$200$ rounds × $4$ GB = 800 GB aggregate uplink. Per-user average: $800 / 1000 = 0.8$ GB per user over the full training (some users are selected more often, others less).

FedAvg replaces $E$ individual gradient exchanges with a single model-update exchange. Each round does $E$ local SGD steps but only one upload.

$E\times$ reduction in total rounds needed (on i.i.d. data) gives $E\times$ total communication savings. On non-IID data, savings are limited by client drift.

Quantization maps each scalar to a finite alphabet, saving bandwidth. The quantized gradient is still statistically informative about the underlying data — gradient inversion attacks recover the sample with minor quality degradation.

True privacy requires either information-theoretic masking (secure aggregation) or randomization (differential privacy). Mere bandwidth reduction does not suffice.

$\mathbb{E}[F(\mathbf{w}_T) - F(\mathbf{w}^*)] \leq \frac{\kappa^2}{T + t} \cdot (\sigma^2 E / (Cn) + G^2)$.

FedAvg's update is an unbiased + bounded-variance estimator of the centralized SGD step. The effective variance includes an $E$-dependent term from local steps; on i.i.d. data, this variance is bounded. Standard SGD analysis with bounded variance gives $O(1/T)$ convergence.

On i.i.d. data, $E$ local epochs are "free" in terms of convergence rate (only constants change). On non-IID data, the heterogeneity $\Gamma$ term enters and constrains $E$.

Each scalar gets rounded to one of $2^b$ evenly- spaced levels in $[-R, R]$. Level spacing $\Delta = 2R/2^b$. Per-scalar quantization error is uniform in $[-\Delta/2, \Delta/2]$; variance $\Delta^2 / 12 = R^2 / (3 \cdot 4^b)$.

Independent errors across scalars: total variance $d \cdot R^2 / (3 \cdot 4^b)$.

SGD with quantized gradients has a variance floor proportional to this quantity. For $b = 8$, $1/4^b \approx 10^{-5}$ — variance floor dominated by inherent stochastic noise. For $b = 1$, $1/4 = 0.25$ — significant.

See §9.3 Algorithm: accumulate discarded entries in e; add e to next gradient; sparsify; update e with new discarded entries.

Without error feedback, the discarded entries are permanently lost. The sparsified gradient is a biased estimate of the true gradient — SGD converges to a biased optimum. Error feedback ensures all gradient entries are eventually transmitted (just with delay), recovering asymptotic unbiasedness.

Stich et al. 2018 prove that Top-$K$ with error feedback matches baseline SGD convergence rate on strongly-convex problems. The proof uses the error buffer's bounded norm to control the bias.

Savings: $32/4 = 8\times$.

Keep $d/100 = 10^6$ entries. Indexing overhead: $\log_2 d = 27$ bits per kept entry. Total: $10^6 \cdot (32 + 27) = 5.9 \cdot 10^7$ bits vs. $32 \cdot 10^8 = 3.2 \cdot 10^9$ original. Savings: $54\times$.

Top-1% then 4-bit quantize the kept values: $10^6 \cdot (4 + 27) = 3.1 \cdot 10^7$ bits. Savings: $3.2 \cdot 10^9 / 3.1 \cdot 10^7 = 103\times$.

Composition is multiplicative in effect but the fixed indexing overhead ($\log d$ per kept entry) limits the combined savings as sparsification becomes aggressive.

Given $\mathbf{g}_k$, $\mathbf{w}$, and the loss $\ell$, minimize $\|\nabla \ell(\mathbf{w}; \hat\xi) - \mathbf{g}_k\|^2$ over $\hat\xi$ via gradient descent.

The gradient $\mathbf{g}_k = \nabla \ell(\mathbf{w}; \xi_k)$ is a deterministic function of $(\mathbf{w}, \xi_k)$. For generic models, this function is (locally) invertible. The optimization landscape has a unique global minimum at $\hat\xi = \xi_k$.

With batch size $B$, the target is $(1/B) \sum_{i=1}^B \nabla \ell(\mathbf{w}; \xi_{k,i})$ — $B$ superimposed signals. The attack must jointly reconstruct all $B$ samples. For $B$ small (up to $\sim 48$), this works; for large $B$, reconstructions degrade.

Data $\mathcal{D}_k$ never leaves user $k$'s device. Only gradient updates $\mathbf{g}_k$ are sent.

$\mathbf{g}_k$ is a deterministic function of $\mathcal{D}_k$ (and $\mathbf{w}$). By the data processing inequality, $\mathbf{g}_k$ can reveal at most as much information as $\mathcal{D}_k$ — but "at most as much" can be all of it. Empirically, gradient inversion recovers training samples.

Raw data locality is not privacy. Privacy requires destroying information about $\mathcal{D}_k$ that leaves the device. Secure aggregation does this by masking; differential privacy does this by adding noise.

With $E$ local SGD epochs, user $k$ makes progress toward its local optimum $\mathbf{w}_k^*$, not the global optimum $\mathbf{w}^*$. For non-IID data, $\mathbf{w}_k^* \neq \mathbf{w}^*$.

FedAvg averages the user-local models: $\mathbf{w}_{t+1} = \sum_k (n_k/n_{\text{tot}}) \mathbf{w}_t^{(k)}$. As $E \to \infty$, $\mathbf{w}_t^{(k)} \to \mathbf{w}_k^*$, so $\mathbf{w}_{t+1} \to \sum_k (n_k/n_{\text{tot}}) \mathbf{w}_k^*$ — the weighted average of user-local optima, not the global optimum.

Bias $\|\mathbf{w}_\infty - \mathbf{w}^*\|$ scales with the heterogeneity $\Gamma = F(\mathbf{w}^*) - \sum_k (n_k/n_{\text{tot}}) F_k(\mathbf{w}_k^*)$. For IID data, $\Gamma = 0$; for highly non-IID, $\Gamma$ is large. FedProx and SCAFFOLD address this by regularization and variance reduction.

Selected users: $Cn = 10^4$. Quantized: $8 \cdot 10^9 = 8 \cdot 10^9$ bits per full gradient. Sparsified to 1%: $10^7$ kept entries, each $8 + 30 = 38$ bits (value + index), total $3.8 \cdot 10^8$ bits = $47.5$ MB per user per round.

$10^4$ users × $47.5$ MB = $475$ GB per round.

$100$ rounds × $475$ GB = $47.5$ TB aggregate uplink across all selected users.

For a $10^6$-user population with 1% participation (= 10,000 active per round), the aggregate traffic is substantial even with aggressive compression. Adding secure aggregation (Chapter 10) roughly doubles the cost (pairwise masks). Per-user budget: $47.5$ MB per round × ~$1$ round per user = $47.5$ MB total. Feasible for Wi-Fi, challenging for 4G.

Dataset: CIFAR-10 or ImageNet-100 (subset). Architecture: ResNet-18 or LeNet-5 (smaller for speed). Training sample: randomly select one image from the dataset.

Given the per-sample gradient, initialize a random image. Minimize $\|\nabla \ell(\mathbf{w}; \hat\xi) - \mathbf{g}\|^2$ via Adam (learning rate $0.1$, 500 iterations). Include a regularizer to encourage valid pixel values (e.g., total-variation regularization).

Compare $\hat\xi$ to the original sample. Metrics:

• Pixel-level MSE or PSNR.
• Cosine similarity in feature space (via a pre-trained classifier).
• Visual inspection.

For LeNet on CIFAR-10, expect PSNR >30 dB and near-pixel-perfect reconstruction.

Increase batch size $B = 1, 2, 4, \ldots, 64$ and measure reconstruction quality. Plot $\text{PSNR}$ vs. $B$ — a direct empirical verification of the §9.4 theorem.

Aggressive compression destroys information; therefore it destroys privacy-sensitive info too. Should improve privacy.

Compression keeps the largest-magnitude entries (top-$K$ sparsification) or the sign (1-bit quantization). These high-information features are precisely the ones most correlated with the training sample. The low-magnitude entries — which do little to distinguish samples — are discarded.

The compressed gradient may be more informative per-bit about the sample than the full gradient. Empirical evidence: 1-bit SignSGD gradients still allow inversion, sometimes with higher efficiency than full gradients (fewer optimization iterations needed for the attacker).

Compression-as-privacy is not just insufficient — it can be counterproductive. Always pair compression with explicit privacy mechanisms (secure aggregation, DP).

Measure leakage: $I(\xi; \mathbf{g}) = H(\xi) - H(\xi \mid \mathbf{g})$. For full leakage, $H(\xi \mid \mathbf{g}) = 0$ (no ambiguity after seeing gradient). For zero leakage, $H(\xi \mid \mathbf{g}) = H(\xi)$ (gradient uninformative).

For deterministic loss and architecture, the gradient is a deterministic function of $\xi$. If invertible, $I(\xi; \mathbf{g}) = H(\xi)$ — full leakage. Non-invertibility arises for simple models (e.g., linear regression with $d < \dim \xi$), partial leakage there.

$I(\{\xi_i\}_{i=1}^B; (1/B) \sum_i \mathbf{g}_i)$ — mutual info between $B$ samples and their mean gradient. The sum has $d$ degrees of freedom; $B \cdot \dim \xi$ joint sample information. When $B \cdot \dim \xi > d$, leakage is reduced. For large $B$, the aggregate gradient is "insufficient statistic" of the samples.

The exact leakage as a function of $(B, d, \dim \xi, \text{loss})$ is open. Empirical studies give operating points. Chapter 18 lists this as one of the open problems for privacy-aware FL. The CommIT-group contributions of Chapters 10–12 provide operational protocols, but the information-theoretic lower bound on leakage remains a research frontier.