PaperlayerView exact revision on arXiv

Source-linked AI summary

Formal Limitations on the Measurement of Mutual Information

David McAllester, Karl Stratos

arXiv:1811.04251v4cs.ITcs.LGstat.ML

TL;DR

Finite-sample mutual-information estimation is difficult, especially when methods rely on distribution-free lower bounds. The paper proves universal O(ln N) limits for such high-confidence bounds, explains the failure through rare unseen events, and identifies an error in a prior MINE theorem.

  • Problem

    Finite-data mutual-information estimation is notoriously difficult, motivating variational methods that maximize parameterized lower bounds as approximations.

  • Method

    The paper proves statistical limitations for distribution-free lower bounds by analyzing KL divergence, entropy, and mutual information, including the Donsker–Varadhan construction.

  • Results

    O(ln N) is the maximum scale of any distribution-free high-confidence mutual-information lower bound estimated from N samples.

  • Takeaways & Limitations

    Meaningful high-confidence lower-bound guarantees are infeasible when the underlying mutual information is large, such as hundreds of bits.

  • Takeaways & Limitations

    The impossibility result depends on distribution-free guarantees; distribution-specific lower bounds under additional assumptions may avoid the same limitation.

Abstract

from arXiv · show

Measuring mutual information from finite data is difficult. Recent work has considered variational methods maximizing a lower bound. In this paper, we prove that serious statistical limitations are inherent to any method of measuring mutual information. More specifically, we show that any distribution-free high-confidence lower bound on mutual information estimated from N samples cannot be larger than O(ln N ).

1 INTRODUCTION

Measuring mutual information from finite data is difficult, motivating variational lower-bound methods. The paper proves that distribution-free high-confidence lower bounds are fundamentally limited to O(ln N) with N samples.

  • 1 INTRODUCTION: Mutual information supports classical and neural unsupervised representation-learning methods.Examples include Brown clustering, INFOMAX, information bottleneck, MINE, CPC, and related neural approaches.
  • 1 INTRODUCTION: Finite-data estimation is notoriously difficult, motivating methods that maximize parameterized lower bounds as approximations to mutual information.MINE and CPC exemplify this variational measurement strategy.
  • 1 INTRODUCTION: O(ln N) is the largest possible scale for any distribution-free high-confidence mutual-information lower bound estimated from N samples.Here, N denotes the number of samples.
  • 1 INTRODUCTION: Large mutual information, such as hundreds of bits, therefore cannot receive a meaningful high-confidence lower-bound guarantee under this setting.The limitation concerns distribution-free guarantees rather than every possible practical estimator.
  • 1 INTRODUCTION: The result is universal to estimators, correcting and generalizing prior estimator-specific analyses while requiring no small-support or minimax assumptions.The paper also reports that it contradicts a polynomial sample-complexity theorem in prior MINE work because of an error in that proof.
  • 1 INTRODUCTION: The paper proposes a difference-of-entropies estimator using cross-entropy upper bounds, which has no formal upper- or lower-bound guarantee.The authors report theoretical and empirical evidence that it can estimate large mutual information from feasible samples.

2 ISSUES WITH THE DONSKER-VARADHAN LOWER BOUND

The Donsker–Varadhan lower bound estimates KL divergence from sample averages involving exponentials, but rare events can remain unseen and invalidate high-confidence guarantees. The paper uses this mechanism to explain estimator failure and identifies an error in a prior MINE convergence claim.

  • 2 ISSUES WITH THE DONSKER-VARADHAN LOWER BOUND: The Donsker–Varadhan bound expresses KL divergence through an expected function value and the logarithm of an exponential expectation.The bound applies to distributions with finite KL divergence and bounded functions.
  • 2 ISSUES WITH THE DONSKER-VARADHAN LOWER BOUND: Sampling estimates the bound using samples from pX and qX, but high-confidence validity requires accounting for unseen outlier events.The empirical estimate can be analyzed under a best-case value of Fmax.
  • 2 ISSUES WITH THE DONSKER-VARADHAN LOWER BOUND: Rare events can dominate the exponential expectation while never appearing in samples from qX.This expectation has the same form as a moment-generating function used in large-deviation analysis.
  • 2.1 Statistical Limitations on Measuring the DV Bound: At least 1/4 is the probability that a property occurring with probability at most 1/N remains unseen in N samples.The probability follows from (1 − 1/N)^N ≥ 1/4 for N ≥ 2.
  • 2.2 Discussion of MINE: MINE applies the DV bound by parameterizing f with a neural network and optimizing an empirical estimate using samples from pXY and pX × pY.The prior work claimed high-confidence accurate measurement with polynomial sample complexity under mild assumptions.
  • 2.2 Discussion of MINE: The paper finds that MINE’s theorem is incorrect because Hoeffding’s inequality was applied to an exponential quantity rather than a bounded-range variable.The resulting bound has exponential dependence on the variable M.

