# what is the relationship between epsilon and sensitivity in the Differential-Privacy?

In some Differential-Privacy(DP) papers, they use epsilon as the x-axis in the figures of the experiments' result while other papers use the sensitivity.

1. What is the relationship between epsilon and sensitivity in the DP?

2. How can I compare the results of different papers?

I'll answer the second question first. The two are distinct concepts — there's no way directly compare graphs or results without more info or context.

Differential privacy is usually obtained by 1. computing a function $$F$$ of the data and 2. adding some noise to the result. The noise must be large enough to hide an individual contribution, and "how well an individual contribution is hidden" is captured by the parameter $$\varepsilon$$.

But for some functions $$F$$, an individual contribution can change the true result more than for others functions. For example:

• The answer to "how many employees of this company have blue eyes?" can only change by one if you add or remove an employee.
• The answer to "what's the average salary of people in this company?" can change by a lot if you remove the CEO's salary.

That concept is captured by sensitivity: the higher the possible change, the higher the sensitivity. And typically, to get $$\varepsilon$$-differential privacy with a fixed $$\varepsilon$$, you have to add more noise when the sensitivity is larger (to compensate). That's the typical relationship between the two concepts.

• There is an interesting paper discussing what are good values for ε for various usage scenarios: J. Lee, C. Clifton, “How much is enough? Choosing ε for differential privacy,” Proceedings of the International Conference on Information Security, Springer, Berlin, Heidelberg, 2011 Commented Mar 4, 2019 at 23:40

Let $$\mathcal{D}$$ be our universe of datasets, and $$M: \mathcal{D}\times \mathbb{R}^n \to [0,\infty)$$ a mechanism where for each dataset $$X\in \mathcal{D}$$, $$M(X,t) = M_X(t)$$ is a probability density over $$t\in \mathbb{R}^n$$.

Now write $$u(X,t) = \log(M(X,t))$$, taking values in $$[-\infty, \infty)$$ so $$M = \exp(u)$$. The sensitivity of $$u$$ is $$\Delta(u) = \sup |u(X,t) - u(Y,t)|$$, with supremum over $$t\in \mathbb{R}^n$$, and neighboring $$X,Y\in \mathcal{D}$$.

The definition of differential privacy states that $$M$$ is $$\varepsilon$$-DP, where $$\varepsilon = \sup |\log(M_X/M_Y)| = \Delta(u)$$ (with supremum over $$t\in \mathbb{R}^n$$, and neighboring $$X,Y\in \mathcal{D}$$).

In short, $$M$$ is $$\Delta(u)$$-DP.