0
$\begingroup$

Why do differential-privacy people care whether or not the noise function saturates the lower bound of Shannon entropy?

For example : Laplace distribution that is used to model the noise function happens to saturate the lower bound of Shannon entropy under epsilon differential privacy constraints. See Theorem 8 in Yu Wang, Zhenqi Huang, Sayan Mitra and Geir E. Dullerud, Entropy-minimizing Mechanism for Differential Privacy of Discrete-time Linear Feedback Systems for an example.

But what is the significance of this saturation?

$\endgroup$
  • $\begingroup$ We expect you to do a significant amount of research and/or self-study before asking. What research/self-study have you done? What possible explanations have you considered? What are your thoughts? You seem to have concluded that differential-privacy people care whether or not (...) -- what's the basis for this conclusion? Please flesh out your question. Generally speaking, a one-sentence question is often a red flag indicating that you should take another look at your question to see if you've done as much research as you could have and provided enough context. $\endgroup$ – D.W. Jun 22 '15 at 22:47
  • $\begingroup$ You've been given similar advice before: 1, 2, 3. I see you've already got quite a bit of experience on this site, but you might want to spend a little time at our help center, e.g., cs.stackexchange.com/help/how-to-ask, to refresh your knowledge of advice for how to ask good questions and use this site effectively. $\endgroup$ – D.W. Jun 22 '15 at 22:51
  • $\begingroup$ I have added some more details. (I didn't give my specific details because I felt that this is a generic question and not tied to the examples I have seen) $\endgroup$ – user6818 Jun 23 '15 at 16:45
  • $\begingroup$ Thanks for the citation. That helps. However, I couldn't find a Lemma 8 in that paper. Do you mean Theorem 8? $\endgroup$ – D.W. Jun 23 '15 at 17:57
  • $\begingroup$ FYI The link to the above paper is dead, but it can be found here: publish.illinois.edu/science-of-security-lablet/files/2014/06/… $\endgroup$ – Racing Tadpole May 15 at 5:33
1
$\begingroup$

In general, if you're not sure about the significance of mathematical results in a published paper, often a good first place to look is the paper's introduction and/or conclusion. The authors often try to provide some explanation why you should care about their results in the introduction and conclusion.

In this case, the following two quotes from the introduction of the paper you cited provide a pretty clear explanation for why the authors care:

we first study an $\epsilon$-differentially private noise-adding mechanism for one-shot queries that provides the best output accuracy, which is measured by the Shannon entropy. [...]

In Section III, we prove that, for a one-shot $n$-dimensional input, there is a lower bound $n + n \ln(2\epsilon)$ on the entropy of the output for an $\epsilon$-differentially private noise-adding mechanism, and the lower bound is achieved by Laplacian noise with parameter $\epsilon$.

In other words, the Shannon entropy measures the accuracy of the output after adding the noise (lower is better); Theorem 8 proves that Laplace noise achieves the lowest possible Shannon entropy, in a particular situation; therefore, we can conclude that Laplace noise is optimal in the sense that it achieves the highest possible output accuracy, in that situation.

$\endgroup$
  • $\begingroup$ I saw that but I would like to know from where does this come from : "Shannon entropy measures the accuracy of the output after adding the noise " ? The whole point of the noise is to create an obfuscation then why would you want it to be more accurate? $\endgroup$ – user6818 Jun 23 '15 at 19:21
  • $\begingroup$ @user6818, that's a different question, and should be asked separately. I think you need to start by reading about differential privacy and understand what the purpose is. The purpose is not just to avoid violating privacy (that could be achieved by outputting nothing); it's also to answer a query, and here we are talking about the accuracy of our estimate of the answer to the query. But again, it's a different question, so it doesn't belong here -- if after serious study you still don't understand, ask a new question. $\endgroup$ – D.W. Jun 23 '15 at 21:26

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.