The optimal mechanism in differential privacy

By Quan Geng, Pramod Viswanath. 2012

141 citations recorded by the source corpus.

Differential privacy is a framework to quantify to what extent individual privacy in a statistical database is preserved while releasing useful aggregate information about the database. In this work we study the fundamental tradeoff between privacy and utility in differential privacy. We derive the optimal ε-differentially private mechanism for single real-valued query function under a very general utility-maximization (or cost-minimization) framework. The class of noise probability distributions in the optimal mechanism has staircase-shaped probability density functions, which can be viewed as a geometric mixture of uniform probability distributions. In the context of ℓ1 and ℓ2 utility functions, we show that the standard Laplacian mechanism, which has been widely used in the literature, is asymptotically optimal in the high privacy regime, while in the low privacy regime, the staircase mechanism performs exponentially better than the Laplacian mechanism. We conclude that the gains of the staircase mechanism are more pronounced in the moderate-low privacy regime.

Subfields: Artificial Intelligence, Computer Science Applications

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Peter Kairouz
2. Pramod Viswanath
3. Quan Geng
4. Sewoong Oh
5. Sanjiv Kumar
6. Liwei Wang
7. Wenlong Mou
8. Ruiqi Guo

In Computer Science Applications

1. Sanjiv Kumar
2. Wei Ding
3. Ruiqi Guo
4. Quan Geng
5. Pramod Viswanath
6. Peter Kairouz
7. Sewoong Oh
8. Liwei Wang

Citations in the corpus

• Extremal Mechanisms for Local Differential Privacy (2014, background): “(for a worst-case input setting) who proposed a family of mechanisms and proved its optimality for monotone utility functions under queries with arbitrary sensitivity [14, 16, 15].”
• Optimal Noise-Adding Mechanism in Additive Differential Privacy (2018, methodology): “Geng and Viswanath (2016b) derived the optimal -differentially private noise adding mechanism for single real-valued query function with arbitrary query sensitivity, and show that the optimal noise distribution has a staircaseshaped probability density function. Geng et al. (2015) generalized the re”
• Differentially private multi-party computation (2014, background): “While such universal mechanisms do not exist in terms of maximizing average accuracy [5], recent work [17, 18] construct a class of mechanisms (termed as “staircase” mechanisms) that are universally optimal in terms of maximizing worst-case accuracy for any cost metric that is monotonic in the error”
• Collect at Once, Use Effectively: Making Non-interactive Locally Private Learning Possible (2017, background): “One can also consider optimal mechanisms in terms of privacy parameters like [14], which is of independent interests.”
• Differentially Private SQL with Bounded User Contribution (2019, methodology): “For all functions, noise is added to internal states using the well-known Laplace mechanism [14, 16] before a differentially private version of the aggregate result can be released.”
• The Optimal Noise-Adding Mechanism in Differential Privacy (2012, background): “An early version of this work has been presented in part in the conference paper [9].”
• Entropy-minimizing mechanism for differential privacy of discrete-time linear feedback systems (2014, background): “For dynamics systems, it has been shown that, under the usual definition, -differential privacy imposes a lower bound on the variance of queries and the minimum is achieved by staircase distributions [8], [9], [10].”
• Optimal Noise Adding Mechanisms for Approximate Differential Privacy (2013, background): “Geng and Viswanath [3] generalize the results of [18] and [20] to real-valued (and integer-valued) query functions with arbitrary sensitivity, and show that the optimal query-output independent perturbation mechanism is the staircase mechanism, which adds noise with a staircase-shaped probability…”
• The Optimal Mechanism in Differential Privacy : Multidimensional Setting (2013, background): “Recently, Geng and Viswanath [3] show that under a general utilitymaximization framework, for single real-valued query function, the optimal -differentially private mechanism is the staircase mechanism, which adds noise with the staircase distribution to the query output.”