Sampling Without Compromising Accuracy in Adaptive Data Analysis

Benjamin Fish, Lev Reyzin, Benjamin I. P. Rubinstein
Proceedings of the 31st International Conference on Algorithmic Learning Theory, PMLR 117:297-318, 2020.

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. This is important to do when both the datasets and the number of queries asked are very large. 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v117-fish20a, title = {Sampling Without Compromising Accuracy in Adaptive Data Analysis}, author = {Fish, Benjamin and Reyzin, Lev and Rubinstein, Benjamin I. P.}, booktitle = {Proceedings of the 31st International Conference on Algorithmic Learning Theory}, pages = {297--318}, year = {2020}, editor = {Kontorovich, Aryeh and Neu, Gergely}, volume = {117}, series = {Proceedings of Machine Learning Research}, month = {08 Feb--11 Feb}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v117/fish20a/fish20a.pdf}, url = {https://proceedings.mlr.press/v117/fish20a.html}, 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. This is important to do when both the datasets and the number of queries asked are very large. 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.} }
Endnote
%0 Conference Paper %T Sampling Without Compromising Accuracy in Adaptive Data Analysis %A Benjamin Fish %A Lev Reyzin %A Benjamin I. P. Rubinstein %B Proceedings of the 31st International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2020 %E Aryeh Kontorovich %E Gergely Neu %F pmlr-v117-fish20a %I PMLR %P 297--318 %U https://proceedings.mlr.press/v117/fish20a.html %V 117 %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. This is important to do when both the datasets and the number of queries asked are very large. 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.
APA
Fish, B., Reyzin, L. & Rubinstein, B.I.P.. (2020). Sampling Without Compromising Accuracy in Adaptive Data Analysis. Proceedings of the 31st International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 117:297-318 Available from https://proceedings.mlr.press/v117/fish20a.html.

Related Material