Pareto-optimal data compression for binary classification tasks

Max Tegmark (MIT); Tailin Wu (MIT)

REVIEW 2 major objections 5 minor 41 references

Pareto-optimal data compression for binary classification tasks

T0 review · 2 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read For binary classification, the Pareto-optimal lossy compressions are exactly contiguous binnings of the class-probability score.

desk verdict A clean theorem about binning the posterior, but the headline claim about compressing X is one reduction step ahead of the proof. read the letter →

arxiv 1908.08961 v2 pith:EAE5HWSH submitted 2019-08-23 cs.LG cs.CVcs.ITmath.ITstat.ML

Max Tegmark (MIT) , Tailin Wu (MIT) This is my paper · ORCID

classification cs.LGcs.CVcs.ITmath.ITstat.ML MSC 94A1594A1762B10

keywords ParetofrontierlossycompressionmutualinformationDiscreteBottleneckbinaryclassificationposteriorprobabilitybinningsufficientstatisticimageclustering

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 is about the trade-off between how many bits you keep from a data set and how much label information those bits retain. Its thesis is that for binary classification this trade-off has a simple exact solution: the only compressions that need to be considered are groupings of the classifier's probability score P(Y=1|X) into contiguous intervals. It first proves the score itself is a lossless distillation, so replacing each image by one real number W=P(Y=1|X) loses no mutual information with the label. Then it proves that binning W into adjacent intervals spans the full Pareto frontier of entropy versus mutual information, turning a hard multiobjective search into a one-dimensional scan of bin boundaries. The payoff is that optimal image clustering, as demonstrated on cats-versus-dogs and digits, becomes an information-theoretically principled procedure rather than a heuristic.

What carries the argument

The load-bearing object is W, the distilled posterior P(Y|X), normalized to a uniform random variable and sorted so the conditional probability P(W|Y=1) increases. The compression is the contiguous binning function B(W,b), which sends W to the integer label of the interval containing it. The Contiguous Binning Theorem (Theorem II.2) is the mechanism: it reduces the original infinite search over encodings of X to a finite-dimensional search over bin-boundary vectors, using a swap operation that moves small measure between bins to push conditional probabilities apart, thereby increasing I(Z,Y) at fixed H(Z).

What would settle it

Enumerate every two-group partition of a small uniform score W with increasing P(W|Y=1) and check whether any non-contiguous grouping gives more label information at the same entropy than the best contiguous binning; one such point would refute the theorem.

Watch

Extended reading notes

Core claim

The central claim is the Contiguous Binning Theorem: if the distilled score W is uniformly distributed and P(W|Y=1) is monotonically increasing, then every Pareto-optimal point (H(Z), I(Z,Y)) is realized by binning W into contiguous intervals. Consequently the points that maximize I(Z,Y) for a fixed number of bins m, the corners of the frontier, can be found by ordinary single-objective optimization over bin boundaries instead of multiobjective or iterative schemes. The proof works by swapping tiny pieces of measure between bins with different conditional probabilities; because such swaps spread the conditional probabilities further apart, they strictly raise mutual information while keeping both marginals fixed. Repeating the swap eliminates any non-contiguous support. Since uniformization and sorting by conditional probability are lossless, the theorem applies to any binary classification task once W is estimated, and the paper verifies the resulting frontiers on MNIST, Fashion-MNIST, and CIFAR-10. Those frontiers turn out to be non-concave, which explains why the linear DIB objective jumps between corners: the phase transitions reported in DIB learning are transitions between different cluster counts.

Load-bearing premise

The method compresses the distilled score W rather than the raw data X, and the whole claim rests on W carrying everything X knows about Y; the paper states this but does not separately prove that an optimal encoder for X can always be replaced by one reading only W.

Editorial extensions

If this is right

For binary classification, the full trade-off curve can be mapped exactly by scanning bin boundaries, without multiobjective optimization or iterative Information Bottleneck alternation.
The DIB phase transitions observed in prior work are transitions between frontier corners, i.e., changes in the number of clusters, because the frontier is non-concave.
Grouping images into a handful of clusters by probability score retains nearly all useful label information: the paper reports five clusters capture 99% of the available information in the cat/dog example.
High classification accuracy does not imply high information retention; 99% binary accuracy corresponds to roughly 0.92 bits, and simply rounding the probability score to fixed decimals is suboptimal.
The resulting clusters are deterministic and information-theoretically optimal soft classifiers, with the usual generalization benefits of compression.

