Abstract
Datasets containing sensitive information are often sequentially analyzed bymany algorithms. This raises a fundamental question in differential privacyregarding how the overall privacy bound degrades under composition. To addressthis question, we introduce a family of analytical and sharp privacy boundsunder composition using the Edgeworth expansion in the framework of therecently proposed f-differential privacy. In contrast to the existingcomposition theorems using the central limit theorem, our new privacy boundsunder composition gain improved tightness by leveraging the refinedapproximation accuracy of the Edgeworth expansion. Our approach is easy toimplement and computationally efficient for any number of compositions. Thesuperiority of these new bounds is confirmed by an asymptotic error analysisand an application to quantifying the overall privacy guarantees of noisystochastic gradient descent used in training private deep neural networks.