Faster Privacy Accounting via Evolving Discretization

We introduce a new algorithm for numerical composition of privacy random variables, useful for computing the accurate privacy parameters for compositions of mechanisms. For the task of self-composing a broad class of mechanisms $K$ times, this algorithm achieves a running time \& memory usage of $\polylog(K)$ (e.g., this class includes the sub-sampled Gaussian mechanism, that appears in the analysis of DP-SGD). By comparison, recent work by Gopi et al. (NeurIPS 2021) has a running time of $\wtilde{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 / memory usage in the work of Gopi et al. from $\wtilde{O}(K^{1.5})$ to $\wtilde{O}(K)$.

• Machine Intelligence

• Algorithms and Theory