Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Improve noise multiplier finding #566

Open
kiddyboots216 opened this issue Feb 15, 2023 · 6 comments
Open

Improve noise multiplier finding #566

kiddyboots216 opened this issue Feb 15, 2023 · 6 comments
Assignees
Labels
enhancement New feature or request

Comments

@kiddyboots216
Copy link

🚀 Feature

Implement Brent's method to find the best value of sigma for a given epsilon.

Motivation

https://github.com/google/differential-privacy/blob/main/python/dp_accounting/mechanism_calibration.py uses a much better method to find the best value of sigma for a given epsilon. Opacus will frequently give you a much larger value of sigma than you need. For example for q=1, steps=60 it will give you 280 vs 240 for GDP. Similar for https://github.com/microsoft/prv_accountant/blob/main/prv_accountant/dpsgd.py

Pitch

Implement Brent's method or any other root-finding method to replace the current naive binary sesarch.

Alternatives

Considered doing this myself, tried for a while, and turns out I don't know how to write search algorithms. And it was quite slow.

@alexandresablayrolles alexandresablayrolles added the enhancement New feature or request label Feb 23, 2023
@alexandresablayrolles
Copy link
Contributor

Thanks for proposing this! One easy fix could be to change the termination condition to be on sigma rather than epsilon? (say, while sigma_high - sigma_low > 0.01)

@alexandresablayrolles alexandresablayrolles self-assigned this Feb 23, 2023
@kiddyboots216
Copy link
Author

I think that will generally take a bit too long to converge for smaller values of epsilon, vs improving the search method. Let me know if you want me to draft an initial PR.

@alexandresablayrolles
Copy link
Contributor

Do you have data points for other privacy parameters? I could not reproduce 280 vs 240 (I'm assuming it is 2.4 and 2.8? ), but my impression in general is that for usual privacy parameters the naive method gets you there.

If you want to draft a PR though you are welcome to, probably we can start with adding a keyword for the method to use (which defaults to "bissect" for now) to have multiple methods implemented.
@ffuuugor any thoughts?

@kiddyboots216
Copy link
Author

Hi, I just tried it again; eps=0.1, q=1, epochs=60, delta=1e-5, opacus produces sigma=280 but using the glws search (different search parameter and different scaling at each iteration) I get sigma=240. Let me know if you can reproduce this -I confirmed this with other people but maybe we're all on the wrong version.

I agree that for large values of epsilon any naive method will be fine, however specifically for research (where we would ideally like to stay in eps<1) opacus's search function is clearly producing larger values of sigma than the search function used in tf-privacy.

I'll list this as a TODO and aim to draft a PR sometime next week.

@ffuuugor
Copy link
Contributor

If you want to draft a PR though you are welcome to, probably we can start with adding a keyword for the method to use (which defaults to "bissect" for now) to have multiple methods implemented. @ffuuugor any thoughts?

Keyword works.
I personally a fan of using make_private and calling get_noise_multiplier on the client side, as it gives more flexibility. With that, it's easy to just add another method to accountants/utils.py in addition to get_noise_multiplier or even implement custom one on the client side

@kiddyboots216
Copy link
Author

In that case as a very initial solution I can just add a method to accountants/utils.py that calls get_noise_multiplier from microsoft/prv_accountant?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request
Projects
None yet
Development

No branches or pull requests

3 participants