Separable Computation of Information Measures

Lizhong Zheng; Xiangxiang Xu

REVIEW 1 major objections 5 minor 12 references

Separable Computation of Information Measures

T0 review · 1 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper proves that any sufficient statistics s(X), t(Y) preserve a broad class of information measures, and it pins down Gács–Körner common information as the entropy of the singular functions with unit singular values.

desk verdict Sound and honestly scoped: exact sufficiency gives clean invariance theorems, with the Gács–Körner spectral characterization the real new money; the omitted proofs and approximation gap are fixable. read the letter →

arxiv 2501.15301 v1 pith:JC5OTKME submitted 2025-01-25 cs.IT cs.LGmath.ITstat.ML

Xiangxiang Xu , Lizhong Zheng This is my paper · ORCID

classification cs.ITcs.LGmath.ITstat.ML MSC 94A1762B10

keywords separablecomputationsufficientstatisticsinformationmeasurescanonicaldependencekernelmodaldecompositionWynercommonGács–Körnerbottleneck

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper asks when an information measure $\theta(X,Y)$ between two variables can be computed from learned feature representations $s(X)$, $t(Y)$ instead of raw data. Its answer: if $s(X)$ and $t(Y)$ are sufficient statistics, so that $X-s(X)-t(Y)-Y$ forms a Markov chain, then $\theta(X,Y)=\theta(s(X),t(Y))$ for mutual information, all $f$-information measures, Wyner's common information, Gács–Körner common information, and Tishby's information bottleneck. The proofs go through the canonical dependence kernel and its singular-value (modal) decomposition, which also yields an explicit formula for Gács–Körner common information as the entropy of the singular functions whose singular value is 1. This matters because practical neural feature estimators can be interpreted as attempting to learn sufficient statistics, and the theorem supplies the condition under which such modular, feature-based estimation is exact rather than heuristic.

What carries the argument

The load-bearing object is the canonical dependence kernel (CDK), $i_{X;Y}(x,y)=\frac{P_{X,Y}(x,y)}{P_X(x)P_Y(y)}-1$, together with its modal decomposition: a singular value decomposition $i_{X;Y}=\sum_i \sigma_i f_i^*(x)g_i^*(y)$, with $\sigma_1\ge\sigma_2\ge\cdots>0$ and orthonormal singular functions. Two facts carry the argument: first, $S$ and $T$ are sufficient exactly when the density ratio of $(X,Y)$ factors through the density ratio of $(S,T)$, so the CDK is unchanged by reducing to sufficient features; second, the singular functions $f^*(X)$, $g^*(Y)$ are minimal sufficient statistics. The CDK also pinpoints the unit singular values: functions $f(X)$ and $g(Y)$ that coincide with probability 1 are exactly linear transforms of the singular functions with $\sigma_i=1$, which yields the Gács–Körner entropy formula and the other invariance proofs.

What would settle it

Take a small finite joint distribution satisfying sufficiency for a chosen $s(X)$, $t(Y)$, compute $C_{GK}$ both by brute-force enumeration of all functions $f,g$ with $P\{f(X)=g(Y)\}=1$ and by the formula $H(f_0^*(X),\ldots,f_k^*(X))$ from the modal decomposition; a single distribution where they differ would refute Theorem 2. Separately, choose an intentionally non-sufficient feature map, such as one that merges two symbols with different conditional distributions of $Y$, and compute $I(X;Y)$ versus $I(s(X);Y)$; seeing the equality fail confirms the condition is doing the work.

Watch

Extended reading notes

Core claim

The central claim is the invariance theorem: for finite-alphabet $X,Y$, if $S=s(X)$ and $T=t(Y)$ are sufficient statistics in the sense $X-S-Y$ and $X-T-Y$ (equivalently $X-S-T-Y$), then $I(X;Y)=I(S;T)$, $I_f(X;Y)=I_f(S;T)$ for every $f$-information, $C(X,Y)=C(S,T)$ for Wyner's common information, $C_{GK}(X,Y)=C_{GK}(S,T)$ for Gács–Körner common information, $L^*_{IB}(X,Y;\beta)=L^*_{IB}(S,T;\beta)$ for every $\beta>0$, and $\vartheta_{X,Y}(R)=\vartheta_{S,T}(R)$ for every $R\ge 0$ for the information bottleneck. Along the way the paper characterizes Gács–Körner common information as $H(f_0^*(X),\ldots,f_k^*(X))$, where $f_i^*$ are the left singular functions of the canonical dependence kernel and $k$ is the largest index with singular value $\sigma_k=1$. The optimal auxiliary variables in Wyner's problem and in the bottleneck are shown to be functions of the sufficient features, which is what makes separable computation possible.