3 STATISTICAL LIMITATIONS ON MEASURING LOWER BOUNDS ON KL DIVERGENCE

The section proves universal statistical limits on distribution-free, high-confidence lower bounds for KL divergence, even when the reference distribution is fully known. An adversarial construction makes such bounds no larger than logarithmic in the sample size and directly limits mutual-information measurement in a sampling-constrained setting.

  • Motivation: The analysis of the Donsker–Varadhan bound is specific to that estimator, motivating a more general impossibility result.The paper notes that alternative lower bounds might avoid this estimator-specific limitation, but Theorem 3.1 addresses all distribution-free lower bounds.
  • Theorem 3.1: Even with complete knowledge of pX, any distribution-free high-confidence lower bound on DKL(pX||qX) estimated from samples of qX is statistically limited.The theorem considers the challenging setting where probabilities under pX are computable but only qX can be sampled.
  • Proof strategy: The proof constructs an adversarial distribution ˜qX with small KL divergence that is difficult to distinguish from qX using N samples.The mixture gives each sample a 1/N chance of coming from pX; when all mixture coins are zero, the observed samples have the same distribution as under qX.
  • Scope and implications: Distribution-free guarantees are the key restriction: without strong assumptions such as small support, a large KL lower bound cannot be guaranteed.The paper contrasts its universal result with distribution-specific bounds that may avoid the same limitation.
  • Implications for mutual information: Because mutual information is a special case of KL divergence, the result limits guarantees above ln N when only pX and pY samples are available.This direct implication concerns the setting where pXY is known but marginals cannot be computed directly.

4 STATISTICAL LIMITATIONS ON MEASURING LOWER BOUNDS ON ENTROPY

The section extends the impossibility argument from KL divergence to entropy lower bounds using sample types and an adversarial low-entropy distribution. It then transfers the logarithmic limitation to mutual information, including continuous variables through discrete binnings.

  • Reduction to entropy: Mutual information equals H(X; pX) − H(X|Y; pXY), so a lower bound on mutual information implies a lower bound on entropy.For discrete variables, entropy is nonnegative, supporting the reduction from mutual-information lower bounds to entropy lower bounds.
  • Entropy limitation: Any distribution-free high-confidence lower bound on entropy requires a sample size exponential in the size of the bound.This establishes the core statistical barrier underlying the entropy theorem.
  • Continuous variables: For continuous variables, mutual information is the supremum over discrete binnings, so the discrete O(ln N) limitation applies as well.The paper therefore assumes the discrete case without loss of generality for this section.
  • Sample types: The type T(S) records how many sample elements occur each number of times and retains the information used to estimate item probabilities and entropy.The paper studies entropy lower bounds computed from this compressed sample representation.
  • Theorem 4.1: For N ≥50 and k ≥2, every distribution-free high-confidence entropy lower bound obeys the theorem’s stated upper bound with probability at least 1 −δ −1.01/k.The theorem applies to any distribution pX and bounds B computed from the type T(S).
  • Proof strategy: The proof truncates a large-support distribution into an adversarial ˜pX with support size 2kN^2, giving H(X; ˜pX) ≤ ln 2kN^2.A birthday-paradox argument controls the event that rare elements repeat, making the adversarial and original sample types difficult to distinguish.
  • Implications for mutual information: The entropy result yields Theorem 1.1 because a mutual-information lower bound implies an entropy lower bound.The construction relies on the lower bound being distribution-free, which permits applying the premise to the adversarial distribution.

5 TOWARD ACCURATE MEASUREMENT OF MUTUAL INFORMATION

The paper proposes estimating mutual information as a difference of entropies using cross-entropy upper bounds, without formal mutual-information bounds. Experiments show this approach can estimate large and small mutual information more accurately than lower-bound estimators.

  • 5.1 Mutual Information as a Difference of Entropies: The difference-of-entropies estimator expresses mutual information using cross-entropy estimates of marginal and conditional entropies.Cross-entropy upper-bounds each entropy, but their difference has neither an upper- nor lower-bound guarantee.
  • 5.1 Mutual Information as a Difference of Entropies: Cross-entropy estimates are sample means of bounded log-loss variables, enabling confidence guarantees even when the true cross-entropy is large.The analysis assumes −ln qX(x) is bounded by Fmax and applies standard concentration bounds.
  • 5.2.1 Synthetic Experiments: In synthetic correlated-Gaussian experiments, DoE is the most accurate estimator for both I(X, Y) > ln N and I(X, Y) ≤ ln N.Both correctly specified Gaussian and misspecified logistic parameterizations produce accurate estimates.
  • 5.2.1 Synthetic Experiments: DoE is the only tested estimator that accurately estimates large mutual information and can approach the truth from either above or below.DV, MINE, and NWJ can be unstable despite occasionally producing estimates larger than ln N.
  • 5.2.2 Mutual Information Between Articles and Translations: Using related articles and translation pairs, DoE estimates over 120 bits and 54 bits of mutual information, respectively, while shuffled pairs yield values near zero.The experiments use language and translation models to estimate the entropy terms.

6 RELATED WORK

Related work studies mutual-information and entropy estimation through nearest neighbors, small-support assumptions, variational bounds, and representation-learning objectives. The paper distinguishes its universal statistical limitation from results tied to particular estimators or restricted distributions.

  • Nearest-Neighbor Estimation: Nearest-neighbor mutual-information estimators can suffer exponential sample complexity, motivating refined methods and broader statistical analysis.The paper contrasts these estimator-specific results with its own general limitations.
  • Small-Support Assumptions: Small-support entropy estimators achieve efficient rates when support is smaller than the sample size, a regime that excludes distributions over all possible images or articles.In that regime, entropy cannot exceed the log of the number of samples.
  • Variational Bounds: MINE and CPC maximize variational lower bounds whose measurable values are statistically constrained; CPC’s bound cannot exceed ln k with k negative samples.Poole et al. analyze bias–variance tradeoffs for variational mutual-information bounds.
  • Representation Learning: Brown clustering, information bottleneck, and related representation-learning methods optimize lower bounds implied by the data processing inequality.The paper states that measuring these lower bounds is subject to the same limitations.

7 CONCLUSIONS

The paper concludes that finite-data measurement of lower bounds on information-theoretic quantities has fundamental statistical limitations. It presents difference-of-entropies estimation as more statistically justified for large mutual information, while lacking formal mutual-information bounds.

  • 7 CONCLUSIONS: The paper identifies serious statistical limitations in measuring lower bounds on KL divergence, entropy, and mutual information from finite data.These limitations affect objectives used in unsupervised representation pretraining.
  • 7 CONCLUSIONS: Difference-of-entropies estimation with cross-entropy loss is presented as more statistically justified than maximizing a lower bound on mutual information.The conclusion frames this as a theoretical argument rather than a formal guarantee for the resulting mutual-information difference.
  • 7 CONCLUSIONS: Cross-entropy upper bounds on entropy provide neither an upper nor a lower bound on mutual information because mutual information is a difference of entropies.This limits the formal guarantees available from the proposed estimator.

A PROOF OF THEOREM 2.1

This proof section develops a variational characterization of KL divergence and imposes a bounded range on the optimizing function. These steps support the paper’s statistical analysis of lower bounds.

  • For any distribution rX, the construction yields a valid distribution over X that can be inserted into the lower bound.
  • Taking the supremum over f in the variational expression recovers the KL divergence between pX and qX.An optimal f is characterized explicitly in the proof.
  • Because the variational objective is invariant to translating f, the proof assumes without loss of generality that f lies in [0, Fmax].This bounded-range assumption enables subsequent statistical control.

B MUTUAL INFORMATION AS THE SUPREMUM OVER BINNINGS

The paper expresses continuous mutual information as the supremum of mutual information over discrete binnings, first establishing this for one-dimensional variables with Riemann-integrable densities.

  • Continuous mutual information is expressed as the supremum of mutual information between discrete binnings of the two continuous variables.
  • The one-dimensional proof partitions each real line into half-open intervals C_i,ϵ = [iϵ, (i + 1)ϵ).
  • The binned variables I_ϵ and J_ϵ record the interval indices containing X and Y, respectively.
  • The argument applies immediately to higher dimensions when mutual information can be expressed as a Riemann integral.

C PAC-BAYESIAN BOUNDS

This section introduces PAC-Bayesian bounds for bounded losses and notes their finite-sample behavior, parameter tuning, and alternative distance-traveled formulation.

  • The L2 PAC-Bayesian bound applies to any parameterized model class and bounded loss, simultaneously for all parameter vectors θ with high probability.
  • Setting λ = 5 yields a specific form of the PAC-Bayesian bound.
  • The bound is linear in 1/N, but a residual gap remains when λ is fixed at 5 as N approaches infinity.
  • The regularization coefficient depends on Fmax, N, and the basin parameter σ, while λ can be tuned using holdout data.
  • The bound can alternatively use distance traveled in parameter space from an initial random parameter setting θ0.

D EXPERIMENT DETAILS

The experiments use article and English-German translation pairs with LSTM encoder-decoder models, estimating mutual information from the difference between language-model and translation-model sequence cross-entropies.

  • Data: Article pairs come from Who-Did-What, using temporally related newswire articles selected through information-retrieval candidates.
  • Data: Translation pairs are English-German sentence pairs extracted from IWSLT 2014.
  • Model: The model is an LSTM encoder-decoder whose decoder also serves as a language model, with shared input and output word embeddings.
  • Training: The model uses 900-dimensional input and hidden states, dropout rate 0.65, SGD, batch size 10, and 40 training epochs.
  • Estimation: Mutual information is estimated as the difference in sequence cross-entropy between the language and translation models.
  • Results: 120.34 bits are obtained for article pairs, while translation pairs yield 54.72 bits.
Loading 1811.04251v4…