Tight Differential Privacy for Discrete-Valued Mechanisms and for the Subsampled Gaussian Mechanism Using FFT
Antti Koskela1, Joonas Jälkö2, Lukas Prediger2 and Antti Honkela1 1 Helsinki Institute for Information Technology HIIT, Department of Computer Science, University of Helsinki, Finland 2 Helsinki Institute for Information Technology HIIT, Department of Computer Science, Aalto University, Finland
Abstract
We propose a numerical accountant for evaluating the tight $(\varepsilon,\delta)$ -privacy loss for algorithms with discrete one dimensional output. The method is based on the privacy loss distribution formalism and it uses the recently introduced fast Fourier transform based accounting technique. We carry out an error analysis of the method in terms of moment bounds of the privacy loss distribution which leads to rigorous lower and upper bounds for the true $(\varepsilon,\delta)$ -values. As an application, we present a novel approach to accurate privacy accounting of the subsampled Gaussian mechanism. This completes the previously proposed analysis by giving strict lower and upper bounds for the privacy parameters. We demonstrate the performance of the accountant on the binomial mechanism and show that our approach allows decreasing noise variance up to 75 percent at equal privacy compared to existing bounds in the literature. We also illustrate how to compute tight bounds for the exponential mechanism applied to counting queries.
中文速览
差分隐私（differential privacy）机制在实际部署时需要精确计算隐私损失参数（ε, δ），但现有方法要么只给出松散的上界、要么缺乏严格的误差保证。本文基于隐私损失分布（privacy loss distribution, PLD）形式化框架，提出了一种针对离散一维输出机制的数值隐私计算器，核心思路是借助快速傅里叶变换（FFT）高效计算多次组合后的隐私损失分布卷积，并通过对该分布的矩进行误差分析，给出（ε, δ）的严格上下界。将该方法应用于子采样高斯机制（subsampled Gaussian mechanism）和二项式机制（binomial mechanism）的实验表明，在相同隐私保证下，本方法可将所需噪声方差降低最高75%，比现有文献中的界更紧。这一工作填补了离散机制隐私计量缺乏严格保证的空白，对差分隐私随机梯度下降等实用场景具有直接价值。
原文 arXiv:2006.07134;中英对照 + 大白话阅读 https://aha.fim.ai/paper/2006.07134v3