Differential Privacy — Noise adding Mechanisms

Published in

Becoming Human: Artificial Intelligence Magazine

10 min readOct 1, 2020

Laplace Mechanism, Exponential Mechanism and Gaussian Mechanism

Summary: Sometimes knowing the basics is important! This the fifth blog post of “Differential Privacy Basics Series” covering the general noise adding mechanism used in Differential Privacy. For more posts like these on Differential Privacy follow Shaistha Fathima on twitter.

Differential Privacy Basics Series

(1) Laplace Mechanism

Numeric queries, functions such as,

are one of the most fundamental types of database queries. These queries map databases to k real numbers. One of the important parameters that will determine just how accurately we can answer such queries is their ℓ1 sensitivity.

The ℓ1 sensitivity of a function gives an upper bound on how much we must perturb its output to preserve privacy, i.e., The ℓ1 sensitivity of a function f captures the magnitude by which a single individual’s data can change the function f in the worst case, and therefore, intuitively, the uncertainty in the response that we must introduce in order to hide the participation of a single individual.

The Laplace distribution is a symmetric version of the exponential distribution. Adds noise from a symmetric continuous distribution to true answer.

The Laplace mechanism will simply compute f, and perturb each coordinate with noise drawn from the Laplace distribution. The scale of the noise will be calibrated to the [(sensitivity of f (query))/ε], where δ is always equal to 0.

Noise is scaled to 1/ε, that is, by adding noise drawn from Lap(1/ε). The expected distortion, or error, is 1/ε, independent of the size of the database.

The Laplace mechanism preserves (ε,0)-differential privacy or ε-differentially private.

This corresponds to the intuition that the more sensitive the query, and the stronger the desired guarantee, the more “noise” is needed to achieve that guarantee.

Another way to look at it is,

The sensitivity of a function f is the amount f’s output changes when its input changes by 1.

Example: Counting queries always have a sensitivity of 1: if a query counts the number of rows in the dataset with a particular property, and then we modify exactly one row of the dataset, then the query’s output can change by at most 1.

Need for Exponential Mechanism when Laplace Mechanism already existed:

Laplace could be used for numeric queries only, while, exponential can be applied for numerical or categorical functional query output.
Most of the differential privacy revolved around real-valued functions which have relatively low sensitivity to change in the data of a single individual and whose usefulness is not hampered by small additive perturbations. A natural question is what happens in the situation when one wants to preserve more general sets of properties? The exponential mechanism helps to extend the notion of differential privacy to address these issues.
(Laplace and Gaussian) are focused on numerical answers, and add noise directly to the answer itself. What if we want to return a precise answer (i.e. no added noise), but still preserve differential privacy? One solution is the exponential mechanism, which allows selecting the “best” element from a set while preserving differential privacy.

Example:

The Laplace Mechanism gives a general purpose way of adding noise to satisfy differential privacy assuming that computing f accurately is the best measure of what we want to extract from our data.
BUT , if input: x= A database of training

dataGoal/Output: y= A neural network that minimizes the training error on x

The neural network returned is defined by a series of weights.
If we were to apply the Laplace Mechanism to this function, Laplace noise would be added to the weights before returning the network.
However, even small fluctuations in weights in a neural network may severely impact the performance of that network.
Therefore, the returned network (with added noise) will likely behave very differently than the initial network found (before adding noise) that minimized error, and thus would have a unpredictably higher error than the minimal error network we desired.
Thus, this presents us with motivation to create another mechanism to satisfy Differential Privacy in such cases where the Laplace Mechanism fails.

(2) Exponential Mechanism

The analyst defines which element is the “best” by specifying a scoring function that outputs a score for each element in the set, and also defines the set of things to pick from.

The mechanism provides differential privacy by approximately maximizing the score of the element it returns — in other words, to satisfy differential privacy, the exponential mechanism sometimes returns an element from the set which does not have the highest score.

Rather than adding noise to the output of a function f, the exponential mechanism draws an output o from a probability distribution. Given a parameter, an input x, and a utility function u with generalized sensitivity ∆u, we draw an output o from the following distribution:

The biggest practical difference between the exponential mechanism and the Laplace mechanism is that the output of the exponential mechanism is always a member of the set R. This is extremely useful when selecting an item from a finite set, when a noisy answer would not make sense.

For example:

We might want to pick a date for a big meeting, which uses each participant’s personal calendar to maximize the number of participants without a conflict, while providing differential privacy for the calendars.

Adding noise to a date doesn’t make much sense: it might turn a Friday into a Saturday, and increase the number of conflicts significantly. The exponential mechanism is perfect for problems like this one: it selects a date without a noise.

The exponential mechanism is interesting for several reasons:

The privacy cost of the mechanism is just epsilon, regardless of the size of R .
It theoretically works for both finite and infinite sets R, but it can be really challenging to build a practical implementation which samples from the appropriate probability distribution when R is infinite.
It represents a “fundamental mechanism” of ε-differential privacy: all other ε-differentially private mechanisms can be defined in terms of the exponential mechanism with the appropriate definition of the scoring function u.

Why is the exponential mechanism so much better? Because it releases less information. The exponential mechanism releases only the identity of the element with the maximum noisy score — not the score itself, or the scores of any other element.

Drawbacks:

The exponential mechanism is extremely general — it’s generally possible to redefine any ε-differentially private mechanism in terms of a carefully chosen definition of the scoring function u. If we can analyze the sensitivity of this scoring function, then the proof of differential privacy comes for free.
On the other hand, applying the general analysis of the exponential mechanism sometimes comes at the cost of looser bounds, and mechanisms defined in terms of the exponential mechanism are often very difficult to implement.
The exponential mechanism is often used to prove theoretical lower bounds (by showing that a differentially private algorithm exists), but practical algorithms often replicate the same behavior using some other approach (such as noisy max approach using laplace mechanism).

(3) Gaussian Mechanism

The Gaussian mechanism is an alternative to the Laplace mechanism, which adds Gaussian noise instead of Laplacian noise. The Gaussian mechanism does not satisfy pure ε -differential privacy, but does satisfy (ε, δ)-differential privacy.

According to the Gaussian mechanism, for a function f(x) which returns a number, the following definition of F(x) satisfies (ε, δ) -differential privacy:

For real-valued functions

we can use the Gaussian mechanism in exactly the same way as we do the Laplace mechanism, and it’s easy to compare what happens under both mechanisms for a given value of ε.

For example:

%matplotlib inline
import matplotlib.pyplot as plt
plt.style.use('seaborn-whitegrid')
import pandas as pd
import numpy as npepsilon = 1
vals_laplace = [np.random.laplace(loc=0, scale=1/epsilon) for x in range(100000)]delta = 10e-5
sigma = np.sqrt(2 * np.log(1.25 / delta)) * 1 / epsilon
vals_gauss = [np.random.normal(loc=0, scale=sigma) for x in range(100000)]plt.hist(vals_laplace, bins=50, label='Laplace')
plt.hist(vals_gauss, bins=50, alpha=.7, label='Gaussian');
plt.legend();

Here, we graph the empirical probability density function of the Laplace and Gaussian mechanisms for ε =1, with δ=10^-5 for the Gaussian mechanism.

Compared to the Laplace mechanism, the plot for the Gaussian mechanism looks “squished.” Differentially private outputs which are far from the true answer are much more likely using the Gaussian mechanism than they are under the Laplace mechanism (which, by comparison, looks extremely “pointy”).

**Gaussian mechanism also has two major drawbacks :**

(i) It requires the use of the the relaxed (ε, δ)-differential privacy definition,

(ii) It’s less accurate than the Laplace mechanism.

So, Why would we want to use it?

In the above example, we have only considered real-valued functions (i.e. the function’s output is always a single real number). Such functions are of the form

Both the Laplace and Gaussian mechanism, however, can be extended to vector-valued functions of the form

This return vectors of real numbers. For example, we can think of histograms as vector-valued functions, which return a vector whose elements consist of histogram bin counts.

Both the Laplace and Gaussian mechanisms can be extended to vector-valued functions. However, there’s a key difference between these two extensions:

(i) The vector-valued Laplace mechanism requires the use of L1 sensitivity, while the vector-valued Gaussian mechanism allows the use of either L1 or L2 sensitivity.

(ii) This is a major strength of the Gaussian mechanism. For applications in which L2 sensitivity is much lower than L1 sensitivity, the Gaussian mechanism allows adding much less noise.

That’s it folks! In the next blog and the LAST blog of this series I will finally answer some of the basic questions on What, why, how , etc followed by list of resources to learn from.

Till then you may also check out my other beginner friendly Series: