Timezone: »

 
Poster
The Saddle-Point Method in Differential Privacy
Wael Alghamdi · Felipe Gomez · Shahab Asoodeh · Flavio Calmon · Oliver Kosut · Lalitha Sankar

Tue Jul 25 02:00 PM -- 04:30 PM (PDT) @ Exhibit Hall 1 #803
in Poster Session 1 »

We characterize the differential privacy guarantees of privacy mechanisms in the large-composition regime, i.e., when a privacy mechanism is sequentially applied a large number of times to sensitive data. Via exponentially tilting the privacy loss random variable, we derive a new formula for the privacy curve expressing it as a contour integral over an integration path that runs parallel to the imaginary axis with a free real-axis intercept. Then, using the method of steepest descent from mathematical physics, we demonstrate that the choice of saddle-point as the real-axis intercept yields closed-form accurate approximations of the desired contour integral. This procedure---dubbed the saddle-point accountant (SPA)---yields a constant-time accurate approximation of the privacy curve. Theoretically, our results can be viewed as a refinement of both Gaussian Differential Privacy and the moments accountant method found in Rényi Differential Privacy. In practice, we demonstrate through numerical experiments that the SPA provides a precise approximation of privacy guarantees competitive with purely numerical-based methods (such as FFT-based accountants), while enjoying closed-form mathematical expressions.

[ PDF] 

Author Information

Wael Alghamdi (Harvard University)
Felipe Gomez (Harvard)
Shahab Asoodeh (Harvard)
Flavio Calmon (Harvard University)
Oliver Kosut (Arizona State University)
Lalitha Sankar (Arizona State University)

More from the Same Authors