CoChat
Sign Up
PreprintCited by 143Computability, Logic, AI AlgorithmsDiverse Interdisciplinary Research StudiesBayesian Modeling and Causal Inference

The DOI matches its DataCite record; 39 of the 39 references it cites were found in a registry or an index; none of the 11 sources its claims cite is checked for support yet.

A Theory of Usable Information Under Computational Constraints

Open access
Xu, Yilun, Zhao, Shengjia, Song, Jiaming, Stewart, Russell, Ermon, Stefano·2020·arXiv
DOI 10.48550/arxiv.2002.10689arXiv 2002.10689
Open this paper in CoChat — free accountOpen PDF

Abstract

We propose a new framework for reasoning about information in complex systems. Our foundation is based on a variational extension of Shannon's information theory that takes into account the modeling power and computational constraints of the observer. The resulting \emph{predictive $\mathcal{V}$-information} encompasses mutual information and other notions of informativeness such as the coefficient of determination. Unlike Shannon's mutual information and in violation of the data processing inequality, $\mathcal{V}$-information can be created through computation. This is consistent with deep neural networks extracting hierarchies of progressively more informative features in representation learning. Additionally, we show that by incorporating computational constraints, $\mathcal{V}$-information can be reliably estimated from data even in high dimensions with PAC-style guarantees. Empirically, we demonstrate predictive $\mathcal{V}$-information is more effective than mutual information for structure learning and fair representation learning.

Overview

AI snapshot

Written from the paper’s full text.

TL;DR

The paper proposes predictive V-information, a variational extension of Shannon information that incorporates the observer’s computational constraints and can be created through computation, violating the data processing inequality. It provides PAC-style estimation guarantees and shows empirical advantages over mutual information for structure learning and fair representation learning.

Key findings

  • Predictive V-information generalizes Shannon mutual information when the predictive family is unrestricted, and recovers other notions such as mean absolute deviation, trace of covariance, and the coefficient of determination \(R^2\) under specific restricted families.
  • Unlike Shannon mutual information, V-information can increase under preprocessing/computation, so the data processing inequality does not hold; this is framed as consistent with representation learning and decryption examples.
  • V-information can be estimated with PAC-style guarantees: Theorem 1 bounds estimation error by \(4R_{|D|}(G_V) + 2B\sqrt{\frac{2\log(1/\delta)}{|D|}}\), and Corollary 1.1 gives a concrete linear-Gaussian bound.
  • In experiments, V-information-based Chow-Liu tree learning recovers ground-truth trees with about 100 samples in simulation-A, outperforms CPC/NWJ/MINE alternatives across data regimes, and outperforms non-parametric Shannon estimators on DREAM5 gene regulatory network inference using 20 genes and 660 datapoints.
  • On Moving-MNIST, V-information decreases with frame distance and Algorithm 1 perfectly recovers relative frame order; on Deterministic-Moving-MNIST it recovers order when frame distances are less than 9.
  • In fairness experiments on Adult, German, and Heritage datasets, features trained to minimize V-information against one attacker family often leak to another; in one special case, a \(V_B\) attacker achieves AUC 0.857 despite \(V_A\)-information minimization.

Methods

  • The paper defines a predictive family \(V\) of computationally bounded predictive models, then defines predictive conditional V-entropy and predictive V-information as \(I_V(X \to Y)=H_V(Y|\emptyset)-H_V(Y|X)\).
  • It proves elementary properties (monotonicity, non-negativity, independence), PAC bounds for empirical V-information using Rademacher complexity, and a finite-sample guarantee for directed Chow-Liu tree structure learning solved via the Chu-Liu algorithm.
  • Experiments cover synthetic high-dimensional tree structures with 7–20 variables each 10-dimensional, DREAM5 gene regulatory network inference, Moving-MNIST and Deterministic-Moving-MNIST frame ordering, and fair representation learning on Adult, German, and Heritage datasets.

Limitations

  • The paper states in Appendix F that general V-information lacks additive algebra such as \(H(X,Y)=H(X)+H(Y|X)\), though this may hold for simple \(V\) such as polynomial-time computable functions.
  • The paper states future work is needed to better integrate V-information with representation learning, active learning, classification, and reinforcement learning.
  • Evident from the text: the synthetic experiments use V-families misspecified with respect to the true conditional distributions; PixelCNN++ tends to overfit in the deterministic Moving-MNIST case; and fair representations trained with one V-information objective do not reliably generalize to other attacker families.

Model-written summary. Check it against the paper before relying on it.

Integrity signals

Registry

DataCite · 10.48550/arxiv.2002.10689

Cites

39 of 39 references verified0 citation errors · 0 not checkable

Statistics

Nothing to recompute.

Verification

Claims the paper makes

