The Limits of Post-Selection Generalization

Abstract

While statistics and machine learning offer numerous methods for ensuring generalization, these methods often fail in the presence of adaptivity---the common practice in which the choice of analysis depends on previous interactions with the same dataset. A recent line of work has introduced powerful, general purpose algorithms that ensure post hoc generalization (also called robust or post-selection generalization), which says that, given the output of the algorithm, it is hard to find any statistic for which the data differs significantly from the population it came from. In this work we show several limitations on the power of algorithms satisfying post hoc generalization. First, we show a tight lower bound on the error of any algorithm that satisfies post hoc generalization and answers adaptively chosen statistical queries, showing a strong barrier to progress in post selection data analysis. Second, we show that post hoc generalization is not closed under composition, despite many examples of such algorithms exhibiting strong composition properties.

References in corpus (7)

• Optimal Inference After Model Selection
• Why Adaptively Collected Data Have Negative Bias and How to Correct for It
• Bayesian Adaptive Data Analysis Guarantees from Subgaussianity
• A Minimax Theory for Adaptive Data Analysis
• Challenges in Bayesian Adaptive Data Analysis
• Generalization for Adaptively-chosen Estimators via Stable Median
• Tight Lower Bounds for Differentially Private Selection

Cited by in corpus (4)

• Towards Formalizing the GDPR's Notion of Singling Out
• Separating Adaptive Streaming from Oblivious Streaming
• Natural Analysts in Adaptive Data Analysis
• Generalization in the Face of Adaptivity: A Bayesian Perspective