15
$\begingroup$

I am currently writing algorithm for differential privacy using the Laplace mechanism.

Unfortunately I have no background in statistics, therefore a lot of terms are unknown to me. So now I'm stumbling over the term: Laplace noise. To make a dataset differential private all papers just talk about adding Laplace noise according to the Laplace distribution to the function values.

$k(X) = f(X) + Y(X)$

(k is the differential private value, f the returned value by the evaluation function and Y the Laplace noise)

Does this mean I create random variables from the Laplace distribution according this function I have from wikipedia https://en.wikipedia.org/wiki/Laplace_distribution?

$ Y = μ − b\ \text{sgn}(U) \ln ⁡ ( 1 − 2 | U | ) $

UPDATE: I plotted up to 100 random variables drawn from the function above, but this doesn't give me a Laplace distribution (not even close). But I think it should model a Laplace distribution.

UPDATE2:

Those are the definitions I have:

(The Laplace Mechanism). Given any function $f:N^{|X|}→R^k$, the Laplace mechanism is defined as: $M_L(x, f(·),\epsilon)=f(x)+(Y_1,...,Y_k)$ where Y are i.i.d. random variables drawn from $Lap(∆f/\epsilon)$

As well as:

To generate Y ( X ), a common choice is to use a Laplace distribution with zero mean and Δ ( f ) /ε scale parameter

$\endgroup$
4
  • $\begingroup$ The second equation you have is the CDF rather than the PDF. You want to sample from the PDF. Here is some python code to sample from the Laplace (biexponential) distribution (docs.scipy.org/doc/numpy-1.9.3/reference/generated/…) $\endgroup$
    – Luca
    Jul 14, 2016 at 8:13
  • 1
    $\begingroup$ Can you provide the exact reference that mentions the "Laplace noise"? I guess that they mean adding r.v. Y to X where Y follows Laplace distribution. As about your update, this method does work -- you must have made mistake in your code, or it is just the fact that you made only 100 draws from it, if you tries 5000 or more I guess it'd start looking more "Laplace"... $\endgroup$
    – Tim
    Jul 14, 2016 at 8:18
  • $\begingroup$ I think my plot actually looks more like a CDF, I added it above, as well as my code. Here are the links to the quotes: 1 2 $\endgroup$
    – Axolotl
    Jul 14, 2016 at 9:09
  • $\begingroup$ I've also seen the code I'm using before and I don't know why it gives me result like this. The plot shows my code, looped 1000 times for f=1 and eps = 1. But I think my main point is, if I understood "Laplace noise" right. The code I can workout somehow. $\endgroup$
    – Axolotl
    Jul 14, 2016 at 9:19

2 Answers 2

17
$\begingroup$

You are correct, adding Laplace noise means that to your variable $X$ you add variable $Y$ that follows Laplace distribution. There are multiple reasons why it is called noise. First, think of signal processing, where message is send over some channel and due to imperfect nature of the channel the received signal is noisy, so you have to isolate signal from the noise. Second, in cryptography we also talk about pseudorandom noise and differential privacy is related to cryptography. Third, in statistics and machine learning we also can talk about statistical noise, statistical models include noise or error terms etc. (there is even a book about forecasting names Signal and the noise by Nate Silver). So we use noise as a more precise synonym for ambiguous randomness.

As about random generation, there is a number of ways how you can draw random values following Laplace distribution, for example:

  1. The inverse transform method described on Wikipedia:
f <- function(n) {
   u <- runif(n, -0.5, 0.5)
   sign(u)*log(1-2*abs(u))
}
  1. If $U$ and $V$ are independent random variables following exponential distribution, then $Y = U-V$ follows Laplace distribution:
g <- function(n) { rexp(n)-rexp(n) }
  1. If $Y$ follows Laplace distribution, then $|Y|$ follows exponential distribution, so:
h <- function(n) { rexp(n)*sample(c(-1,1), n, replace = TRUE) }

On the plots below you can see distribution of $10^{5}$ samples drawn using each of the functions with accompanying Laplace density (red line).

enter image description here

To simplify the examples I use standard Laplace distribution with scale = 1, but you can easily change the outcomes by multiplying the results using different scaling factor.

$\endgroup$
2
  • $\begingroup$ Thanks! That's answering my question, I was just really confused about the term "noise" and couldn't find a proper explanation. $\endgroup$
    – Axolotl
    Jul 15, 2016 at 0:38
  • $\begingroup$ I plotted the histogram for my code and it looks good :) $\endgroup$
    – Axolotl
    Jul 15, 2016 at 2:23
2
$\begingroup$

The Laplace or double exponential distribution falls off exponentially to the left and right around some mean. It's basically the exponential mirrored to the other side.

  • If you want the likelihood, use the likelihood of the exponential and add an abs() to the observed value. The log likelihood is simply the abs() of the residuals, multiplied by the rate of the exponential.

  • To sample, the easiest is to draw from -1,1, and multiply with a draw from the exponential distribution, which is available in most programming languages. Alternatively, as noted above, you will also find direct implementations of the Laplace, but it may require a bit more searching.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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