On the Cardinality of Optimal Representations in the Binary-Source Information Bottleneck
Abstract
The information bottleneck (IB) seeks a representation U of a source X that retains as much information as possible about a target Y, subject to a constraint on I(U;X). A classical argument shows that it suffices to consider representations with at most |π³|+1 symbols, and this bound is known to be tight whenever |π³| β₯ 3. We show that the binary case behaves differently: if X is binary and Y is finite, then for every joint distribution of (X,Y) and every rate constraint, the IB optimum is attained by a binary U. Hence the bound |π°| β€ |π³|+1 sharpens to |π°| β€ |π³| for binary sources. The proof combines a separating hyperplane argument with the observation that, for a binary source, the ratio of the second derivatives of the two entropy functions involved is concave.
Related
- Optimal Multitask Representations Under a Rate Constraint: An Information Bottleneck Analysis
- Polynomially Solvable Cases of the Quadratic Binary Optimization Problem with a Fixed Cardinality Constraint
- A Parallel Heuristic for the Fixed Cardinality Binary Quadratic Program
- On the Information Bottleneck for Stable Variables
- Dynamics Aware Past-Future Information Bottleneck
BibTeX
@misc{tang2026cardinality,
title = {{On the Cardinality of Optimal Representations in the Binary-Source Information Bottleneck}},
author = {Dier Tang and Jun Chen},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.06627},
eprint = {2610.06627},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.06627},
}
RIS
TY - UNPB
TI - On the Cardinality of Optimal Representations in the Binary-Source Information Bottleneck
AU - Dier Tang
AU - Jun Chen
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2610.06627
UR - https://arxiv.org/abs/2610.06627
AB - The information bottleneck (IB) seeks a representation U of a source X that retains as much information as possible about a target Y, subject to a constraint on I(U;X). A classical argument shows that it suffices to consider representations with at most |π³|+1 symbols, and this bound is known to be tight whenever |π³| β₯ 3. We show that the binary case behaves differently: if X is binary and Y is finite, then for every joint distribution of (X,Y) and every rate constraint, the IB optimum is attained by a binary U. Hence the bound |π°| β€ |π³|+1 sharpens to |π°| β€ |π³| for binary sources. The proof combines a separating hyperplane argument with the observation that, for a binary source, the ratio of the second derivatives of the two entropy functions involved is concave.
ER -