The Limits of Post-Selection Generalization
The work investigates algorithms that guarantee post hoc generalization—where a small sample accurately reflects a larger population's statistics—and finds significant limitations. It establishes tight lower bounds on the error for adaptively chosen statistical queries and proves that this property is not preserved when combining (composing) multiple such algorithms.