Algorithmic Stability for Adaptive Data AnalysisThanks: This work unifies and subsumes the two arXiv manuscripts [BSSU15, NS15].
Raef Bassily Thanks: 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 Thanks: 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 Thanks: 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 Thanks: Harvard University, John A. Paulson School of Engineering and Applied Sciences. Supported by NSF grants CCF-1116616, CCF-1420938, and CNS-1237235. Uri Stemmer Thanks: Ben-Gurion University of the Negev, Depaprtment of Computer Science. Supported by the Ministry of Science and Technology, Israel. Jonathan Ullman Thanks: 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.
原文 arXiv:1511.02513;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1511.02513v1