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.
Beschreibung
[1709.09778] Sampling Without Compromising Accuracy in Adaptive Data Analysis
%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
}