Source-linked AI summary
Mutual Information Constrained Chernoff Bottleneck
Dier Tang, Guangyue Han
TL;DR
Because mutual information does not directly characterize downstream testing error, the paper optimizes Chernoff information under a mutual-information rate constraint. It shows that the IB’s single-sample log-loss advantage gives way to the Chernoff bottleneck in error and equivocation as sample size grows.
Problem
Mutual information measures representation relevance but does not directly characterize downstream binary-testing error, whose exponent is determined by Chernoff information.
Source: §1 · p. 1Method
The mutual information constrained Chernoff bottleneck maximizes Chernoff information between the encoded conditional distributions subject to a rate constraint on I(U;X).
Source: §1 · p. 2Results
When the objectives disagree, the IB is best for single-sample log-loss, but the Chernoff bottleneck is overtaken by neither in error probability and equivocation as n grows.
Source: §1 · p. 3Takeaways & Limitations
An optimal encoder can use at most k + 1 outputs, where k is the number of distinct likelihood ratios.
Source: §1 · p. 2The encoder-update subproblem minimizes a concave function over a convex feasible set, so global optimality cannot be expected in general.
Source: §5.1 · p. 12
Abstract
from arXiv · showhide
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.
1 Introduction
The paper replaces the information bottleneck’s relevance objective with Chernoff information to target downstream binary-testing error under a rate constraint. It characterizes the resulting rate curve, bounds encoder size, develops an algorithm, and compares the bottleneck with the classical IB.
1 Introduction
- The classical IB measures relevance through I(U;Y), but this does not directly characterize downstream decision error; for binary testing from separately encoded samples, the error exponent is Chernoff information.The paper notes that the Chernoff objective lacks properties underpinning classical IB algorithms and cardinality arguments, so these must be studied anew.Source: §1 · pp. 1–2
- C(R) strictly increases up to H(V), then reaches the uncompressed Chernoff exponent; unlike the IB curve, it need not be concave.V merges symbols with equal likelihood ratio.Source: §1 · p. 2
- An optimal encoder exists with at most k + 1 outputs, where k is the number of distinct likelihood ratios.The bound is sharpened by reducing the problem to V.Source: §1 · p. 2
- The proposed alternating algorithm updates the encoder with a generalized Blahut–Arimoto method and updates the Chernoff parameter s by solving a nonlinear equation.Its iterates remain feasible, and Chernoff information converges monotonically.Source: §1 · p. 2
- When the objectives disagree, the IB’s single-sample log-loss advantage is overtaken by the Chernoff bottleneck in equivocation and error probability as n grows.The paper also reports that the IB need not have lower error probability even for small n.Source: §1 · pp. 2–3
- On 20 Newsgroups topic detection, compressing each word to 1 nat—17% of its entropy—retains 90% of the error exponent and nearly the uncompressed classifier’s accuracy.Synthetic-source experiments also confirm the C(R) theory and yield randomized likelihood-ratio quantizers.Source: §1 · p. 3
2 Problem Setup
The setup considers finite-alphabet observations and a binary hypothesis, with an encoder producing representations used for testing. The encoder is constrained by mutual information with the observation, and its objective reflects information lost from the testing exponent.
2 Problem Setup
- For i.i.d. observations encoded separately, the testing error exponent is the Chernoff information between the induced conditional distributions of the representation.The setup assumes distinct conditional distributions for the two hypotheses.Source: §2 · p. 3
- The encoder distortion d(K) measures how much information about inferring Y is lost during encoding.A lemma establishes that this distortion is nonnegative.Source: §2 · p. 3
- The bottleneck maximizes the encoded Chernoff information subject to I(U;X) ≤ R, with the prior affecting the rate through the marginal distribution of X.The paper calls this problem the mutual information constrained Chernoff bottleneck.Source: §2 · p. 4
- The statistic V merges observations with equal likelihood ratios, equivalently equal posteriors, and is minimal sufficient for Y; its entropy is H(V).The deterministic encoder for V outputs the merged symbol associated with each observation.Source: §2 · p. 5
3 Global Shape of the C(R) Curve
The optimal Chernoff information curve rises strictly until the entropy of the likelihood-ratio statistic V, then saturates at the uncompressed exponent. Below that threshold, optimal encoders use the full rate budget, while the curve need not be concave.
3 Global Shape of the C(R) Curve
- V preserves the uncompressed Chernoff objective at rate H(V), and any encoder using less than H(V) has a strict inequality in the stated comparison for interior s.This reduction underlies the saturation and strict-increase characterization.Source: §3 · pp. 5–6
- C(R) is strictly increasing on [0, H(V)] and equals the uncompressed Chernoff information for every R ≥ H(V).The deterministic encoder for V attains the uncompressed exponent at rate H(V).Source: §3 · pp. 5–6
- For every R ≤ H(V), each optimal encoder uses the full rate budget I(U;X) = R.This follows from strict increase of C(R) below H(V).Source: §3 · p. 6
- Unlike the IB curve, C(R) need not be concave; the paper gives a symmetric binary source with 0 < a ≤ 10^-3 for which it is not concave.The IB curve is concave by time-sharing, whereas the Chernoff curve does not inherit that guarantee.Source: §3 · p. 7
4 Cardinality Bounds and Attainability
The section establishes that the constrained optimum is attained with a finite output alphabet, sharpened to k+1 outputs by reducing X to its distinct likelihood-ratio statistic V. This reduction preserves the relevant conditional distributions and shows that C(R) depends on the source only through the joint distribution of V and Y.
4 Cardinality Bounds and Attainability
- The maximum in (18) is achievable, and |U| can be restricted to |X|+1 without loss of generality.R is non-empty and compact, and C(K) is continuous with respect to K.Source: §4 · pp. 7, 9
- Reducing X to V preserves the induced conditional distributions while not increasing mutual information in the reduction from X to V.Conversely, an encoder of V can be implemented through V=ν(X) with the same mutual information.Source: §4 · p. 9
- At most k+1 outputs suffice to attain the optimum, using an encoder of V where k is the number of distinct likelihood ratios.The optimal encoder can be implemented on X through the mapping to V.Source: §4 · pp. 9–10
- The curve C(R) depends on the source only through the joint distribution of V and Y; compressing X is never better than compressing V at any rate.V merges symbols of X that have equal likelihood ratios.Source: §4 · pp. 9–10
5 An Alternating Optimization Algorithm
The algorithm alternates between updating the encoder under a fixed Chernoff parameter and updating that parameter for a fixed encoder. Its component steps use generalized Blahut–Arimoto optimization and a nonlinear equation, with a rate bracket for the encoder update.
5 An Alternating Optimization Algorithm
- The algorithm alternates between minimizing over the encoder K at fixed s and updating s at fixed K.These are the two steps used to optimize Problem 2.Source: §5 · p. 11
5.1 Step (a): Generalized Blahut-Arimoto Algorithm
- For fixed s, the encoder update uses a linear objective obtained from a tangent plane of the concave function BM, and the resulting rate–distortion problem is solved by generalized Blahut–Arimoto.The objective is a tangent-plane upper bound that is exact at the current encoder.Source: §5.1 · pp. 12–13
5.2 Step (b): Solving a Nonlinear Equation
- For fixed K, the update selects the unique s in (0, 1) satisfying the nonlinear equation.The equation can be solved numerically, for example by bisection, Newton’s method, or Brent’s method.Source: §5.2 · p. 14
5.3 Alternating Optimization Algorithm for Problem 2
- Algorithm 2 uses a λ bracket while searching for an encoder whose mutual information meets the rate constraint.The listed steps compute the encoder’s rate and safeguard the update when it exceeds R.Source: §5.3 · p. 15
5.4 Convergence Analysis
- The convergence analysis considers encoders in the rate-feasible set and s in (0, 1).The stated conditions for the step-a bounds include these constraints.Source: §5.1 · p. 12, §5.4 · p. 15
R G(K). Let L∗
The analysis establishes convergence properties for both the Lagrangian encoder update and the alternating procedure. It also shows that the trade-off search can maintain a rate-feasible bracket and that the Chernoff information increases to a limit.
R G(K). Let L∗
- Algorithm 1 converges to a global minimizer of the Lagrangian, with a nonincreasing objective sequence.A stopping certificate is also stated for the iteration.Source: R G(K). Let L∗ · p. 16
- I(λ) is nonincreasing, and a threshold λ* separates values with rate above R from values with rate at most R.The bracket [0, Γ/R] keeps λ* within its bounds and maintains I(λbig) ≤ R.Source: R G(K). Let L∗ · pp. 16–17
- For a fixed encoder, the Chernoff parameter s* is the unique root of the stated equation and lies in (0, 1).The proof uses strict convexity and the endpoint values of ψK.Source: R G(K). Let L∗ · p. 17
- With exact s-updates, Algorithm 2 has feasible iterates and its Chernoff information is nondecreasing and convergent.The limit is bounded above by C(R), and s remains uniformly bounded away from 0 and 1.Source: R G(K). Let L∗ · pp. 17–18
6 When Does the Chernoff Bottleneck Outperform the IB?
When the IB and Chernoff objectives disagree, the IB can have lower equivocation for one sample, but the Chernoff bottleneck has lower error and equivocation for all sufficiently large sample counts. The section relates this reversal to the shared asymptotic exponent of error and equivocation.
6 When Does the Chernoff Bottleneck Outperform the IB?
- The IB's one-sample equivocation advantage does not imply a small-sample error advantage, because IB optimizes I(U;Y), not 1−Pe(1;K).The discussion notes that Chernoff bottleneck can therefore be favored even for small n in some cases.Source: §6 · pp. 19–20
- For every encoder, equivocation and Bayes error have the same asymptotic exponent.The lemma establishes this relation for n≥1.Source: §6 · p. 19
- When C(KIB) < C(R), the Chernoff encoder has lower error probability and equivocation for all sufficiently large n.This comparison concerns the encoders at rate R.Source: §6 · pp. 19–20
- If additionally I_KCB(U;Y) < I_KIB(U;Y), IB has lower equivocation at n=1, and the equivocation difference changes sign at least once.The n=1 ordering follows from H(Y|U)=H(Y)−I(U;Y).Source: §6 · p. 20
- The two objective-disagreement assumptions require R < H(V); for R ≥ H(V), the IB encoder is sufficient for Y and data processing gives the uncompressed exponent.Source: §6 · p. 20
7 Numerical Experiments
The experiments find that the rate–Chernoff curve and optimal encoders follow the predicted likelihood-ratio structure, while compressed words retain much of the error exponent on 20 Newsgroups. In the comparison with the information bottleneck, the Chernoff bottleneck needs fewer samples at smaller error levels.
7.1 The C(R) Curve
- Across the synthetic sources, C(R) rises strictly to H(V) and then equals CX; source F’s curve lies below the chord from (0, 0) to (H(V), CX).Source B is concave, while source F illustrates that C(R) need not be concave.Source: Figure 1 · p. 21, §7.1 · p. 21
7.2 Structure of the Optimal Encoder
- For source C, optimal encoders are randomized likelihood-ratio quantizers; at R≈0.61, the deterministic split {X1}, {X2 ∪ X3} coincides with the curve’s kink.Below the kink, the encoder randomizes X1’s separation; above it, it randomizes the separation of X2 and X3.Source: Figure 2 · p. 22, §7.2 · p. 22
7.3 Real Dataset Practice
- On i.i.d. test-word statistics, fitted error-decay rates are within about 10% of C(R); on document draws, error levels near 2% for both classifiers.The document-level floor reflects words following each document’s distribution rather than being i.i.d. given the topic.Source: Figure 3 · p. 23, §7.3 · p. 24
- At rate R = 1 nat per word (17% of H(X)), the encoder keeps 90% of CX; at R = 0.25 (4% of H(X)), it keeps 47%.Source: §7.3 · p. 24
- On 20 Newsgroups, each word used the same encoder with 16 outputs, and error was measured on both i.i.d. topic-word draws and draws from individual test documents.The latter is the actual task; the former approximates the model up to training–test mismatch.Source: §7.3 · pp. 22–23
7.4 Comparison with the IB
- Across rates, the Chernoff bottleneck’s exponent is 23–25% larger, while at smaller errors it needs 18–25% fewer samples than the IB.The IB has smaller equivocation and error only below the crossover sample count n_c.Source: Table 3 · p. 24, §7.4 · p. 25
8 Conclusion
The paper studies a mutual-information-constrained Chernoff bottleneck for representations used in binary testing, deriving its rate behavior and an alternating optimization algorithm. It compares this objective with the classical information bottleneck and reports synthetic and real-data results.
8 Conclusion
- C(R) increases strictly until R = H(V), reaches the uncompressed exponent there, and stays constant afterward; unlike the IB curve, it need not be concave.V merges symbols of X with equal likelihood ratio; every optimal encoder uses the full rate budget for R ≤ H(V).Source: §8 · p. 25
- An encoder with at most k + 1 outputs suffices to attain C(R), where k is the number of distinct likelihood ratios.The bound follows by reducing the input to V, which merges symbols with equal likelihood ratio.Source: §8 · p. 25
- The proposed algorithm alternates between encoder updates using a generalized Blahut–Arimoto method and a nonlinear equation for the Chernoff parameter s.Its iterates remain feasible and have nondecreasing, convergent Chernoff information, though the limit need not be globally optimal.Source: §8 · p. 26
- When the IB and Chernoff objectives disagree, the IB encoder has smaller equivocation at n = 1, but the Chernoff bottleneck has smaller error and equivocation for all large n.On one source, it needs 18–25% fewer samples once error falls below about 0.2.Source: §8 · p. 26
- At 1 nat, compressing each word to 17% of its entropy retains 90% of the error exponent and yields nearly uncompressed-classifier accuracy.On actual test documents, the errors are ordered as C(R).Source: §8 · p. 26
- The Chernoff bottleneck evaluates representations by the decay rate of downstream decision error rather than by average relevance.The authors present it as a principled criterion for compact representations for inference.Source: §8 · p. 26
A Several Facts Used in the Proof
This appendix section lists mathematical facts used in the proofs and includes proof excerpts concerning likelihood-ratio classes and equality conditions.
A Several Facts Used in the Proof
- The listed proof tools include Young’s and Hölder’s inequalities, a weighted-average inequality, Heine-Borel, joint convexity of relative entropy, and Pinsker’s inequality.The supplied statements include equality conditions for Young’s and Hölder’s inequalities.Source: A Several Facts Used in the Proof · p. 30
B.1 Proof of Lemma 3.2
- Grouping symbols of X into likelihood-ratio classes gives class probabilities related by their likelihood ratio, and the proof equates the resulting Chernoff coefficient with that for X.The passage identifies V as a deterministic function of X and considers each class X_j.Source: §B.1 · p. 30
B.2 Proof of Lemma 3.3
- The equality argument shows that equality in the coefficient bound forces U to determine V, yielding I(U;X) = H(V).The proof then uses the contrapositive to obtain its conclusion.Source: §B.2 · p. 31
B.4 Proof of Example 3.7
These proof excerpts establish a nonconcavity example, properties of the feasible encoder set, and a reduction from X to its likelihood-ratio class variable V.
B.4 Proof of Example 3.7
- C(R0) ≤ 0.2506, below the 0.276 value that concavity would require, establishing the example’s nonconcavity.The argument uses V = X for this example and compares C(R0) with a chord bound.Source: §B.4 · pp. 31–32
B.5 Proof of Lemma 4.1
- The rate-constrained encoder set is shown to be nonempty, closed, bounded, and convex.The proof uses a constant encoder for non-emptiness and continuity of mutual information for closedness.Source: §B.5 · p. 32
B.6 Proof of Lemma 4.3
- The proof constructs an encoder on V and shows that its mutual information with V equals the original encoder’s mutual information with X when U depends on X only through V.V groups symbols of X by likelihood-ratio class.Source: §B.6 · p. 33
B.8 Proof of Lemma 5.7
- The proof excerpt invokes Young’s inequality and a positive lower bound independent of the encoder.The supplied passage gives no further conclusion for this proof step.Source: §B.8 · p. 34
B.9 Proof of Theorem 5.8
The proof excerpt establishes monotone descent and convergence properties for the generalized Blahut–Arimoto updates used in the algorithm.
B.9 Proof of Theorem 5.8
- The updates maintain positive output probabilities and encoder entries, so the relative entropies used in the proof remain finite.Positivity follows by induction from the full-support initialization.Source: §B.9 · p. 34
- Each update does not increase the Lagrangian, and summing the inequality over iterations yields a rate bound.The excerpt applies the inequality first to the current iterate and then to a minimizer.Source: §B.9 · p. 34
- Compactness gives a convergent subsequence whose limit is a global minimizer; the divergence to that limit tends to zero, yielding convergence of the iterates.The proof also shows the output distributions converge to the limit distribution.Source: §B.9 · p. 34
B.10 Proof of Lemma 5.10
The proof shows that the rate I(λ) is nonincreasing in λ, then uses a threshold λ* to certify feasibility and bracket it by bisection. It also establishes bounds on G(K(λ)) for feasible choices, with equality when I(λ) = R or λ = 0.
B.10 Proof of Lemma 5.10
- Increasing λ cannot increase I(λ), because optimality at two λ values yields (λ2 − λ1)(I1 − I2) ≥ 0.The proof compares encoders minimizing Lλ1 and Lλ2.Source: §B.10 · p. 35
- For feasible K(λ), G(K(λ)) is bounded relative to G*, with equality when I(λ) = R or λ = 0.Compactness of the feasible encoder set and continuity of G ensure G* is attained.Source: §B.10 · p. 35
- For λ > λ*, every choice of K(λ) satisfies I(λ) ≤ R, whereas for λ < λ*, every choice satisfies I(λ) > R.The threshold obeys λ* ≤ (Γ − β)/R < Γ/R.Source: §B.10 · p. 35
- Bisection preserves λ* in its bracket and keeps I(λbig) ≤ R; after n steps, the bracket width is Γ/(R 2^n).The update assigns the lower endpoint only when I(λ) > R and the upper endpoint only when I(λ) ≤ R.Source: §B.10 · p. 35