Why isn't SampledWithoutReplacementDpEvent used instead of PoissonSampledDpEvent for DP-SGD epsilon calculation?

[BjarnePfitzner]

Why isn't SampledWithoutReplacementDpEvent used instead of PoissonSampledDpEvent for DP-SGD epsilon calculation?

[galenmandrew]

First of all, it is important to note that neither PoissonSampledDpEvent nor SampledWithoutReplacementDpEvent accurately describe the training procedure of looping over the (perhaps shuffled) dataset and forming batches. SampledWithoutReplacementDpEvent would be correct if you were sampling fixed-sized batches uniformly at random and independently across rounds. There is no known tight analysis of the shuffle and iterate style training that is most commonly used.

So the choice between PoissonSampledDpEvent nor SampledWithoutReplacementDpEvent comes down to other considerations. The main argument in favor of PoissonSampledDpEvent is that the privacy guarantee you derive from it is under the "add/remove-one" notion of dataset adjacency. SampledWithoutReplacementDpEvent gives you a guarantee under "replace-one" adjacency, which it is believed produces epsilon values about a factor of two larger.

For a formally correct guarantee under "add/remove-one" adjacency, in the case where each example is visited at most once, you could analyze a single (not composed) application of the unamplified Gaussian mechanism, corresponding to the scenario where the adversary knows in which round the targeted example appears. However, this is probably a pessimistic estimate of epsilon, since it does not take into account shuffling.

For a better estimate of the true privacy loss, you could apply empirical privacy estimation techniques.

[BjarnePfitzner]

Thank you for your detailed explanation! That clarifies it :)