How Private is DP-SGD?
Lynn Chua Badih Ghazi Pritish Kamath Ravi Kumar Pasin Manurangsi Amer Sinha Chiyuan Zhang
We demonstrate a substantial gap between the privacy guarantees of the
Adaptive Batch Linear Queries (ABLQ) mechanism under different types of batch
sampling: (i) Shuffling, and (ii) Poisson subsampling; the typical analysis of
Differentially Private Stochastic Gradient Descent (DP-SGD) follows by
interpreting it as a post-processing of ABLQ. While shuffling based DP-SGD is
more commonly used in practical implementations, it is neither analytically nor
numerically amenable to easy privacy analysis. On the other hand, Poisson
subsampling based DP-SGD is challenging to scalably implement, but has a
well-understood privacy analysis, with multiple open-source numerically tight
privacy accountants available. This has led to a common practice of using
shuffling based DP-SGD in practice, but using the privacy analysis for the
corresponding Poisson subsampling version. Our result shows that there can be a
substantial gap between the privacy analysis when using the two types of batch
sampling, and thus advises caution in reporting privacy parameters for DP-SGD.