🔢 mathematics

Rate-Distortion-Classification Representation Theory for Bernoulli Sources

This paper investigates task-oriented lossy compression for Bernoulli sources under Hamming distortion and binary classification constraints by deriving closed-form tradeoffs for one-shot representations, characterizing achievable distortion-classification regions via linear programming, and establishing computable bounds on the rate penalty required for universal encoders.

Original authors: Nam Nguyen, Thinh Nguyen, Bella Bose

Published 2026-05-19

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Nam Nguyen, Thinh Nguyen, Bella Bose

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to send a secret message (a picture, a sound, or a piece of data) across a noisy, crowded room. You have a limited amount of space to shout the message (this is your Rate).

In the old days, the goal was simple: shout the message as clearly as possible so the listener hears every word exactly right. This is Distortion. If you shout too quietly to save space, the listener hears static. If you shout too loudly, you run out of breath (space).

But in the modern world, sometimes you don't need the exact words. You just need the listener to know the gist or the category of the message. For example, if you are sending a photo of a cat, you might not need the listener to see every whisker perfectly (low distortion), but you absolutely need them to know it's a "cat" and not a "dog" (high classification accuracy).

This paper is about finding the perfect balance between shouting clearly enough to be understood and shouting efficiently enough to save space, specifically when the goal is to help a computer make a decision (like identifying a cat).

Here is a breakdown of the paper's ideas using simple analogies:

1. The Setup: The "Binary" Game

The authors focus on a very specific, simplified version of this problem.

The Source: Imagine a light switch that is either ON or OFF. This is a "Bernoulli source." It's the simplest kind of data.
The Noise: The room is noisy. Sometimes the switch flips by accident.
The Task: The listener has to guess a secret label attached to the switch (e.g., "Is this switch part of the 'Kitchen' circuit or the 'Bedroom' circuit?").

2. The Three-Way Tradeoff (RDC)

The paper studies a three-way tug-of-war called RDC:

Rate: How many bits (shouts) you use.
Distortion: How different the received message is from the original (how many times the light switch is flipped by mistake).
Classification: How often the listener guesses the secret label correctly.

The Big Discovery: You can't just minimize errors. Sometimes, to make the classification (guessing the label) better, you actually have to accept more errors in the raw message, as long as those errors don't confuse the label.

3. The "One-Shot" Magic Trick (Common Randomness)

The authors first looked at a scenario where the sender and receiver share a secret "random seed" (like a shared deck of cards or a pre-agreed schedule).

Analogy: Imagine the sender and receiver both have the same magic book. Before sending a message, they flip a coin in the book. If it's heads, they agree to send the message "upside down." If it's tails, they send it "right side up."
The Result: Because they share this secret randomness, they can compress the message much more efficiently. The paper provides a precise mathematical formula (a "closed-form" answer) for exactly how much space you need to save to get a specific level of classification accuracy. It's like having a cheat sheet that tells you the absolute minimum number of words needed to get the job done.

4. The "Universal" Encoder (The Swiss Army Knife)

This is the most practical part of the paper.

The Problem: In the real world, you might have one sender (an encoder) but many different receivers with different needs. One receiver might need perfect image quality (low distortion), while another just needs to know if the image is "sunny" or "cloudy" (high classification).
The Old Way: You would build a different sender for every single receiver. This is expensive and wasteful.
The New Way (Universal Encoder): Can you build one sender that works for everyone?
- The Catch: To be a "Swiss Army Knife" that does everything, this one sender has to be slightly bigger (use more bits) than a specialized tool designed for just one job.
- The "Rate Penalty": The paper calculates exactly how much extra space (the "penalty") you have to pay to have this one universal sender. They found a way to calculate the minimum and maximum of this penalty using a type of math puzzle called a "Linear Program."

5. The "Lower Boundary" Map

The authors also figured out how to draw a map for a fixed sender.

Imagine you have a specific compression algorithm (a fixed "encoder").
The paper shows you how to calculate the best possible performance you can get from that specific encoder. It draws a line on a graph showing: "If you want this much classification accuracy, this is the best image quality you can possibly get with this specific tool."
They did this by turning the problem into a simple math equation that computers can solve quickly.

Summary of the Paper's Claims

Exact Formulas: For simple "On/Off" data, they found exact formulas for the tradeoff between message size, message errors, and task accuracy, assuming the sender and receiver share a secret random seed.
The Universal Cost: They proved that if you want one encoder to handle many different tasks (some needing perfect images, some needing just a label), there is a calculable "tax" (rate penalty) you must pay. You can't get the perfect performance of a specialized encoder for free; you have to pay extra bits to be universal.
Computable Limits: They provided a method (using linear programming) to calculate the best possible performance for any given encoder and to find the bounds on how much extra space a universal encoder needs.

What the paper does NOT do:

It does not test this on real photos of cats or dogs.
It does not propose a new AI algorithm to build these encoders.
It does not discuss medical or clinical uses.
It stays strictly within the mathematical theory of "On/Off" data sources to prove these fundamental limits.

In short, this paper is a blueprint. It tells us the theoretical limits of how efficiently we can compress data when the goal is to help a machine make a decision, and it calculates the exact cost of trying to use one "all-purpose" compressor for many different jobs.

Technical Summary: Rate-Distortion-Classification Representation Theory for Bernoulli Sources

Problem Formulation
This paper investigates task-oriented lossy compression through the lens of Rate-Distortion-Classification (RDC) representations. The study focuses on a specific setting where the source $X$ is a Bernoulli random variable, the distortion measure is Hamming distance, and a binary classification variable $S$ is coupled to the source via a binary symmetric channel (BSC) model ( $S = X \oplus S_1$ ).

The core problem addresses two distinct but related challenges:

Single-Point Optimization: Characterizing the fundamental tradeoffs between communication rate ( $R$ ), reconstruction distortion ( $D$ ), and classification uncertainty ( $C$ , measured as conditional entropy $H(S|\hat{X})$ ) for a specific operating point.
Universal Representation: Determining the cost of designing a single, fixed encoder that must support a family of distortion-classification operating points $\Theta$ , rather than a single point. This involves quantifying the "rate penalty"—the excess rate required by a universal encoder compared to the optimal task-specific design.

Methodology
The authors employ an information-theoretic framework, building upon the "one-shot common-randomness" formulation. Their methodology proceeds in three stages:

One-Shot Characterization with Common Randomness:
The authors first derive closed-form characterizations for the one-shot RDC function $R^*(D, C)$ and its dual, the Distortion-Rate-Classification (DRC) function $D^*(R, C)$ . They utilize a representation-based viewpoint where the reconstruction $\hat{X}$ is modeled as a deterministic function of the source $X$ and a common random seed $U$ (i.e., $\hat{X} = f(X, U)$ ). This formulation allows the problem to be reduced to optimizing over the distribution of the random seed $U$ . For Bernoulli sources, the authors demonstrate that the optimal strategy involves a mixture of four deterministic mappings: identity, bit-flip, constant-zero, and constant-one.
Achievable Region via Linear Programming:
To analyze the performance of a fixed representation $Z$ , the paper characterizes the achievable Distortion-Classification (DC) region $\Pi(p_{Z|X})$ . By parameterizing the decoder and the channel between $X$ and $\hat{X}$ , the authors formulate the lower boundary of this region as a linear program (LP). This allows for the efficient computation of the minimum distortion achievable for a given classification constraint $C$ for any fixed representation.
Universal Encoder Analysis:
The paper extends the analysis to the universal setting, where a single encoder must satisfy a set of constraints $\Theta$ . The authors define the universal RDC function $R(\Theta)$ as the infimum of mutual information $I(X; Z)$ over all representations $Z$ that can support every $(D, C) \in \Theta$ . To bound the minimum rate penalty $\Delta(\Theta)$ , they construct computable lower and upper bounds. The lower bound is derived by solving an LP over the joint distribution of two reconstructions ( $\hat{X}_1, \hat{X}_2$ ) corresponding to the boundary points of the operating set. The upper bound is derived using the convexity of the RDC function and geometric properties of its level sets.

Key Contributions and Results

Closed-Form Tradeoffs: The paper provides explicit, closed-form expressions for the one-shot operational RDC and DRC functions for Bernoulli sources under Hamming distortion with common randomness. These expressions partition the parameter space into distinct regimes based on the activity of the distortion and classification constraints.
Linear Programming Formulation: A novel LP formulation is derived to characterize the lower boundary of the achievable DC region induced by a fixed representation. This provides a tractable method to evaluate the performance of specific representation schemes.
Bounds on Universal Rate Penalty: The authors establish computable lower and upper bounds on the minimum asymptotic rate required for universality. These bounds quantify the fundamental cost of using a single encoder to support multiple DC objectives.
Numerical Illustration: The theoretical results are illustrated through numerical examples, showing the achievable regions and the resulting universal RDC/DRC curves, which demonstrate the tradeoffs between rate, distortion, and classification performance.

Significance and Claims
The paper claims to provide an analytically tractable benchmark for understanding universality in task-oriented lossy compression. By extending the binary-source perception framework (previously studied for Rate-Distortion-Perception) to classification constraints, the work formalizes the limits of reusing a single encoder across multiple distortion-classification objectives.

The authors emphasize that their results offer a complete description of the achievable regions and rate penalties for the specific case of Bernoulli sources. They position this work as a theoretical foundation that clarifies the fundamental costs associated with "one-size-fits-all" encoders in decision-oriented systems, contrasting them with task-specific designs. The paper does not propose new deep learning architectures or experimental deployments but rather establishes the information-theoretic limits and bounds that such systems must adhere to.