nucleation

LIT-356: How much does your data exploration overfit? Controlling bias via information usage

1 min read

Properties5
StatusActive — read in full 2026-09-29 (NOTE-308); Worth reading as the origin of the mutual-information bias and generalisation bound that LIT-347 (Xu & Raginsky) extends, and as the first place its adaptive-composition chain rule and its per-query "information budget" with Gaussian noise (½·log(1+SNR) per query) appear. Read it knowing that it is stated for a finite set of m candidate statistics, and that "the bound is tight" is shown only for Gaussian argmax and threshold selections, as squared-error (not bias) bounds except in the exponential case.
Version2
Tagslearning-theory, information-theory, probabilistic-modeling, anthology-candidate
Cited as “paper” byNOTE-308 — How much does your data exploration overfit? Controlling bias via information usage
Cited as “source” byTHEORY-028 — The expected bias of any data-dependent choice, and the expected generalisation error of any learning algorithm, is at most √(2σ²·I) for σ-subgaussian losses, where I is the information the output carries about the data

Graph View

Russo & Zou (2015), IEEE Transactions on Information Theory 66(1):302–323, January 2020 (Crossref-verified). An earlier version, “Controlling Bias in Adaptive Data Analysis Using Information Theory”, appeared at AISTATS 2016 (PMLR 51; the proceedings version was not read) and is arXiv v1 (16 Nov 2015). — arXiv:1511.05219

Standing in the record

Filed on 2026-09-29 as a supplemental reading. The close readings of the owner’s prior-art novelty map’s references found the map’s citation for this point wrong, or its source unreachable, and this work is the candidate replacement. published: is the first appearance (ADR-002).

It was filed Deferred, unread. NOTE-308 is the close reading of 2026-09-29, and it placed the work: Active — Worth reading as the origin of the mutual-information bias and generalisation bound that LIT-347 (Xu & Raginsky) extends, and as the first place its adaptive-composition chain rule and its per-query “information budget” with Gaussian noise (½·log(1+SNR) per query) appear. Read it knowing that it is stated for a finite set of m candidate statistics, and that “the bound is tight” is shown only for Gaussian argmax and threshold selections, as squared-error (not bias) bounds except in the exponential case.

Backlinks