Vulnerability gap in DP-SGD privacy analysis
Most practical implementations of DP-SGD shuffle the training examples and divide them into fixed-size mini-batches, but directly analyzing the privacy of this process is challenging. Since the mini-batches have a fixed size, if we know that a certain example is in a mini-batch, then other examples have a smaller probability of being in the same mini-batch. Thus, it becomes possible for training examples to leak information about each other.
Consequently, it has become common practice to use privacy analyses that assume that the batches were generated using Poisson subsampling, wherein each example is included in each mini-batch independently with some probability. This allows for viewing the training process as a series of independent steps, making it easier to analyze the overall privacy cost using composition theorems, a widely used methodology in various open-source privacy accounting methods, including those developed by Google and Microsoft. But a natural question arises: is the aforementioned assumption a reasonable one?
The guarantee of differential privacy is quantified in terms of two parameters (ε, δ), which together represent the “privacy cost” of the algorithm. The smaller ε and δ are, the more private the algorithm is. We establish a technique to prove lower bounds on the privacy cost when using shuffling, which means that the algorithm is no more private (that is, the ε, δ values are no smaller) than the bounds that we compute.
In the figure below, we plot the trade-off between the privacy parameter ε and the scale σ of noise applied in DP-SGD, for a fixed number of steps of training (10,000 in this case) and the parameter δ (10-6 in this case). The curve ε𝒟 corresponds to creating the batches without any shuffling or sampling, and the curve ε𝒫 corresponds to DP-SGD with batches using Poisson subsampling. The curve ε𝒮 is obtained using our lower bound technique, showing that for small σ, the actual privacy cost of using DP-SGD with shuffling (orange line, below) can be significantly higher than that of Poisson subsampling (green line).