Timezone: »

 
Spotlight
Faster Privacy Accounting via Evolving Discretization
Badih Ghazi · Pritish Kamath · Ravi Kumar · Pasin Manurangsi

Wed Jul 20 02:25 PM -- 02:30 PM (PDT) @ Room 307
in SA: Privacy-preserving Statistics and Machine Learning »
We introduce a new algorithm for numerical composition of privacy random variables, useful for computing the accurate differential privacy parameters for compositions of mechanisms.Our algorithm achieves a running time and memory usage of $polylog(k)$ for the task of self-composing amechanism, from a broad class of mechanisms, $k$ times; this class, e.g., includes the sub-sampled Gaussian mechanism, that appears in the analysis of differentially private stochastic gradient descent (DP-SGD).By comparison, recent work by Gopi et al. (NeurIPS 2021) has obtained a running time of $\widetilde{O}(\sqrt{k})$ for the same task.Our approach extends to the case of composing $k$ different mechanisms in the same class, improving upon the running time and memory usage in their work from $\widetilde{O}(k^{1.5})$ to $\wtilde{O}(k)$.
Keywords: SA: Privacy-preserving Statistics and Machine Learning

Author Information

Badih Ghazi (Google)
Pritish Kamath (Google Research)
Ravi Kumar (Google)
Pasin Manurangsi (Google Research)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors