Assume we have an $n$-dimensional real-valued function $f$ whose $\ell_1$ sensitivity is equal to $GS(f) = 1$. We can also assume the sensitivity of each dimension is also $\Delta f = 1$.

For pure differential privacy, we have the Laplace Mechanism, whose magnitude is parametrized by the privacy level $\epsilon > 0$ and the $\ell_1$ sensitivity. If we were to add noise to each $n$ dimension by using sequential/basic-composition, we were going to need to scale the Laplace distribution with $\propto \Delta f / (\epsilon / n) = n / \epsilon$. However, since $GS(f) = 1$, we do not need to rely on basic proposition, rather, we can immediately add noise with magnitude $\propto GS(f) /\epsilon = 1 / \epsilon$. In summary, when we have $\Delta f = GS(f)$, we can sample $n$ iid noise from Laplace distribution with $\propto \Delta f/\epsilon$, and the $n$-dimensional result is still $\epsilon$-DP (privacy does not decay).

I am wondering whether we can extend this to approximate differential privacy; not for a specific noise mechanism like the Gaussian, but in general.

Question: Assume there exists a mechanism $\mathcal{M}$ that satisfies $(\epsilon, \delta)$-DP for any single-dimensional query with sensitivity $\Delta f = 1$. If I use this for each $n$ component of $f$, do I still have $(\epsilon, \delta)$-DP? Again, if we had $GS(f) = n \cdot \Delta f$, then we would have decayed to $(n\epsilon, n\delta)$-DP, but now I am wondering if when $GS(f) = \Delta f$ we can claim a similar result as in the Laplace noise case explained above.


1 Answer 1


The question might not be well-defined: what does this mean for a mechanism to "satisfy (ε,δ)-DP for any single-dimensional query with sensitivity Δ=1"? What constraints do you want this mechanism to have?

If the mechanism can do anything, then here is a counterexample with pure DP. Consider the mechanism $M$ that rounds up its (real-valued) input then applies Laplace noise of scale 1. Then, for any single-dimensional query with sensitivity $1$, applying $M$ to the result will give ε-DP with ε=1. But now, consider a function $f$ that outputs [0, ..., 0] on dataset $D_1$ and [0.1, ..., 0.1] (with $n=10$) on $D_2$. That function has global sensitivity 1, but applying $M$ to each component gives ε=10, not ε=1.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.