Repository navigation
Question on monotonic queries #272
Description
Hi!
First, thanks for this amazing library! I use it heavily in my research, and it has been spotless! :)
A quick technicality: It is common knowledge (mentioned in the Algorithmic Foundations of Differential Privacy as well) that queries that are monotonic w.r.t to the neighbouring relationship enjoy a discount in sensitivity of 1/2. More precisely, in the add/remove neighbouring definition, when we add, we can only increase the output of our query; similarly, when we remove, we can only decrease the output of a query.
I assume this would also work nicely for PLDs, but I would like to know if there is support for this out of the box. I am not sure if it's enough to halve the sensitivity. Would any change to the mechanisms be required?
Activity
[-]Question on monothonic queries[/-][+]Question on monotonic queries[/+]hasenoehrl commentedon Sep 17, 2024
Hi,
thanks for reaching out. And for the great question.
Before getting into PLDs. I have to admit I am a bit puzzled by the notion of enjoying a discount in sensitivity of 1/2.
tudorcebere commentedon Sep 17, 2024
It is the second scenario, and my initial question was a bit confusing because I mentioned the add/remove relationship. The following paragraph clearly describes what I am after:
Page 41 here ``A function is monotonic..." up to Theorem 3.13 describes what I am going after.
Usually, if add/remote has sensitivity equal to s, replace has 2 * s.
As far as I understand, when the above happens (monotonicity constraint on the query), both neighbouring relations (add/remove and replace) enjoy the same sensitivity of 1. Typically, without this extra information, add/remove would've had a sensitivity of 1 and replaced the sensitivity of 2.
My question is whether it's possible to exploit this information via PLDs and what the correct way of doing that is.
pritkamath commentedon Sep 24, 2024
Hi.
What is the exact mechanism that you are interested in?
Is it the NoisyArgMax mechanism? Or generally noisy sum queries?
tudorcebere commentedon Sep 25, 2024
Hi @pritkamath,
I am interested in general noisy sum queries.
pritkamath commentedon Sep 25, 2024
Okay. In that case, you can simply consider the PLDs corresponding to the noise mechanisms with the correct sensitivity.
I'm not sure if this is related to the question you have in mind, but even though the PLDAccountant takes as input the neighboring relation, it does not really use it yet for Additive noise mechanisms supported (Laplace/Gaussian).
The
LaplaceDpEventandGaussianDpEventare defined in terms of only thenoise_multiplier, and the understanding is that it has to be scaled with the sensitivity before adding to the sum query result.So if you scale it with the correct sensitivity for the considered adjacency and problem setting, it should be fine. Please let us know if this answers your question or not.
Thanks!