Connect the Dots: Tighter Discrete Approximations of Privacy Loss Distributions

Differential privacy (DP) [9, 8] has become widely adopted as a notion of privacy in analytics and machine learning applications, leading to numerous practical deployments including in industry [13, 29, 16, 3, 7] and government agencies [2]. The DP guarantee of a (randomized) algorithm is parameterized by two real numbers $\varepsilon>0$ and $\delta\in[0,1]$; the smaller these values, the more private the algorithm.

The appeal of DP stems from the strong privacy that it guarantees (which holds even if the adversary controls the inputs of all other users in the database), and from its nice mathematical properties. These include composition, whose basic form [8] says that executing an $(\varepsilon_{1},\delta_{1})$-DP algorithm and an $(\varepsilon_{2},\delta_{2})$-DP algorithm and returning their results gives an algorithm that is $(\varepsilon_{1}+\varepsilon_{2},\delta_{1}+\delta_{2})$-DP. While basic composition can be used to bound the DP properties of $k$ algorithms, it is known to not be tight, in particular for large values of $k$. In fact, advanced composition [12] yields a general improvement, often translating to $\approx\sqrt{k}$ reduction in the $\varepsilon$ privacy bound of the composition of $k$ mechanisms each of which being $(\varepsilon_{0},\delta_{0})$-DP. Such a reduction can be sizeable in practical deployments, and therefore much research has been focusing on obtaining tighter composition bounds in various settings.

In the aforementioned setting where each mechanism has the same DP parameters, Kairouz et al. [17] derived the optimal composition bound. For the more general case of composing $k$ mechanisms whose privacy parameters are possibly different, i.e., the $i$th mechanism is guaranteed to be $(\varepsilon_{i},\delta_{i})$-DP for some parameters $\varepsilon_{i},\delta_{i}$, computing the (exact) DP parameters of the composed mechanism is known to be #P-complete [27].

While the results of [17, 27] provide a complete picture of privacy accounting when we assume only that the $i$th mechanism is $(\varepsilon_{i},\delta_{i})$-DP, we can often arrive at tighter bounds when taking into account some additional information about the privacy loss of the mechanisms. For example, the Moments Accountant [1] and Rényi DP [26] methods keep track of (upper bounds on) the Renyi divergences of the output distributions on two adjacent databases; this allows one to compute upper bounds on the privacy parameters. These tools were originally introduced in the context of deep learning with DP (where the composition is over multiple iterations of the learning algorithm) in which they provide significant improvements over simply using the DP parameters of each mechanism. Other known tools that can also be used to upper-bound the privacy parameters of composed mechanisms include concentrated DP [11, 6] and its truncated variant [5]. These methods are however all known not to be tight, and do not allow a high-accuracy estimation of the privacy parameters.

A numerical method for estimating the privacy parameters of a DP mechanism to an arbitrary accuracy, which has been the subject of several recent works starting with [24, 30], relies on the privacy loss distribution (PLD). This is the probability mass function of the so-called privacy loss random variable in the case of discrete mechanisms, and its probability density function in the case of continuous mechanisms. From the PLD of a mechanism, one can easily obtain its (tight) privacy parameters. Moreover, a crucial property is that the PLD of a composition of multiple mechanisms is the convolution of their individual PLDs. Thus, [19] used the Fast Fourier Transform (FFT) in order to speed up the computation of the PLD of the composition. Furthermore, explicit bounds on the approximation error for the resulting algorithm were derived in [19, 20, 18, 15]. The PLD has been the basis of multiple open-source implementations from both industry and academia including [23, 22, 25]. We note that the PLD can be applied to mechanisms whose privacy loss random variables do not have bounded moments, and thus for which composition cannot be analyzed using the Moments Accountant or Rényi DP methods. An example such mechanism is DP-SGD-JL from [4].

A crucial step in previous papers that use PLDs is in approximating the distribution so that it has finite support; this is especially needed in the case where the PLD is continuous or has a support of a very large size, as otherwise the FFT cannot be performed efficiently. With the exception of [15]¹¹1Gopi et al. [15] uses an estimator that is neither pessimistic nor optimistic, and instead derive their final values of $\delta$ using concentration bound-based error estimates., previous PLD-based accounting approaches [24, 19, 20, 18] employ pessimistic estimators and optimistic estimators of PLDs. Roughly speaking, the former overestimate (i.e., give upper bounds on) $\delta$, whereas the latter underestimate $\delta$. For efficiency reasons, we would like the support of the approximate PLDs to be as small as possible, while retaining the accuracy of the estimates.

