differentially private release of histograms (non-negative valued queries)

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?

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).

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.