The Saddlepoint Accountant for Differential Privacy Accounting
Juan Gomez
Abstract:
When designing differentially private iterative algorithms, each query to the sensitive dataset necessarily leads to privacy loss. Algorithms which keep track of the privacy loss are known as “accounting” algorithms. How to optimally account for privacy in the limit of large number of queries is an open problem in differential privacy. In this work, we propose the Saddle Point Accountant (SPA). We provide rigorous performance guarantees by deriving upper and lower bounds for the privacy-accounting approximation error offered by the SPA. Numerical experiments applying the SPA to a differentially-private stochastic gradient descent algorithm demonstrate that SPA achieves comparable accuracy to state-of-the-art accounting methods (which scale like sqrt(k) for k queries) while scaling independent of the number of queries.