The Saddle-Point Accountant for Differential Privacy
This work provides a faster method for privacy accounting in differential privacy, which is crucial for practitioners in machine learning and data analysis, though it appears incremental as it builds on existing numerical techniques.
The authors tackled the problem of accurately and efficiently computing privacy guarantees for composed differential privacy mechanisms by introducing the saddle-point accountant (SPA), which uses large-deviation methods and central limit theorems to achieve comparable accuracy to state-of-the-art methods with faster runtime, as shown in numerical experiments.
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 crux of SPA is a combination of large-deviation methods with central limit theorems, which we derive via exponentially tilting the privacy loss random variables corresponding to the DP mechanisms. One key advantage of SPA is that it 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 a faster runtime.