Load-bearing premise

The entire set of equalities rests on the learned features being exactly sufficient statistics, so that $X-s(X)-t(Y)-Y$; if that Markov condition fails, the paper provides no guarantee and the equalities can break.

Editorial extensions

If this is right

Feature-based mutual information estimation is exact whenever the learned features are sufficient statistics; the estimator no longer needs access to raw $X$ and $Y$.
The optimal Wyner common-information channel $W$ can be restricted to depend on $(S,T)$, so common information can be computed from sufficient features without loss.
Gács–Körner common information is a spectral quantity: it is the entropy of the top segment of canonical features whose singular values equal 1.
For any $\beta>0$ and any $R\ge 0$, the information bottleneck Lagrangian optimum and the $\vartheta(R)$ curve are invariant under sufficient-statistic reduction, so bottleneck computations can be carried out on features.
All $f$-information measures, including mutual information and divergences based on other convex functions with $f(1)=0$, are invariant under sufficient-statistic reduction.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

An extension the authors leave open is quantification: when features are only approximately sufficient, the equalities degrade, and the modal decomposition suggests a perturbation bound based on discarded singular modes with $\sigma_i<1$. The paper itself stops at the exact case.
The Gács–Körner formula suggests a practical null hypothesis for learning common information: after estimating the CDK singular spectrum, the number of singular values at 1, together with $H$ of the corresponding $f_i^*$, is the quantity to test; finite-sample versions would require deciding how close to 1 counts as 1.
Because Proposition 1 phrases sufficiency purely in terms of the CDK, any information measure that is a function of the CDK may inherit the same separable-computation property; the paper demonstrates this for the listed measures but does not give a general criterion.
In continuous or weak-dependence settings, universal features have known analytic forms, so the same invariance might be derivable outside finite alphabets; the paper's proofs are restricted to finite alphabets.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Quick take: this is a sound, honestly scoped theory paper. The main new results are the Gács–Körner characterization via singular values of the canonical dependence kernel and the Wyner/IB invariance proofs; the mutual-information and f-information invariance is classical and the paper says so. The proofs are mostly rigorous, and the modal-decomposition machinery earns its keep.

Where it is good: Proposition 1 gives a clean equivalence among the two marginal sufficiency conditions, the joint Markov chain, and the density-ratio factorization. The proof of Theorem 2 is elegant: using σ_i ≤ 1 to force coefficient identities in the E[(f(X)-g(Y))^2] expansion is a nice trick, and the resulting characterization of CGK(X,Y) as H(f*_0(X),...,f*_k(X)) with k the largest index having σ_k=1 is genuinely new. The Wyner and IB proofs are longer but coherent, and the construction in Lemma 5 is effective.

Soft spots, in proportion: the big one is the assumption. The theorems all assume S and T are exactly sufficient, i.e., X-S-T-Y. That is a strong condition for the motivating application of learned features; the paper cites [3] noting learned features can fail to carry the needed information, and then gives no approximation bounds or finite-sample statements when sufficiency holds only approximately. That limits practical applicability but does not undermine the internal math. The paper should be more explicit that the guarantees are conditional and that the design question—how to learn features that are approximately sufficient—remains open.

Two smaller issues: Lemma 3 is stated with "Proof: Omitted" but it is easily supplied by the chain rule under the given Markov conditions; Corollary 1's proof is also omitted but it is a direct consequence of Proposition 1. There are minor typos in Eq. (1) (the denominator should be PX(x)PY(y)) and Eq. (25) (f*_i(Y) should be f*_i(X)). None of these affect the main theorems.

