Dual Query: Practical Private Query Release for High Dimensional Data

Marco Gaboardi, Emilio Jesus Gallego Arias, Justin Hsu, Aaron Roth, Zhiwei Steven Wu
; Proceedings of the 31st International Conference on Machine Learning, PMLR 32(2):1170-1178, 2014.

Abstract

We present a practical, differentially private algorithm for answering a large number of queries on high dimensional datasets. Like all algorithms for this task, ours necessarily has worst-case complexity exponential in the dimension of the data. However, our algorithm packages the computationally hard step into a concisely defined integer program, which can be solved non-privately using standard solvers. We prove accuracy and privacy theorems for our algorithm, and then demonstrate experimentally that our algorithm performs well in practice. For example, our algorithm can efficiently and accurately answer millions of queries on the Netflix dataset, which has over 17,000 attributes; this is an improvement on the state of the art by multiple orders of magnitude.

Cite this Paper


BibTeX
@InProceedings{pmlr-v32-gaboardi14, title = {Dual Query: Practical Private Query Release for High Dimensional Data}, author = {Marco Gaboardi and Emilio Jesus Gallego Arias and Justin Hsu and Aaron Roth and Zhiwei Steven Wu}, booktitle = {Proceedings of the 31st International Conference on Machine Learning}, pages = {1170--1178}, year = {2014}, editor = {Eric P. Xing and Tony Jebara}, volume = {32}, number = {2}, series = {Proceedings of Machine Learning Research}, address = {Bejing, China}, month = {22--24 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v32/gaboardi14.pdf}, url = {http://proceedings.mlr.press/v32/gaboardi14.html}, abstract = {We present a practical, differentially private algorithm for answering a large number of queries on high dimensional datasets. Like all algorithms for this task, ours necessarily has worst-case complexity exponential in the dimension of the data. However, our algorithm packages the computationally hard step into a concisely defined integer program, which can be solved non-privately using standard solvers. We prove accuracy and privacy theorems for our algorithm, and then demonstrate experimentally that our algorithm performs well in practice. For example, our algorithm can efficiently and accurately answer millions of queries on the Netflix dataset, which has over 17,000 attributes; this is an improvement on the state of the art by multiple orders of magnitude.} }
Endnote
%0 Conference Paper %T Dual Query: Practical Private Query Release for High Dimensional Data %A Marco Gaboardi %A Emilio Jesus Gallego Arias %A Justin Hsu %A Aaron Roth %A Zhiwei Steven Wu %B Proceedings of the 31st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2014 %E Eric P. Xing %E Tony Jebara %F pmlr-v32-gaboardi14 %I PMLR %J Proceedings of Machine Learning Research %P 1170--1178 %U http://proceedings.mlr.press %V 32 %N 2 %W PMLR %X We present a practical, differentially private algorithm for answering a large number of queries on high dimensional datasets. Like all algorithms for this task, ours necessarily has worst-case complexity exponential in the dimension of the data. However, our algorithm packages the computationally hard step into a concisely defined integer program, which can be solved non-privately using standard solvers. We prove accuracy and privacy theorems for our algorithm, and then demonstrate experimentally that our algorithm performs well in practice. For example, our algorithm can efficiently and accurately answer millions of queries on the Netflix dataset, which has over 17,000 attributes; this is an improvement on the state of the art by multiple orders of magnitude.
RIS
TY - CPAPER TI - Dual Query: Practical Private Query Release for High Dimensional Data AU - Marco Gaboardi AU - Emilio Jesus Gallego Arias AU - Justin Hsu AU - Aaron Roth AU - Zhiwei Steven Wu BT - Proceedings of the 31st International Conference on Machine Learning PY - 2014/01/27 DA - 2014/01/27 ED - Eric P. Xing ED - Tony Jebara ID - pmlr-v32-gaboardi14 PB - PMLR SP - 1170 DP - PMLR EP - 1178 L1 - http://proceedings.mlr.press/v32/gaboardi14.pdf UR - http://proceedings.mlr.press/v32/gaboardi14.html AB - We present a practical, differentially private algorithm for answering a large number of queries on high dimensional datasets. Like all algorithms for this task, ours necessarily has worst-case complexity exponential in the dimension of the data. However, our algorithm packages the computationally hard step into a concisely defined integer program, which can be solved non-privately using standard solvers. We prove accuracy and privacy theorems for our algorithm, and then demonstrate experimentally that our algorithm performs well in practice. For example, our algorithm can efficiently and accurately answer millions of queries on the Netflix dataset, which has over 17,000 attributes; this is an improvement on the state of the art by multiple orders of magnitude. ER -
APA
Gaboardi, M., Arias, E.J.G., Hsu, J., Roth, A. & Wu, Z.S.. (2014). Dual Query: Practical Private Query Release for High Dimensional Data. Proceedings of the 31st International Conference on Machine Learning, in PMLR 32(2):1170-1178

Related Material