For $k\in{\mathbb{N}}$, we use $[k]$ to denote $\{1,\dots,k\}$. For a set $S\subseteq{\mathbb{R}}\cup\{-\infty,+\infty\}$, we write $\exp(S)$ to denote $\{e^{a}\mid a\in S\}$. Similarly, for $S\subseteq{\mathbb{R}}_{\geq 0}\cup\{+\infty\}$, we use $\log(S)$ to denote $\{\log(a)\mid a\in S\}$. Here we use the (standard) convention that $e^{+\infty}=+\infty$ and $e^{-\infty}=0$; we also use the convention that $(+\infty)\cdot 0=(-\infty)\cdot 0=0$. Moreover, we use $[x]_{+}$ as a shorthand for $\max\{x,0\}$.

We use $\operatorname*{supp}(P)$ to denote the support of a probability distribution $P$. For two distributions $P,Q$, we use $P\otimes Q$ to denote the product distribution of the two. Furthermore, when $P,Q$ are over an additive group, we use $P\ast Q$ to denote the convolution of the two distributions.

As alluded to in the previous section, to take full advantage of FFT, it is important that a PLD is discretized in a way such that its support is finite. For exposition purposes, we will assume that the discretization points include $-\infty$ and $+\infty$. We will use $\mathcal{E}$ for discretization points for the PLD and $\mathcal{A}$ for the corresponding discretization points for the hockey-stick curve:

For the remaining of this work, we will operate under the above assumption and we will not state this explicitly for brevity.

Using the characterization in Lemma 2.1, we can also characterize the hockey-stick curve of PLDs whose support is on a prespecified finite set $\mathcal{E}$, stated more precisely in the lemma below. Furthermore, the “inverse” part of the lemma yields an algorithm (Algorithm 1) that can construct $A,B$ given $(h(\alpha_{i}))_{\alpha_{i}\in\mathcal{A}}$ which we will use in the sequel.

A consequence of Lemma 3.2 is that $h$ is completely specified by $h(\mathcal{A})$. More formally, given $f:\mathcal{A}\to[0,1]$, the only possible extension of $f$ to a hockey-stick curve is its piecewise-linear extension $\overline{f}$ defined by

for all $\alpha\in{\mathbb{R}}_{\geq 0}\cup\{+\infty\}$. Note that this $\overline{f}$ may still not be a hockey-stick curve, as it may not be convex.

• Proof of Lemma 3.2.

  $(\Leftarrow)$ We start with the converse direction by describing an algorithm that, given $h(\alpha_{0}),\dots,h(\alpha_{k})$, can construct the desired $P,Q$. In fact, we will construct distributions $P$ and $Q$ with supports contained in $\mathcal{A}$ satisfying the following:

  1. ($\Pi_{1}$)

     $P(\alpha)=\alpha\cdot Q(\alpha)$ for all $\alpha\in\mathcal{A}\setminus\{+\infty\}$,

  2. ($\Pi_{2}$)

     $Q(\infty)=0$,

  3. ($\Pi_{3}$)

     $D_{\alpha}(P||Q)=h(\alpha)$ for all $\alpha\in\mathcal{A}$.

  The first two conditions imply that $\operatorname*{supp}(\mathsf{PLD}_{(P,Q)})\subseteq\mathcal{E}$ and the last condition implies that $h_{(P,Q)}=h$ as desired.

  The construction of $P,Q$ is described in Algorithm 1.

  procedure DiscretizePLD($h(\alpha_{0}),\dots,h(\alpha_{k})$)

       $Q(\alpha_{k})\leftarrow 0$ $\triangleright$ $\alpha_{k}=+\infty$

       for $i=k-1,\dots,1$ do

           $Q(\alpha_{i})\leftarrow\frac{h(\alpha_{i-1})-h(\alpha_{i})}{\alpha_{i}-\alpha_{i-1}}-\frac{h(\alpha_{i})-h(\alpha_{i+1})}{\alpha_{i+1}-\alpha_{i}}$      

       $Q(\alpha_{0})\leftarrow 1-\sum_{j\in[k-1]}Q(\alpha_{j})$ $\triangleright$ $\alpha_{0}=0$

       $P(\alpha_{0})\leftarrow 0$ $\triangleright$ $\alpha_{0}=0$

       for $i=1,\dots,k-1$ do

           $P(\alpha_{i})\leftarrow\alpha_{i}\cdot Q(\alpha_{i})$      

       $P(\alpha_{k})\leftarrow h(\alpha_{k})$ $\triangleright$ $\alpha_{k}=+\infty$