Reading between the lines

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

Editorial inference: the contiguous-binning theorem suggests a calibration test: when the trained score W is well calibrated (P(Y=1|W)=W), the exact frontier can be computed from the empirical distribution of W alone, so the method should transfer to any probabilistic classifier, not just neural networks.
Editorial inference: for multi-class tasks the lossless distillation produces an (n-1)-dimensional posterior vector, and the likely generalization is that optimal frontiers live on contiguous regions of the probability simplex ordered by likelihood ratio; a direct extension would make the bin-boundary scan exponential in classes.
Editorial inference: because the frontiers are non-concave, any downstream system that pays a linear cost per stored bit will prefer the corners; this predicts that practical soft-classifier designs with a storage penalty should use a few well-chosen bins rather than interpolating along the frontier.
Editorial inference: the vertical-binning reformulation suggests a practical shortcut that the paper notes but does not develop: bin the conditional probability P(Y=1|W) itself into equal-width slices, which can be implemented without fitting the distribution f(W|Y).

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

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 genuinely useful paper for the DIB crowd. The Contiguous Binning Theorem is a real extension of Kurkoski-Yagi's fixed-bin-count optimality result to the full entropy-information frontier, and the experimental demonstration on real images is engaging. But the paper's own headline claim—that this solves the Pareto frontier for compressing X—is not quite what the proof shows. The theorem proves optimality among deterministic functions of the distilled posterior W. Every W-only encoder is an X-encoder, so that direction is fine. The other direction is missing: an arbitrary deterministic g(X) induces a stochastic channel from W to Z, and the proof never shows that some deterministic binning of W can match or beat that channel. A concavity/extreme-point argument could likely close this, and the classical likelihood-ratio quantizer results suggest it is true, but it is not in the paper. That is a load-bearing omission, not a footnote.

The lossless distillation theorem is correct (it is the sufficiency of the posterior, well known), and the uniformization/sorting steps are sensible. The proof of Theorem II.2 itself is solid; the swapping argument is clean. I also credit the authors for explicitly noting that the DIB linear objective cannot find convex parts of the frontier, which is a real insight, and for the comparison against Blahut-Arimoto on the toy example.

Softer issues: the monotonicity assumption is handled by binning and sorting, which is only approximate for continuous W; fine in practice, but the theorem is stated for the continuous case. The experiments report '99% of class information' for CIFAR-10 with five bins, but that figure is relative to a lower bound on I(X,Y) derived from the classifier's cross-entropy, and there are no error bars or repeated runs. The GitHub link is given but without a commit hash, so reproducibility is slightly weaker than ideal. None of these are fatal, but a referee should ask for the X-to-W step to be proven or stated as an assumption, and for the information numbers to be qualified as lower-bound estimates.

Paper is for readers working on information bottleneck, likelihood-ratio quantization, or interpretable clustering. It deserves a serious referee, even though my own verdict would be conditional on the gap being patched.

Referee Report

2 major / 5 minor

Summary. The paper addresses lossy compression of a data variable X into a discrete code Z=f(X) for binary classification, with the goal of mapping the Pareto frontier of (H(Z), I(Z,Y)). It first proves a lossless distillation theorem: for Y in {1,...,n}, the posterior vector W=P(Y|X) satisfies I(W,Y)=I(X,Y), so W is a sufficient statistic. For binary Y, the paper then claims that after uniformizing W and making the conditional probability P(Y=1|W) monotone, the entire Pareto frontier of the original compression problem is obtained by binning W into contiguous intervals. This reduces the frontier computation to a one-dimensional search over bin boundaries. The method is demonstrated on an analytic toy model, MNIST, Fashion-MNIST, and CIFAR-10, and is compared with the Blahut-Arimoto method for the DIB objective. The paper also interprets DIB phase transitions as transitions between 'corner' points of the Pareto frontier.

