%0 Conference Paper %1 fish2017sampling %A Fish, Benjamin %A Reyzin, Lev %A Rubinstein, Benjamin I. P. %D 2017 %K alt2020 convergence generalization readings sampling %T Sampling Without Compromising Accuracy in Adaptive Data Analysis %U http://arxiv.org/abs/1709.09778 %X 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. In particular, we describe a mechanism that provides a polynomial speed-up per query over previous mechanisms, without needing to increase the total amount of data required to maintain the same generalization error as before. We prove that this speed-up holds for arbitrary statistical queries. We also provide an even faster method for achieving statistically-meaningful responses wherein the mechanism is only allowed to see a constant number of samples from the data per query. Finally, we show that our general results yield a simple, fast, and unified approach for adaptively optimizing convex and strongly convex functions over a dataset.

@inproceedings{fish2017sampling, abstract = {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. In particular, we describe a mechanism that provides a polynomial speed-up per query over previous mechanisms, without needing to increase the total amount of data required to maintain the same generalization error as before. We prove that this speed-up holds for arbitrary statistical queries. We also provide an even faster method for achieving statistically-meaningful responses wherein the mechanism is only allowed to see a constant number of samples from the data per query. Finally, we show that our general results yield a simple, fast, and unified approach for adaptively optimizing convex and strongly convex functions over a dataset.}, added-at = {2019-11-27T15:17:08.000+0100}, author = {Fish, Benjamin and Reyzin, Lev and Rubinstein, Benjamin I. P.}, biburl = {https://www.bibsonomy.org/bibtex/2c722e7f1caf2fb2903fdb01d912f1ef9/kirk86}, description = {[1709.09778] Sampling Without Compromising Accuracy in Adaptive Data Analysis}, interhash = {c0dfa09f6d51d6f56c55a3b10ca1d88f}, intrahash = {c722e7f1caf2fb2903fdb01d912f1ef9}, keywords = {alt2020 convergence generalization readings sampling}, note = {cite arxiv:1709.09778}, timestamp = {2019-11-27T15:17:08.000+0100}, title = {Sampling Without Compromising Accuracy in Adaptive Data Analysis}, url = {http://arxiv.org/abs/1709.09778}, year = 2017 }