Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold and Aaron Roth (2015), Science 349(6248), 636–638.
Key takeaways
From the reading, NOTE-848, of the Supplementary Material only.
- Max-information bounds overfitting (Theorem 2, proved). P[S ∈ R(φ)] ≤ 2^{I∞(S;φ)}·max P[S ∈ R(φ)]; so I∞ ≤ log₂e·τ²n gives an overfitting probability at most e^{−τ²n} (Corollary 3).
- Privacy bounds max-information (Lemma 5, proved). ε-differential privacy gives I∞ ≤ log₂e·εn, and post-processing keeps it, so the analyst may choose queries freely from private answers.
- Sharper versions (proofs in companion papers). ε ≤ τ gives P[|P[φ] − E_S[φ]| > τ] ≤ 6e^{−τ²n}; an (ε, δ) version gives failure probability β.
- Thresholdout (Theorem 11, proof elsewhere). Answer with the training estimate unless it disagrees with the holdout beyond a noisy threshold. All m answers are within τ with probability 1 − β, while fewer than B overfitting events have occurred, for n = O(ln(m/β)/τ²·min{B, √(B ln(m/β))/τ}).
- Scope. [0, 1]-valued statistical queries on a discrete universe; the simulations used a different implementation from the one analysed.
Standing in the record
Filed 2026-10-12 for QUESTION-040, the selection-bias half. Read in part on 2026-10-14 (NOTE-848): the Supplementary Material in full, the main text not reached. THEORY-318, filed from it, answers QUESTION-040 in part: a search whose access to the test data runs through a private mechanism is bounded in how far it can inflate a statistic. It does not say how far an unmediated search has inflated one, which is the form of the question’s d′ correction. It complements THEORY-028 (Russo & Zou, NOTE-308), giving the high-probability, worst-case counterpart of its expected bound. The reusable-holdout procedure as advice for tuning models belongs in the anthology, which does not hold the paper.