Verdict: this deserves a serious referee. The CGK spectral characterization in particular is a worthwhile contribution, and the paper is careful about what it claims. It needs minor revision to fill the omitted proofs and to soften the "practical design" language. I'd bring it to our reading group if we're doing an information-measures session, and I'd cite it if I work on feature-based estimation.

Referee Report

1 major / 5 minor

Summary. The manuscript studies when an information measure theta(X,Y) can be computed from learned feature representations s(X) and t(Y) without loss. Under the standing assumption that s(X) and t(Y) are sufficient statistics for X and Y, equivalently X-s(X)-t(Y)-Y, it proves four invariance results: mutual information and f-information satisfy I_f(X;Y)=I_f(S;T); Wyner's common information satisfies C(X,Y)=C(S,T); Gács-Körner common information is characterized by H(f_0^*(X),...,f_k^*(X)) with k the largest index such that sigma_k=1 in the modal decomposition; and the information bottleneck curve satisfies theta_{X,Y}(R)=theta_{S,T}(R) for all R>=0, with L*_IB(X,Y;beta)=L*_IB(S,T;beta) for all beta>0. The proofs use the canonical dependence kernel and its modal decomposition, together with several Markov-chain lemmas.

Significance. If the results hold, they give a clean conditional guarantee for modular, representation-based estimation of several information measures. The characterization of Gács-Körner common information through the singular modes with unit singular values is a nice connection. The proofs are mostly complete and self-contained, and the Markov-chain structure is made explicit. The main practical caveat, which the paper itself acknowledges, is that the guarantee is conditional on exact sufficiency; no approximation bounds or finite-sample statements are given for approximately sufficient learned features, so the advertised practical scope should be phrased carefully.

major comments (1)

[Section V, Lemma 3] The lemma is stated with 'Proof: Omitted' and is subsequently used in the proof of Lemma 5 and in the proof of Theorem 3, so the information bottleneck invariance arguments depend on an unproved statement. The lemma is true, and a short proof can be supplied via the chain rule, but it should appear in the manuscript for the proof of Theorem 3 to be complete.

minor comments (5)

[Section II-A, Eq. (1)] The denominator of the canonical dependence kernel is written as P_X(y)P_Y(y); it should be P_X(x)P_Y(y).
[Section III-A, Corollary 1] The proof of Corollary 1 is omitted with 'We omit the proof.' Since it follows immediately from Proposition 1, please add the two-line derivation so that the f-information invariance is fully supported.
[Section V-C, Eq. (25)] In the expansion of E[(f(X)-g(Y))^2], the term f_i^*(Y) should be f_i^*(X); the displayed formula currently misstates the argument.
[Section IV] The text reads 'invariance to the choices of sufﬁcient statics'; 'statics' should be 'statistics'.
[Abstract and Introduction] The phrase 'mild assumptions' overstates the condition of exact sufficiency; consider wording that reflects that the theorems are conditional on s(X) and t(Y) being sufficient statistics, since approximate or learned features are outside the proven scope.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the sufficiency-based invariance theorems are proved from the Markov assumptions and modal decomposition, not from their conclusions.

full rationale

The derivation chain is self-contained conditional on the stated sufficiency assumption. Proposition 1 is proven from the definition of sufficiency and elementary density-factorization, and Corollary 1 follows immediately from that factorization. Theorem 1 constructs W' via Lemma 4 and uses the identity I(W';X,Y)=I(W;X,Y)-I(W;X,Y|S,T) to force the optimal W to satisfy W-(X,Y)-(S,T); this is a direct optimality argument, not an assumption of the conclusion. Theorem 2's Gacs-Korner proof is an independent spectral proof: Eq. (25) decomposes E[(f(X)-g(Y))^2] into a sum of nonnegative terms using the bound sigma_i <= 1, forcing f=A f-hat and g=A g-hat, and hence H(f(X)) <= H(f*_0,...,f*_k). The use of Proposition 2, cited as [4, Proposition 2], is a citation to a standalone minimal-sufficiency theorem whose assumptions do not include Gacs-Korner invariance or the separable-computation conclusion; it is therefore independent support rather than a self-referential premise. Theorem 3 follows from Lemma 5, which is proved from the Markov assumptions, and the omitted Lemma 3 is a standard graphoid composition that is readily supplied. No fitted parameter is renamed as a prediction, and no equality is assumed in the form of its conclusion. The only caveats are scope limitations the paper itself states: exact sufficiency is required, and no approximation bounds or finite-sample guarantees are given for learned approximately-sufficient features. The omitted proof of Lemma 3 is a completeness gap, not a circular step.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No free parameters or fitted quantities appear; all results are analytic. The paper imports the modal decomposition framework and minimal-sufficiency theorem from the authors' prior work, and uses one unproved lemma. No new entities are postulated.

