The Logarithmic Sample Complexity Wall of Mutual Information

30 concepts22 papers1 proposal

In modern machine learning, Mutual Information (MI) serves as a critical metric for quantifying how much one variable tells us about another. It is the engine behind self-supervised representation learning, where models like Contrastive Predictive Coding (CPC) attempt to maximize the information shared between different views of the same data. However, researchers have uncovered a fundamental mathematical barrier: it is nearly impossible to accurately estimate high values of mutual information without an astronomical number of samples.

The Logarithmic Ceiling

The core of the problem lies in a "sample complexity wall." As McAllester and Stratos formally proved, any distribution-free lower bound on mutual information derived from $N$ samples cannot exceed $O(\ln N)$.

To understand the intuition, imagine trying to prove that two variables are perfectly correlated. If you only have 100 samples, the most information you can statistically "prove" exists between them is roughly $\ln(100) \approx 4.6$ bits. Even if the true relationship contains 1,000 bits of information, a standard estimator will plateau at that logarithmic ceiling. This limitation means that to reliably detect high-information dependencies, the required sample size must grow exponentially with the amount of information being measured.

Why Contrastive Learning Hits the Wall

This theoretical limit has immediate consequences for contrastive representation learning. Popular objectives like InfoNCE rely on comparing a "positive" sample against a batch of "negative" samples. Poole et al. and Song and Ermon demonstrated that these estimators are mathematically capped by the logarithm of the batch size.

When the true mutual information in high-dimensional data (like images or video) exceeds this batch-size limit, the estimator becomes severely biased. It systematically underestimates the dependency, regardless of how powerful the underlying neural network is. As Sordoni et al. noted, this forces a choice between using prohibitively large, computationally expensive batches or accepting a representation that fails to capture the full complexity of the data.

Strategies to Bypass the Limit

Researchers have proposed several architectural and mathematical workarounds to climb over or tunnel through this logarithmic wall:

  • Decomposition: Sordoni et al. introduced DEMI, which uses the chain rule to break a single high-dimensional MI estimation problem into a sum of smaller, conditional pieces. By tackling "bite-sized" chunks of information, the model can capture more total dependency without hitting the batch-size ceiling on any single component.
  • Generative Modeling: While discriminative estimators (which classify positives vs. negatives) are strictly bound by sample size, generative approaches that model density directly may offer a way out. Dahlke and Pacheco and Duong and Nguyen have explored using normalizing flows to transform complex distributions into simple Gaussians, allowing for more exact MI measurements that aren't as strictly tethered to the $O(\ln N)$ limit.
  • Gradient Estimation: Instead of trying to estimate the absolute value of MI—which is where the bias is most destructive—Wen et al. proposed directly estimating the gradients of MI. This allows for stable representation learning even when the absolute value of the information remains unknown.
  • Sampling Efficiency: To handle the need for more negative samples without blowing up memory, Shrivastava and Spring utilized Locality-Sensitive Hashing (LSH) to sample negatives from the entire dataset rather than just the current batch, effectively increasing the $N$ in the $\ln N$ bound.

Information as a Learning Constraint

Beyond estimation, this logarithmic relationship defines the fundamental limits of learning itself. Nokleby et al. linked the mutual information between training samples and model parameters to Bayes risk, suggesting that the "compression" of a posterior distribution is inherently tied to sample complexity. Similarly, Bassily et al. showed that learners constrained to use "little information" about their training sets gain stronger generalization guarantees, but at the cost of stricter data requirements.

Ultimately, the logarithmic wall suggests that while mutual information is a powerful lens for understanding machine learning, our ability to measure it is physically constrained by the scale of our observations. As Ryu et al. observed, the success of contrastive learning may not actually require precise MI estimation, but rather the ability to learn the structure of data relationships despite the biased measurements provided by finite samples.

Key Foundational Work

Information-based clustering (2005) — contributed 1 concept elements to this direction.
Rate-distortion bounds on Bayes risk in supervised learning. (2016) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_logarithmic_mutual_information_bound_f6a0d48b,
  title = {logarithmic mutual information bound},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/logarithmic-mutual-information-bound/rdr_f6a0d48b844a4453b73fc11de2c55503},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_logarithmic_mutual_information_bound_f6a0d48b_v1,
  title = {logarithmic mutual information bound},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/logarithmic-mutual-information-bound/rdr_f6a0d48b844a4453b73fc11de2c55503/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake