Calculating differentially private average of a dataset

I was looking into Google's DP library and its implementation of bounded DP-average. The library implemented DP-average following the following algorithm presented in Li et al. (2016):

Proposition 2.22 Algorithm 2.3 satisfies ϵ-DP. [The] proof is quite long and tedious. We include [it] because to our knowledge this algorithm has not been presented in the literature before.

Algorithm 2.3: Noisy average clamping-down

\begin{align*} & \textbf{Input: } D\text{: one-dimensional dataset}, \epsilon\text{: privacy parameter},\left[a_\text{min},a_\text{max}\right]\text{: data range} \\ & S \leftarrow D.Sum() \\ & C \leftarrow D.Count() \\ & \textbf{if } C = 0 \textbf{ then} \\ & \ \ \ \ \textbf{return } a_\text{min} \text{ with prob }\frac{1}{2}\text{exp}\left(-\epsilon/2\right) \text{, and a value sampled uniformly from }\left[a_\text{min},a_\text{max}\right]\text{ with prob }1-\frac{1}{2}\text{exp}\left(-\epsilon/2\right)\\ & \textbf{end if}\\ & A \leftarrow \left(\frac{S+\text{Lap}\left(\left(a_\text{max}-a_\text{min}\right)/\epsilon\right)}{C}\right) \\ & \textbf{if } A < a_\text{min} \textbf{ then} \\ & \ \ \ \ \textbf{return } a_\text{min} \\ & \textbf{else if } A > a_\text{max} \textbf{ then} \\ & \ \ \ \ \textbf{return } a_\text{max} \\ & \textbf{else } \\ & \ \ \ \ \textbf{return } A \\ & \textbf{endif} \end{align*}

This calculates the DP-average from DP-Sum and True-Count. My question is: is it is possible to improve it by adding noise to the true mean?

For instance, Let's assume there are $$N$$ sets and each set can have 0 to 100 elements in it. Then the sensitivity of the DP-average should be $$100/N$$. On the other hand, the sensitivity of the sum-mechanism is 100. Instead of using the sum-mechanism, we could add Laplace noise to the true average as follows:

DP-average = True average + $$\text{Lap}\left(100/\left(N\cdot\epsilon\right)\right)$$

Wouldn't this add less noise to the DP-average compared to Algorithm 2.3, thus allowing for a smaller $$\epsilon$$?

• Give a link or full reference to the document you mention May 26 '21 at 22:16

Now, to answer your question about adding noise directly: when building DP algorithms, you are only allowed to make decisions based on differentially private data. Even something as simple as "what is the scale of the noise we are adding" can actually leak more information than expected. In your question, $$N$$ is a private quantity, since it can go up or down by one if a user is added or removed to the dataset. This means that you can't use it as an argument to the noise without adding noise to it first, to make it differentially private as well (and count it towards the privacy budget).