Exercises

$n \cdot d/b = 100 \cdot 10^5 / 8 = 1.25 \times 10^6$ symbols.

$d = 10^5$ symbols.

Digital is $12.5\times$ longer.

$V = 1/50 + 0.5/2500 = 0.02 + 0.0002 = 0.0202$.

$0.1 \cdot 0.0202 / 2 = 0.00101$.

$\ntn{mseagg}/n^2 = \sigma_g^2/n$ $\Rightarrow \ntn{mseagg} = n \sigma_g^2$.

$\ntn{mseagg}^{\text{matched}} = 100 \cdot 2 = 200$.

AirComp with MSE $\ll 200$ is over-engineered; MSE $\gg 200$ is under-engineered. Design around 200.

$\tau = 0.01/0.02 = 0.5$.

$P(|h|^2 \geq 0.5) = e^{-0.5} \approx 0.607$.

About $61\%$ of users included per round. The remaining $39\%$ are excluded; mitigate via $\alpha$- fairness.

$-\ln(0.3) \approx 1.20$.

Under unconstrained: $\mathbb{E}[\max \gamma] = O(\log n)$ in large $n$. For $n = 20$, this is around $\sim 3$. $\kappa \approx 3/1.2 - 1 = 1.5$.

$\eta_{0.7} = 1/(1 - 0.7 \cdot 0.5) = 1/0.65 \approx 1.5$. (Different derivation — calibrate empirically.)

About $50\%$ more convergence rounds to reach the same aggregate floor. In exchange: unbiased participation.

Sort descending: $\{2, 1.5, 1.0, 0.5, 0.3\}$.

$\sum_t (1/\lambda - 1/\gamma_k^{(t)}) = 5/\lambda - (0.5 + 0.67 + 1 + 2 + 3.33) = 5/\lambda - 7.5 = 10$. $\Rightarrow 1/\lambda = 3.5$.

All powers positive: $P^{(t)} = 3.5 - 1/\gamma_k^{(t)} = \{3.0, 2.83, 2.5, 1.5, 0.17\}$. All positive ✓.

$\sum = 3.0 + 2.83 + 2.5 + 1.5 + 0.17 = 10$. ✓

Strong rounds (high $\gamma$) receive most power; the weak round (0.3) receives only $0.17$ — nearly idle. Water-filling naturally emphasizes good channel realizations.

$V = 0.02 + 0.001 = 0.021$.

$0.1 \cdot 0.021 / 2 = 0.00105$. Below target.

$(0.9)^T \leq 0.01/10 = 0.001$ $\Rightarrow T \log(0.9) \leq \log(0.001)$ $\Rightarrow T \geq \log(0.001)/\log(0.9) \approx 65.4$. So $T \geq 66$ rounds.

Require $\tfrac{64}{2}\log(1 + 1/(99 \sigma_m^2)) \leq 0.01$.

$32 \log(1 + 1/(99\sigma_m^2)) \leq 0.01$ $\log(1 + 1/(99\sigma_m^2)) \leq 3.1 \cdot 10^{-4}$ $1 + 1/(99\sigma_m^2) \leq e^{3.1 \cdot 10^{-4}} \approx 1 + 3.1 \cdot 10^{-4}$ $1/(99\sigma_m^2) \leq 3.1 \cdot 10^{-4}$ $\sigma_m^2 \geq 1/(99 \cdot 3.1 \cdot 10^{-4}) \approx 32.6$.

$\sigma_m^2 \approx 33$ times $\sigma_z^2 = 1$. Mask dominates per-user representation variance by an order of magnitude, giving 0.01-nat-per-round privacy.

The masks don't degrade the aggregate MSE (they cancel). The mask variance is a pure privacy knob.

Exponential decay to floor of $\sim 0.001$ (computed above). At $T = 100$: both terms of Theorem 17.2.1 matter; need $\sim 66$ rounds to reach floor. At $T = 100$, loss $\approx 0.001$.

$O(L V / (\mu^2 T)) = O(10 \cdot 0.021 / 100) = 0.0021$. Actually slightly larger than (a) at $T = 100$.

For $T = 100$, constant $\eta_{\text{lr}}$ is slightly better. For $T = 1000$, (b) would outperform (a). Decreasing is asymptotically optimal but pays a slower rate.

Short horizon $T$ — constant $\eta_{\text{lr}}$. Long horizon $T$ — decreasing. The crossover depends on the target loss gap.

$R = \tfrac{1}{2}\log(1 + 50/0.01) = \tfrac{1}{2}\log(5001) \approx 6.15$ bits per channel use per scalar. Independent of $\sigma_m^2$.

$I(z_k; r) \leq \tfrac{d}{2} \log(1 + 1/(49 \sigma_m^2))$. For $\sigma_m^2 = 0.1$: $\approx 64 \log(1.2) \approx 64 \cdot 0.19 = 12$ nats. $\sigma_m^2 = 1$: $\approx 64 \cdot 0.02 = 1.3$ nats. $\sigma_m^2 = 10$: $\approx 0.13$ nats. $\sigma_m^2 = 100$: $\approx 0.013$ nats. $\sigma_m^2 = 1000$: $\approx 0.0013$ nats.

The feasible region is a rectangle: rate fixed, privacy monotone in $\sigma_m^2$.