Let us now verify that both $P$ and $Q$ are valid probability distributions. First, notice that $Q(\alpha_{i})\geq 0$ due to the convexity of $h$. Furthermore,

where the last inequality follows from (iii). Thus, $Q$ is indeed a probability distribution. As for $P$, notice that $P(\alpha_{i})\geq 0$ for all $\alpha_{i}\in\mathcal{A}$. Finally, we also have

meaning that $P$ is a probability distribution as desired.

Properties 1 and 2 are immediate from the construction. We will now check Property 3, based on two cases whether $\alpha>\alpha_{k-1}$.

• $\triangleright$

  Case I: $\alpha\geq\alpha_{k-1}$. In this case, we have $D_{\alpha}(P||Q)=P(+\infty)-e^{\varepsilon}Q(+\infty)=h(+\infty)$.

• $\triangleright$

  Case II: $\alpha<\alpha_{k-1}$. Suppose that $\alpha\in[\alpha_{i-1},\alpha_{i})$ for $i\in[k-1]$. We have

  	$\displaystyle D_{\alpha}(P||Q)$	$\displaystyle=P(\{\alpha_{i},\dots,\alpha_{k}\})-\alpha\cdot Q(\{\alpha_{i},\dots,\alpha_{k}\})$
  		$\displaystyle=\sum_{j=i}^{k}(\alpha_{j}-\alpha)\cdot Q(\alpha_{j})$
  		$\displaystyle=\frac{\alpha-\alpha_{i}}{\alpha_{i-1}-\alpha_{i}}\cdot\sum_{j=i}^{k}(\alpha_{j}-\alpha_{i-1})\cdot Q(\alpha_{j})$
  		$\displaystyle\quad+\frac{\alpha_{i-1}-\alpha}{\alpha_{i-1}-\alpha_{i}}\cdot\sum_{j=i}^{k}(\alpha_{j}-\alpha_{i})\cdot Q(\alpha_{j}).$

  Furthermore, we have

  	$\displaystyle\sum_{j=i}^{k}(\alpha_{j}-\alpha_{i-1})\cdot Q(\alpha_{j})$
  	$\displaystyle=\sum_{j=i}^{k}(\alpha_{j}-\alpha_{i-1})$
  	$\displaystyle\qquad\cdot\left(\frac{h(\alpha_{j-1})-h(\alpha_{j})}{\alpha_{j}-\alpha_{j-1}}-\frac{h(\alpha_{j})-h(\alpha_{j+1})}{\alpha_{j+1}-\alpha_{j}}\right)$
  	$\displaystyle=h(\alpha_{i-1}).$

  Similarly, we also have $\sum_{j=i}^{k}(\alpha_{j}-\alpha_{i})\cdot Q(\alpha_{j})=h(\alpha_{i})$. Combining the three equalities, we arrive at

  $\displaystyle D_{\alpha}(P||Q)$

  $\displaystyle=\frac{\alpha-\alpha_{i}}{\alpha_{i-1}-\alpha_{i}}\cdot h(\alpha_{i-1})+\frac{\alpha_{i-1}-\alpha}{\alpha_{i-1}-\alpha_{i}}\cdot h(\alpha_{i}),$

  which is equal to $h(\alpha)$ due to assumption (iv).

As a result, $h_{(P,Q)}=h$ as desired.

$(\Rightarrow)$ We will now prove this direction. (i), (ii), and (iii) follow immediately from Lemma 2.1. As a result, it suffices to only prove (iv) and (v). Suppose that $h_{(P,Q)}=h$ for some pair $(P,Q)$ such that $\operatorname*{supp}(\mathsf{PLD}_{(P,Q)})\subseteq\mathcal{E}$. Let $R$ be a shorthand for the distribution of $\exp(\mathsf{PLD}_{(P,Q)})$. To prove (iv), consider any $\alpha\in[\alpha_{i-1},\alpha_{i})$ for some $i\in[k-1]$. We then have

which completes the proof of (iv).

Next, we prove (v). Consider any $\alpha\geq\alpha_{k-1}$. We have

thereby completing our proof. ∎

As we have described in Figure 1, pessimistic estimates of PLDs with finite supports are crucial in the PLD-based privacy accounting framework. The better these pessimistic estimates approximate the true PLD, the more accurate is the resulting upper bound $\delta^{\uparrow}(\varepsilon)$.

