Fast Composition of Differential Privacy via the Saddle Point Accountant
Juan Felipe Gomez
Abstract:
We introduce a new differential privacy (DP) accountant called the saddle-point accountant (SPA). SPA approximates privacy guarantees for the composition of DP mechanisms in an accurate and fast manner. Our approach is inspired by the saddle point method—a ubiquitous numerical technique in statistics. We prove rigorous performance guarantees by deriving upper and lower bounds for the approximation error offered by SPA. The two key advantages of SPA are that it gives relative error guarantees for DP parameters and runs in constant time for the n-fold composition of a privacy mechanism. Numerical experiments demonstrate that SPA achieves comparable accuracy to state-of-the-art accounting methods with better runtime guarantees.