What is meant by "Laplace noise"?

Question

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

Answer 1

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))
}

2. 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) }

3. 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).

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.

Answer 2

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.