assumptions (5)

standard math Data processing inequality (Lemma 1)
Used throughout; cited to Cover and Thomas [12].
domain assumption Modal decomposition of the canonical dependence kernel via SVD (Section II-A), including Proposition 2 that f*(X), g*(Y) are minimal sufficient statistics
This is a known result from the authors' prior work [4],[8],[9]; the paper relies on it for the Gács-Körner proof and for practical feature choices.
standard math Lemma 3 (U-X-Y, U-(X,Y)-Z, X-Z-Y implies U-X-Z-Y), stated without proof
Used in the proof of Theorem 3; the paper omits the proof, though the result is a standard contraction/intersection property.
domain assumption Finite alphabets with positive marginals for X and Y
The paper restricts to finite-alphabet discrete random variables; this bounds the scope and makes the SVD finite-dimensional.
domain assumption S=s(X) and T=t(Y) are exact sufficient statistics, i.e., X-S-T-Y
This is the main hypothesis of Theorems 1-3 and all derived equalities.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Separable Computation of Information Measures." pith.science (2026). https://pith.science/paper/JC5OTKME

@misc{pith2026250115301,
  author       = {Pith},
  title        = {Pith review of: Separable Computation of Information Measures},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/JC5OTKME}},
  note         = {Machine review of arXiv:2501.15301}
}

abstract

We study a separable design for computing information measures, where the information measure is computed from learned feature representations instead of raw data. Under mild assumptions on the feature representations, we demonstrate that a class of information measures admit such separable computation, including mutual information, $f$-information, Wyner's common information, G{\'a}cs--K{\"o}rner common information, and Tishby's information bottleneck. Our development establishes several new connections between information measures and the statistical dependence structure. The characterizations also provide theoretical guarantees of practical designs for estimating information measures through representation learning.

Figures

Figures reproduced from arXiv: 2501.15301 by the authors.

**Figure 1.** Computing an information measure θ(X, Y ) in two steps: (1) obtain transformed variables s(X), t(Y ) and (2) apply an estimator on s(X), t(Y ). For high-dimensional X, Y with unknown probability structures, the first step can be implemented by data-driven approaches, e.g., deep neural network training, corresponding to the feature learning process, where s(X) and t(Y ) are the learned feature representations. we hav… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

12 extracted references · 9 canonical work pages

[3]

Approximating mutual information of high-dimensional variables using le arned representations,

G. Gowri, X. Lun, A. M. Klein, and P . Yin, “Approximating mutual information of high-dimensional variables using le arned representations,” in The Thirty-eighth Annual Conference on Neural Information Processing Systems , 2024. [Online]. Available: https://openreview.net/forum?id=HN05DQxyLl

work page 2024
[1]

Prediction and entropy of printed englis h,

C. E. Shannon, “Prediction and entropy of printed englis h,” Bell system technical journal , vol. 30, no. 1, pp. 50–64, 1951

work page 1951
[2]

Mutual information neural esti mation,

M. I. Belghazi, A. Baratin, S. Rajeshwar, S. Ozair, Y . Ben gio, A. Courville, and D. Hjelm, “Mutual information neural esti mation,” in International conference on machine learning . PMLR, 2018, pp. 531–540

work page 2018
[4]

Dependence induced representations ,

X. Xu and L. Zheng, “Dependence induced representations ,” in 2024 60th Annual Allerton Conference on Communication, Control , and Computing. IEEE, 2024, pp. 1–8

work page 2024
[5]

The common information of two dependent rando m vari- ables,

