More General Queries and Less Generalization Error in Adaptive Data Analysis
By Raef Bassily, Adam D. Smith, Thomas Steinke, Jonathan Ullman. 2015
15 citations recorded by the source corpus.
Adaptivity is an important feature of data analysis---typically the choice of questions asked about a dataset depends on previous interactions with the same dataset. However, generalization error is typically bounded in a non-adaptive model, where all questions are specified before the dataset is drawn. Recent work by Dwork et al. (STOC '15) and Hardt and Ullman (FOCS '14) initiated the 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 distribution $\mathcal{P}$ and a set of $n$ independent samples $x$ is drawn from $\mathcal{P}$. We seek an algorithm that, given $x$ as input, "accurately" answers a sequence of adaptively chosen "queries" about the unknown distribution $\mathcal{P}$. How many samples $n$ must 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 samples $n$ that are needed to answer statistical queries that improve over the bounds of Dwork et al. *We prove the first upper bounds on the number of samples required to answer more general families of queries. These include arbitrary low-sensitivity queries and the important class of convex risk minimization queries. As in Dwork et al., our algorithms are based on a connection between differential privacy and generalization error, but we feel that our analysis is simpler and more modular, which may be useful for studying these questions in the future.
Subfields: Artificial Intelligence
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Vitaly Feldman
- Aaron Roth
- Cynthia Dwork
- Jonathan Ullman
- Moritz Hardt
- Adam D. Smith
- Thomas Steinke
- Omer Reingold
Citations in the corpus
- Preserving Statistical Validity in Adaptive Data Analysis (2014, methodology): “give an alternative approach for using a differentially private algorithm to answer statistical and more general types of queries [6].”
- The Ladder: A Reliable Leaderboard for Machine Learning Competitions (2015, background): “This shows that the tree itself cannot grow larger than 2B and we may take a union bound over all 2B nodes.”
- Generalization in Adaptive Data Analysis and Holdout Reuse (2015, methodology): “An example of the application of SparseValidate for answering statistical and low-sensitivity queries that is based on our analysis can be found in [1].”