2
$\begingroup$

I am wondering why (not how) we relax $\epsilon$-differential privacy to $(\epsilon, \delta)$-differential privacy. Is the main motivation to reduce the variance of the noise added to the query with a slight sacrifice from the strength of privacy?

$\endgroup$
2
  • 3
    $\begingroup$ Have you read this answer, crypto.stackexchange.com/a/61200/82720. I think there is trade-off between epsilon and delta. $\endgroup$
    – Cloud Cho
    Jul 31, 2020 at 22:39
  • $\begingroup$ @CloudCho thanks! more than the answer, the comments in the link provided addresses to my question. $\endgroup$ Aug 1, 2020 at 0:36

1 Answer 1

2
$\begingroup$

I help implement and ship anonymization strategies based on differential privacy in a large tech company. In my experience, the $\delta$ is mainly used for two reasons.

  • Partition selection: when computing histograms on an unbounded space, you can threshold the results (or do smarter things) and, at the cost of a non-zero $\delta$, avoid having to specify the full list of partitions in advance>.
  • Gaussian noise: since Gaussian is based on the $L_2$ sensitivity, it is very convenient to use when adding noise to a lot of metrics at once; if a single user can influence $k$ metrics, the noise needs to be scaled by $\sqrt{k}$ instead of $k$ with Laplace noise$^1$. But Gaussian noise doesn't give you pure $\varepsilon$-DP, you have to have a non-zero $\delta$.

Gaussian noise is particularly used for machine learning use cases. In such contexts, you also often want to use results on amplification by sampling, which also require a non-zero $\delta$.

$\endgroup$

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.