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

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.