Sharp Composition Bounds for Gaussian Differential Privacy via Edgeworth Expansion
This work addresses a fundamental issue in differential privacy for datasets analyzed by multiple algorithms, offering incremental improvements in privacy bounds.
The paper tackles the problem of privacy degradation under sequential composition in differential privacy by introducing sharp privacy bounds using Edgeworth expansion, achieving improved tightness compared to existing methods based on the central limit theorem, with computational efficiency for any number of compositions.
Datasets containing sensitive information are often sequentially analyzed by many algorithms. This raises a fundamental question in differential privacy regarding how the overall privacy bound degrades under composition. To address this question, we introduce a family of analytical and sharp privacy bounds under composition using the Edgeworth expansion in the framework of the recently proposed f-differential privacy. In contrast to the existing composition theorems using the central limit theorem, our new privacy bounds under composition gain improved tightness by leveraging the refined approximation accuracy of the Edgeworth expansion. Our approach is easy to implement and computationally efficient for any number of compositions. The superiority of these new bounds is confirmed by an asymptotic error analysis and an application to quantifying the overall privacy guarantees of noisy stochastic gradient descent used in training private deep neural networks.