Rate-Distortion and the Information Bottleneck

Allow a little distortion to compress harder: Rate-Distortion Theory R(D) gives "the minimum bits required 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 had to restore every bit exactly, 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 also transforms: instead of asking "how many bits for lossless compression?", we ask—given a tolerated upper bound on distortion, what is the minimum number of bits required? 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): For discrete sources, where d(x,\hat x)=0 only holds for exact reconstruction, R(0)=H(X), reverting to the entropy lower bound for lossless compression. For continuous sources with squared error, R(0)=\infty typically holds, so you cannot directly substitute differential entropy for H(X) here.
• When D is large enough that "guessing everything as a constant on average" is acceptable: R(D)=0, requiring zero bits to transmit.

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

The Information Bottleneck Principle

Now, let's transplant this idea. 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 (which is some compression of X). A good T must satisfy two pulling against each other objectives simultaneously:

• Compression: Minimize I(X;T). T should retain as little information about X as possible, discarding irrelevant details.
• Fidelity: Maximize I(T;Y). 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 more information. The standard setting assumes the joint distribution p(x,y)p(t\mid x), so the Markov relationship should be written as Y\to X\to T (or T-X-Y): given X, T is conditionally independent of Y, meaning T can only extract information from X that is relevant to Y. Of course, during prediction we use T to estimate Y, but the "prediction flow X\to T\to\hat Y" and the "probabilistic dependency Y\to X\to T" are two different things.

"Memorize then Compress" in Deep Networks

The reason the Information Bottleneck attracts attention is 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": discarding input details, while preserving task-relevant information, may help generalization.

It is honest to note: whether this "compression phase" is universal, or whether it is the cause of generalization, remains controversial in academia (some work suggests it depends on activation functions and the estimation methods for 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 in the Information Bottleneck of "maximizing I(T;Y)" leads directly to modern self-supervised / contrastive learning.

Take InfoNCE (used in SimCLR, CPC, etc.) as an example: under corresponding positive/negative sample construction and sampling assumptions, it provides a computable lower bound for mutual information I. Minimizing the InfoNCE loss is equivalent to raising this lower bound—making representations better at distinguishing "what belongs together." However, the tightness of the lower bound depends on the number of negative samples and the sampling method, so you cannot directly equate the loss value with the true mutual information.

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 delving into the derivation of the InfoNCE lower bound.

How these tools are applied in LLM scenarios—perplexity, KL in RLHF, 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 the fitting/compression two-phase, 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 Y→X→T, compression vs. fidelity trade-off, memorize then compress, representation learning, InfoNCE, contrastive learning