Timezone: »

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
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)$.

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