Аннотация
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.
Пользователи данного ресурса
Пожалуйста,
войдите в систему, чтобы принять участие в дискуссии (добавить собственные рецензию, или комментарий)