Rate-Distortion and the Information Bottleneck

Allow a little distortion to compress harder: Rate-Distortion Theory R(D) gives the "minimum bits needed given a tolerated distortion D". The Information Bottleneck brings this idea into machine learning: learn a representation T that minimizes input compression I(X;T) while maximizing predictive information I(T;Y). This provides a theoretical framework for understanding the "memorize then compress" phenomenon in deep networks.

Introduction: Allowing Distortion Raises the Ceiling

The source coding in the previous chapter was lossless—reconstruction required bit-by-bit recovery, with the lower bound fixed at entropy.

However, many scenarios do not require exact reconstruction. JPEG discards high-frequency details imperceptible to the human eye; MP3 discards frequency bands masked by hearing; intermediate representations in neural networks discard information irrelevant to the task. These are intentional "discards," and you barely notice them.

Once distortion is allowed, the compressible space expands dramatically. The question transforms: instead of asking "how many bits for lossless?", we ask—given a tolerated distortion upper bound, what is the minimum number of bits? This chapter first answers this question (rate-distortion) and then brings the same logic into machine learning (the information bottleneck).

The Rate-Distortion Function R(D)

To discuss "tolerated distortion," we must first quantify it. Rate-distortion theory uses a distortion measure d(x, \hat{x}) (such as squared error or Hamming distance) to quantify "how far the reconstruction \hat{x} is from the original x."

The rate-distortion function is defined as: the minimum bit rate required, subject to the constraint that the average distortion does not exceed D.

R(D) = \min_{p(\hat{x} \mid x):\, \mathbb{E}[d]\leq D} I(X; \hat{X})

It is a monotonically decreasing curve: the larger the tolerated distortion D, the lower the required bit rate R. The two endpoints illustrate the extremes:

• D=0 (no distortion allowed): R(0) = H(X), reverting to the entropy lower bound for lossless compression.
• D is large enough that "guessing everything as a constant on average" is acceptable: R(D)=0, requiring zero bits to transmit.

R(D) is to lossy compression what entropy is to lossless compression—they are both insurmountable theoretical lower bounds. The area above the curve is achievable; the area below is physically impossible.

The Information Bottleneck Principle

Now, let's move this logic elsewhere. The Information Bottleneck (Tishby 1999) generalizes rate-distortion to representation learning—except that "distortion" is no longer measured by pixel error, but by "how much task-relevant information is lost."

The setup is as follows: given input X and target label Y, we want to learn an intermediate representation T (a form of compression of X). A good T must simultaneously satisfy two pulling against each other objectives:

• Compression: I(X;T) should be as small as possible. T should retain as little information about X as possible, discarding irrelevant details.
• Fidelity: I(T;Y) should be as large as possible. T should retain as much information as possible to predict Y.

Combining these two forces into a Lagrangian objective:

\min\ I(X;T) - \beta \cdot I(T;Y)

\beta is the trade-off knob: small \beta favors aggressive compression; large \beta favors retaining information. Here, X \to T \to Y forms a Markov chain (T obtains information only through X and cannot know Y out of thin air), making T the "bottleneck" in the middle.

"Memorize then Compress" in Deep Networks

The reason the Information Bottleneck attracts attention is due to an observation by Tishby et al.

When training deep networks, if you track the trajectory of each layer on the (I(X;T),\ I(T;Y)) plane, you often see two phases: first, a fitting phase, where I(T;Y) rises rapidly as the network "memorizes" the training data; then, a compression phase, where I(X;T) slowly decreases as the network squeezes out input information irrelevant to the label, improving generalization.

This provides an information-theoretic perspective on "why deep learning generalizes": good representations are compressed representations.

A honest note is needed: whether this "compression phase" is universal, or whether it is the cause of generalization, remains controversial in academia (some work points out it depends on activation functions and the estimation method of mutual information). Therefore, treat it as a heuristic framework rather than a settled conclusion—it provides a language to characterize representation quality using information quantities, which is valuable in itself.

Connecting Representation Learning and Contrastive Learning

The idea of "maximizing I(T;Y)" in the Information Bottleneck directly leads to modern self-supervised / contrastive learning.

Take InfoNCE (used in SimCLR, CPC, etc.) as an example: it is essentially a computable lower bound of mutual information I. Minimizing InfoNCE is equivalent to maximizing the mutual information between representations of positive sample pairs—ensuring the representation retains information about "what and what are the same thing."

Looking further, you will find that many objectives in representation learning are essentially manipulating the two directions of the Information Bottleneck—either compressing or retaining information. We stop here without expanding on the lower-bound derivation of InfoNCE.

How these tools are applied in LLM scenarios—perplexity, KL in RLHF, and the compression perspective of scaling laws—are consolidated in Information Theory in LLMs.

References

• Paper: "The Information Bottleneck Method" (Tishby, Pereira & Bialek, 1999 — the original Information Bottleneck paper)
• Paper: "Opening the Black Box of Deep Neural Networks via Information" (Shwartz-Ziv & Tishby, 2017 — observation of fitting/compression two phases, with controversies)
• Textbook: "Elements of Information Theory" (Cover & Thomas — Chapter 10 Rate Distortion Theory)
• Paper: "Representation Learning with Contrastive Predictive Coding" (Oord et al., 2018 — InfoNCE as a lower bound for mutual information)

Keywords: rate-distortion, R(D) function, lossy compression, Information Bottleneck, Tishby, Markov chain X→T→Y, trade-off between compression and fidelity, memorize then compress, representation learning, InfoNCE, contrastive learning