Tight Analysis of Privacy and Utility Tradeoff in Approximate Differential Privacy

Quan Geng, Wei Ding, Ruiqi Guo, Sanjiv Kumar
Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, PMLR 108:89-99, 2020.

Abstract

We characterize the minimum noise amplitude and power for noise-adding mechanisms in (epsilon, delta)-differential privacy for single real-valued query function. We derive new lower bounds using the duality of linear programming, and new upper bounds by analyzing a special class of (epsilon, delta)-differentially private mechanisms, the truncated Laplacian mechanisms. We show that the multiplicative gap of the lower bounds and upper bounds goes to zero in various high privacy regimes, proving the tightness of the lower and upper bounds. In particular, our results close the previous constant multiplicative gap in the discrete setting. Numeric experiments show the improvement of the truncated Laplacian mechanism over the optimal Gaussian mechanism in all privacy regimes.

Cite this Paper

BibTeX
@InProceedings{pmlr-v108-geng20a, title = {Tight Analysis of Privacy and Utility Tradeoff in Approximate Differential Privacy}, author = {Geng, Quan and Ding, Wei and Guo, Ruiqi and Kumar, Sanjiv}, booktitle = {Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics}, pages = {89--99}, year = {2020}, editor = {Chiappa, Silvia and Calandra, Roberto}, volume = {108}, series = {Proceedings of Machine Learning Research}, month = {26--28 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v108/geng20a/geng20a.pdf}, url = {https://proceedings.mlr.press/v108/geng20a.html}, abstract = {We characterize the minimum noise amplitude and power for noise-adding mechanisms in (epsilon, delta)-differential privacy for single real-valued query function. We derive new lower bounds using the duality of linear programming, and new upper bounds by analyzing a special class of (epsilon, delta)-differentially private mechanisms, the truncated Laplacian mechanisms. We show that the multiplicative gap of the lower bounds and upper bounds goes to zero in various high privacy regimes, proving the tightness of the lower and upper bounds. In particular, our results close the previous constant multiplicative gap in the discrete setting. Numeric experiments show the improvement of the truncated Laplacian mechanism over the optimal Gaussian mechanism in all privacy regimes.} }
Endnote
%0 Conference Paper %T Tight Analysis of Privacy and Utility Tradeoff in Approximate Differential Privacy %A Quan Geng %A Wei Ding %A Ruiqi Guo %A Sanjiv Kumar %B Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2020 %E Silvia Chiappa %E Roberto Calandra %F pmlr-v108-geng20a %I PMLR %P 89--99 %U https://proceedings.mlr.press/v108/geng20a.html %V 108 %X We characterize the minimum noise amplitude and power for noise-adding mechanisms in (epsilon, delta)-differential privacy for single real-valued query function. We derive new lower bounds using the duality of linear programming, and new upper bounds by analyzing a special class of (epsilon, delta)-differentially private mechanisms, the truncated Laplacian mechanisms. We show that the multiplicative gap of the lower bounds and upper bounds goes to zero in various high privacy regimes, proving the tightness of the lower and upper bounds. In particular, our results close the previous constant multiplicative gap in the discrete setting. Numeric experiments show the improvement of the truncated Laplacian mechanism over the optimal Gaussian mechanism in all privacy regimes.
APA
Geng, Q., Ding, W., Guo, R. & Kumar, S.. (2020). Tight Analysis of Privacy and Utility Tradeoff in Approximate Differential Privacy. Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 108:89-99 Available from https://proceedings.mlr.press/v108/geng20a.html.

Related Material