Equipped with tools developed in the previous section, we will now describe our finite-support pessimistic estimate of a PLD. Specifically, given a pair $(A,B)$ of distributions, we would like to compute $(P^{\uparrow},Q^{\uparrow})$ such that $(P^{\uparrow},Q^{\uparrow})\succeq(A,B)$ with $\operatorname*{supp}(\mathsf{PLD}_{(P^{\uparrow},Q^{\uparrow})})\subseteq\mathcal{E}$. In fact, as we will show below (Lemma 4.1), our choice of $\mathsf{PLD}_{(P^{\uparrow},Q^{\uparrow})}$ “best approximates” $\mathsf{PLD}_{(A,B)}$.

Our construction of the pair $(P^{\uparrow},Q^{\uparrow})$ is simple: run DiscretizePLD (Algorithm 1) on the input $h_{(A,B)}(\alpha_{0}),\dots,h_{(A,B)}(\alpha_{k})$.

Recall from the proof of Lemma 3.2 that this construction simply gives $h_{(P^{\uparrow},Q^{\uparrow})}$, which is a piecewise-linear extension of $h_{(A,B)}(\alpha_{0}),\dots,h_{(A,B)}(\alpha_{k})$. In other words, we simply “connect the dots” to construct the hockey-stick curve of our pessimistic estimate. Note that this, together with the convexity of $h_{(A,B)}$ (Lemma 2.1), implies that $(P^{\uparrow},Q^{\uparrow})\succeq(A,B)$ as desired.

Additionally, it is not hard to observe that our choice of pessimistic PLD is the best possible, in sense that $(P^{\uparrow},Q^{\uparrow})$ is the least element (under the domination partial order) among all pairs that dominate $(A,B)$:

• Proof.

  Recall that it suffices to prove that $h_{(P,Q)}(\alpha)\geq h_{(P^{\uparrow},Q^{\uparrow})}(\alpha)$ for all $\alpha\in{\mathbb{R}}_{\geq 0}\cup\left\{+\infty\right\}$. We will consider two cases based on the value of $\alpha$:

  • $\triangleright$

    Case I: $\alpha\geq\alpha_{k-1}$. From Lemma 3.2, we simply have $h_{(P,Q)}(\alpha)=h_{(P,Q)}(+\infty)\geq h_{(A,B)}(+\infty)=h_{(P^{\uparrow},Q^{\uparrow})}(\alpha)$.

  • $\triangleright$

    Case II: $\alpha_{k-1}>\alpha\geq 0$. Suppose that $\alpha\in[\alpha_{i-1},\alpha_{i})$. From Lemma 3.2(ii), we have

    	$\displaystyle h_{(P,Q)}(\alpha)$
    	$\displaystyle=\frac{\alpha-\alpha_{i}}{\alpha_{i-1}-\alpha_{i}}\cdot h_{(P,Q)}(\alpha_{i-1})+\frac{\alpha_{i-1}-\alpha}{\alpha_{i-1}-\alpha_{i}}\cdot h_{(P,Q)}(\alpha_{i})$
    	$\displaystyle\geq\frac{\alpha-\alpha_{i}}{\alpha_{i-1}-\alpha_{i}}\cdot h(\alpha_{i-1})+\frac{\alpha_{i-1}-\alpha}{\alpha_{i-1}-\alpha_{i}}\cdot h(\alpha_{i})$
    	$\displaystyle=h_{(P^{\uparrow},Q^{\uparrow})}(\alpha),$

    where the first inequality follows from $(P,Q)\succeq(A,B)$ and the last equality follows from our construction of $(P^{\uparrow},Q^{\uparrow})$. ∎

We remark that $\mathsf{PLD}_{(P^{\uparrow},Q^{\uparrow})}$ also has a simple form, due to the properties 1 and 2:

for all $i\in[k]$.

We next consider optimistic PLDs, i.e., $\mathsf{PLD}_{(P,Q)}$ dominated by a given $\ \mathsf{PLD}_{(A,B)}$. We start by showing that, unlike pessimistic PLDs for which there is the “best” possible choice (Lemma 4.1), there is no such a choice for optimistic PLDs:

