We introduce a new algorithm for numerical composition of privacy random
variables, useful for computing the accurate differential privacy parameters
for composition of mechanisms. Our algorithm achieves a running time and memory
usage of $\mathrm{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. 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 their running time and memory
usage from $\widetilde{O}(k^{1.5})$ to $\widetilde{O}(k)$.

本论文介绍了一个新算法，用于计算隐私随机变量的数字组成，可用于计算机制的组合的准确差分隐私参数。该算法可以在多项式对数 (k) 的时间和内存使用情况下自我组合机制 k 次。该方法不仅适用于子采样高斯机制等广泛机制的分析，还可扩展至组合同类别别不同机制的情况，并改进了运行时间和内存使用率。