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?

Improve this question
$\endgroup$
5
  • $\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. ♦
    Commented Jun 22, 2015 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. ♦
    Commented Jun 22, 2015 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
    Commented Jun 23, 2015 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. ♦
    Commented Jun 23, 2015 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
    Commented May 15, 2019 at 5:33

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\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
    Commented Jun 23, 2015 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. ♦
    Commented Jun 23, 2015 at 21:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.