CS Paper Radar

Between Hi-Fi and MMI: the overlap of redundancy and synergy in partial information decomposition

Niels Van Santen, Yves Rosseel, Daniele Marinazzo

cs.IT physics.data-anstat.ME ·submitted 2026-11-05 14:59 UTC · v1

Abstract

Partial information decomposition (PID) splits the information that two sources carry about a target into redundant, unique and synergistic parts, with nonnegative decompositions lying on a segment where redundancy measures are bounded by the positive part of the co-information and the smaller source-target information. We parameterize this segment by the overlap, the common excess of redundancy and synergy over their net balance, and show that for many of the named PID measures, their redundancy can be written as the largest positive part of the co-information over a set of reference distributions. This common form induces an ordering of those PIDs on the segment. With the smallest redundancy and synergy and the largest unique atoms of any nonnegative PID, the information-theoretic version of Hi-Fi, a feature-importance method, is the zero-overlap end of the segment for two sources, with the maximum overlap bound given by the minimum mutual information (MMI) PID. We introduce, by splitting the co-information into a pairwise maximum- entropy part and the third-order connected information, a PID that sits at zero overlap except when pairwise redundancy and triadic synergy coexist. For three or more sources the bivariate results hold on every pair of merged source groups, and among all nonnegative solutions of the lattice equations MMI and Hi-Fi still give the smallest and largest unique atoms but zero overlap on all pairs at once is often unattainable. Two inequalities across pairs are necessary in general and sufficient for three sources. For identity targets zero overlap is possible exactly when the sources' information diagram is nonnegative. In random three- and four-source distributions zero overlap on all pairs fails in 21-100% of the cases.

Closest papers

Nearest neighbours by meaning across the whole index.

Partial Information Decomposition When Some Sources Are Known: A Source Chain Rule and a No-Go Theorem

cs.IT ·2026-10-24 ·Aaron J. Gutknecht
theory similarity 0.69
Abstract · 23 pages, 3 figures, 2 tables

Partial information decomposition (PID) splits the information that several sources carry about a target into atoms, distinguished by which collections of sources give access to them. We ask how such a decomposition should behave when some of the sources are already known. The access structure of the atoms suggests one answer: discard the atoms that the known sources provide and regroup the rest according to which further sources unlock them. The classical construction of conditional information suggests another: recompute the decomposition under the conditional distributions and average. We show that the two answers agree, atom by atom, exactly when redundant information obeys a source chain rule, an analogue of the chain rule of mutual information: when the same sources are added to several collections, the enlarged collections share everything the added sources provide and, beyond that, exactly what the original collections share once the added sources are known. The rule divides established measures of redundant information, so that adopting or rejecting it genuinely narrows the choice of measure. Our main result is a no-go theorem: for three or more sources, the source chain rule and local positivity, the requirement that all atoms be nonnegative, cannot hold together in any PID.

0.31

Redundancy and synergy in multivariate Gaussians via the Blackwell order

cs.IT stat.ML ·2026-10-05 ·Artemy Kolchinsky
theory similarity 0.65
Abstract

The goal of the partial information decomposition (PID) is to quantify the redundant and synergistic information that multiple sources provide about a target. PID has many applications in machine learning, neuroscience, and other fields, but defining and computing it for high-dimensional continuous systems remains challenging. Here, we define a PID for multivariate Gaussian systems based on the Blackwell order, which formalizes when one channel is more informative than another. We prove that Gaussian channels are optimal for extracting both redundant and union information, yielding an intuitive geometric interpretation and an efficient numerical algorithm for the PID. Our union information and synergy coincide with the well-known BROJA measures, and we derive closed-form expressions for both in the case of two sources. We also argue that Blackwell redundancy (which differs from BROJA) is the only existing redundancy measure that satisfies a set of natural desiderata. We demonstrate the scalability of our method on systems with up to a thousand dimensions or sources. Our approach is illustrated on an optimal control problem, where it identifies redundant and synergistic interactions between sensor and memory.

