Sensitivity of probability measure in differential privacy

Question

I know that we need some sort of sensitivity(global, local) to calculate noise that needs to be added for differential privacy. The noise is the maximum difference between two neighboring datasets. However, if I am working in probability spaces, i.e. my values are bounded by 0,1. My sensitivity would be 1, which seems too large for adding noise to the probabilities.

I tried looking up any relevant literature that provides any tighter upper bounds, but no success. I am only interested in adding noise to the probabilities, not to the mechanism that they are generated from.

Answer 1

Do you need local differential privacy (i.e. no central server knows the real data of individuals) or global differential privacy (where you have all the real data, and want to generate differentially private statistics out of it)?

In the former case, you need to add a significant amount of noise (typically Laplace noise) to each probability, and there's basically no better way of doing it. This will mean that every data point will be very noisy, but if you have enough of them, you might be able to retrieve some information. The "amount of noise" will be similar to the randomized response mechanism described here or here.

In the latter case, it depends on what you're computing. If you're computing the average probability, the noise you add can be scaled by $1/n$, where $n$ is the total number of users. See for example the methods presented here, in the "summing or averaging numbers" section.

Answer 2

It would be pretty useful if you would describe particularly what you're doing. This is because it can be easy to use more context to design more efficient DP algorithms.

Consider a database $D$ where each user has some number in $[k]$ associated with them, and you want to return a differentially private estimate of:

$$p_k = \Pr_{x\in D}[x = k]$$ You're right that without more information, $p_k\in[0,1]$, so you'd have to add a ton of laplacian noise to each $p_k$, an obvious problem.

This is where we can use special knowledge about the problem we're trying to solve --- since we're assuming each user has a single number associated with them, their inclusion in the database can only impact a single $p_k$. Specifically, we can write: $$p_k = \frac{|\mathsf{count}_k(D)|}{n}$$ where $\mathsf{count}_k(D) = \{x\in D \mid x = k \}$. Now, count queries themselves have sensitivity 1, so from this perspective $p_k$ actually has sensitivity $\frac{1}{n}$. Since the inclusion of a user can only impact a single $p_k$, the entire sensitivity of the query will be $1/n$ (instead of $1$ like we previously thought).

---

This is to say that the mechanism the probabilities are generated from is quite important, because it's precisely understanding this mechanism that allows you to get tighter bounds on the sensitivity. Without this understanding you can only bound things by the worst-case behavior among all mechanisms with the same codomain, which you've noticed can be quite bad in general.