A. Wyner, “The common information of two dependent rando m vari- ables,” IEEE Transactions on Information Theory , vol. 21, no. 2, pp. 163–179, 1975

work page 1975
[6]

Common information is far less t han mutual information

P . Gács, , and J. Körner, “Common information is far less t han mutual information.” Problems of Control and Information Theory , vol. 2, pp. 149–162, 1973

work page 1973
[7]

The information bottleneck method,

N. Tishby, F. C. Pereira, and W. Bialek, “The information bottleneck method,” arXiv preprint physics/0004057 , 2000

arXiv 2000
[8]

Universal features for high-dimensional learning and inf erence,

S.-L. Huang, A. Makur, G. W. Wornell, and L. Zheng, “Universal features for high-dimensional learning and inf erence,” F oundations and Trends® in Communications and Information Theory, vol. 21, no. 1-2, pp. 1–299, 2024. [Online]. Available: http://dx.doi.org/10.1561/0100000107

doi:10.1561/0100000107 2024

Show all 12 references

[9]

Neural feature learning in function s pace,

X. Xu and L. Zheng, “Neural feature learning in function s pace,” Journal of Machine Learning Research , vol. 25, no. 142, pp. 1–76, 2024

2024
[10]

On sequences of pairs of dependent random variables,

H. S. Witsenhausen, “On sequences of pairs of dependent random variables,” SIAM Journal on Applied Mathematics , vol. 28, no. 1, pp. 100–113, 1975

1975
[11]

Hypothesis testing with co mmunication constraints,

R. Ahlswede and I. Csiszár, “Hypothesis testing with co mmunication constraints,” IEEE transactions on information theory , vol. 32, no. 4, pp. 533–542, 1986

1986
[12]

T. M. Cover and J. A. Thomas, Elements of infor- mation theory (2. ed.) . Wiley, 2006. [Online]. Available: http://www.elementsoﬁnformationtheory.com/

2006

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.

[1] [3]

Approximating mutual information of high-dimensional variables using le arned representations,

G. Gowri, X. Lun, A. M. Klein, and P . Yin, “Approximating mutual information of high-dimensional variables using le arned representations,” in The Thirty-eighth Annual Conference on Neural Information Processing Systems , 2024. [Online]. Available: https://openreview.net/forum?id=HN05DQxyLl

work page 2024

[2] [1]

Prediction and entropy of printed englis h,

C. E. Shannon, “Prediction and entropy of printed englis h,” Bell system technical journal , vol. 30, no. 1, pp. 50–64, 1951

work page 1951

[3] [2]

Mutual information neural esti mation,

M. I. Belghazi, A. Baratin, S. Rajeshwar, S. Ozair, Y . Ben gio, A. Courville, and D. Hjelm, “Mutual information neural esti mation,” in International conference on machine learning . PMLR, 2018, pp. 531–540

work page 2018

[4] [4]

Dependence induced representations ,

X. Xu and L. Zheng, “Dependence induced representations ,” in 2024 60th Annual Allerton Conference on Communication, Control , and Computing. IEEE, 2024, pp. 1–8

work page 2024

[5] [5]

The common information of two dependent rando m vari- ables,

A. Wyner, “The common information of two dependent rando m vari- ables,” IEEE Transactions on Information Theory , vol. 21, no. 2, pp. 163–179, 1975

work page 1975

[6] [6]

Common information is far less t han mutual information

P . Gács, , and J. Körner, “Common information is far less t han mutual information.” Problems of Control and Information Theory , vol. 2, pp. 149–162, 1973

work page 1973

[7] [7]

The information bottleneck method,

N. Tishby, F. C. Pereira, and W. Bialek, “The information bottleneck method,” arXiv preprint physics/0004057 , 2000

arXiv 2000

[8] [8]

Universal features for high-dimensional learning and inf erence,

S.-L. Huang, A. Makur, G. W. Wornell, and L. Zheng, “Universal features for high-dimensional learning and inf erence,” F oundations and Trends® in Communications and Information Theory, vol. 21, no. 1-2, pp. 1–299, 2024. [Online]. Available: http://dx.doi.org/10.1561/0100000107

doi:10.1561/0100000107 2024