Faster Privacy Accounting via Evolving Discretization

Differential privacy (DP) (Dwork et al., 2006b, a) has become the preferred notion of privacy in both academia and the industry. Fueled by the increased awareness and demand for privacy, several systems that use DP mechanisms to guard users’ privacy have been deployed in the industry (Erlingsson et al., 2014; Shankland, 2014; Greenberg, 2016; Apple Differential Privacy Team, 2017; Ding et al., 2017; Kenthapadi & Tran, 2018; Rogers et al., 2021), and the US Census (Abowd, 2018). Besides the large volume of data, many of these systems offer real-time private data analytic and inference capabilities, which entail strict computational efficiency requirements on the underlying DP operations.

We recall the definition of DP (Dwork et al., 2006b, a):

The DP guarantees of a mechanism are captured by the privacy parameters $\varepsilon$ and $\delta$; the smaller these parameters, the more private the mechanism. Often a mechanism is simultaneously DP for multiple privacy parameters; this is captured by studying the privacy loss of a mechanism $\mathcal{M}$—the curve $\delta_{\mathcal{M}}(\cdot)$ for which the mechanism is $(\varepsilon,\delta_{\mathcal{M}}(\varepsilon))$-DP.

A fundamental mathematical property satisfied by DP is composition, which prescribes the privacy guarantees of results from executing multiple DP mechanisms. In basic composition (Dwork et al., 2006a), a mechanism that returns the results of executing an $(\varepsilon_{1},\delta_{1})$-DP mechanism and an $(\varepsilon_{2},\delta_{2})$-DP mechanism is $(\varepsilon_{1}+\varepsilon_{2},\delta_{1}+\delta_{2})$-DP. Unfortunately, this bound becomes weak when composing a large number of mechanisms. The advanced composition (Dwork et al., 2010) offers stronger bounds: roughly speaking, composing $k$ mechanisms that are each $(\varepsilon,\delta)$-DP yields a mechanism whose privacy parameters are of the order of $\sqrt{k}\varepsilon$ and $k\delta$—clearly more desirable than the basic composition. In fact, obtaining tight composition bounds has been an active research topic. Kairouz et al. (2015) showed how to obtain the exact privacy parameters of self-composition (mechanism composed with itself), while Murtagh & Vadhan (2016) showed that the corresponding problem for the more general case is #P-complete.

Let $\mathbb{Z}_{>0}$ denote the set of all positive integers, $\mathbb{R}_{\geq 0}$ the set of all non-negative real numbers, and let $\overline{\mathbb{R}}=\mathbb{R}\cup\{-\infty,+\infty\}$. For any two random variables $X$ and $Y$, we denote by $d_{\mathrm{TV}}(X,Y)$ their total variation distance.

Our two-stage algorithm for the case of $k$-fold self-composition is given in Algorithm 2. We assume $k=k_{1}\cdot k_{2}+r$ where $k_{1},k_{2}\in\mathbb{Z}_{>0}$, $r<k_{1}$, and $k_{1}\approx k_{2}\approx\sqrt{k}$, which for instance can be achieved by taking $k_{1}=\lfloor\sqrt{k}\rfloor$, $k_{2}=\left\lfloor k/k_{1}\right\rfloor$, and $r=k-k_{1}\cdot k_{2}$.

The algorithm implements the circular convolution $\oplus_{L}$ using Fast Fourier Transform (FFT). For any $L$ and $x\in\mathbb{R}$, we define $x\ (\mathrm{mod}\ 2L)=x-2Ln$ where $n\in\mathbb{Z}$ such that $x-2Ln\in(-L,L]$. Given $x,y\in\mathbb{R}$ the circular addition is defined as

Similarly, for random variables $X,Y$, we define $X\oplus_{L}Y$ to be their convolution modulo $2L$ and $Y^{\oplus_{L}k}$ to be the $k$-fold convolution of $Y$ modulo $2L$.

Observe that $\mathsf{DiscretizeRV}$ with mesh size $h$ and truncation parameter $L$ runs in time $O(L/h)$, assuming an $O(1)$-time access to $\mathsf{CDF}_{Y}(\cdot)$. The FFT convolution step runs in time $O\left(\frac{L_{i}}{h_{i}}\log\frac{L_{i}}{h_{i}}\right)$; thus the overall running time of $\mathsf{TwoStageSelfComposePRV}$ is

The approximation guarantees provided by our two-stage algorithm are captured in the following theorem. For convenience, we assume that $k$ is a perfect square (we set $k_{1}=k_{2}=\sqrt{k}$). The complete proof is in Section 3.1.

In terms of a concrete running time bound, Theorem 3.1 implies:

