Sharp Composition Bounds for Gaussian Differential Privacy via Edgeworth Expansion

Area of Science:

• Computer Science
• Cryptography
• Machine Learning

Background:

• Sequential analysis of sensitive datasets by multiple algorithms raises concerns about cumulative privacy loss.
• Existing composition theorems in differential privacy often provide loose bounds, necessitating tighter analytical methods.

Purpose of the Study:

• To introduce novel, analytical, and tight privacy bounds under composition for sequential data analysis.
• To improve the accuracy of privacy bound degradation calculations in differential privacy frameworks.

Main Methods:

• Utilizing the Edgeworth expansion within the framework of f-differential privacy.
• Developing a family of analytical privacy bounds that offer improved tightness over existing methods.

Main Results:

• The proposed privacy bounds demonstrate enhanced tightness compared to those derived from the central limit theorem.
• The approach is computationally efficient and easy to implement for any number of compositions.

Conclusions:

• The Edgeworth expansion provides a more accurate approximation for composition theorems in differential privacy.
• The new bounds offer superior quantification of privacy guarantees, particularly for applications like private deep neural network training using noisy stochastic gradient descent.