Differential privacy guarantees of Gaussian noise, when each coordinate has different sensitivity

Question

Suppose you have a function $f$ that takes a dataset $D$ as input and returns an output in $\mathbb{R}^d$.

If this function has $L^2$-sensitivity $\Delta$, then the analytical Gaussian mechanism (Theorem 8 in this paper) says that if you add Gaussian noise of variance $\sigma^2$ to each coordinate of result, with: $$ \Phi\left(\frac{\Delta}{2\sigma}-\frac{\epsilon\sigma}{\Delta}\right)-e^\varepsilon\Phi\left(-\frac{\Delta}{2\sigma}-\frac{\epsilon\sigma}{\Delta}\right) \le \delta$$ where $\Phi$ is the Gaussian CDF, then you obtain an $(\varepsilon,\delta)$-differentially private mechanism.

Now, suppose that there is a finer way of describing the sensitivity of $f$. Rather than only knowing a bound on the maximum $L^2$ norm of $f(D_1)-f(D_2)$ for neighboring $D_1$ and $D_2$, we have a per-coordinate sensitivity bound: we know that the first coordinate of $f(D_1)-f(D_2)$ is always below $\Delta_1$ (in absolute value), the second below $\Delta_2$, etc., and $\Delta_d$ bounds the sensitivity along the $d$-th coordinate.

In this case, intuitively, adding the same magnitude of noise along each coordinate doesn't seem like the best solution. For example, if $\Delta_1$ is much smaller than the other per-coordinate sensitivities, then we will likely add too much noise to the first coordinate for it to be useful. Thus my question: is there an equivalent analytical result where we can add Gaussian noise proportional to each coordinate sensitivity?

I know I could be using Laplace noise instead, but then the per-coordinate noise magnitude grows in $O(d)$ instead of $O(\sqrt{d})$ (unless $d$ is sufficiently big to use the Advanced Composition Theorem, but that only makes a big difference for large values of $d$), so I'm interested in a Gaussian noise formula hoping that it will work well for not-too-high values of $d$ (say, $5<d<50$).

Answer 1

I haven't read your full question, but the answer to:

Is there an equivalent analytical result where we can add Gaussian noise proportional to each coordinate sensitivity?

and (implicitly)

Can the noise scale better than $O(d)$ for $d$-dimensional output?

Then the answer is yes. The following should be able to be easily adapated for essentially any mechanism $\mathcal{M}$, but I'll focus on the case that the mechanism is adding independent mean-zero Gaussian noise, as this is your case. Moreover, this argument should work provided that the sensitivity is "homogenous" in a certain sense --- in particular, any sensitivity defined with respect to a norm should work, so any $\ell_p$ sensitivity (for $p\geq 1$ I think).

Throughout this, I will write $\vec{\Delta} = (\Delta_1,\dots, \Delta_d)$ to be a vector of the per-coordinate sensitivities of $f(x)$. I will write the $i$th coordinate of $f(x)$ as $f(x)_i$. I will also write $\mathsf{diag}(\vec{\Delta})$ to denote the $d\times d$ diagonal matrix with $(i, i)$ entry $\Delta_i$.

The idea here is to transform $f(x)$ as follows:

$$g(x) = \mathsf{diag}(\vec{\Delta})^{-1}f(x)$$

If you compute the $\ell_2$sensitivity of $g(x)$, you get that:

\begin{align*} \Delta_2(g) &= \max_{x, y} \lVert g(x) - g(y)\rVert\\ &= \max_{x, y}\lVert \mathsf{diag}(\vec{\Delta})^{-1} (f(x)- f(y))\rVert\\ &= \max_{x, y}\sqrt{\sum_{i\in[d]} \left(\frac{|f(x)_i-f(y)_i|}{\Delta_i}\right)^2}\\ &\leq \sqrt{\sum_{i\in[d]} \left(\max_{x, y}\frac{|f(x)_i-f(y)_i|}{\Delta_i}\right)^2}\\ &\leq \sqrt{\sum_{i\in[d]} \left(\frac{\Delta_i}{\Delta_i}\right)^2}\\ & = \sqrt{d} \end{align*} So, we have that $\Delta_2(g)\leq \sqrt{d}$. I'm pretty sure this should extend in a straightforward way to give you that $\Delta_p(g) \leq \sqrt[p]{d}$, which would explain why you can only get the upper bound of $O(d)$ for the $\ell_1$ sensitivity.

Anyway, now we can just apply (essentially any) differentially private mechanism to $g(x)$. In particular, the Gaussian mechanism states that:

$$h(x) = g(x) + \mathcal{N}^d(0, 2\ln(1.25/\delta)n/\epsilon^2)$$

Is $(\epsilon, \delta)$ differentially private. For what follows, recall that differential privacy is closed under post-processing, so "we're done" on the topic of privacy.

$h(x)$ has the undesirable property that $\mathbb{E}[h(x)] = \mathbb{E}[g(x)] + 0 = \mathbb{E}[\mathsf{diag}(\vec{\Delta})^{-1}f(x)] \neq f(x)$, so we have (potentially significantly) biased the output of your function. Fortunately, we can fix this by having our output be $\mathsf{diag}(\vec{\Delta})h(x)$ (which you can quickly check leads to an unbiased output). In total, the mechanism which outputs:

$$f(x) + \mathcal{N}\left(0, \frac{2\ln(1.25/\delta)n}{\epsilon^2}\mathsf{diag}(\vec{\Delta})^2\right)$$

Is therefore $(\epsilon, \delta)$ differentially private. This is what you would expect --- if you have sensitivities which are different in each coordinate, then instead of "spherical" Gaussian noise, one should use ellipsoidal Gaussian noise "matched" to each coordinate, which is precisely what the mechanism does when you write it all out. Note that the gaussian noise is no longer the product of $d$ i.i.d. gaussians (but still has quite simple covariance structure).