Significance. If the main theorem is fully established for the original X-compression problem, this is a valuable result: it gives an exact, finite-dimensional characterization of the DIB Pareto frontier under a monotone-likelihood condition, replacing iterative approximations with a direct search and clarifying the non-concave structure of the frontier. The lossless distillation theorem (Theorem II.1) is clean and correct, and Appendix A provides a quantitative bound on the information lost by fine binning. The release of code and the comparison with Blahut-Arimoto are also strengths. The principal weakness is a scope gap: the proof of Theorem II.2 is carried out for deterministic functions of W, whereas the paper's headline claims are about deterministic functions of X. The result is likely repairable, but the missing reduction is load-bearing.

major comments (2)

[§II.B.4, Eq. (21); §II.C] The original problem in Eq. (1) optimizes over deterministic encoders g: X -> Z, but Theorem II.2 and Eq. (21) optimize over deterministic encoders g: W -> Z. The proof of Theorem II.2 even begins by writing 'Z≡g(X)' and then immediately defines μ_i = {w ∈ [0,1] : g(w)=i}, so the argument is entirely about functions of W. Because W is a deterministic function of X, every W-encoder is an admissible X-encoder, which gives achievability of the frontier by binning W. The converse, however, is not established: an X-encoder may split individual level sets {x : w(x)=w} and thereby induce a genuinely stochastic map from W to Z, and the data-processing inequality I(Z,Y) ≤ I(W,Y) does not imply that every such X-encoder is dominated by a deterministic W-encoder. This missing equivalence is load-bearing because the abstract and Section II.C claim that the full Pareto frontier for compressing X is obtained by binning W. The authors should either prove the reduction (for example, by showing that any stochastic channel W -> Z is dominated by a deterministic W -> Z for the (H,I) tradeoff, or by a direct extreme-point argument), or restate Theorem II.2 as a result about the W-compression problem and weaken the claims about X accordingly.
[§II.B.4, proof of Theorem II.2] The proof's swap argument assumes that the non-contiguous binning has a bin k whose support has two separated components with some other bin l occupying the interval between them. The text handles the case p_k = p_l by saying it 'swap[s] to entirely eliminate the discontiguity, and repeat[s] our swapping procedure between other bins until we increase the entropy (again obtaining a contradiction) or end up with a fully contiguous binning.' This case is not proved in detail: it is not shown that the required swaps can always be performed without changing the marginal bin probabilities, nor that the process terminates with a definite contradiction when a non-contiguous optimal binning exists. Since the theorem is the central result, this gap should be closed with a precise argument or by citing a standard result.

minor comments (5)

[§II.B.4] In Theorem II.2, the notation 'bin boundaries b1 < ... < bn−1' reuses n, which already denotes the number of classes; use a different symbol such as M or N for the number of bins.
[§II.B.2, Eq. (31)] In the definition of f(w,a), the variable x appears inside the sum and in the polynomial term, but the function is written as a function of w; replace x with w for consistency.
[§II.B.4, proof of Theorem II.2] The first sentence of the proof says 'Z≡g(X)' even though the theorem concerns g(W); this wording obscures the fact that the proof does not address general functions of X and should be corrected.
[Table II] The CIFAR-10 entries for cat and dog appear as two-line rows, which makes it unclear which coefficient vector corresponds to which class and how the two lines relate to equations (34)–(38); please format this more clearly.
[Abstract and §III.D] There are a few typos: 'can be conveniently be found' in the abstract and 'traveoﬀ' in Section III.D should read 'can conveniently be found' and 'tradeoff', respectively.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the Pareto-frontier proof is self-contained and does not reduce to its inputs.

full rationale

The derivation chain is self-contained. Theorem II.1 defines W = P(Y|X) and proves I(W,Y)=I(X,Y) directly from the identity P(Y|X)=P(Y|W); this is a definitional identity with a proof, not a fitted input. Theorem II.2 is the load-bearing result, and its proof is constructive: it uses Theorem B.1, proved by differentiating mutual information with respect to an epsilon transfer of probability mass, to show that non-contiguous binnings can be improved while preserving H(Z), so a Pareto-optimal point must be contiguous. The uniformization and monotonic-sorting steps are explicitly justified as information-preserving reparameterizations, and the experiments fit density models only to display the method, not to generate the theorem. The only notable logical concern is the leap from Eq. (21), which optimizes deterministic encoders of W, to Eq. (1), which optimizes encoders of X; but that is an unproven equivalence (a correctness risk), not a circular reduction, because the paper never defines the conclusion into the premise. There is a self-citation in the discussion of DIB phase transitions (refs. [24,25]), but that interpretation is not load-bearing for the main derivation.

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

