REVIEW 4 major objections 4 minor
Linear cost mutual information estimation and independence test of similar performance as HSIC
T0 review · 4 major / 4 minor · reviewed 2026-08-05 · deepseek-v4-flash
Pith's one-line read HCR estimates mutual information at linear cost and matches HSIC sensitivity.
desk verdict Promissory abstract: the HCR-based MI estimator is plausible and worth a full-text look, but the central truncation claim is unproven. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central machinery is the HCR expansion: a hierarchy of mixed moments (first correlation, then variance/homoscedasticity, then higher-order products) whose squared values sum to an approximation of mutual information. Each mixed moment is a normalized centred moment between the two variables; its computation is a single O(n) pass over the data. The hierarchy is what makes the linear cost possible and what connects low-order descriptive statistics to an information-theoretic quantity.
What would settle it
Take two joint distributions that are constructed to be indistinguishable up to all moments included in some fixed HCR depth, but have different true mutual information (e.g., a distribution where dependence appears only in third-order interactions). If HCR with that depth gives the same dependence score for both while HSIC or a direct MI estimate distinguishes them, the approximation is shown to miss higher-order structure.
Extended reading notes
Core claim
The paper's central claim is that mutual information between two samples can be approximated by a sum of squares of normalized mixed moments—features that jointly encode correlation, homoscedasticity, and higher-order interactions. HCR (Hierarchical Correlation Reconstruction) computes these features in O(n) time each and aggregates them into a dependence measure that in tests shows equal or higher sensitivity than HSIC. The same features provide an explicit generative model of the joint distribution at a chosen significance level, which HSIC does not give.
Load-bearing premise
The approximation assumes that low-order mixed moments—up to whatever depth the hierarchy is stopped—capture enough of the joint distribution that the sum of their squares stands in for the true mutual information; if real dependencies live in the omitted high-order moments, the estimate is biased and the test may miss them.
Editorial extensions
If this is right
- Dependence testing on datasets with millions of points becomes feasible on ordinary hardware, since each feature costs O(n) rather than O(n^2.37).
- The sum-of-squares approximation gives a direct way to estimate mutual information without density estimation or binning.
- The moment hierarchy lets users choose a trade-off: O(d^2) features for pairwise dependencies, O(d^3) if triplewise interactions matter, and so on.
- HCR yields a joint distribution model at the chosen significance level, so the same computation that tests independence also describes the dependence structure.
Reading between the lines
- The same moment-based MI approximation could be used as a training objective or regularizer in representation learning, since it is differentiable and linear-cost.
- A natural stress test is to compare HCR against HSIC on distributions engineered to differ only in high-order moments; if the approximation misses those, its sensitivity advantage would vanish.
- The hierarchical construction hints at a whole family of estimators: higher-order moment features could be pruned adaptively to the observed data, yielding an automatic complexity score.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes HCR (Hierarchical Correlation Reconstruction) as a linear-cost alternative to HSIC for dependence testing and mutual information estimation. The abstract claims that HCR computes a single dependence feature—a mixed moment such as correlation or homoscedasticity—in O(n) time, approximates mutual information as a sum of squares of such features, and achieves sensitivity at least matching HSIC in tests, while also providing a joint distribution model at a chosen significance level. The abstract also acknowledges that the number of features scales as O(d^2) for pairwise dependencies and O(d^3) for triplewise dependencies. No derivations, proofs, or experimental details are included in the available abstract-only text.
Significance. If the claims are correct, the paper would offer a practically important speedup: replacing HSIC's O(n^2.37) matrix-based cost with O(n) per feature could enable dependence testing on very large samples. The moment-sum approximation is conceptually simple, and the abstract is honest about the O(d^2) scaling for pairwise feature screening. However, the central assertion that a finite set of low-order mixed moments accurately approximates mutual information is not demonstrated in the abstract. Since the available text contains no derivation, no convergence result, and no experimental evidence, the significance is conditional on a full manuscript that substantiates these claims.
major comments (4)
- [Abstract, second sentence] The load-bearing claim is that mutual information can be approximated as 'just sum of squares of such nontrivial mixed moments.' This is not derived, and finite sets of low-order mixed moments do not in general determine mutual information. For example, distributions can share the same low-order moments up to any fixed order while having arbitrarily large mutual information, or can have vanishing low-order moments while still being strongly dependent. Without a convergence theorem, a truncation error bound, or an explicit class of distributions for which the approximation holds, the central claim is unsupported.
- [Abstract, phrase 'in tests of even higher sensitivity to dependencies'] This sentence reports empirical superiority over HSIC, but the abstract gives no experimental protocol: no sample sizes, no baselines beyond HSIC, no definition of 'sensitivity,' and no quantitative comparison. As written, this is an unverifiable assertion. The full text must provide reproducible experiments and a precise sensitivity metric to support the claim of 'similar performance as HSIC' (or better).
- [Abstract, O(n) complexity statement] The abstract states that a single dependence feature is calculated in O(n) linear time, but also notes that the number of features is O(d^2) for pairwise dependencies. Thus the overall cost of a pairwise independence screen is O(n d^2), not O(n). If the paper's 'linear cost' claim refers to per-feature cost in n, this should be stated explicitly to avoid misleading readers about high-dimensional scaling.
- [Abstract, 'providing actual joint distribution model for chosen significance level'] This claim is vague. It is unclear how a finite set of mixed moments determines a full joint distribution, or how a significance level is selected. The abstract does not explain whether HCR constructs a maximum-entropy distribution, a parametric model, or a nonparametric fit. This is another substantial claim that requires derivation and validation in the full text.
minor comments (4)
- [Abstract, terminology] The term 'mixed moments' is used without definition; in particular, 'homoscedasticity' is not a moment but a property of equal variances. Please clarify the moment-based definitions and the role of each feature.
- [Abstract, 'nontrivial'] The word 'nontrivial' is ambiguous—does it mean nonzero, non-Gaussian, or independent of lower-order moments? A precise definition would help.
- [Title and abstract] The title says 'similar performance as HSIC' while the abstract claims 'even higher sensitivity to dependencies.' These are different claims; they should be aligned or the discrepancy explained.
- [Abstract, 'state-of-art method'] Calling HSIC 'state-of-art' is subjective and may need a broader citation context. Also, the complexity O(n^2.37) is asymptotic; practical implementations often use approximations, so a brief qualification would be useful.
Circularity Check
No circularity visible in abstract; claim is an approximation, not a definition.
full rationale
The abstract presents HCR as an estimator: it approximates mutual information by a sum of squared mixed moments. This is a modeling/approximation claim, not a definition of MI in terms of those moments. No parameter is fitted to MI values, and no self-citation appears. The O(n) cost claim is complexity, not circular. Without the full derivation, no step can be exhibited that reduces a prediction to its inputs. The load-bearing assumption about moment truncation is a correctness concern, not circularity. Per instructions, absence of full text prevents identifying specific equations, and speculation is prohibited. Honest non-finding is appropriate.
Assumptions & free parameters
free parameters (1)
- Moment truncation order (number of mixed moments) =
Not specified; complexity varies as O(d^2) for pairwise, O(d^3) for triplewise
assumptions (3)
- domain assumption The joint distribution of the two variables is adequately described by a set of low-order mixed moments (correlation, homoscedasticity, etc.)
- domain assumption Mutual information can be approximated by the sum of squares of standardized mixed moments
- ad hoc to paper HCR provides a valid hierarchical expansion of the joint distribution
Cite this review
Pith. "Pith review of Linear cost mutual information estimation and independence test of similar performance as HSIC." pith.science (2026). https://pith.science/paper/WS2DZB2Y
@misc{pith2026250818338,
author = {Pith},
title = {Pith review of: Linear cost mutual information estimation and independence test of similar performance as HSIC},
year = {2026},
howpublished = {\url{https://pith.science/paper/WS2DZB2Y}},
note = {Machine review of arXiv:2508.18338}
}
abstract
Evaluation of statistical dependencies between two data samples is a basic problem of data science/machine learning, and HSIC (Hilbert-Schmidt Information Criterion)~\cite{HSIC} is considered the state-of-art method. However, for size $n$ data sample it requires multiplication of $n\times n$ matrices, what currently needs $\sim O(n^{2.37})$ computational complexity~\cite{mult}, making it impractical for large data samples. We discuss HCR (Hierarchical Correlation Reconstruction) as its linear cost practical alternative, in tests of even higher sensitivity to dependencies, and additionally providing actual joint distribution model for chosen significance level, by description of dependencies through features being mixed moments, starting with correlation and homoscedasticity. Also allowing to approximate mutual information as just sum of squares of such nontrivial mixed moments between two data samples. Such single dependence describing feature is calculated in $O(n)$ linear time. Their number to test varies with dimension $d$ - requiring $O(d^2)$ for pairwise dependencies, $O(d^3)$ if wanting to also consider more subtle triplewise, and so on.
Reviewed August 5, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.