Algorithmic Stability for Adaptive Data Analysis
Raef Bassily University of California San Diego, Center for Information Theory and Applications and Department of Computer Science and Engineering. Part of this work was done while the author was at Pennsylvania State University, supported by NSF award CDI-0941553. Kobbi Nissim Ben-Gurion University of the Negev, Department of Computer Science and Center for Research on Computation and Society (CRCS), Harvard University. Supported by a grant from the Sloan Foundation, a Simons Investigator grant to Salil Vadhan, and NSF grant CNS-1237235. Adam Smith Pennsylvania State University, Department of Computer Science and Engineering. Supported by NSF award IIS-1447700, a Google Faculty Award and a Sloan Foundation research award. Thomas Steinke Harvard University, John A. Paulson School of Engineering and Applied Sciences. Supported by NSF grants CCF-1116616, CCF-1420938, and CNS-1237235. Uri Stemmer Ben-Gurion University of the Negev, Depaprtment of Computer Science. Supported by the Ministry of Science and Technology, Israel. Jonathan Ullman Northeastern University, College of Computer and Information Science. Part of this work was done while the author was at Columbia University, supported by a Junior Fellowship from the Simons Society of Fellows.
Abstract
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 the formal study of this problem, and gave the first upper and lower bounds on the achievable generalization error for adaptive data analysis.
中文速览
真实数据分析中，研究者往往根据已有结果决定下一步要问什么问题，这种"自适应"分析方式会导致统计结论失效、出现大量虚假发现（false discovery），但现有统计理论大多只保证非自适应场景下的有效性。本文在Dwork等人的工作基础上，通过将差分隐私（differential privacy）重新理解为一种算法稳定性（algorithmic stability），证明了一个更优、更简洁的"迁移定理"：只要回答查询的机制足够稳定，其在样本上的答案就能可靠地推广到真实分布，而所需样本量仅为$n \gtrsim \sqrt{k}/\alpha^2$（$k$为查询次数，$\alpha$为精度），比此前最优结果在精度依赖上达到了最优。此外，论文还首次将上述保证推广到低敏感度查询（low-sensitivity queries）和优化查询（optimization queries）等更广泛的查询类别，为机器学习中的风险最小化等核心任务提供了理论依据。这一结果直接回应了科学界反复出现的数据重复使用导致结论不可靠的问题，为自适应数据分析的合法性提供了严格的数学基础。
原文 arXiv:1511.02513;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1511.02513v1