论文标题
通过不断发展的离散化更快的隐私会计
Faster Privacy Accounting via Evolving Discretization
论文作者
论文摘要
我们引入了一种用于隐私随机变量数值组成的新算法，可用于计算机制组成的准确差分隐私参数。我们的算法实现了$ \ mathrm {polylog}（k）$的运行时间和内存使用量，用于从广泛的机制（$ k $ times）中进行自我组合的任务；例如，该类别包括亚采样的高斯机制，该机制出现在差异私有随机梯度下降的分析中。相比之下，Gopi等人的最新工作。 （Neurips 2021）在同一任务中获得了$ \ widetilde {o}（\ sqrt {k}）$的运行时间。我们的方法扩展到在同一类中构成$ k $不同机制的情况，从$ \ widetilde {o}（k^{1.5}）$转化为$ \ wideTilde {o} $ \ widetilde {o}（k）$。
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)$.
