nucleation

LIT-1068: Outcome Indistinguishability

2 min read

Properties4
StatusActive — read in full 2026-10-15 from the arXiv preprint, arXiv:2011.13426v1 (arxiv.org/pdf/2011.13426, 61 pp.), the only arXiv version. The STOC 2021 version of record (doi:10.1145/3406325.3451064) was not read; its only open copies are submitted versions (arXiv, MIT DSpace). The recurrence algebra of Theorems 5.9–5.10 and the proof of Proposition 6.3 were checked for structure only. Worth reading as the source of outcome indistinguishability. A predictor is adequate relative to a class A of distinguishers when none can tell its sampled outcomes from Nature's. The paper sets out four levels by the distinguisher's access to the predictor (none, the sampled prediction, oracle queries, the code). It proves the lower two equivalent to multi-accuracy and multi-calibration and gives OI predictors of size O(s/ε²) whatever Nature's complexity. At the oracle level it gives conditional hardness (clique counting, or BPP ≠ PSPACE): cheap distinguishers with query access can force any OI predictor to be about as costly as Nature's own. For QUESTION-103 it supplies the formal half: distinguishing advantage is the ROC quantity, and with all subset distinguishers it becomes statistical distance. It says nothing about SDT, criteria or ideal-observer efficiency, and adds that access as well as budget sets an observer's power. For CLAIM-152 it is an instance of adequacy relative to the observer class with the target held fixed, with no uniqueness or minimality of the predictor. For QUESTION-104 it shows a restricted class accepting a coarser model (p̃ ≡ 1/2 where Nature's two halves are computationally indistinguishable), but at the oracle and code levels a bounded observer need not be satisfied by a cheap model.
Tagslearning-theory, probabilistic-modeling, anthology-candidate
Cited as “paper” byNOTE-885 — Dwork, Kim, Reingold, Rothblum & Yona — Outcome Indistinguishability
Cited as “source” byTHEORY-349 — For binary outcomes and a fixed representation of individuals, a predictor can pass every test in a bounded class without being close to nature: outcome indistinguishability to tests that see the sampled prediction is equivalent, with stated losses, to multicalibration over a closely related class of sets, a predictor meeting it exists at size polynomial in the tests' size and the tolerance whatever nature's complexity, and learning one is as hard as weak agnostic learning of the class, THEORY-354 — An observer's power to refute a predictor depends on its access to the predictor as well as on its budget: against tests that see only the sampled prediction a predictor of size O(s/ε²) always passes, but if fine-grained clique counting is hard, or BPP ≠ PSPACE, some cheap tests that may query the predictor adaptively pass only predictors about as costly as nature's own

Graph View

Dwork, C., Kim, M. P., Reingold, O., Rothblum, G. N. and Yona, G. (2021). Outcome indistinguishability. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2021). ARXIV-2011.13426

Key takeaways

Read in full (NOTE-885). A predictor p̃ is outcome indistinguishable (OI) relative to a class A of distinguishers when no A ∈ A can tell an individual with Nature’s outcome from the same individual with an outcome drawn from Ber(p̃_i). The paper sets out four levels by how much access the distinguisher has to p̃: none, the prediction on the sampled individual, oracle queries, or the code. The lower two levels are equivalent to multi-accuracy and multi-calibration over closely related classes. At those levels OI predictors exist with size O(s/ε²), whatever Nature’s complexity. At the oracle level, under fine-grained hardness of clique counting or BPP ≠ PSPACE, some efficient distinguisher classes force any OI predictor to be nearly as expensive as Nature’s own predictor. That gives a strict separation between oracle access and sample access. OI never requires p̃ ≈ p*. A predictor is good only relative to A, and with the paper’s construction a weak A gives a coarse predictor that a richer A would refute. The paper covers binary outcomes, a fixed representation of individuals and single samples (multi-sample OI is left mostly to future work).

Why this is here

The owner asked whether material downstream of computational indistinguishability, or the signal detection literature, could help with CLAIM-302 and the bounded-observer questions. Read for QUESTION-103. It makes “a model is sufficient for a bounded observer” precise, which CLAIM-152 and QUESTION-104 reach for. It is machine-learning theory and carries the anthology flag; it is filed here for that question (ADR-005, ADR-013).

The reading (NOTE-885) adds and narrows. How strong an observer is depends on its access to the predictor as well as its budget: with oracle or code access a cheap observer can force the predictor to be as complex as nature, which qualifies QUESTION-104. The paper says nothing about signal detection, and proves no minimal or unique sufficient partition.

Backlinks