1
$\begingroup$

It is well-known that to make the result of a $\mathbb{R}^d$-valued query $(\varepsilon,\delta)$-differentially private, you can add noise to it. If you add Laplace noise, you need to scale the noise by the $L_1$-sensitivity of the query; if you add Gaussian noise, you need to scale it by the $L_2$-sensitivity instead.

Are there noise functions that scale with, say, $L_3$-sensitivity, or any other $L_p$-sensitivity with $p>2$? If not, how to formalize and prove this impossibility result?

$\endgroup$
3
$\begingroup$

You can measure your sensitivity in an arbitrary norm. The exponential mechanism, that samples from the distribution proportional to $\exp(-\epsilon |z-f(x)|_p / 2)$ will give pure DP. This is more general, and the K-norm mechanism will allow you handle sensitivity measured in norms other than some p-norm. For pure DP, these p-norm mechanisms are optimal. In particular, when sensitivity is measured in the $\ell_2$ norm, the optimal mechanism adds noise from the Gamma distribution.

How then does the Gaussian noise mechanism do better? It gives you $(\epsilon, \delta)$-DP instead of pure DP. It is natural to ask what the optimal approximate DP mechanism is for other sensitivity measures. It turns out that for approximate DP, the right Gaussian mechanism is always optimal. You just convert your $\ell_p$ sensitivity bound into an $\ell_2$ sensitivity bound (by finding the smallest $\ell_2$ ball that contains your $\ell_p$ ball) and add Gaussian noise based on that. Here again, there are analogous results for sensitivity being measured in non-p-norms.

Some caveats are in order. Optimal above is for your error being measured in the Euclidean distance. Some of the results are optimal only up to logarithmic factors. When you care about error in other norms (say $\ell_\infty$), there can be other more interesting mechanisms.

References: The upper bounds for $\ell_p$ balls are straightforward. The lower bounds are in https://arxiv.org/abs/0907.3754, and https://arxiv.org/abs/1212.0297. Simpler lower bounds for CDP/RDP are in https://arxiv.org/abs/1911.08339.

$\endgroup$
2
  • $\begingroup$ Thanks for the comprehensive answer! If I understand correctly, these optimality results also mean that if a single user can influence at most $k$ dimensions in the output, with per-coordinate sensitivity $1$, then the noise we need to add to each coordinate will be proportional to $\sqrt(k)$, so with the $L_2$-sensitivity — which was what I was trying to figure out, but I realize now that the question wasn't ideally worded. $\endgroup$
    – Ted
    Sep 26 '20 at 9:01
  • 1
    $\begingroup$ That's correct. the $\sqrt{k}$-scale Gaussian mechanism is the optimal mechanism, at least without additional assumptions. $\endgroup$
    – Kunal
    Sep 27 '20 at 14:15
1
$\begingroup$

What you are looking for seems like the K-norm mechanism by Hardt and Talwar (2009). In a recent paper, Awan and Slavković formulate it in a way that directly answers your question in a generic way (see Proposition 2.8): Releasing with an additive noise with the density function $$f(x) = \frac{\exp(−\frac{\varepsilon}{\Delta}‖x‖_p)}{\Gamma(m+1) \lambda (\frac{\Delta}{\varepsilon}p))},$$ where $\Delta$ is any upper bound on the sensitivity of the query in the $L_p$ norm, will satisfy $\varepsilon$-DP.

$\endgroup$
1
  • $\begingroup$ Ah this looks promising, thanks! However, I'm not seeing why the error of this distribution is proportional to $||x||_p$, am I missing something obvious? It also looks like in the papers linked, $K$ is not a number, but a "norm ball", so I'm not sure it's possible to simply replace it with any integer $p$ (e.g. the $\lambda(\frac{\Delta}{p}/\varepsilon)$ term isn't well-typed). $\endgroup$
    – Ted
    Sep 25 '20 at 20:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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