add pointer to paper documenting the epsilon computation when it is available

[srxzr]

Hi all,

The code seems to implement Abadi et al.'s work. However, the way you compute the overall epsilon does not follow the Abadi's paper. I was wondering if you can give me some references about how you calculated the epsilon.

Thanks,

[npapernot]

@ilyamironov would be the best person to answer this question, but my guess is that the RDP paper would be a good starting points: https://arxiv.org/abs/1702.07476.

[ilyamironov]

Indeed, the algorithm that we use to maintain the RDP accountant is different from the Abadi et al. paper. We are working on a paper that fully documents the procedure. Once it's available, we'll update the README file. (For the record, the results of doing privacy analysis via the moments/RDP accountant must be identical. The main difference is in numerical stability for a wide range of parameters.)

[ycpei]

@srxzr The epsilon is computed using the inversion of Item 2 of Theorem 2 in Abadi et. al., and it computes the smallest such epsilon given a list of lambdas (alpha or orders in the code).

The rdp parameter is the log moment generating function (alpha in Abadi et. al.), computed using _compute_log_a_int or _compute_log_a_frac depending on whether lambda is an integer or not.

_compute_log_a_int uses the binomial expansion to compute the log moment generating function of log((1 - q) mu_0(X) + q mu_1(X)) - log (mu_0(X)) where mu_0 is the density of N(0, sigma^2) and mu_1 is the density of N(1, sigma^2), and X is distributed according to (1 - q) mu_0 + q mu_1.

I have yet to decode _compute_log_a_frac.

Hope this helps. Let me know if you have further questions.

[srxzr]

@ycpei Thank you for your response. Just to make sure Abadi et. al. uses random sampling (instead of shuffling) but the implementations here use shuffling. I was wondering if you use any theorem to compensate for the difference.

Also, I implemented a random sampler with replacement and my results were a bit lower compare to the shuffling.

[ilyamironov]

@srxzr Re shuffling vs sampling, it's a correct observation. Our analysis assumes that the minibatches are iid samples, while in practice they are most likely fixed-sized disjoint (within a single epoch) samples. The best reference that compares various policies of sampling is this one: https://arxiv.org/pdf/1807.01647.pdf

[schien1729]

Paper posted on arXiv: https://arxiv.org/pdf/1908.10530.pdf