The Price of Online Queries in Differential Privacy
29 mins 52 secs,
54.63 MB,
MP3
44100 Hz,
249.74 kbits/sec
Share this media item:
Embed this media item:
Embed this media item:
About this item
| Description: |
Bun, M (Princeton University)
Thursday 8th December 2016 - 12:00 to 12:30 |
|---|
| Created: | 2016-12-19 11:38 |
|---|---|
| Collection: | Data Linkage and Anonymisation |
| Publisher: | Isaac Newton Institute |
| Copyright: | Bun, M |
| Language: | eng (English) |
| Distribution: |
World
(downloadable)
|
| Explicit content: | No |
| Aspect Ratio: | 16:9 |
| Screencast: | No |
| Bumper: | UCS Default |
| Trailer: | UCS Default |
| Abstract: | Co-authors: Thomas Steinke (IBM Research - Almaden), Jonathan Ullman (Northeastern University)
We consider the problem of answering queries about a sensitive dataset subject to differential privacy. The queries may be chosen adversarially from a larger set of allowable queries via one of three interactive models. These models capture whether the queries are given to the mechanism all in a single batch (“offline”), whether they are chosen in advance but presented to the mechanism one at a time (“online”), or whether they may be chosen by an analyst adaptively (“adaptive”). Many differentially private mechanisms are just as efficient in the adaptive model as they are in the offline model. Meanwhile, most lower bounds for differential privacy hold in the offline setting. This suggests that the three models might be equivalent. We prove that these models are all, in fact, distinct. Specifically, we show that there is a family of statistical queries such that exponentially more queries from this family can be answered in the offline model than in the online model. We also exhibit a family of search queries such that many more queries from this family can be answered in the online model than in the adaptive model. We also investigate whether such separations might hold for simple queries, such as threshold queries over the real line. Joint work with Thomas Steinke and Jonathan Ullman. Related Links https://arxiv.org/abs/1604.04618 - Full version of manuscript |
|---|---|
Available Formats
| Format | Quality | Bitrate | Size | |||
|---|---|---|---|---|---|---|
| MPEG-4 Video | 640x360 | 1.94 Mbits/sec | 434.27 MB | View | Download | |
| WebM | 640x360 | 533.46 kbits/sec | 116.63 MB | View | Download | |
| iPod Video | 480x270 | 522.13 kbits/sec | 114.09 MB | View | Download | |
| MP3 * | 44100 Hz | 249.74 kbits/sec | 54.63 MB | Listen | Download | |
| Auto | (Allows browser to choose a format it supports) | |||||