Sampling Without Compromising Accuracy in Adaptive Data Analysis

Benjamin Fish, Lev Reyzin, Benjamin I. P. Rubinstein

In this work, we study how to use sampling to speed up mechanisms for answering adaptive queries into datasets without reducing the accuracy of those mechanisms. This is important…