The Limits of Post-Selection Generalization
The Limits of Post-Selection Generalization
复制标题
DOI：
--
复制
发表时间：
2018-06
期刊：
影响因子：
--
通讯作者：
Kobbi Nissim;Adam D. Smith;T. Steinke;Uri Stemmer;Jonathan Ullman
中科院分区：
文献类型：
--
作者：
Kobbi Nissim;Adam D. Smith;T. Steinke;Uri Stemmer;Jonathan Ullman
虽然统计和机器学习提供了许多确保概括的方法，但这些方法通常在存在 *---选择分析的常见实践中取决于先前与同一数据集的相互作用的常见实践。最近的一项工作引入了功能强大的通用算法，可确保一个称为 *事后概括 *（Cummings等人，Colt'16）的属性，该算法说，当授予算法的输出时，没有人能够找到数据与人口的不同统计量。在这项工作中，我们对满足事后概括的算法的力量有一些局限性。首先，我们显示了满足事后概括并回答自适应选择的统计查询的任何算法的误差的紧密下限，显示了在选择后数据分析中进展的强烈障碍。其次，我们表明，尽管许多算法表现出强大的组成特性，但事后概括并未在组成下关闭。
While statistics and machine learning offers numerous methods for ensuring generalization, these methods often fail in the presence of *post selection*---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 a property called *post hoc generalization* (Cummings et al., COLT'16), which says that no person when given the output of the algorithm should be able 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.