Exercises

$\gamma_k = \{1.0, 0.8, 0.3, 0.5\}$.

$\min_k \gamma_k = 0.3$ (user 3).

$\eta^{\star} = \sqrt{0.3} \approx 0.548$; $\mathsf{MSE}^{\star} = 0.02/0.3 \approx 0.067$.

$\varphi_k(s) = 1/s$.

$\psi(u) = n/u$.

$\psi(\sum_k \varphi_k(s_k)) = \psi(\sum_k 1/s_k) = n / \sum_k (1/s_k)$. ✓ One AirComp channel use suffices.

$\phi_{\max} = 10° = 0.175$ rad.

$\sin(0.175)/0.175 \approx 0.1736/0.175 \approx 0.9949$.

$\sigma_s^2 (1 - 0.9949^2) = 1 \cdot (1 - 0.9898) \approx 0.0102$.

If noise floor is $0.01$, misalignment adds about $100\%$ — doubling the total MSE. Tightening to $\phi_{\max} = 5°$ would reduce the misalignment floor to $\approx 0.0026$, essentially negligible.

$|\eta|^2 \sigma_s^2 / ((n-1)|\eta|^2\sigma_s^2 + \sigma^2) = 1 / (99 + 0.1) \approx 0.0101$.

$\tfrac{1}{2}\ln(1 + 0.0101) \approx \tfrac{1}{2} \cdot 0.01005 \approx 0.005$ nats.

$\approx 0.0072$ bits per user per round.

Less than one percent of a bit of individual information leaks per round at $n = 100$. For longitudinal privacy over $T$ rounds, the total leakage is bounded by $T \cdot 0.005$ nats; the user can budget a target leakage ceiling to set maximum rounds.

Current: $\eta^2 = 0.5$. Target: $\eta^2 \geq 1$. Factor: $2\times$ in $\eta^2$ needs $2\times$ in $P$: $3$ dB increase.

After dropping: $\min \gamma_k = 1.2$, $\mathsf{MSE} = 0.01/1.2 \approx 0.0083$ — meets target. But aggregate is now $\sum_{k \notin \text{dropped}} s_k$, missing some users.

Option (a) costs $3$ dB transmit power (halving battery life). Option (b) costs statistical representativeness ($k$ users excluded). For FL, (a) is usually preferred because it preserves all users' gradients; (b) is preferred when all users' data is i.i.d. and battery is critical.

The operator faces the golden thread in miniature: power vs. statistical representativeness. No universal answer; deployment specifics determine the choice.

$\varphi_k(s) = (s - c)^2 / n$. Each user computes this locally (they know their own $s_k$ and the constant $c$).

$\psi(u) = u$ (identity).

If $c$ must itself be computed (e.g., $c = \bar{s}$), then the aggregate is not nomographic — it's a two-step protocol: first AirComp to compute $\bar{s}$, then a second AirComp round to compute the empirical variance $\sum_k (s_k - \hat{\bar{s}})^2/n$. The second round inherits MSE from the first.

A one-step AirComp of empirical variance requires $c$ to be a known reference value (e.g., zero, or a previous-round parameter). Otherwise, plan two rounds.

$\sigma^{\text{agg}} = 1 \cdot \sqrt{2\ln(1.25/10^{-5})}/1 = \sqrt{2 \cdot 11.7} \approx 4.84$.

Each user must add their own $\sigma_z = \sigma^{\text{agg}} \approx 4.84$ to their individual upload. Aggregate $\sum_k s_k$ has noise $\sqrt{n} \cdot \sigma^{\text{agg}} \approx 48.4$ — privacy still holds but noise is much larger.

Each user adds $\sigma_z^{\text{per-user}} = \sigma^{\text{agg}}/\sqrt{n} = 4.84/10 = 0.484$. Aggregate dither is $\sqrt{n \cdot (0.484)^2} = \sqrt{100 \cdot 0.234} = \sqrt{23.4} \approx 4.84$ — the required level.

The aggregate has the same $\sigma^{\text{agg}}$ in both cases, but AirComp uses $10\times$ less per-user dither. The useful gradient survives in the aggregate much better under AirComp.

Variance is $\frac{1}{n}\sum_k s_k^2 - (\frac{1}{n}\sum_k s_k)^2$. The second term depends on all $s_k$ non-trivially (not via a sum of pre-processing). In particular, $(\frac{1}{n}\sum_k s_k)^2$ is quadratic in the sum — not nomographic.

Round 1: compute $\hat{\bar{s}} = \frac{1}{n}\sum_k s_k$. Round 2: users compute $(s_k - \hat{\bar{s}})^2 / n$ locally; AirComp these. Result: empirical variance $\hat{\text{Var}}$.