• Proof.

  Let $(A,B)$ be the result of the $\varepsilon$-DP binary randomized response, i.e.,

  	$\displaystyle A(0)=B(1)=\frac{e^{\varepsilon}}{e^{\varepsilon}+1},$
  	$\displaystyle A(1)=B(0)=\frac{1}{e^{\varepsilon}+1}.$

  It is simple to verify that

  $\displaystyle h_{(A,B)}(\alpha)=\begin{cases}1-\alpha&\text{ if }\alpha\leq e^{-\varepsilon},\\ \frac{e^{\varepsilon}}{e^{\varepsilon}+1}-\frac{\alpha}{e^{\varepsilon}+1}&\text{ if }e^{-\varepsilon}<\alpha<e^{\varepsilon},\\ 0&\text{ if }\alpha\geq\varepsilon.\end{cases}$

  Let $\mathcal{A}$ be $\{0,\alpha_{1},\alpha_{2},+\infty\}$ where $\alpha_{1}=e^{-\varepsilon}-\gamma,\alpha_{2}=e^{-\varepsilon}+\gamma$ for any $\gamma<\min\{e^{\varepsilon}-e^{-\varepsilon},e^{-\varepsilon}\}$.

  Let $h_{1}:\mathcal{A}\cup\{+\infty\}\to[0,1]$ be defined as

  	$\displaystyle h_{1}(0)$	$\displaystyle=1,$
  	$\displaystyle h_{1}(\alpha_{1})$	$\displaystyle=h_{(A,B)}(\alpha_{1}),$
  	$\displaystyle h_{1}(\alpha_{2})$	$\displaystyle=1-\alpha_{2},$
  	$\displaystyle h_{1}(+\infty)$	$\displaystyle=0,$

  and let $\overline{h}_{1}$ be its piecewise-linear extension. It is again simple to verify that $\overline{h}_{1}$ satisfies the conditions in Lemma 3.2 and therefore $\overline{h}_{1}=h_{(P_{1},Q_{1})}$ for some $P_{1},Q_{1}$ such that $\mathsf{PLD}_{(P_{1},Q_{1})}$ is supported on $\mathcal{E}$. Furthermore, it can be checked from our definition that $(A,B)\succeq(P_{1},Q_{1})$.

  Similarly, let $h_{2}:\mathcal{A}\cup\{+\infty\}\to[0,1]$ be defined as

  	$\displaystyle h_{2}(0)$	$\displaystyle=1,$
  	$\displaystyle h_{2}(\alpha_{1})$	$\displaystyle=1-e^{-\varepsilon}+\frac{\gamma}{e^{\varepsilon}+1},$
  	$\displaystyle h_{2}(\alpha_{2})$	$\displaystyle=h_{(A,B)}(\alpha_{2}),$
  	$\displaystyle h_{2}(+\infty)$	$\displaystyle=0,$

  and let $\overline{h}_{2}$ be its piecewise-linear extension. Again, $\overline{h}_{2}=h_{(P_{2},Q_{2})}$ for some $P_{2},Q_{2}$ such that $\mathsf{PLD}_{(P_{2},Q_{2})}$ is supported on $\mathcal{E}$ and $(A,B)\succeq(P_{2},Q_{2})$.

  Now, consider any $(P,Q)\preceq(A,B)$ such that $\mathsf{PLD}_{(P,Q)}$ is supported on $\mathcal{E}$. We claim that $(P,Q)\nsucceq(\hat{P}_{1},\hat{Q}_{1})$ or $(P,Q)\nsucceq(P_{2},Q_{2})$. To prove this, assume for the sake of contradiction that $(P,Q)\nsucceq(P_{1},Q_{1})$ and $(P,Q)\nsucceq(P_{2},Q_{2})$. This means that

  	$\displaystyle h_{(P,Q)}(\alpha_{1})$	$\displaystyle\geq h_{1}(\alpha_{1})=h_{(A,B)}(\alpha_{1}),$
  	$\displaystyle h_{(P,Q)}(\alpha_{2})$	$\displaystyle\geq h_{2}(\alpha_{2})=h_{(A,B)}(\alpha_{2}).$

  From piecewise-linearity of $h_{(P,Q)}$ restricted to $[\alpha_{1},\alpha_{2}]$ (Lemma 3.2), we then have $h_{(P,Q)}(e^{\varepsilon})=\frac{1}{2}\left(h_{(P,Q)}(\alpha_{1})+h_{(P,Q)}(\alpha_{2})\right)>h_{(A,B)}(e^{\varepsilon})$, a contradiction to the assumption that $(P,Q)\preceq(A,B)$. ∎