Algorithmic Stability for Adaptive Data Analysis
Algorithmic Stability for Adaptive Data Analysis
复制标题
自适应数据分析的算法稳定性
DOI：
10.1137/16m1103646
复制
发表时间：
2021
影响因子：
1.6
通讯作者：
Ullman, Jonathan
中科院分区：
文献类型：
--
作者：
Bassily, Raef;Nissim, Kobbi;Smith, Adam;Steinke, Thomas;Stemmer, Uri;Ullman, Jonathan
自适应性是数据分析的一个重要特征--对数据集提出的问题的选择通常取决于以前与同一数据集的交互。然而，统计有效性通常在非自适应模型中进行研究，其中所有问题都在绘制数据集之前指定。最近Dwork et al.（STOC，2015）和Hardt and Ullman（FOCS，2014）的工作开始了对这个问题的一般形式化研究，并给出了自适应数据分析可实现的泛化误差的第一个上界和下界。我们寻求一种算法，给定x作为输入，准确地回答一系列自适应选择的关于未知distributionP的“queries”。我们必须从分布中抽取多少样本，作为查询类型、查询数量和所需准确度的函数？在这项工作中，我们对解决这个问题做出了两个新的贡献：我们给出了回答统计查询所需的样本数量的上限。该界限改进和简化了Dwork等人的工作。（STOC，2015），并已被这些作者应用于后续工作（Science，2015; NIPS，2015）。我们证明了回答更一般的查询族所需的样本数量的第一个上限。这些包括任意低敏感度查询和一类重要的优化查询（或者，风险最小化查询）。我们的算法是基于一个连接与算法的稳定性的形式差异隐私。我们扩展了他们的工作，给出了一个定量的最佳，更一般，更简单的证明他们的主要定理，保证差分隐私的稳定性概念意味着低泛化错误。我们还表明，较弱的稳定性保证，如有界KL发散和总变差距离导致相应较弱的推广保证。
Adaptivity is an important feature of data analysis - the choice of questions to ask about a dataset often depends on previous interactions with the same dataset. However, statistical validity is typically studied in a nonadaptive model, where all questions are specified before the dataset is drawn. Recent work by Dwork et al. (STOC, 2015) and Hardt and Ullman (FOCS, 2014) initiated a general formal study of this problem, and gave the first upper and lower bounds on the achievable generalization error for adaptive data analysis.Specifically, suppose there is an unknown distributionPand a set ofnindependent samplesxis drawn fromP. We seek an algorithm that, givenxas input, accurately answers a sequence of adaptively chosen ``queries'' about the unknown distributionP. How many samplesnmust we draw from the distribution, as a function of the type of queries, the number of queries, and the desired level of accuracy?In this work we make two new contributions towards resolving this question:We give upper bounds on the number of samplesnthat are needed to answerstatistical queries. The bounds improve and simplify the work of Dwork et al. (STOC, 2015), and have been applied in subsequent work by those authors (Science, 2015; NIPS, 2015).We prove the first upper bounds on the number of samples required to answer more general families of queries. These include arbitrarylow-sensitivity queriesand an important class ofoptimization queries(alternatively,risk minimization queries).As in Dwork et al., our algorithms are based on a connection withalgorithmic stabilityin the form ofdifferential privacy. We extend their work by giving a quantitatively optimal, more general, and simpler proof of their main theorem that the stability notion guaranteed by differential privacy implies low generalization error. We also show that weaker stability guarantees such as bounded KL divergence and total variation distance lead to correspondingly weaker generalization guarantees.