nucleation

LIT-1309: A Theory of Usable Information Under Computational Constraints

1 min read

Properties5
StatusActive — read 2026-10-21 (NOTE-1048) in full, from arXiv:2002.10689v1, the ICLR 2020 camera-ready; worth reading as the usable-information literature the record lacked: it defines predictive V-information, the information a predictor restricted to a family V can extract, shows that computation can create it (so the data-processing inequality fails for it), and bounds its estimation error by the Rademacher complexity of V (THEORY-846, THEORY-840). Read it knowing that the failure of the data-processing inequality is shown by informal examples (decryption, feature learning), not by a theorem, that V-information is not bounded by Shannon information unless V's input-free predictions include the true marginal (the record's counterexample, THEORY-846), that Proposition 1.2's "mean absolute deviation" is the deviation about the geometric median, and that the experiments are small.
Version2
Tagsinformation-theory, learning-theory, anthology-candidate
Cited as “paper” byNOTE-1048 — Xu, Zhao, Song, Stewart and Ermon — A theory of usable information under computational constraints
Cited as “source” byTHEORY-840 — When every log-likelihood a predictive family V can assign lies in [−B, B], the V-information estimated from N samples is within 4R_N(G_V) + 2B√(2 log(1/δ)/N) of the true V-information with probability at least 1 − 2δ, with R_N(G_V) the Rademacher complexity of the family's log-likelihoods; so usable information relative to a family of small complexity can be estimated in high dimension, and what is estimated is that family's information, not Shannon's, THEORY-846 — Information usable by a predictor restricted to a family V can be created by computing on the data, so the data-processing inequality fails for V-information: with Z the exclusive-or of two fair independent bits, linear and one-coordinate families extract nothing about Z from the pair and all of it from their exclusive-or; V-information computed from any function of the source is bounded by the source's Shannon information when the family's input-free predictions can match the marginal of the target, and can exceed it otherwise

Graph View

Xu, Y., Zhao, S., Song, J., Stewart, R. & Ermon, S. (2020). A Theory of Usable Information Under Computational Constraints. International Conference on Learning Representations (ICLR 2020). arXiv:2002.10689 (25 February 2020).

Read 2026-10-21 in full, in NOTE-1048. The summary was checked against the reading.

Why this is here

The owner asked for it in the exchange of 2026-10-20/21: “get started reading the proposed works. also this one: https://arxiv.org/abs/2002.10689”. It is the usable-information literature that CLAIM-199 says the record does not hold (“the literature on usable information is not held here”), and TERM-064 repeats the gap. Its V-information is CLAIM-199’s “best risk over the rules in a class the receiver can apply” under log loss, with the risk turned into an information. It bears on CLAIM-225, CLAIM-081 and CLAIM-270, on QUESTION-110 and QUESTION-111, and on CLAIM-304’s computational case.

Backlinks