Question on monotonic queries

[tudorcebere]

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?

[hasenoehrl]

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.

• Do you mean that if you have a query that say counts users (which is monotonic) then the sensitivity is 1. But if you had a query summing over values of users, where the values can be +1 or -1, then the sensitivity would be 2?
• Or do you mean a discount compared to DP where the neighbouring notion is that of replacing one entry with another?

[tudorcebere]

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]

Hi.

What is the exact mechanism that you are interested in?
Is it the NoisyArgMax mechanism? Or generally noisy sum queries?

[tudorcebere]

Hi @pritkamath,

I am interested in general noisy sum queries.

[pritkamath]

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 LaplaceDpEvent and GaussianDpEvent are defined in terms of only the noise_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!