Pareto-optimal clustering with the primal deterministic information bottleneck

The Big Picture

Imagine you’re packing for a long trip, but your suitcase has a strict weight limit. You can’t bring everything, so you make choices: keep the essentials, ditch the rest. But how do you optimally decide what counts as essential? That question sits at the heart of one of the deepest problems in information theory, and it turns out, in machine learning too.

The core challenge is a fundamental tension: the more you compress data, the less information you retain. Squeeze too hard and details blur. Hold too loosely and you’re not compressing at all. For decades, researchers have studied this trade-off mathematically, but most approaches only revealed a partial picture, a smooth curve that obscured rich, discrete structure hiding beneath.

A new paper from MIT and IAIFI researchers Andrew Tan, Max Tegmark, and Isaac Chuang maps that hidden terrain in full. Their central contribution: a new algorithmic framework for mapping out the complete set of best possible trade-offs (the Pareto frontier) between compression and information retention. Every point on this frontier represents a balance where you can’t squeeze data any harder without losing something meaningful, and you can’t preserve any more without giving up compression.

The framework applies to the Deterministic Information Bottleneck (DIB), a mathematical approach to finding the most informative way to group inputs into clusters. The team demonstrates it on tasks ranging from compressing the English alphabet to classifying color in natural images.

Key Insight: By solving the clustering problem directly, keeping both competing objectives separate rather than blending them into a single number, the researchers reveal a much richer set of optimal clusterings that are completely invisible to conventional approaches.

How It Works

The standard approach to the Information Bottleneck (and its deterministic variant, DIB) takes two competing objectives and combines them into a single score using a trade-off parameter β. This is the Lagrangian relaxation: pick β, optimize, get one point on the frontier. Sweep β across values and you trace a curve. Simple, but with a critical blind spot.

The Lagrangian approach only finds solutions on the convex hull of the feasible solution space. Picture the outermost skin stretched tightly around all possible solutions. Everything tucked inside is missed. In discrete problems, where encodings are hard assignments of inputs to clusters, many optimal solutions live inside the convex hull, geometrically unreachable by any choice of β. These solutions are Pareto optimal (you can’t improve one objective without sacrificing the other) but no Lagrangian scan will ever find them.

The figure above makes this concrete. On the left, the Lagrangian DIB frontier looks sparse and smooth. On the right, the primal DIB frontier, solved directly, exposes a staircase of discrete optimal clusterings. Most of these lie inside the convex hull and are completely invisible to the Lagrangian approach.

So the authors tackle the primal DIB problem head-on: instead of combining objectives into a single scalar, keep them separate and look for clusterings that genuinely maximize preserved information for a given entropy constraint. The search space grows super-exponentially with input size, which makes brute force impossible. Their solution, Pareto Mapper, is an ε-greedy agglomerative search:

1. Start with the “identity clustering,” where every input sits in its own cluster.
2. Iteratively consider all pairwise merges of existing clusters.
3. Evaluate each merge on both objectives: entropy reduction and mutual information with the target.
4. Add Pareto-optimal points to a maintained frontier; probabilistically explore near-Pareto points using the ε-greedy acceptance criterion.
5. Continue until the queue is exhausted.

The ε parameter controls exploration. High ε chases leads far from the current frontier, useful when sampling noise is significant. Low ε keeps the search tight. The result is an approximate Pareto frontier discovered in polynomial time, despite a super-exponential search space.

Why It Matters

Model selection, choosing the right number of clusters or compression level, is typically done by picking a single β and solving. But this hides structure.

The primal frontier reveals natural “corners”: sharp bends in the Pareto curve where a small increase in entropy yields a large gain in information retention. These corners are stable, meaningful, and often correspond to the right number of clusters for a given dataset. The Lagrangian approach, by flattening the frontier onto a convex hull, obscures exactly these decision-relevant features.

Three applications show how broadly this matters. Compressing the English alphabet (mapping 26 letters to fewer clusters based on co-occurrence statistics) yields linguistically meaningful groupings on the primal frontier. For natural image color classification, color categories emerge at different compression levels. And for a group theory-inspired synthetic dataset with mathematically known structure, the frontier’s shape aligns with the algebraic structure of the data, serving as ground-truth validation.

There’s also a clean theoretical result: Pareto-optimal frontiers are logarithmically sparse. The number of distinct optimal clusterings grows only as the logarithm of the total number of possible encodings. This explains why Pareto Mapper can work at all. The needle of optimality is rare, but the haystack shrinks faster than you’d expect.

Bottom Line: Tackling the Pareto frontier of clustering directly, rather than through convex relaxation, unlocks a richer map of the compression-information trade-off and provides a principled new toolkit for model selection in machine learning.