CS Paper Radar

On the Information Bottleneck for Stable Variables

Dongmin Park, Jihad Fahs, Mohamad Assaad

cs.IT ·submitted 2026-10-06 09:06 UTC · v2

Abstract

We consider a generalization of the Gaussian information bottleneck problem to jointly stable variables $X$ and $Y$. Specifically, for $X = Y + A$, where $A$ is stable and independent of $Y$, we find optimal stable linear encoders of the form $T = kX + N$, with $N$ stable and independent of $X$. We characterize the linear stable information bottleneck in closed-form and its critical value. Furthermore, we show that, except for the Gaussian case, such stochastic linear encoders are strictly suboptimal, while becoming asymptotically optimal at large compression rates. Our linear solution recovers the Gaussian information bottleneck for jointly Gaussian variables as a special case.

Comment
13 pages, 3 figures

Closest papers

Nearest neighbours by meaning across the whole index.

What Should an Information Bottleneck Encoder Learn? Separating Representation Learning from Rate Control

cs.LG cs.IT ·2026-10-26 ·Hassan Tavakoli, Bella Bose
similarity 0.72
Abstract

The information bottleneck (IB) trades compression of an input $X$ against prediction of a target $Y$ through a multiplier $β=1/λ$, yet each operating point is usually served by training, or fully conditioning, a new encoder. For jointly Gaussian data, we show that the IB solution factorizes as $A(β)=D(β)W$: the information-bearing directions $W$ do not depend on $β$, and $β$ acts only through scalar gains. We ask whether this separation of \emph{representation} from \emph{rate control} survives beyond Gaussian models, treating the budget as a given operating parameter rather than a quantity to be optimized. For a budget-free representation \(F(X)\), the \emph{separation gap} is controlled by the \emph{sufficiency deficit} $ε_F=I(X;Y\mid F(X))$: We show there is at least $ε_F$ in the worst case for finite inputs, and it is bounded uniformly in $λ$ by a function of $ε_F$ for finite label alphabets. The same certificate extends to a new target distribution and to pooled multi-domain data, where a conditional-alignment term appears. On MNIST, SVHN, CIFAR-10 and STL-10 (10 seeds, eight prespecified budgets), a frozen CNN representation with one compressor--decoder pair per budget reduces estimated training multiply--accumulate operations (MACs) by $7.7\times$ and wall-clock time by about $2\times$ relative to end-to-end VIBs, and attains higher budget-averaged accuracy ($65.6\%$ versus $57.3\%$ per domain; $67.1\%$ versus $57.1\%$ pooled), with the advantage concentrated at strong compression, where the VIBs collapse. At weak compression ($λ\le0.036$), VIB has higher cross-entropy and ECE; its surrogate Lagrangian is higher per domain, indistinguishable from the pooled VIB in the macro average, and lower on the pooled test set.

0.10

Mutual Information Constrained Chernoff Bottleneck

cs.IT cs.LGmath.OCmath.ST+1 ·2026-09-29 ·Dier Tang, Guangyue Han
similarity 0.67
Abstract · 35 pages, 4 figures, 3 tables. Feedback and comments are welcome!

The classical information bottleneck (IB) measures the relevance of a representation $U$ of $X$ to a target $Y$ by $I(U;Y)$, which does not directly characterize the error of downstream decisions. For a binary hypothesis $Y$ inferred from many separately encoded observations, the optimal error exponent is the Chernoff information between the two conditional distributions of $U$ given $Y$. We study the mutual information constrained Chernoff bottleneck, which seeks an encoder that maximizes this Chernoff information subject to a rate constraint $I(U;X) \leq R$. We show that its optimal value $C(R)$ increases strictly up to $R = H(V)$, where $V$ merges the symbols of $X$ with equal likelihood ratio, remains at the uncompressed exponent beyond, and, unlike the IB curve, need not be concave. We further show that $k+1$ outputs suffice to attain $C(R)$, where $k$ is the cardinality of $V$. We propose an alternating algorithm that updates the encoder via a generalized Blahut--Arimoto algorithm and the Chernoff parameter $s$ via a nonlinear equation, and prove that its iterates remain feasible, with nondecreasing and convergent Chernoff information. Comparing with the classical IB for $n$ samples, we show that, whenever the two objectives disagree, the IB encoder has the smaller equivocation $H(Y|U^{n})$ at $n = 1$, whereas the Chernoff bottleneck has the smaller error probability and equivocation for all large $n$. Numerical experiments confirm the theory, and on real topic-detection data from the 20 Newsgroups corpus, compressing each word to only $17\%$ of its entropy retains $90\%$ of the error exponent and nearly the accuracy of the uncompressed classifier.

0.40

Second-Order Asymptotics for the Gaussian Multiple-Access Channel at Corner Points

cs.IT ·2026-08-18 ·Vincent Y. F. Tan
theory similarity 0.64
Abstract · 28 pages, 4 figures

We establish exact second-order coding rate regions at the two corner points of the capacity region of the two-user Gaussian multiple-access channel. For any average error probability $\varepsilon\in(0,1)$, we characterize the $n^{-1/2}$-scale fluctuations of achievable rates around each corner point, proving a converse that matches the previously known achievability bound. The proof first extracts a rectangular subcode that preserves the independence of the two transmitted codewords. The Polyanskiy--Verdú good-code output distribution theorem then yields log-determinant constraints that induce a spectral decomposition of a trimmed codebook into diffuse and exceptional subspaces. An entropic Brascamp--Lieb projection inequality controls the codeword inner product on the diffuse subspace, while variance-inflated Gaussian output distributions handle the low-dimensional exceptional subspace. Combining these two treatments yields the joint Gaussian limit required for the matching second-order converse.

0.47

Exact Common Information and Exact Channel Synthesis for Correlated Gaussian Sources

cs.IT ·2026-08-26 ·Lei Yu
similarity 0.61
Abstract · 16 pages, 2 figures

In this paper, we resolve two conjectures posed by Yu and Tan in 2020 (in two separate papers published in the IEEE Trans. Inf. Theory). Specifically, we establish that: 1) the exact common information for a pair of $ρ$-correlated Gaussian sources is given by the conjectured expression $\frac{1}{2}\log\frac{1+ρ}{1-ρ}+\fracρ{1+ρ}$; and 2) the admissible region for the shared randomness rate and the communication rate in exact channel synthesis is exactly the conjectured one. These results yield two important consequences. First, for any $ρ>0$, the exact common information of a correlated Gaussian pair strictly exceeds Wyner's common information. Second, for $ρ>0$, the exact channel synthesis of such a pair requires strictly higher rates than the total-variation version. The proof combines an exact optimal-transport representation of the worst-case Gaussian cross-entropy, Fathi's Gaussian transport inequality, and a determinant inequality arising from the covariance structure of the conditional means.

0.36

The Information Bottleneck and the Privacy Funnel are NP-hard

cs.IT ·2026-10-15 ·Roberto Bruno, Ugo Vaccaro
similarity 0.60
Abstract · Updated version of the manuscript with additional results. Submitted for publication

Given a joint distribution $P_{XY}$ of random variables $X,Y$ on finite alphabets, the information bottleneck method seeks a representation $T$ of $X$ that is as informative as possible about $Y$ while compressing $X$; the privacy funnel asks for a representation that discloses much about $X$ while leaking little about $Y$. In both scenarios $T$ and $Y$ are conditionally independent given $X$. We show that computing the optimal value $\operatorname{IB}(P_{XY},R) = \sup_T \{ I(Y;T) : I(X;T) \le R \}$ of the information bottleneck problem, as well as its Lagrangian relaxation $L_β(P_{XY}) = \sup_T [ I(Y;T) - βI(X;T) ]$, is NP-hard. Moreover, unless $\mathrm{P} = \mathrm{NP}$, neither $\operatorname{IB}(P_{XY},R)$ nor $L_β(P_{XY})$ can be approximated in polynomial time within an additive error of order $|\mathcal{X}|^{-(1+α)}$, for every fixed $α> 0$. We also prove that computing the privacy funnel $\operatorname{PF}(P_{XY},r) = \inf_T \{ I(Y;T) : I(X;T) \ge r \}$ and its Lagrangian relaxation $Λ_β(P_{XY}) = \inf_T [ I(Y;T) - βI(X;T) ]$ is NP-hard, and that, unless $\mathrm{P} = \mathrm{NP}$, neither can be approximated in polynomial time within an additive error of order $|\mathcal{X}|^{-2}$.

