Rate-Distortion-Classification Representation Theory for Bernoulli Sources
Nam Nguyen , Thinh Nguyen , and Bella Bose · 2026
Read Rate-Distortion-Classification Representation Theory for Bernoulli Sources by Nam Nguyen , Thinh Nguyen , and Bella Bose (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-11919.txt.
Introduction
Nam Nguyen, Thinh Nguyen, and Bella Bose study lossy compression built for a task. The source is a Bernoulli stream. The error gauge is Hamming distance. The class to keep is tied to the source by a symmetric noisy link.
They derive closed forms for the trade. That trade links rate, error, and class skill. They treat both the one-shot case with shared randomness and its dual form. Task-first compression can save bits when full detail is not needed. The forms give exact limits for this clean case. Closed forms give exact limits for this clean task.
Catalog record
| CREATOR | Nam Nguyen , Thinh Nguyen , and Bella Bose |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 55 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-11919
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Rate-Distortion-Classification Representation Theory for Bernoulli Sources Nam Nguyen , Thinh Nguyen , and Bella Bose Abstract We study task-oriented lossy compression through the lens of rate-distortion-classification (RDC) representations. The source is Bernoulli, the distortion measure is Hamming, and the binary classification variable is coupled to the source via a binary symmetric model. Building on the one-shot common-randomness formulation, we first derive closed-form characterizations of the one-shot RDC and the dual distortion-rate-classification (DRC) tradeoffs. We then use a representation-based viewpoint and characterize the achievable distortion-classification (DC) region induced by a fixed representation by deriving its lower boundary via a linear program. Finally, we study universal encoders that must support a family of DC operating points and derive computable lower and upper bounds on the minimum asymptotic rate required for universality, thereby yielding bounds on the corresponding rate penalty. Numerical examples are provided to illustrate the achievable regions and the resulting universal RDC/DRC curves. Emails: [email protected], [email protected], [email protected] I Introduction Rate-distortion theory provides a fundamental framework for understanding the limits of lossy compression by characterizing the minimum rate required to represent a source subject to a fidelity constraint [ 3 , 7 ] . While classical rate-distortion theory focuses on reconstruction accuracy, it is now well understood that minimizing distortion alone does not necessarily preserve information relevant for downstream tasks or human perception. This observation has motivated extensive research on task-aware and perception-constrained lossy compression. In particular, Blau and Michaeli [ 5 ] introduced the rate-distortion-perception (RDP) framework, which incorporates perceptual quality as a third dimension alongside rate and distortion. By modeling perceptual quality through distribution-level constraints between the source and reconstruction, the RDP framework reveals a fundamental tradeoff between distortion fidelity and perceptual realism. These ideas have inspired both theoretical developments and practical deep learning-based compression systems [ 4 , 17 , 12 , 2 , 20 , 28 ] . More recently, attention has shifted toward compression schemes that explicitly account for downstream inference and decision-making. In such settings, the reconstruction is required not only to approximate the source, but also to preserve information relevant to a latent task variable [ 24 , 26 ] . The rate-distortion-classification (RDC) framework formalizes this perspective by introducing information-theoretic constraints that quantify the residual uncertainty of the task variable given the reconstruction [ 16 , 30 , 25 ] . Compared to perception-based constraints, classification constraints directly capture task performance and are particularly well suited for decision-oriented systems [ 19 , 14 , 13 , 18 ] . While existing RDC results characterize optimal tradeoffs for individual operating points, practical systems often require a single encoder to support multiple distortion and classification requirements. Redesigning or retraining an encoder for each operating point is undesirable in resource-constrained or multi-task environments. This motivates the notion of universal encoder representations , where a fixed encoder produces a shared representation that can be paired with different decoders to meet a family of objectives. The fundamental cost of enforcing such universality is captured by the associated rate penalty , defined as the excess rate required by a universal encoder relative to the best task-specific design. A universal encoder representation-based framework for perception-constrained lossy compression was developed by Zhang et al. [ 29 ] , where universal RDP representations and one-size-fits-all encoders were formalized, along with the associated rate penalty. Building on this framework, Qian et al. [ 22 ] specialized the theory to Bernoulli sources under Hamming distortion, enabling closed-form characterizations of the one-shot RDP function and a complete description of achievable distortion-perception regions. Extending the notion of universality from perception to task-oriented settings, Nguyen et al. [ 21 ] developed the theoretical framework for universal RDC representations, establishing fundamental limits on reusing a single encoder across multiple distortion-classification (DC) objectives. In this paper, we study RDC representations for Bernoulli sources under Hamming distortion, where a binary classification variable is coupled to the source through a symmetric noise model. Building on the binary-source perception framework in [ 22 ] , we extend the analysis to classification constraints. We first derive closed-form characterizations of the one-shot RDC and distortion-rate-classification (DRC) tradeoffs under common randomness and derive the achievable DC region induced by a fixed representation. We then consider the universal setting, in which a single encoder must support a family of DC operating points, and derive computable lower and upper bounds on the resulting minimum rate penalty. II RDC Tradeoff with Common Randomness II-A Problem Formulation We study a task-oriented lossy compression problem in which an observable source X\sim p_{X} is statistically coupled with a collection of latent target variables S_{1},\dots,S_{K}\sim p_{S_{1},\dots,S_{K}} . The joint distribution p_{X,S_{1},\dots,S_{K}} captures the dependence between the observable data and the underlying task variables. Although the variables S_{1},\dots,S_{K} are not directly observed, they are typically recoverable, possibly with uncertainty, from the source observation X . For example, when X represents an image, the variables S_{k} may correspond to semantic attributes such as object classes or scene categories. Figure 1: Task-oriented lossy compression framework. As depicted in Figure 1 , the system consists of an encoder-decoder pair. Given a length- n source sequence X^{n}\sim p_{X}^{n} , the encoder f:\mathcal{X}^{n}\to\{1,\dots,2^{nR}\} maps the source sequence to a finite-rate message Z . The decoder g:\{1,\dots,2^{nR}\}\to\hat{\mathcal{X}}^{n} uses this message to produce a reconstruction \hat{X}^{n} . The fundamental objective is to minimize the required communication rate while maintaining both reconstruction fidelity and task performance [ 25 , 21 ] . Distortion constraint. The reconstruction \hat{X} is required to satisfy an average distortion constraint \mathbb{E}[\Delta(X,\hat{X})]\leq D, (1) where \Delta(\cdot,\cdot) denotes a prescribed distortion measure, such as Hamming distortion or mean-squared error. Classification constraint. In addition to reconstruction quality, we impose explicit constraints on the preservation of task-relevant information. Specifically, for each target variable S_{k} , the reconstruction must satisfy H(S_{k}|\hat{X})\leq C_{k},\qquad k\in[K], (2) for some C_{k}>0 . This constraint bounds the residual uncertainty of the task variable S_{k} given the reconstructed source and ensures a prescribed level of classification performance [ 25 , 21 ] . Definition 1 ( One-Shot RDC Function ) . A rate R is one-shot achievable with respect to \Theta for the source variable X if there exists a random seed U , independent of X , and an encoder p_{Z|X,U} such that H(Z|U)\leq R . For every (D,C)\in\Theta , a decoder p_{\hat{X}|Z,U} can be constructed to meet the constraints \mathbb{E}[\Delta(X,\hat{X})]\leq D and H(S|\hat{X})\leq C , where the joint distribution satisfies p_{X,Z,\hat{X},U}=p_{X}p_{U}p_{Z|X,U}p_{\hat{X}|Z,U} , equivalently X\rightarrow Z\rightarrow\hat{X} given U . The infimum of such rates is denoted by R^{*}(\Theta) . When \Theta consists of a single (D,C) pair: \displaystyle R^{*}(D,C)=\penalty\ \displaystyle\underset{\displaystyle p_{U},p_{M|X,U},p_{\hat{X}|M,U}}{\mathrm{min}}\quad H(M|U) (3a) \displaystyle\mathmakebox[\widthof{$\underset{\displaystyle\phantom{p_{U},p_{M|X,U},p_{\hat{X}|M,U}}}{\mathrm{min}}$}][c]{\mathmakebox[\widthof{$\mathrm{min}$}][l]{\mathrm{\kern 1.00006pts.t.}}}\quad \displaystyle\mathbb{E}[\Delta(X,\hat{X})]\leq D, (3b) \displaystyle H(S|\hat{X})\leq C. (3c) Figure 2: One-shot setting with common randomness. Role of the common randomness U . In Figure 2 , the random seed U represents common randomness shared between the encoder and the decoder. When such common randomness is available, the message Z can be encoded using approximately H(Z|U) bits through variable-length coding. Definition 2 ( Asymptotic RDC Function ) . A rate R is asymptotically achievable with respect to \Theta for the i.i.d. source sequence \{X^{(t)}\}_{t=1}^{\infty}\overset{\text{i.i.d.}}{\sim}p_{X} if for some positive integer n , there exists a random seed U and an encoder p_{Z|X^{n},U} such that \frac{1}{n}H(Z|U)\leq