Formal Limitations on the Measurement of Mutual Information
By David A. McAllester, Karl Stratos. 2018
337 citations recorded by the source corpus.
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 ).
Subfields: Artificial Intelligence, Computational Theory and Mathematics, Statistics and Probability, Information Theory
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Sergey Levine
- Yoshua Bengio
- Mohit Bansal
- Ruslan Salakhutdinov
- Jianfeng Gao
- Quoc V. Le
- Percy Liang
- Pieter Abbeel
In Computational Theory and Mathematics
- Sergey Levine
- Shixiang Shane Gu
- George Tucker
- Jimmy Ba
- Timothy P. Lillicrap
- Mohammad Norouzi
- Stefano Ermon
- Ofir Nachum
In Statistics and Probability
- Arash Vahdat
- Stefano Ermon
- Ben Poole
- Shixiang Shane Gu
- Danijar Hafner
- Sherjil Ozair
- Aäron van den Oord
- Timothy P. Lillicrap
In Information Theory
- Stefano Ermon
- Jiaming Song
- Alexander A. Alemi
- William Buchwalter
- Tiago Pimentel
- Benjamin Bloem-Reddy
- Michael Tschannen
- Philip Bachman
Citations in the corpus
- Learning Representations by Maximizing Mutual Information Across Views (2019, methodology): “While the mutual information bounds in [Vondrick et al., 2018, Eslami et al., 2018] rely on explicit density estimation, our method uses the contrastive bound from CPC [van den Oord et al., 2018], which has been further analyzed by McAllester and Stratos [2018], and Poole et al. [2019].”
- Contrastive Multiview Coding (2019, neutral): “Finally, we note that recent work [37] shows that the bound in Eq.”
- On Mutual Information Maximization for Representation Learning (2019, methodology): “Given the fundamental limitations of MI estimation (McAllester and Statos, 2018), recent work has focused on deriving lower bounds on MI (Barber and Agakov, 2003; Belghazi et al., 2018; Poole et al., 2019).”
- What makes for good views for contrastive learning (2020, background): “Furthermore, theoretical and experimental work has highlighted that estimating mutual information in high dimensions is challenging and empirical work has shown that the InfoNCE and other bounds used in practice can be quite loose [43, 55, 51].”
- On Variational Bounds of Mutual Information (2019, background): “Future work should identify whether such estimators are impossible (McAllester & Stratos, 2018), or whether certain distributional assumptions or neural network inductive biases can be leveraged to build tractable estimators.”
- Dream to Control: Learning Behaviors by Latent Imagination (2019, background): “While avoiding pixel prediction, the amount of information this bound can extract efficiently is limited (McAllester and Statos, 2018).”
- A Divergence Minimization Perspective on Imitation Learning Methods (2019, background): “Sample-Based KL Estimates Recent investigations have demonstrated that sample-based estimates of lower bounds of KL divergence may significantly under-estimate the KL divergence [41].”
- Learning Robust Representations via Multi-View Information Bottleneck (2020, background): “Since accurate estimation of mutual information is extremely expensive (McAllester & Stratos, 2018), we focus on relatively small experiments that aim to uncover the difference be-tween popular approaches for representation learning.”
- Multi-label Contrastive Predictive Coding (2020, background): “Variational mutual information estimators Estimating mutual information from samples is challenging [36, 54].”
- Shape or Texture: Understanding Discriminative Features in CNNs (2021, background): “Besides statistical limitations on the ability to accurately estimate mutual information (McAllester & Stratos, 2020), even estimates which give neither upper nor lower bounds or those which give loose bounds are still useful in practice.”
- A Bayesian Framework for Information-Theoretic Probing (2021, methodology): “(5)Cross mutual information (XMI) has been used in several previous work such as (Pimentel et al., 2019, 2020b; Bugliarello et al., 2020; McAllester and Stratos, 2020; Torroba Hennigen et al., 2020; Fernandes et al., 2021; O’Connor and Andreas, 2021).”
- Disentangling Label Distribution for Long-tailed Visual Recognition (2020, methodology): “However, [54, 12, 41] have pointed out the instability of directly using the DV representation.”
- Simpler, Faster, Stronger: Breaking The log-K Curse On Contrastive Learners With FlatNCE (2021, background): “However, this conjecture is mostly based on experimental observations rather than formal variance analyses [33], and the comparison is not technically fair since the less biased estimators use far less samples [13, 34, 3].”
- Data-Efficient Mutual Information Neural Estimator (2019, methodology): “MI estimation can also be achieved by estimating individual entropy terms involved through kernel density estimation [2] or cross-entropy [31].”
- Wasserstein Dependency Measure for Representation Learning (2019, background): “However, as shown by McAllester and Statos [35], lower bounds to the mutual information are only tight for sample size exponential in the mutual information.”
- Contrastive Learning for Weakly Supervised Phrase Grounding (2020, background): “An overview of such estimators is discussed in [31,40] while the statistical limitations are reviewed in [26,34].”
- Understanding the Limitations of Variational Mutual Information Estimators (2019, background): “However, estimating mutual information from samples is challenging (McAllester & Statos, 2018) and traditional parametric and non-parametric approaches (Nemenman et al., 2004; Gao et al., 2015; 2017) struggle to scale up to modern machine learning problems, such as estimating the MI between images…”