Entropy Doubling as a Detector of Hidden Subclasses

Classifiers trained on coarse labels such as "pneumothorax" or "blond hair" often do well on average and badly on a rare subgroup that nobody labeled. A known example is chest X-ray models that learn to spot chest drains, the tubes placed after treatment, so they fail on untreated patients who have no drain. This proposal tests a simple idea from information theory for finding such subgroups without labels. If you quantize a one-dimensional projection of a model's features to integers, then add two independent draws from the same class and measure how much the Shannon entropy grows, the growth is small and predictable when the class forms one smooth lump. It is systematically larger when the class is secretly a mixture of separated lumps. The reason is that sums of draws from different lumps land in new places, so the distribution of the sum spreads out more than it would for a single lump. Research on the discrete entropy power inequality gives the floor on this growth, and results on discrete log-concave distributions constrain what a single smooth lump can do. Together they supply a calibrated null band, and exceeding that band is evidence of hidden structure.

The practical question is whether this "entropy doubling" test finds minority subclasses that clustering-based discovery misses. The case that matters most is the one where subclasses overlap in the full feature space but separate along a few directions. The literature names this regime as the place where current methods break, and it is also where a one-dimensional, calibrated statistic could help. The proposal builds the detector and derives how its detection threshold depends on minority size. It then compares the detector head-to-head against clustering and against simpler non-Gaussianity indices on standard worst-group benchmarks.

Core Claim

Take class-conditional features $z$ with class label $y$, a unit direction $w$, and a quantizer $Q$ that rounds $w^\top z$ to an integer grid. The within-class entropy doubling is

$$D(w) = H\big(Q(w^\top z) + Q(w^\top z') \mid y\big) - H\big(Q(w^\top z) \mid y\big),$$

where $z, z'$ are independent draws from the same class. The distribution of the sum is the self-convolution of the empirical histogram, so no pairing of samples is needed. A new entropy power inequality for integer-valued random variables proves $D(w) \ge g(H)$ for a universal, strictly positive function $g$. Its conditional form $H(X+X' \mid Y,Y') - H(X\mid Y) \ge \bar g(H(X\mid Y))$ is exactly the class-conditioned quantity above. That paper is purely information-theoretic. Here its lower bound serves as the floor of a test.

The claim is that $D(w)$ has an upper envelope when the within-class projection is a single discrete log-concave lump, and that mixtures exceed it. The upper envelope is to be derived using the concentration-function machinery of Concentration functions and entropy bounds for discrete log-concave distributions. Consider a two-component mixture with minority weight $p$ and separation large relative to component width. A direct calculation over the three sum locations (both majority, mixed, both minority) gives an excess over the single-lump value of order $p\log(1/p)$. That is the minority's own contribution to label entropy. It suggests detection needs roughly $n \gtrsim 1/(p\log(1/p))^2$ samples up to estimator constants, by the usual $1/\sqrt n$ fluctuation of plug-in entropy on a small support.

This scaling is honest about the difficulty: very rare strata give a weak signal. The regime where the test can plausibly win is different. It is the regime where the minority is well separated along some direction yet buried in the full space. There, a one-dimensional histogram estimate is statistically cheap while high-dimensional clustering is not.

Coarse discretization is a deliberate choice, not a convenience. Equivalence of Additive-Combinatorial Linear Inequalities for Shannon Entropy and Differential Entropy shows that balanced inequalities transfer between discrete and differential entropy under fine quantization, but affine ones with constant offsets do not. An entropy power bound with a gap term is such an affine statement. At coarse bin widths the discrete test is therefore genuinely different from its continuous counterpart, and it has its own null band. The companion paper On additive-combinatorial affine inequalities for Shannon entropy and differential entropy motivates treating bin width as an explicit parameter rather than letting it go to zero.

Research Program

The theory component has two parts. First, derive or tabulate the upper envelope of $D$ for discrete log-concave pmfs as a function of $H$. The spiky versus diffuse decomposition used in A New Entropy Power Inequality for Integer-Valued Random Variables and the log-concave concentration bounds above are the starting tools. Where closed forms are out of reach, compute the envelope numerically over parameterized log-concave families. Second, bound the excess doubling for two- and $k$-component mixtures in terms of weights and separation. This gives a detection phase diagram that speaks directly to the "low slice strength" failure reported for Domino: Discovering Systematic Errors with Cross-Modal Embeddings.

The method component searches for directions. Within each class, it scores candidate directions by $D(w)$ minus the envelope, bootstrapped for a p-value. Candidates come from the top within-class principal components, random projections, and a gradient-free local refinement; a soft-histogram relaxation allows gradient ascent as a variant. The method then splits the class at the valley of the histogram along the best significant direction and recurses until nothing exceeds the band. The resulting pseudo-groups are passed to Group Distributionally Robust Optimization (Group DRO), which minimizes the loss of the worst-off group. The recipe follows Distributionally Robust Neural Networks for Group Shifts, including its strong $L_2$ penalty and group-size adjustment. This mirrors the discover-then-retrain protocol of No Subclass Left Behind, GEORGE, so that only the discovery step differs.

Baselines

The naive reference is standard empirical risk minimization, which minimizes average loss with no group information. Distributionally Robust Neural Networks for Group Shifts reports worst-group accuracy under this setup of 60.0% on Waterbirds, 41.1% on CelebA (blond males), and 65.7% on MultiNLI. It is rerun with the same backbones.

The upper reference is Group DRO with oracle group labels. The same paper reports it at 90.5%, 86.7%, and 77.7% worst-group accuracy respectively. Closing the gap between these two anchors is the scale for all results.

The strongest label-free competitor on the retraining task is GEORGE. It clusters UMAP-reduced penultimate features with a silhouette-selected Gaussian mixture, then runs Group DRO on the clusters, and it reports gains of up to 14–15 points in worst-case subclass accuracy and closing up to 62% of the gap to the oracle. No per-dataset GEORGE worst-group number was found on Lacuna for Waterbirds, CelebA, or MultiNLI, so GEORGE is rerun under identical features, the same Group DRO tuning grid, and the same validation budget.

The strongest competitor on discovery is Domino. It fits an error-aware mixture over cross-modal embeddings, labels, and predictions, and reports recovering 36% of ground-truth slices on its benchmark versus 24% for unimodal clustering. For discovery, the proposed test is run on the same CLIP-style embeddings Domino uses, and also conditioned on the model's correctness, which parallels Domino's use of predictions.

Beating GEORGE means higher worst-group accuracy with inferred groups on at least two of the three standard benchmarks, at equal average-accuracy cost, averaged over seeds with intervals. Beating Domino means a higher slice recovery rate on its suite.

Two ablations isolate the key ingredient. The first keeps the identical direction search and splitting but swaps the score for classical non-Gaussianity indices: excess kurtosis, a negentropy approximation, and Hartigan's dip statistic. The second swaps discrete doubling for a continuous kernel estimate of $h(X+X')-h(X)$ at matched sample size.

Why not just…?

Why not just use kurtosis or negentropy projection pursuit, which already hunts for non-Gaussian directions? This is the real threat, since doubling is a relative of negentropy. The first ablation is designed to settle it. The expected advantage is narrow and specific. Kurtosis is dominated by tails and can be positive or negative for mixtures depending on weights. A small separated minority, however, adds new sum locations that doubling picks up regardless of which side it sits on. If kurtosis or dip matches doubling on the synthetic phase diagram and on the benchmarks, the practical contribution collapses. The note would then report the detection-threshold theory as the result and not claim a better detector.

Why not just cluster penultimate features, as GEORGE does? GEORGE's own authors state that it fails when subclasses are not separable in feature space. Learning With Multi-Group Guarantees For Clusterable Subpopulations proves that cluster-then-predict pipelines are brittle under overlap and converge more slowly. Neither result shows that a one-dimensional test does better, so a synthetic study plants a minority separated along a single direction while overlapping elsewhere and varies its weight and separation. If GEORGE recovers it as often as doubling, the proposal's niche does not exist.

Why not just use a larger pretrained model? The Effect of Model Size on Worst-Group Generalization finds larger pretrained models cut Waterbirds worst-group error by about 18.39%. It also finds they leave a substantial gap and plateau on CelebA. The detector is therefore run on features from both small and large backbones, to check that its gains do not vanish as the backbone grows.

Proposed Experiments

The decisive synthetic check is the phase diagram. Integer-valued mixtures are generated with minority weight $p$ ranging from well under a tenth up to a half, together with varying separations. Undersampled MNIST, in which one digit is artificially rare, provides a real-image counterpart. The measured detection boundary should follow the predicted $p\log(1/p)$ scaling, which comes from the three-location sum calculation. If it does not, the theory is wrong regardless of benchmark numbers.

The benchmark experiments cover Waterbirds, CelebA, and MultiNLI with ResNet and BERT backbones. They measure worst-group accuracy after Group DRO on inferred groups, and group recovery measured against the held-out true groups. The Domino suite is used for slice recovery. The medical cases in Hidden Stratification Causes Clinically Meaningful Failures in Machine Learning for Medical Imaging provide a qualitative test: whether the top-scoring direction on chest X-ray features separates drain from no-drain cases. That paper reports ROC AUC of 0.94 with drains versus 0.77 without on CXR14.

The quantization bin width is swept from coarse to fine. The predicted signature is that the discrete test diverges from the continuous ablation only at coarse widths, as the affine-inequality results imply. If the discrete test never outperforms the continuous estimate at any width, discreteness adds nothing and the proposal says so.