Approximate differential privacy: avoiding composition in vector-queries

Question

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.

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.