26 No basis given · 11 Own interpretation · 10 Own result · 5 Check pending · 4 No full text of the sources · 1 Not checked yet

Verify all 5 references — free account

Show all 42 claims

  • It may state two separate claims as one. 12
  • Probably not a substantial claim. 5
  • The quote only partly states this claim. 1
15 of 15

  • The authors state this as an assumption.

    Certain functions h are one-way: there exists a polynomial algorithm to compute h(x) but no polynomial algorithm to compute h^{-1}(y).

    “modern cryptography is founded on the assumption that certain functions h : X → Y are one-way, meaning that there exists an polynomial algorithm to compute h(x) but no polynomial algorithm to compute h -1 (y).”

  • The authors state this as an assumption.

    The random variable Y ∈ R^d and the predictive family V is the Gaussian family V = {f : x → N(φ(x), Σ), x ∈ X; ∅ → N(µ, Σ) | µ ∈ R^d; Σ = 1/2 I_{d×d}; φ ∈ Φ}.

    “Assume random variable Y ∈ R d , V = {f : x → N (φ(x), Σ), x ∈ X ; ∅ → N (µ, Σ)|µ ∈ R d ; Σ = 1 2 I d×d ; φ ∈ Φ}.”

  • The authors state this as an assumption.

    For all f ∈ V, x ∈ X, y ∈ Y, log f[x](y) ∈ [-B, B].

    “Assume ∀f ∈ V, x ∈ X , y ∈ Y, log f [x](y) ∈ [-B, B].”

  • The authors state this as an assumption.

    For all f ∈ V, y ∈ Y, log f[∅](y) ∈ [-B, B].

    “Assume ∀f ∈ V, y ∈ Y, log f [∅](y) ∈ [-B, B].”

  • The authors state this as an assumption.

    X = {x ∈ R^{dx}, ||x||_2 ≤ k_x}, Y = {y ∈ R^{dy}, ||y||_2 ≤ k_y}, and V = {f : f[x] = N(Wx + b, I), f[∅] = N(c, I), W ∈ R^{dy×dx}, b, c ∈ R^{dy}, ||(W, b)||_2 ≤ 1}.

    “Assume X = {x ∈ R dx , x 2 ≤ k x } and Y = {y ∈ R dy , y 2 ≤ k y }. If V = {f : f [x] = N (W x + b, I), f [∅] = N (c, I), W ∈ R dy×dx , b, c ∈ R dy , (W, b) 2 ≤ 1}”

  • The authors state this as an assumption.

    The function f_θ achieves the optimum value for I_NWJ.

    “Assume that f θ achieves the optimum value for I NWJ .”

  • The authors state this as an assumption.

    U is discrete and V belongs to predictive family 1.

    “Assume U is discrete and V belongs to preditive family 1.”

  • The authors state this as an assumption.

    The discussion is restricted to distributions with probability density functions or probability mass functions with respect to the underlying measure, and ∅ ∈ X.

    “Regularity Conditions: To minimize technical overhead we restrict out discussion only to distributions with probability density functions (PDF) or probability mass functions (PMF) with respect to the underlying measure.Also ∅ ∈ X .”
8 of 8

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

Each contradiction between two passages listed here was confirmed by an independent check.

2 of 2

Citations

Cites

Show all 39 references

Cited by

Sorted by citations

Related

See all

Metadata

Authors
Xu, Y., Zhao, S., Song, J., Stewart, R., & Ermon, S.
Affiliations
  • Peking University (CN)
  • Stanford University (US)
ORCID
Venue
arXiv
Publisher
arXiv
Published
2020
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.2002.10689
arXiv
2002.10689
OpenAlex
W2996336810
Cited by
142
References
39
Citations by year
2026: 28 · 2025: 22 · 2024: 21 · 2023: 30 · 2022: 8 · 2021: 20 · 2020: 12
Type
posted content
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Funders
  • National Science Foundation (1651565, 1522054, 1733686)
  • Office of Naval Research
  • Air Force Office of Scientific Research (FA9550-19-1-0024)
Topics
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Computability, Logic, AI Algorithms
  • Physical Sciences › Computer Science › Artificial Intelligence › Diverse Interdisciplinary Research Studies
  • Physical Sciences › Computer Science › Artificial Intelligence › Bayesian Modeling and Causal Inference
Keywords
Shannon mutual information, computational resource constraints, data processing inequality, representation learning, feature hierarchy, structure learning, fair representation learning, high-dimensional estimation

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

A language model drew the claims from the paper on 2026-11-11, under version 3 of the claim definition (model deepseek-v4.1-flash, prompt extract-v3).

A second model labelled each claim on 2026-11-11 (model jev-1.13-20260917, definition revision gold-guideline-v0.2).

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review