0.32

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.59
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

Mutual Information Constrained Chernoff Bottleneck

cs.IT cs.LGmath.OCmath.ST+1 ·2026-09-29 ·Dier Tang, Guangyue Han
similarity 0.58
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.39

Wyner's Common Information and the Common Entropy are NP-Hard to Compute

cs.IT ·2026-10-11 ·Roberto Bruno, Ugo Vaccaro
theory similarity 0.58
Abstract · A preliminary version of the manuscript

Wyner's common information $J(p)$ and the common entropy $G(p)$ of a pair of random variables $(X,Y)$ with finite ranges and joint distribution $p$ are both defined by an optimization over the auxiliary random variables $W$ that make $X$ and $Y$ conditionally independent: $J(p)$ is the infimum of the mutual information $I(X,Y;W)$, and $G(p)$ is the infimum of the entropy $H(W)$. We prove that both quantities are NP-hard to compute. For Wyner's common information, deciding whether $J(p)$ is strictly smaller than a given integer $r$ is NP-hard, and the problem is NP-complete on tables that are uniform on their support and have the same number of positive entries in every row. The reduction is from Maximum Edge Biclique and rests on an exact criterion, in terms of rectangles in the support of $p$, for improving on the auxiliary $W=X$; every yes-instance satisfies $J(p)<r-1/(4N^2)$ and every no-instance satisfies $J(p)=r$, where $N$ is the number of positive entries of $p$. For the common entropy, deciding whether $G(p)\le r$ for a rational number $r$ is NP-hard, even for tables with at most four nonzero entries in each row, all taking one of two values. The reduction is from exact cover by $3$-sets and rests on a majorization property of the masses of the nonnegative rank-one decompositions of $p$, combined with a quantitative form of the Schur concavity of entropy. In both cases the separation between yes- and no-instances is inverse-polynomial in the size of $p$, so that approximating $J(p)$ or $G(p)$ within a suitable inverse-polynomial additive error is also NP-hard. The two mechanisms are genuinely different: we exhibit a table on which a large rectangle in the support lowers $J$ below the threshold of our first reduction while leaving $G$ on it.

0.15

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.57
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

The marginal is pretty good

cs.IT quant-ph ·2026-09-04 ·Lukas Schmitt, Gui-Long Jiang, Shi-Bing Li, Joseph M. Renes
theory similarity 0.57
Abstract · 12 pages, Gui-Long Jiang and Shi-Bing Li added as authors, Theorem 3.1 now holds for $α\in(0,1)$ (instead of $[1/2,1)$), Theorem 4.1 and 4.2…

One-shot information theory measures often require an optimization over states, but the form of these optimizers can be complicated or depend on the initial problem in nonlinear ways. In this note, we show that in many instances using the marginal instead of the optimal state is sufficiently good and only changes the result by a small factor. We prove that for the Petz--Rényi and sandwiched--Rényi divergences of order $α\in(0,1)$, replacing the optimizing state on $B$ by the marginal $ρ_B$ results in a multiplicative overhead of at most $1/α$.

0.28

Fourier entropy of threshold functions and their compositions

cs.IT math.PR ·2026-10-12 ·Yitzchak Shmalo
theory similarity 0.56
Abstract

We prove the Fourier entropy--influence inequality for every linear threshold function, with a constant below $8.937$ and no restrictions on its weights or threshold. The argument applies to regular Boolean functions and gives logarithmic bounds for their Boolean combinations and for unions with bounded variable overlap. Character multiplication preserves the estimates and yields bounds by influence minus variance. Under arbitrary product measures, symmetric thresholds satisfy the strengthened inequality needed for read-once composition, uniformly in depth and fan-in. A joint description of each Fourier set refines the overlap estimate and recovers constant bounds for addressing. Exact selector identities extend the bound to orthogonal multiplexers with shared data. Rare activation preserves the optimal constant of unrestricted FEI. The proofs combine pivotal antichains, spectral reference measures, and product-measure composition.

0.44