Original article was published by shaistha fathima on Becoming Human: Artificial Intelligence Magazine

### Differential Privacy — Noise adding Mechanisms

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

*What is Differential Privacy?**Global vs Local Differential Privacy**Differential Privacy Definition**Query “Sensitivity” types and effects on Differential Privacy Mechanism**Differential Privacy — Noise adding Mechanisms**Differential Privacy Basics Series Conclusion and Important list of resources.*

### (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

**, and perturb**

*f***with noise drawn from the Laplace distribution.**

*each coordinate*

*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 sensitivethe query, and thestrongerthedesired guarantee, themore “noise” is neededto achieve that guarantee.

**Another way to look at it is,**

Thesensitivityof a functionfis the amountf’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.

### Trending AI Articles:

1. Fundamentals of AI, ML and Deep Learning for Product Managers

3. Graph Neural Network for 3D Object Detection in a Point Cloud

4. Know the biggest Notable difference between AI vs. Machine Learning

Thus we can achieve differential privacy for our example query by using the Laplace mechanism with sensitivity 1 and an ε of our choosing. For now, let’s pick ε = 0.1. We can sample from the Laplace distribution using Numpy’s random.laplace.

Considerable care must be taken when programming real-valued mechanisms, such as the Laplace mechanism, due to subtleties in the implementation of floating point numbers. Otherwise differential privacy can be destroyed, as outputs with non-zero probability on a database *x*, may, because of rounding, have zero probability on adjacent databases *y*. This is just one way in which the implementation of floating point requires scrutiny in the context of differential privacy, and it is not unique.

*Drawbacks* :

*Drawbacks*:

(i) It is only really good for low sensitivity queries. (usually with L1 sensitivity)

(ii) Need large epsilon values (aka privacy budget) if you are going to fire off a bunch of queries. (Large epsilon values produce results that are less accurate in order to achieve the privacy guarantee).

(iii) Provides solution to handle numeric queries, but cannot be applied to the non-numeric valued queries like “what is the most common nationality in this room”: Chinese/Indian/American…

### 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
= A database of training*input: x*

** 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 likelythan the*behave very differently**initial network found (before adding noise)*that minimized error, and thus would have athan the minimal error network we desired.*unpredictably higher error* - 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

**from a probability distribution. Given a parameter , an input**

*o***, and a utility function**

*x***with generalized sensitivity**

*u***, we draw an output**

*∆u***from the following distribution:**

*o*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.

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

**Drawbacks:**

— it’s generally possible to redefine any ε-differentially private mechanism in terms of a carefully chosen definition of the scoring function*The exponential mechanism is extremely general**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
, and mechanisms defined in terms of the exponential mechanism are*comes at the cost of looser bounds*.*often very difficult to implement* - The exponential mechanism is
(by showing that a differentially private algorithm*often used to prove theoretical lower bounds**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 np

epsilon = 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* :

*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:

*Introduction to “Tensors”**Basic Concepts You Should Know Before Starting with the “Neural Networks” (NN)*

### References:

- https://www.cis.upenn.edu/~aaroth/Papers/privacybook.pdf
- https://www.seas.upenn.edu/~cis399/files/lecture/l21.pdf
- https://kth.diva-portal.org/smash/get/diva2:1112478/FULLTEXT01.pdf

### Don’t forget to give us your 👏 !

Differential Privacy — Noise adding Mechanisms was originally published in Becoming Human: Artificial Intelligence Magazine on Medium, where people are continuing the conversation by highlighting and responding to this story.