Improve noise multiplier finding

[kiddyboots216]

🚀 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]

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)

[kiddyboots216]

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]

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]

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]

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]

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?