In many practical regimes of interest, $\varepsilon_{\mathrm{up}}/\varepsilon_{\mathrm{err}}$ is a constant. For ease of exposition in the following, we assume that $\varepsilon_{\mathrm{err}}$ is a small constant, e.g. $0.1$ and suppress the dependence on $\varepsilon_{\mathrm{err}}$. Suppose the original mechanism $\mathcal{M}$ underlying $Y$ satisfies $(\varepsilon=\frac{1}{\sqrt{k\cdot\log(1/\delta_{\mathrm{err}})}},\delta=o_{k}\left(\frac{1}{k^{1.25}}\right))$-DP. Then by advanced composition (Dwork et al., 2010), we have that $\mathcal{M}^{\circ t}$ satisfies $(\varepsilon\sqrt{2t\log\frac{1}{\delta^{\prime}}}+2t\varepsilon(e^{\varepsilon}-1),t\delta+\delta^{\prime})$-DP. If $t\delta+\delta^{\prime}\lesssim\frac{t\delta_{\mathrm{err}}}{k^{1.25}}$, then we have that $\varepsilon_{Y^{\oplus t}}\left(\frac{t\delta_{\mathrm{err}}}{k^{1.25}}\right)\lesssim\sqrt{\frac{t}{k}\ln\frac{k}{t\delta_{\mathrm{err}}}}$. Instantiating this with $t=1,\sqrt{k}$, and $k$ gives us that $\varepsilon_{\mathrm{up}}$ is at most a constant.

Note that, to set the value of $L_{1}$ and $L_{2}$, we do not need the exact value of $\varepsilon_{Y^{\oplus k}}$ (or $\varepsilon_{Y^{\oplus\sqrt{k}}}$ or $\varepsilon_{Y}$). We only need an upper bound on $\varepsilon_{Y^{\oplus k}}$, which can often be obtained by using the RDP accountant or some other method.

For the case when $k$ is not a perfect square, using a similar analysis, it is easy to see that the approximation error would be no worse than the error in $k_{2}(k_{1}+1)$ self-compositions. The running time increases by a constant because of the additional step of $r$-fold convolution to get $Y_{r}$ and the final convolution step to get $Y_{2}\oplus_{L_{2}}\widetilde{Y}_{r}$; however this does not affect the asymptotic time complexity of the algorithm. Moreover, as seen in Section 4, even with this additional cost, $\mathsf{TwoStageSelfComposePRV}$ is still faster than the algorithm in Gopi et al. (2021).

We empirically evaluate $\mathsf{TwoStageSelfComposePRV}$ on the tasks of self-composing two kinds of mechanism acting on dataset of real values $x_{1},\ldots,x_{n}$ as

• $\triangleright$

  Laplace Mechanism : returns $\sum_{i}x_{i}$ plus a noise drawn from $L(0,b)$ given by the $\mathsf{PDF}$ $P(x)=e^{-|x|/b}/2b$.

• $\triangleright$

  Poisson Subsampled Gaussian Mechanism with probability $\gamma$: Subsamples a random subset $S$ of indices by including each index independently with probability $\gamma$. Returns $\sum_{i\in S}x_{i}$ plus a noise drawn from the Gaussian distribution $\mathcal{N}(0,\sigma^{2})$.

Both these mechanisms are highly used in practice. For each mechanism, we compare against the implementation by Gopi et al. (2021)²²2github.com/microsoft/prv_accountant (referred to as GLW) on three fronts: (i) the running time of the algorithm, (ii) the number of discretized buckets used, and (iii) the final estimates on $\delta_{Y^{\oplus k}}(\varepsilon)$ which includes comparing lower bound $\delta_{Y_{2}}(\varepsilon+\varepsilon_{\mathrm{err}})-\delta_{\mathrm{err}}$, estimates $\delta_{Y_{2}}(\varepsilon)$ and upper bounds $\delta_{Y_{2}}(\varepsilon-\varepsilon_{\mathrm{err}})+\delta_{\mathrm{err}}$. We use $\varepsilon_{\mathrm{err}}=0.1$ and $\delta_{\mathrm{err}}=10^{-10}$ in all the experiments.

We run each algorithm for a varying number $k$ of self-compositions of a basic mechanism. The noise parameter of basic mechanism is chosen such that the final $\delta(\varepsilon)$ value after $k$-fold composition is equal to $10^{-6}$ for each value of $k$.³³3these values were computed using the Google DP accountant github.com/google/differential-privacy/tree/main/python. The exact choice of noise parameters used are shown in Figure 3.

The comparison for the Laplace mechanism is shown in Figure 1 and for the subsampled Gaussian mechanism is shown in Figure 2. In terms of accuracy we find that for the same choice of $\varepsilon_{\mathrm{err}}$ and $\delta_{\mathrm{err}}$, the estimates returned by $\mathsf{TwoStageSelfComposePRV}$ are nearly identical to the estimates returned by GLW for the subsampled Gaussian mechanism. On the other hand, the estimates for Laplace mechanism returned by both algorithms are similar and consistent with each other, but strictly speaking, incomparable with each other.

We extend the approach in $\mathsf{TwoStageSelfComposePRV}$ to give a multi-stage algorithm (Algorithm 3), presented only when $k$ is a power of $2$ for ease of notation. Similar to the running time analysis of $\mathsf{TwoStageSelfComposePRV}$, the running time of $\mathsf{RecursiveSelfComposePRV}$ is given as

assuming an $O(1)$-time access to $\mathsf{CDF}_{Y}(\cdot)$.