Faster Privacy Accounting via Evolving Discretization

Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi
Proceedings of the 39th International Conference on Machine Learning, PMLR 162:7470-7483, 2022.

Abstract

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 a mechanism, 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 ˜O(√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 ˜O(k1.5) to \wtildeO(k).

Cite this Paper

BibTeX
@InProceedings{pmlr-v162-ghazi22a, title = {Faster Privacy Accounting via Evolving Discretization}, author = {Ghazi, Badih and Kamath, Pritish and Kumar, Ravi and Manurangsi, Pasin}, booktitle = {Proceedings of the 39th International Conference on Machine Learning}, pages = {7470--7483}, year = {2022}, editor = {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan}, volume = {162}, series = {Proceedings of Machine Learning Research}, month = {17--23 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v162/ghazi22a/ghazi22a.pdf}, url = {https://proceedings.mlr.press/v162/ghazi22a.html}, abstract = {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 a mechanism, 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)$.} }
Endnote
%0 Conference Paper %T Faster Privacy Accounting via Evolving Discretization %A Badih Ghazi %A Pritish Kamath %A Ravi Kumar %A Pasin Manurangsi %B Proceedings of the 39th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2022 %E Kamalika Chaudhuri %E Stefanie Jegelka %E Le Song %E Csaba Szepesvari %E Gang Niu %E Sivan Sabato %F pmlr-v162-ghazi22a %I PMLR %P 7470--7483 %U https://proceedings.mlr.press/v162/ghazi22a.html %V 162 %X 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 a mechanism, 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)$.
APA
Ghazi, B., Kamath, P., Kumar, R. & Manurangsi, P.. (2022). Faster Privacy Accounting via Evolving Discretization. Proceedings of the 39th International Conference on Machine Learning, in Proceedings of Machine Learning Research 162:7470-7483 Available from https://proceedings.mlr.press/v162/ghazi22a.html.

Related Material