1
$\begingroup$

Two practical questions arise when releasing differentially private histograms/counts via addition of Laplace/Gaussian noise:

1) Is the result of noise addition truncated/rounded (since we know that the counts should correspond to natural numbers)?

2) What happens to bins with zero counts? Addition of noise to those (which should take place as per my understanding) might result to a negative result: should this be eventually truncated to zero?

$\endgroup$
1
$\begingroup$

This paper answers these questions: https://arxiv.org/pdf/1103.0825.pdf

In short, (1) Noisy counts can be rounded. Another option is to use the Geometric distribution to noise in the form of integers. Another option is to leave unrounded, and make inferences (estimate functions of the data) with the noisy, floating point values for each bin. (2) Can replace negatives with zeros, or leave as negative.

From Section 2.1:

Because the noise can be negative, M0 can contain negative entries. In many applications, it is not meaningful to have negative counts. However, we can adjust for this, e.g., by rounding negative values up to the smallest meaningful value, 0. Let M0 + denote the anonymized table obtained from M0 via this procedure. For small range queries or for point queries, using M0 + tends to be more accurate than M0 . However, since the noise is symmetric, retaining negative values is useful for large queries which touch many entries, since the noise cancels. More precisely, the sum of noise values is zero in expectation (but has non-trivial variance).

$\endgroup$
1
$\begingroup$

To complete maurice's answer:

  1. The post-processing property of differential privacy guarantees that you can apply any kind of data cleaning process to the results of a differentially private algorithm, and not break the differential privacy property. So you can round the noise, or use something like the staircase mechanism instead of the more classic Laplacian or Gaussian mechanism. If you use Laplace noise, you actually should round the results, to avoid floating-point attacks.

  2. There are three possible options. The easiest conceptually is to add noise to each bin, even if it has a zero count (then, you can do whatever post-processing you want). However, that's often not possible, especially if the dataset is sparse: there might be too many bins. In that case, you can either use the method mentioned in maurice's answer, which gives you pure $\varepsilon$-differential privacy, but it requires to have a bounded number of bins. Otherwise, you can simply add noise only to non-zero counts and threshold low counts, like what is explained in this blog post — this will give you $(\varepsilon,\delta)$-differential privacy, which is a bit worse, but typically acceptable in practice if $\delta$ is small enough.

$\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.