The recently proposed Fast Fourier Transform (FFT)-based accountant for evaluating $(\varepsilon,\delta)$-differential privacy guarantees using the privacy loss distribution formalism has been shown to give tighter bounds than commonly used methods such as R\'enyi accountants when applied to homogeneous compositions, i.e., to compositions of identical mechanisms. In this paper, we extend this approach to heterogeneous compositions. We carry out a full error analysis that allows choosing the parameters of the algorithm such that a desired accuracy is obtained. The analysis also extends previous results by taking into account all the parameters of the algorithm. Using the error analysis, we also give a bound for the computational complexity in terms of the error which is analogous to and slightly tightens the one given by Murtagh and Vadhan (2018). We also show how to speed up the evaluation of tight privacy guarantees using the Plancherel theorem at the cost of increased pre-computation and memory usage.
翻译:最近提议的快速Fourier变换(FFT)会计对使用隐私损失分配格式来评估$(\varepsilon,\delta)美元差异性隐私保障,其使用隐私损失分配格式的形式证明,与R\'enyi会计师等常用方法相比,对同一结构的构成,即相同机制的构成,具有更严格的限制。在本文件中,我们将这一方法扩大到不同结构。我们进行了完全的错误分析,以便选择算法参数,从而获得理想的准确性。分析还考虑到了算法的所有参数,从而扩展了先前的结果。我们使用错误分析,还设定了计算复杂程度的界限,其误差与Murtagh和Vadhan(2018年)给出的错误类似,并略微收紧。我们还展示了如何加快对使用Plancherel Theorem(Plancherel theorem)的严格隐私保障的评估,其成本是增加的预数和记忆使用。