0.24

On the Cardinality of Optimal Representations in the Binary-Source Information Bottleneck

cs.IT cs.LGmath.OC ·2026-10-05 ·Dier Tang, Jun Chen
similarity 0.60
Abstract · 9 pages. Feedback and comments are welcome!

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 $|\mathcal{X}|+1$ symbols, and this bound is known to be tight whenever $|\mathcal{X}| \geq 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 $|\mathcal{U}| \leq |\mathcal{X}|+1$ sharpens to $|\mathcal{U}| \leq |\mathcal{X}|$ 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.

0.16

Linear Coding of LTI Sources Over Vector Gaussian Channels: A Majorization Approach

cs.IT eess.SYmath.OC ·2026-08-30 ·Shihao Jin, Junhui Li, Shinji Hara, Wei Chen
similarity 0.59
Abstract · 16 pages, 7 figures

We study the design of linear time-invariant (LTI) encoder-decoder pairs for transmitting the state of a discrete-time LTI vector source over power-constrained parallel Gaussian channels with feedback. Two types of power constraints are considered. Under individual subchannel power constraints, a necessary and sufficient condition for designing an encoder-decoder pair that achieves bounded estimation error covariance (EEC) is established via two coupled majorization inequalities involving the subchannel signal-to-noise ratios and the antistable poles of the source. Under total channel power constraint, we derive the minimum total power required for a feasible encoder-decoder design by exploiting partial-order progamming under majorization order. An analytical optimal power allocation is obtained for the case of equal noise variances, which admits a water-filling interpretation; for general noise case, a sequential water-filling algorithm is developed. Our results reveal that the difficulty of transmitting a discrete-time LTI source via LTI coding is governed not only by its topological entropy, but also by the evenness of the log-magnitudes of its antistable poles. The design methods for feasible encoder-decoder pairs are also provided.

0.31

A Self-Coupling Gaussian Extremal Inequality for Information-Constrained Optimal Transport with Applications to Rate-Distortion-Perception

cs.IT ·2026-10-18 ·Jiayang Zou, Jun Chen, Ayfer Özgür, Jia Wang
theory similarity 0.58
Abstract · 31 pages. Submitted to IEEE Transactions on Information Theory

How much mutual information is needed to achieve a target correlation between two copies of a prescribed distribution? We prove a sharp Gaussian extremal inequality for this self-coupling problem: among distributions with a fixed mean and covariance, the Gaussian has the greatest minimum information cost for meeting a positive semidefinite cross-covariance target. The inequality is strict for non-Gaussian distributions when the target is positive definite. The proof uses a midpoint gluing construction. Two Ornstein--Uhlenbeck half-bridges, each started from the prescribed endpoint law, meet at a common intermediate distribution and are joined by conditional gluing. Changing the Gaussian reference then turns the resulting relative-entropy bound into the desired extremal inequality. As a first application, scaling one endpoint of the self-coupling establishes Gaussian extremality for rate-distortion-perception with unlimited common randomness, under quadratic distortion and squared Wasserstein-2 perception measures. We also establish an analogous result for finite common randomness, where the problem involves two mutual information constraints associated with an auxiliary random variable. In that setting, we retain an intermediate observation on one half-bridge and balance the two information budgets simultaneously using the Poincaré-Miranda theorem.

0.36