Chapter Summary

Chapter Summary

Key Points

• 1.

  The Information Bottleneck. The IB framework $\min_{P_{T|X}} I(X;T) - \beta I(T;Y)$ is a rate-distortion problem with KL divergence as the distortion measure. It provides a principled tradeoff between compression and relevance, solved by the Blahut-Arimoto algorithm. The information plane hypothesis connects IB to deep learning, though the extent of compression in trained networks remains debated.

• 2.

  Mutual Information Generalization Bounds. The Xu-Raginsky bound $|\mathbb{E}[\text{gen}]| \leq \sqrt{2I(W;S)/n}$ shows that generalization is controlled by the mutual information between the learned model and the training data. This makes precise the intuition that learning is compression: algorithms that extract fewer bits from the training data generalize better. The PAC-Bayes framework provides a complementary view using KL divergence to a prior.

• 3.

  Distributed Learning Limits. Distributed mean estimation with total budget $B$ bits has minimax MSE $\max\{d/n, d^2/B\}$, revealing a phase transition at $B = dn$. Below this threshold, communication is the bottleneck. Gradient quantization with random dithering achieves the optimal rate up to logarithmic factors.

• 4.

  Over-the-Air Computation. The MAC superposition $Y = \sum_k h_k X_k + Z$ naturally computes sums, enabling order-$K$ speedup for federated gradient aggregation. The computation capacity for nomographic functions matches the sum-rate MAC capacity. Practical challenges include synchronization, channel inversion under fading, and the power penalty from weak users.

• 5.

  Unifying Theme: Information Theory as the Language of Learning. Entropy, mutual information, and rate-distortion theory are not just tools for communication — they characterize the fundamental limits of learning, compression, and distributed computation. The same proof patterns (random coding, typicality, Fano's inequality) that underpin channel coding also govern sample complexity and generalization in machine learning.