3
$\begingroup$

In differential privacy solutions and more specifically for queries that they do entail counting the proposed solutions define the Laplace distribution that is best calibrated for low error. Other solutions for non-numerical queries propose exponential distribution. However, it is not clear why noise from a Laplace distribution is chosen for numerical? What is the special property that best suits the Laplace distributrion?

$\endgroup$
1
$\begingroup$

In order to bridge the gap between two worst case scenarios to produce similar distribution of privatized answers certain noise is added. For example the salaries of a CEO (max) and a line worker or who ever gets minimum wage (min) may not be produce similar distribution without the noise.

Random values taken from Laplacian distribution with standard deviation is large enough to cover the gap.

This link has a good beginners tutorial with detailed explanation. Around 15.33 minutes in the video the speaker discusses about the issues like Global Sensitivity and Laplacian Noise. Subsequently she discusses the proof too.

$\endgroup$
  • $\begingroup$ yes but why laplacian and not gaussian for example??What is the special property that makes laplacian suitable for differential privacy $\endgroup$ – curious Jul 24 '15 at 14:46
  • $\begingroup$ I thought the second line "Random values .." answers the same. For detailed explanation please follow the excellent video link i gave $\endgroup$ – sashank Jul 25 '15 at 13:02
0
$\begingroup$

The Laplace mechanism is a symmetric exponential distribution, which works particularly well with the differential privacy guarantee: when you compare two Laplace distributions of the same scale, with a different mean, the ratio between the tails stays the same. For example, in the following graph, the Laplace distribution has a parameter of $1/ln(3)$, so the ratio between two distributions is bounded by $3$ and $1/3$.

Two Laplace distributions

The Gaussian distribution, on the other hand, doesn't have this nice property. It's not as straightforward to find out the maximum ratio between two Gaussians with the same standard deviation and different means. Let's compute the ratio of density functions of two Gaussians, centered respectively in $0$ and $1$. Getting rid of the constant factor, we have:

\begin{align} \frac{e^{-\frac{(x-1)^2}{2\mu^2}}}{e^{-\frac{x^2}{2\mu^2}}} & = e^{\frac{x^2-(x-1)^2}{2\mu^2}} \\ & = e^{\frac{2x-1}{2\mu^2}} \end{align}

This is unbounded when $x$ increases. So you can't get true differential privacy with a Gaussian. You can use it to obtain relaxations of the definition though, like $(\varepsilon,\delta)$-differential privacy or Rényi differential privacy.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.