The Round-2 estimate inherits additional MSE from the Round-1 noise in $\hat{\bar{s}}$: perturbation propagates through the squared-residual computation. The total MSE is $\approx 2\mathsf{MSE}$ (first round on variance, second round's propagation).

Compound-step AirComp doubles the channel-use cost and MSE. For FL of moments, prefer first-moment aggregates (gradient mean) and accept the variance is a secondary-round quantity.

Dropping leaves 19 users, aggregating $\sum_{k=2}^{20} s_k$. MSE drops $5\times$, but data is $19/20 \cdot \sum_{\text{all}} s_k$ — a $5\%$ bias if the aggregate matters globally.

Boost by $5\times$ (7 dB): all users included, MSE still $5\times$ better than status quo. Battery drain for the weak user is $5\times$.

Depends on (i) whether the excluded user's data is biased (favor boost) and (ii) battery constraints (favor drop). Quantitatively: let $B$ = value of including user per round; $C$ = cost of $5\times$ battery drain. Drop if $B < C$; boost if $B > C$. In practice, most FL deployments favor rotation across rounds to amortize costs.

Let $\mathbf{h}_k \in \mathbb{C}^n$ be user $k$'s channel to the $n$ receive antennas. The received signal is $\mathbf{r} = \mathbf{H} \mathbf{b} \odot \mathbf{s} + \mathbf{w}$, where $\mathbf{H}$ is the $n \times n$ matrix with columns $\mathbf{h}_k$, $\mathbf{b}$ is the user-transmit-scaling vector, and $\mathbf{s}$ is the source vector.

If $\mathbf{H}$ has full rank (which it does w.p. 1 for random fading channels), the receiver can invert: $\mathbf{H}^{-1} \mathbf{r} = \mathbf{b} \odot \mathbf{s} + \mathbf{H}^{-1} \mathbf{w}$. Dividing by $b_k$ recovers each $s_k$ (with noise).

The access point now directly observes each $s_k$ (up to noise). The "superposition privacy" of single-antenna AirComp is gone — MIMO fundamentally changes the threat model.

Always assume the AP may one day upgrade to MIMO. Layer cryptographic aggregation (Chapter 10) or information- theoretically secure federated learning (Chapter 17) on top for defense in depth.

The max is nomographic over $2n+1$ AirComp rounds: each round computes one term of Kolmogorov's sum. Each round incurs its own AirComp MSE.

$\varphi_k(s) = s^p$ gives aggregate $\sum_k s_k^p$; $\psi(u) = u^{1/p}$ gives smooth-max. One channel use.

Approximation error: $(\sum_k s_k^p)^{1/p}$ converges to $\max_k s_k$ as $p \to \infty$, but $\varphi_k$ becomes numerically unstable (large $p$ amplifies differences).

For reasonable tolerances ($\varepsilon = 0.01$ of the max value), $p \approx 100$ suffices. One round vs. $2n+1$ rounds — $>99\%$ communication savings at the cost of approximation error. Choose based on exact-vs-approximate requirement.

For aggregate-level $(\varepsilon, \delta)$-DP, the aggregate dither variance $n \sigma_z^2 = \sigma_{\text{agg}}^2$ is fixed.

$\mathsf{MSE} = \sigma^2/|\eta|^2 + \sigma_{\text{agg}}^2$ where $|\eta|^2 = P \cdot |h|^2/\sigma_s^2$ (assuming aligned best-case channel).

Increasing $P$ reduces the first term; the second term (DP floor) is independent of $P$. As $P \to \infty$, MSE $\to \sigma_{\text{agg}}^2$ — an irreducible DP floor.

At fixed $(\varepsilon, \delta)$, the operator can trade $P$ (battery cost) against the inability to reduce MSE below the DP floor. If MSE floor is above the downstream tolerance, reduce DP guarantee (increase $\varepsilon$, relax privacy) to reduce $\sigma_{\text{agg}}^2$ and permit lower MSE.

The Pareto frontier is sharp: AirComp with DP is a power- and-privacy-constrained system. Production FL must specify both simultaneously.

Aggregate noise: $n\sigma_Q^2 = n \cdot \text{range}^2 / (12 \cdot 4^b)$. Bandwidth: $\Theta(nb)$ channel uses.

With the same channel-use budget $nb$, AirComp can do $nb$ rounds — each of MSE $\sigma^2/\eta^2$. With averaging, the effective MSE scales as $1/nb \cdot \sigma^2/\eta^2$ — typically much smaller than $n \sigma_Q^2$.

For modest $n$ and $b$, digital is fine. For large $n$ and modest MSE tolerance, AirComp's bandwidth efficiency dominates.

For $n = 100, b = 8$: $\sigma_Q^2/\text{range}^2 \approx 10^{-5}$, aggregate $\approx 10^{-3}$. AirComp with $\sigma^2/\eta^2 = 10^{-4}$ — comparable. Above $n = 100$, AirComp typically wins on bandwidth by $10\times$ or more.

$\mathsf{MSE}(P) = \kappa/P$ where $\kappa = \sigma^2/\min_k(|h_k|^2/\sigma_s^2)$. As $P \to \infty$, MSE $\to 0$.

$d^2(\kappa/P)/dP^2 = 2\kappa/P^3 > 0$. Convex in $P$.

With $T$ rounds and total energy $E$, distribute as $P_t = E/T$ uniformly (by convexity / AM-GM). Total MSE $T \cdot \kappa/(E/T) = T^2 \kappa/E$. Minimize over $T$: only one round is optimal (more rounds hurts).

Under time-varying channels ($\kappa_t$ varying across rounds), water-filling assigns more power to good-channel rounds, breaking uniformity. Optimal $P_t^{\star} \propto \sqrt{\kappa_t}$.

$\mathsf{MSE}_{\text{ZF}} = |\psi'|^2 \sigma^2/\eta^2$. Linear receiver.

Bayesian post-processor: $\hat{f}(r) = \mathbb{E}[f | r]$. For Gaussian $s_k$ and sub-quadratic $\psi$, MMSE can outperform ZF by using priors on the source.

Per the Cramer-Rao inequality, unbiased estimation of $f$ has MSE $\geq \mathbb{E}[|\psi'|^2] \sigma^2/\eta^2$ — matching ZF up to a constant. Biased estimation (e.g., shrinkage) can go below — but introduces bias.

The minimum MSE for nomographic AirComp is characterized only in special cases (linear $\psi$, Gaussian sources). The general optimal receiver is open.

Approximate message passing (AMP) receivers, deep-learning post-processors, and structured-prior Bayesian methods all offer potential improvements. Chapter 18 revisits this frontier.