This is the key engineering benefit of the CommIT scheme: rate and privacy are separate design knobs — a privacy improvement is not purchased with a rate loss. Compare with schemes (e.g., digital + cryptographic SecAgg) where privacy adds communication cost.

Require both terms $\leq \varepsilon^2/2$. Gives: $\eta_{\text{lr}} \leq \varepsilon^2/(2LV)$ and $T \geq 4F_0/(\eta_{\text{lr}} \varepsilon^2)$.

$T \geq 4F_0 \cdot 2LV/\varepsilon^2 \cdot 1/\varepsilon^2 = 8F_0 L V/\varepsilon^4$.

Non-convex FL takes $O(1/\varepsilon^4)$ rounds — much worse than $O(\log(1/\varepsilon))$ for strong convexity. Aggregation MSE enters as $V$, scaling the round count linearly.

For deep-network FL, thousands of rounds are typical. Aggregation MSE affects round count linearly; halving MSE halves round count.

$\sum_{k \geq 2} \mathbf{g}_k = (n-1) \nabla F + \sum_{k \geq 2} \mathbf{b}_k - \mathbf{b}_1$ (using $\sum_k \mathbf{b}_k = 0$ w.l.o.g.). The estimate of the gradient is biased by $-\mathbf{b}_1/n$.

Over $T$ rounds, the bias accumulates into a steady-state error of $O(\|\mathbf{b}_1\|/\mu)$.

Systematically excluding any user with biased gradient introduces a persistent convergence bias. Even if MSE is controlled, the model is drawn toward an unrepresentative optimum. The fix: $\alpha$-fairness, even at MSE cost.

In applications with mandatory fairness (e.g., demographic parity in healthcare), systematic exclusion violates law. Fairness is not just nice-to-have; it may be a compliance requirement.

Rounds 1 to $K-1$: AirComp aggregation. Round $K$: digital upload, use a cryptographic digest (Merkle root or hash) to verify that previous aggregations were not spoofed.

Digital round costs $\Theta(n \cdot d/b)$ symbols; AirComp rounds cost $\Theta(d)$ each. Total over $K$ rounds: $n d/b + (K-1) d$ symbols.

Pure digital: $K \cdot n d / b$ symbols. Hybrid: $n d /b + (K-1) d$ symbols. Ratio: $\text{hybrid/digital} = 1/K + (K-1)/(Knb/b) \cdot b/n = 1/K + (K-1)b/(Kn)$. For $n = 50, b = 8, K = 10$: $1/10 + 9 \cdot 8/(10 \cdot 50) = 0.1 + 0.144 = 0.244$ — four times more efficient than pure digital.

Hybrid gets AirComp's bandwidth gain plus periodic integrity checks. Detection of spoofing is delayed by at most $K - 1$ rounds. Trade $K$ against detection latency.

Optimal $K$ given attacker power, FL convergence impact, and integrity requirement: open. Chapter 18 revisits.

$F(\boldsymbol{\theta}) = \tfrac{1}{2}\|\boldsymbol{\theta}\|^2$; gradients are Gaussian with mean $\boldsymbol{\theta}$ and covariance $\sigma_g^2 \mathbf{I}$. Aggregation adds Gaussian noise with covariance $\ntn{mseagg} \mathbf{I}/n^2$.

$\boldsymbol{\theta}_{t+1} = (1 - \eta_{\text{lr}})\boldsymbol{\theta}_t - \eta_{\text{lr}} \mathbf{v}_t$ where $\mathbf{v}_t$ is Gaussian with covariance $V = \sigma_g^2/n + \ntn{mseagg}/n^2$. $\mathbb{E}[\|\boldsymbol{\theta}_t\|^2]$ satisfies a linear recursion converging to $\eta_{\text{lr}} V/(2 - \eta_{\text{lr}})$ = $\eta_{\text{lr}} V/(1 + \mu)$ for $\mu = 1$.

Theorem 17.2.1 bound: $\eta_{\text{lr}} V/(2 \cdot 1) = \eta_{\text{lr}} V/2$ (using $\mu = L = 1$). Simulated: $\eta_{\text{lr}} V/2$. The bound is tight in this regime.

In regimes close to the Gaussian model, the bound is tight. For non-Gaussian, bounded gradients can be tighter than $\sigma_g^2$, giving a slightly smaller floor. Practical measurement: simulate a realistic FL task; compare with bound; typically within $30\%$.

Variables: $\{\mathcal{S}_t, P_k^{(t)}\}_{t=0}^{T-1}$. Objective: $\mathbb{E}[F(\boldsymbol{\theta}_T)]$. Constraints: per-user energy, per-round power.

(1) Per-round: threshold + water-filling (Pareto per round). (2) Meta: choose target MSE from convergence.

Empirically, $< 5\%$ loss vs. optimal in many regimes. The gap comes from failing to coordinate across rounds: if a good-channel round is expected soon, spending less now to preserve energy pays off.

Methods: dynamic programming on channel-state trajectory (exponential in state space); Lyapunov optimization for stationary channels (tractable, gives competitive bounds); reinforcement learning for non-stationary channels (heuristic, no guarantees).

Characterize the optimal joint-design for non-stationary channels with energy and fairness constraints. This is an open problem at the intersection of optimization and information theory — the Chapter 18 frontier.