Private Query Release Assisted by Public Data

Raef Bassily, Albert Cheu, Shay Moran, Aleksandar Nikolov, Jonathan Ullman, Steven Wu
Proceedings of the 37th International Conference on Machine Learning, PMLR 119:695-703, 2020.

Abstract

We study the problem of differentially private query release assisted by access to public data. In this problem, the goal is to answer a large class $\mathcal{H}$ of statistical queries with error no more than $\alpha$ using a combination of public and private samples. The algorithm is required to satisfy differential privacy only with respect to the private samples. We study the limits of this task in terms of the private and public sample complexities. Our upper and lower bounds on the private sample complexity have matching dependence on the dual VC-dimension of $\mathcal{H}$. For a large category of query classes, our bounds on the public sample complexity have matching dependence on $\alpha$.

Cite this Paper

BibTeX
@InProceedings{pmlr-v119-bassily20a, title = {Private Query Release Assisted by Public Data}, author = {Bassily, Raef and Cheu, Albert and Moran, Shay and Nikolov, Aleksandar and Ullman, Jonathan and Wu, Steven}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, pages = {695--703}, year = {2020}, editor = {III, Hal Daumé and Singh, Aarti}, volume = {119}, series = {Proceedings of Machine Learning Research}, month = {13--18 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v119/bassily20a/bassily20a.pdf}, url = {https://proceedings.mlr.press/v119/bassily20a.html}, abstract = {We study the problem of differentially private query release assisted by access to public data. In this problem, the goal is to answer a large class $\mathcal{H}$ of statistical queries with error no more than $\alpha$ using a combination of public and private samples. The algorithm is required to satisfy differential privacy only with respect to the private samples. We study the limits of this task in terms of the private and public sample complexities. Our upper and lower bounds on the private sample complexity have matching dependence on the dual VC-dimension of $\mathcal{H}$. For a large category of query classes, our bounds on the public sample complexity have matching dependence on $\alpha$.} }
Endnote
%0 Conference Paper %T Private Query Release Assisted by Public Data %A Raef Bassily %A Albert Cheu %A Shay Moran %A Aleksandar Nikolov %A Jonathan Ullman %A Steven Wu %B Proceedings of the 37th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2020 %E Hal Daumé III %E Aarti Singh %F pmlr-v119-bassily20a %I PMLR %P 695--703 %U https://proceedings.mlr.press/v119/bassily20a.html %V 119 %X We study the problem of differentially private query release assisted by access to public data. In this problem, the goal is to answer a large class $\mathcal{H}$ of statistical queries with error no more than $\alpha$ using a combination of public and private samples. The algorithm is required to satisfy differential privacy only with respect to the private samples. We study the limits of this task in terms of the private and public sample complexities. Our upper and lower bounds on the private sample complexity have matching dependence on the dual VC-dimension of $\mathcal{H}$. For a large category of query classes, our bounds on the public sample complexity have matching dependence on $\alpha$.
APA
Bassily, R., Cheu, A., Moran, S., Nikolov, A., Ullman, J. & Wu, S.. (2020). Private Query Release Assisted by Public Data. Proceedings of the 37th International Conference on Machine Learning, in Proceedings of Machine Learning Research 119:695-703 Available from https://proceedings.mlr.press/v119/bassily20a.html.

Related Material