Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.


Boosting is a general method for improving the accuracy of learning algorithms. We use boosting to construct {em privacy-preserving synopses} of the input database. These are data structures that yield, for a given set $Q$ of queries over an input database, reasonably accurate estimates of the responses to every query in~$Q$. Given a {em base synopsis generator} that takes a distribution on $Q$ and produces a ``weak'' synopsis that yields ``good'' answers for a majority of the weight in $Q$, our {em Boosting for Queries} algorithm obtains a synopsis that is good for all of~$Q$. We ensure privacy for the rows of the database, but the boosting is performed on the {em queries}.

We provide an (inefficient) base synopsis generator for sets of {em arbitrary} low-sensitivity queries (queries whose answers do not vary much under the addition or deletion of a single row). This yields the first privacy-preserving synopsis generator for arbitrary low-sensitivity queries.

Boosting is an iterative method. In our Boosting for Queries algorithm, each iteration incurs a certain privacy loss. In analyzing the cumulative privacy loss over many iterations, we obtain a bound on the {em expected} privacy loss from a single $eps$-dfp{} mechanism. Combining this with {em evolution of confidence} arguments from the literature, we get a fresh perspective -- and stronger bounds -- on the expected cumulative privacy loss due to multiple mechanisms, each providing $eps$-differential privacy or one of its relaxations, and each operating on (potentially) different, adaptively chosen, databases. snote{changed ``the first bounds'' to ``stronger bounds'', to deflect possible claims that such guarantees are folklore/obvious for $(keps,kdelta)$ type results}

Finally, we can also view the input database as a training set in a learning algorithm, where each row corresponds to an element in the training set. Given the power and prevalence of boosting, it is natural t

Questions and Answers

You need to be logged in to be able to post here.