The theorem itself is parameter-free. The free parameters enter only in the experimental pipeline: the density fits in Table II and the trained network weights. The main unproven premise is the reduction from functions of X to functions of W. The sufficiency of the posterior is standard. No new entities are postulated.

free parameters (2)

density fit coefficients a for P(W|Y) = Table II lists coefficients for each dataset and class, e.g., for CIFAR-10 cat: 0.9230, 0.2165, 0.0859, 6.0013…
These coefficients parameterize the estimated conditional distributions P(W|Y) used to compute the Pareto frontiers in Figure 8. They are fitted to the outputs of trained neural networks and carry no uncertainty estimates.
CIFAR-10 specialized fit parameters aA and aB = Table II, CIFAR-10 rows
For CIFAR-10, the density is fit with the more complex form of equations (34)-(38), adding extra parameters beyond the standard polynomial-exponential family of equation (31).

assumptions (5)

standard math The posterior P(Y|X) is a sufficient statistic for Y, so I(W,Y)=I(X,Y).
Proved as Theorem II.1; this is a classical sufficient-statistic result, not an ad hoc assumption.
domain assumption W can be assumed uniform and p1(w) monotonic without loss of generality.
Used in Theorem II.2 through the uniformization step (16) and the sorting step. The uniformization is invertible, but the sorting step requires a measure-preserving rearrangement, which is standard but not explicitly proven.
ad hoc to paper Every deterministic encoder X->Z can be replaced by a deterministic encoder W->Z without worsening the DIB tradeoff.
This reduction is implicit in Section II.B but not proven. Theorem II.2 is proven for functions of W, while the Pareto frontier in equation (1) is over all functions of X. This is the weakest premiss of the paper.
domain assumption The parametric family of equation (31) can approximate the true conditional densities well enough for the reported frontiers.
The paper reports small KL divergences for the toy example, but no approximation bounds are given for the real datasets, so the computed frontiers are estimates.
domain assumption The trained neural network outputs approximate the true posterior P(Y|X).
Section III.E acknowledges the classifiers are imperfect and overconfident; the computed frontiers are for the approximated W, not for the true X, and the true I(X,Y) is unknown.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Pareto-optimal data compression for binary classification tasks." pith.science (2026). https://pith.science/paper/EAE5HWSH

@misc{pith2026190808961,
  author       = {Pith},
  title        = {Pith review of: Pareto-optimal data compression for binary classification tasks},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EAE5HWSH}},
  note         = {Machine review of arXiv:1908.08961}
}

abstract

The goal of lossy data compression is to reduce the storage cost of a data set $X$ while retaining as much information as possible about something ($Y$) that you care about. For example, what aspects of an image $X$ contain the most information about whether it depicts a cat? Mathematically, this corresponds to finding a mapping $X\to Z\equiv f(X)$ that maximizes the mutual information $I(Z,Y)$ while the entropy $H(Z)$ is kept below some fixed threshold. We present a method for mapping out the Pareto frontier for classification tasks, reflecting the tradeoff between retained entropy and class information. We first show how a random variable $X$ (an image, say) drawn from a class $Y\in\{1,...,n\}$ can be distilled into a vector $W=f(X)\in \mathbb{R}^{n-1}$ losslessly, so that $I(W,Y)=I(X,Y)$; for example, for a binary classification task of cats and dogs, each image $X$ is mapped into a single real number $W$ retaining all information that helps distinguish cats from dogs. For the $n=2$ case of binary classification, we then show how $W$ can be further compressed into a discrete variable $Z=g_\beta(W)\in\{1,...,m_\beta\}$ by binning $W$ into $m_\beta$ bins, in such a way that varying the parameter $\beta$ sweeps out the full Pareto frontier, solving a generalization of the Discrete Information Bottleneck (DIB) problem. We argue that the most interesting points on this frontier are "corners" maximizing $I(Z,Y)$ for a fixed number of bins $m=2,3...$ which can be conveniently be found without multiobjective optimization. We apply this method to the CIFAR-10, MNIST and Fashion-MNIST datasets, illustrating how it can be interpreted as an information-theoretically optimal image clustering algorithm.

Figures

Figures reproduced from arXiv: 1908.08961 by the authors.

**Figure 3.** FIG. 3: Essentially all information about [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗

**Figure 2.** FIG. 2: Sample data from Section III. Images from MMNIST [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗

Figures from the paper (5 more)

**Figure 4.** Figure 4: FIG. 4: The reason that the Pareto frontier can never be [PITH_FULL_IMAGE:figures/full_fig_p006_4.png]

**Figure 5.** Figure 5: FIG. 5: Contour plot of the function [PITH_FULL_IMAGE:figures/full_fig_p009_5.png]

**Figure 6.** Figure 6: shows observed cumulative distribution functions Fi(w) (solid curves) for the Wi = P(Y = 1|Xi) 10 The architecture is adapted from github.com/kuangliu/pytorchcifar, for which we use its ResNet18 model; the only difference in architecture is that we use 2 rather than …

**Figure 7.** Figure 7: FIG. 7: The solid curves show the actual conditional proba [PITH_FULL_IMAGE:figures/full_fig_p011_7.png]

**Figure 9.** Figure 9: FIG. 9: The Pareto frontier our analytic example is computed [PITH_FULL_IMAGE:figures/full_fig_p013_9.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

41 extracted references · 35 canonical work pages

[1]

Uniformization of W For convenience and without loss of generality, we will henceforth assume that f(w) = 1, i.e., that W has a uniform distribution on the unit interval [0 , 1]. We can do this because if W were not uniformly distributed, we could make it so by using the standard statistical tech- nique of applying its cumulative probability distribution ...

work page
[2]

Pareto-optimal

Binning W Given a set of bin boundaries b1 < b2 < ... < bn−1 grouped into a vector b, we deﬁne the integer-value con- 6 Throughout this paper, we will use the term “Pareto-optimal” or “optimal” in this sense, i.e., maximizing I(X, Y ) for a ﬁxed H(Z). 5 FIG. 2: Sample data from Section III. Images from MMNIST (top), Fashion-MNIST (middle) and CIFAR-10 are...

work page
[3]

Making the conditional probability monotonic For convenience and without loss of generality, we can assume that the conditional probability distribution ¯p1(w) is a monotonically increasing function. We can do this because if this were not the case, we could make it so by sorting the bins by increasing conditional probabil- ity, as illustrated in Figure 3...

work page
[4]

While ﬁne-grained binning has no eﬀect on the entropy H(Y ) and negligible eﬀect on I(W,Y ), it dramatically reduces the entropy of our data

Proof that Pareto frontier is spanned by contiguous binnings We are now ﬁnally ready to tackle the core goal of this paper: mapping the Pareto frontier ( H∗,I∗) of opti- mal data compression X↦→ Z that reﬂects the tradeoﬀ between H(Z) and I(Z,Y ). While ﬁne-grained binning has no eﬀect on the entropy H(Y ) and negligible eﬀect on I(W,Y ), it dramatically ...

work page
[5]

Only Pkj and Plj change,

work page
[6]

both marginal distributions remain the same,

work page
[7]

horizontal

the new conditional probabilities p′ k andp′ l are fur- ther apart. Figure 4 shows how this can be accomplished for non- contiguous binning: let k be a bin with non-contiguous support set µk (bin 2 in the illustrated example), let l be a bin whose support µl (bin 4 in the example) contains a positive measure subset µmid l ⊂ µl within two parts µleft k and...

work page
[8]

For practical exam- ples where this is not the case, we can instead train a neural network to implement a function ˆw(X) that ap- proximatesP (Y =1|X)

Approximating w(X) For our toy example, we knew the conditional proba- bility distribution P (Y|X) and could therefore compute W = w(X) = P (Y =1|X) exactly. For practical exam- ples where this is not the case, we can instead train a neural network to implement a function ˆw(X) that ap- proximatesP (Y =1|X). For our toy example, we train a fully connected...

work page

Show all 41 references

[9]

cat” and “dog

Approximating f1(W ) For practical examples where the conditional joint probability distributionP (W,Y ) cannot be computed an- alytically, we need to estimate it from the observed dis- tribution ofW -values output by the neural network. For our examples, we do this by ﬁtting ...
[10]

Pearson, The London, Edinburgh, and Dublin Philo- sophical Magazine and Journal of Science 2, 559 (1901)

K. Pearson, The London, Edinburgh, and Dublin Philo- sophical Magazine and Journal of Science 2, 559 (1901)

1901
[11]

Vincent, H

P. Vincent, H. Larochelle, Y. Bengio, and P.-A. Man- zagol, in Proceedings of the 25th international conference on Machine learning (ACM, 2008), pp. 1096–1103

2008
[12]

Goodfellow, J

I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Ben- gio, in Advances in neural information processing systems (2014), pp. 2672–2680

2014
[13]

Hotelling, Biometrica 28, 321 (1936)

H. Hotelling, Biometrica 28, 321 (1936)

1936
[14]

Eckart and G

C. Eckart and G. Young, Psychometrika 1, 211 (1936)

1936
[15]

A. v. d. Oord, Y. Li, and O. Vinyals, arXiv preprint arXiv:1807.03748 (2018)

2018 arXiv
[16]

D. G. Clark, J. A. Livezey, and K. E. Bouchard, arXiv preprint arXiv:1905.09944 (2019)

2019 arXiv
[17]

Tegmark, arXiv preprint arXiv:1902.03364 (2019)

M. Tegmark, arXiv preprint arXiv:1902.03364 (2019)

2019 arXiv
[18]

B. M. Kurkoski and H. Yagi, IEEE Transactions on In- formation Theory 60, 4544 (2014)

2014
[19]

Tishby, F

N. Tishby, F. C. Pereira, and W. Bialek, arXiv preprint physics/0004057 (2000)

2000 arXiv
[20]

A. Tan, L. Meshulam, W. Bialek, and D. Schwab, Bul- letin of the American Physical Society (2019)

2019
[21]

Strouse and D

D. Strouse and D. J. Schwab, Neural computation 29, 1611 (2017)

2017
[22]

A. A. Alemi, I. Fischer, J. V. Dillon, and K. Murphy, arXiv preprint arXiv:1612.00410 (2016)

2016 arXiv
[23]

Chalk, O

M. Chalk, O. Marre, and G. Tkacik, in Advances in Neu- ral Information Processing Systems (2016), pp. 1957– 1965

2016
[24]

Fischer, The conditional entropy bottleneck (2018), URL openreview.net/forum?id=rkVOXhAqY7

I. Fischer, The conditional entropy bottleneck (2018), URL openreview.net/forum?id=rkVOXhAqY7

2018
[25]

R. A. Amjad and B. C. Geiger, IEEE Transactions on Pattern Analysis and Machine Intelligence (2019)

2019
[26]

I. Y. Kim and O. L. de Weck, Structural and multidisci- plinary optimization 29, 149 (2005)

2005
[27]

Krizhevsky, V

A. Krizhevsky, V. Nair, and G. Hinton, online: http://www. cs. toronto. edu/kriz/cifar. html 55 (2014)

2014
[28]

LeCun, C

Y. LeCun, C. Cortes, and C. Burges, AT&T Labs [On- line]. Available: http://yann. lecun. com/exdb/mnist 2, 18 (2010)

2010
[29]

H. Xiao, K. Rasul, and R. Vollgraf, arXiv preprint arXiv:1708.07747 (2017)

2017 arXiv
[30]

Krizhevsky and G

A. Krizhevsky and G. Hinton, Tech. Rep., Citeseer (2009)

2009
[31]

K. He, X. Zhang, S. Ren, and J. Sun, in Proceedings of the IEEE conference on computer vision and pattern recognition (2016), pp. 770–778

2016
[32]

Strouse and D

D. Strouse and D. J. Schwab, Neural computation 31, 596 (2019)

2019
[33]

T. Wu, I. Fischer, I. Chuang, and M. Tegmark, arXiv preprint arXiv:1907.07331 (2019)

2019 arXiv
[34]

T. Wu, I. Fischer, I. Chuang, and M. Tegmark, Entropy 21, 924 (2019)

2019
[35]

Thompson, A

J. Thompson, A. J. Garner, J. R. Mahoney, J. P. Crutch- ﬁeld, V. Vedral, and M. Gu, Physical Review X8, 031013 (2018)

2018
[36]

Blahut, IEEE transactions on Information Theory 18, 460 (1972)

R. Blahut, IEEE transactions on Information Theory 18, 460 (1972)

1972
[37]

Arimoto, IEEE Transactions on Information Theory 18, 14 (1972)

S. Arimoto, IEEE Transactions on Information Theory 18, 14 (1972)

1972
[38]

Chechik, A

G. Chechik, A. Globerson, N. Tishby, and Y. Weiss, Jour- nal of machine learning research 6, 165 (2005)

2005
[39]

D. J. Rezende and F. Viola, arXiv preprint arXiv:1810.00597 (2018)

2018 arXiv
[40]

Achille and S

A. Achille and S. Soatto, The Journal of Machine Learn- ing Research 19, 1947 (2018)

2018
[41]

Still, arXiv preprint arXiv:1705.00612 (2017)

S. Still, arXiv preprint arXiv:1705.00612 (2017)

2017 arXiv

Pith tools

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

[1] [1]

Uniformization of W For convenience and without loss of generality, we will henceforth assume that f(w) = 1, i.e., that W has a uniform distribution on the unit interval [0 , 1]. We can do this because if W were not uniformly distributed, we could make it so by using the standard statistical tech- nique of applying its cumulative probability distribution ...

work page

[2] [2]

Pareto-optimal

Binning W Given a set of bin boundaries b1 < b2 < ... < bn−1 grouped into a vector b, we deﬁne the integer-value con- 6 Throughout this paper, we will use the term “Pareto-optimal” or “optimal” in this sense, i.e., maximizing I(X, Y ) for a ﬁxed H(Z). 5 FIG. 2: Sample data from Section III. Images from MMNIST (top), Fashion-MNIST (middle) and CIFAR-10 are...

work page

[3] [3]

Making the conditional probability monotonic For convenience and without loss of generality, we can assume that the conditional probability distribution ¯p1(w) is a monotonically increasing function. We can do this because if this were not the case, we could make it so by sorting the bins by increasing conditional probabil- ity, as illustrated in Figure 3...

work page

[4] [4]

While ﬁne-grained binning has no eﬀect on the entropy H(Y ) and negligible eﬀect on I(W,Y ), it dramatically reduces the entropy of our data

Proof that Pareto frontier is spanned by contiguous binnings We are now ﬁnally ready to tackle the core goal of this paper: mapping the Pareto frontier ( H∗,I∗) of opti- mal data compression X↦→ Z that reﬂects the tradeoﬀ between H(Z) and I(Z,Y ). While ﬁne-grained binning has no eﬀect on the entropy H(Y ) and negligible eﬀect on I(W,Y ), it dramatically ...

work page

[5] [5]

Only Pkj and Plj change,

work page

[6] [6]

both marginal distributions remain the same,

work page

[7] [7]

horizontal

the new conditional probabilities p′ k andp′ l are fur- ther apart. Figure 4 shows how this can be accomplished for non- contiguous binning: let k be a bin with non-contiguous support set µk (bin 2 in the illustrated example), let l be a bin whose support µl (bin 4 in the example) contains a positive measure subset µmid l ⊂ µl within two parts µleft k and...

work page

[8] [8]

For practical exam- ples where this is not the case, we can instead train a neural network to implement a function ˆw(X) that ap- proximatesP (Y =1|X)

Approximating w(X) For our toy example, we knew the conditional proba- bility distribution P (Y|X) and could therefore compute W = w(X) = P (Y =1|X) exactly. For practical exam- ples where this is not the case, we can instead train a neural network to implement a function ˆw(X) that ap- proximatesP (Y =1|X). For our toy example, we train a fully connected...

work page