Optimal Accounting of Differential Privacy via Characteristic Function

Introduction

Differential privacy (DP) (Dwork et al., 2006) is one of the most promising approaches towards addressing the privacy challenges in the era of artificial intelligence and big data. Recently, DP is going through an exciting transformation from a theoretical construct into a practical technology (see, e.g., Apple, Differential Privacy Team, 2017; Erlingsson et al., 2014; Dajani et al., 2017), which demands constant-tight privacy accounting tools that use the privacy budget with optimal efficiency.

Much of the progress in the recent theory and practice of DP has been driven by Renyi Differential Privacy (RDP) (Mironov, 2017), e.g., it is the major technical component behind the first practical method for deep learning with differential privacy (Abadi et al., 2016). More broadly, RDP is among several recent work in differential privacy that conducts fine-grained mechanism specific analysis (Bun and Steinke, 2016; Abadi et al., 2016; Mironov, 2017; Balle and Wang, 2018; Wang et al., 2019; Dong et al., 2021; Sommer et al., 2019; Koskela et al., 2020). At the heart of these breakthroughs is the idea of using a function to describe the privacy guarantee of a randomized procedure, thus produces significantly more favorable privacy-utility tradeoff and tighter bounds under composition. (See Table 1 for a summary their pros and cons).

Note that no single approach dominates others in all dimensions. Renyi DP could be undefined for certain privacy loss distributions, and cannot be used to provide the optimal $(\epsilon,\delta)$-DP computation in general (discussed in Section 3). Privacy profiles and $f$-DP are unwieldy under composition; and the method of (Koskela et al., 2020) is limited to mechanisms with univariate output where $\log(p/q)$ admits a density; or those with discrete outputs. Usually, for a new mechanism, we would be lucky to have any one of these functional descriptions. The need to derive these manually for each new mechanism is clearly limiting the creativity of researchers and practitioners in DP.

In addition, there are some unresolved foundational issues related to the PLD formalism. As is repeatedly articulated by the authors, the PLD formalism is defined for each pair of neighboring datasets separately, thus, strictly speaking, does not imply DP unless we can certify that the pair of neighboring datasets is the worst-case. This is challenging because such a pair of datasets might not exist and it is unclear how we can define a partial ordering of two privacy loss distributions.

In this paper, we provide a unified treatment to these functional representations and resolve the aforementioned subtle issues related to the PLD formalism. Our contributions are summarized below.

We formalize and generalize the notion of “worst-case” pair distributions discussed in (Sommer et al., 2019) to a “dominating pair” and prove several basic properties of the dominating pairs including finding such pairs from any privacy-profiles, adaptive composition and amplification by sampling. These results substantially broaden the applicability of PLD formalism (Sommer et al., 2019) in deriving worst-case DP guarantees.

We propose a lossless representation of the privacy loss RV by its characteristic function ($\phi$-function) and derive optimal conversion formula to (and from) privacy-profile, tradeoff-function ($f$-DP) and the distribution function of the privacy loss RV. Many of these conversion rules correspond naturally to the classical Fourier / Laplace transforms (and their inverses) from the signal processing literature.

We design an Analytical Fourier Accountant (AFA, extending the Fourier accountant of (Koskela et al., 2020, 2021)) which represents the complex logarithm of the $\phi$ function symbolically. AFA can be viewed as an extension of the (analytical) moments-accountant (Abadi et al., 2016; Wang et al., 2019) to complex $\alpha$, thus allowing straightforward composition. Computing $\delta$ as a function of $\epsilon$ for $(\epsilon,\delta)$-DP boils down to a numerical integral which we use a Gaussian quadrature-based method to solve efficiently and accurately.

Experimentally, we demonstrate that our approach provides substantially tighter privacy guarantees over compositions than RDP on both basic mechanisms and their subsampled counterparts. Our results essentially match the results from (Dong et al., 2021) and (Koskela et al., 2021) but neither rely on central-limit-theorem type asymptotic approximation nor require choosing appropriate discretization a priori as in the FFT-based Fourier Accountant.

Related work: The paper builds upon the existing work on RDP-based privacy accounting (Abadi et al., 2016; Mironov, 2017; Wang et al., 2019) as well as $f$-DP (Dong et al., 2021). Our main theoretical contribution is to substantially broaden the applicability of the PLD formalism (Sommer et al., 2019) by proposing the notion of dominating pairs and providing general recipes for constructing these dominating pairs. The closest to algorithmic contribution is the work of Koskela et al. (2020, 2021), who propose Fourier accountant and an FFT-based approximation scheme, the characteristic function view can be seen as an analytical version of their Fourier accountant (hence the name AFA). AFA is more generally applicable, and allows more flexible use of existing methods for numerical integral. The recent work of Gopi et al. (2021) improves the FFT accountant substantially. It is complementary to us in that it does not address the foundational issues of the PLD formalism, nor do they propose an analytical representation that allows a more modular design of the privacy accountant. Notably, we can use any blackbox numerical integration tool, e.g., Gaussian quadrature, and set the desired error bound on-the-fly, while an FFT-accountant requires setting the parameters at initialization. Finally, Canonne et al. (2020) considered $\phi$ function and its numerical / computational properties but the discussion is restricted to the discrete Gaussian mechanism.

Privacy accounting is closely related to the classical advanced composition of $(\epsilon,\delta)$-DP (Dwork et al., 2010); Kairouz et al. (2015) provides the optimal $k$-fold composition of an $(\epsilon,\delta)$-DP mechanism and Murtagh and Vadhan (2016) shows that computing the tightest possible bound for the composition of $k$ heterogeneous mechanisms is $\#P$-hard. The recent line of work (that we are building upon) challenges the basic primitive of composing $(\epsilon_{i},\delta_{i})$-DP by composing certain functional descriptions of the mechanisms themselves, which sometimes avoids the computational hardness (but not always) and results in even stronger composition than the best $(\epsilon,\delta)$-DP type composition would allow (Bun and Steinke, 2016).

Notations and preliminary

In this section, we review the standard definition of differential privacy, its RDP relaxation, introduce the characteristic function and draw connections with RDP.

Differential privacy and its equivalent definitions. With these notations clarified, we can now formally define differential privacy.

A randomized algorithm $\mathcal{M}$ is $(\epsilon,\delta)$-DP if for every pair of neighboring datasets $D,D^{\prime}$, and every possible output set $S\subseteq\mathcal{O}$ the following inequality holds:

We can alternatively interpret DP from the views of a divergence metric of two probability distributions, a hypothesis testing view of a binary-classifier, as well as the distribution of the log-odds ratio. Let us first define these quantities formally.

Let $\phi$ be a classifier to distinguish two distributions $P$ and $Q$ using a sample. $\alpha_{\phi}$ be its Type I error (false positive rate) and $\beta_{\phi}$ be its Type II error (false negative rate). The tradeoff function $T_{P,Q}(\alpha):\rightarrow$ is defined to be $T_{P,Q}(\alpha):=\inf_{\phi}\{\beta_{\phi}\;|\;\alpha_{\phi}\leq\alpha\}.$

The privacy loss random variable of for a pair of neighboring dataset $D,D^{\prime}$ under mechanism $\mathcal{M}$ is defined as $L_{P,Q}:=\log\frac{\mathcal{M}(D)(o)}{\mathcal{M}(D^{\prime})(o)}\text{ where }o\sim\mathcal{M}(D);$ similarly, we have $L_{Q,P}:=\log\frac{\mathcal{M}(D^{\prime})(o)}{\mathcal{M}(D)(o)}\text{ where }o\sim\mathcal{M}(D^{\prime}).$

These quantities can be used to equivalently define differential privacy (Wasserman and Zhou, 2010; Barthe and Olmedo, 2013; Kairouz et al., 2015; Balle and Wang, 2018; Balle et al., 2018; Dong et al., 2021).

The following statements about a randomized algorithm $\mathcal{M}$ are equivalent to Definition 1

$\sup_{D\simeq D^{\prime}}H_{e^{\epsilon}}(\mathcal{M}(D)\|\mathcal{M}(D^{\prime}))\leq\delta.$

$\sup_{D\simeq D^{\prime}}T_{\mathcal{M}(D),\mathcal{M}(D^{\prime})}(\alpha)\geq\max\{0,1-\delta-e^{\epsilon}\alpha,e^{-\epsilon}(1-\delta-\alpha).$

$\Pr_{o\sim\mathcal{M}(D)}[L_{P,Q}>\epsilon]-e^{\epsilon}\Pr_{o\sim\mathcal{M}(D^{\prime})}[L_{Q,P}<-\epsilon]\leq\delta$ for all neighboring $D,D^{\prime}$.

We highlight that in all these definitions, it is required for the bound to cover all pairs of neighboring datasets $D,D^{\prime}$.

Mechanism-specific analysis / Functional representation of DP guarantee. Each of these equivalent interpretations could be used to provide more-fine-grained description of a differential privacy mechanism $\mathcal{M}$. For instance, the privacy profile $\delta_{\mathcal{M}}(\epsilon)$ upper bounds the HS-divergence for all $\epsilon$ and the $f$-DP lowerbounds the tradeoff function for all Type I error $\alpha$ (see Table 1). In addition, Sommer et al. (2019) proposes the PLD formalism, which represents the privacy loss RV by its density function. The PLD formalism can be viewed as another functional representation, but it is qualitatively different from privacy profile and $f$-DP. We will expand further on PLD in Section 3.

Renyi Differential Privacy and Moments Accountant. Renyi differenital privacy (RDP) (Mironov, 2017) is another generalization of pure-DP via Renyi divergence (denoted by $\mathcal{D}_{\alpha}(P||Q)$).

We say a randomized algorithm $\mathcal{M}$ is $(\alpha,\epsilon(\alpha))$-RDP with order $\alpha\geq 1$ if for neighboring datasets $D,D^{\prime}$,

$(\epsilon,\alpha)$-RDP implies $(\epsilon(\alpha)+\frac{\log(1/\delta)}{\alpha-1},\delta)$-DP, thus by viewing RDP as a function $\epsilon_{\mathcal{M}}(\cdot)$, we can find the best $\epsilon$ parameter by optimizing over $\alpha$. Tighter conversion formula had been proposed recently (Balle et al., 2020; Asoodeh et al., 2021), which we discuss in Appendix.

The main advantage of RDP is that it composes naturally over multiple adaptively chosen mechanisms via a straightforward rule $\epsilon_{\mathcal{M}_{1}\times\mathcal{M}_{2}}\leq\epsilon_{\mathcal{M}_{1}}+\epsilon_{\mathcal{M}_{2}}$. It recovers the advanced composition when converting to $(\epsilon,\delta)$-DP and yields substantial additional savings. These properties, together with the privacy-amplification by sampling, makes RDP the natural choice for privacy accounting in various algorithms of differentially private deep learning. The related algorithm that keeps track of the moment generating function of $L_{P,Q}(o)$ is called “moments accountant” (Abadi et al., 2016; Wang et al., 2019).

Motivation of our research

In this section, we discuss a number of limitations of Renyi DP and PLD formalism that, in part, motivated our research.

1𝑒p=\frac{e}{1+e}. Pane (a) shows the RDP function of RR and GM, clearly, RR also satisfies the same RDP of the Gaussian mechanism for all $\alpha$. Pane (b) in the middle compares the $f$-DP of the two mechanisms, as well as the $f$-DP implied by the optimal conversion from RDP. Pane (c) shows the privacy profile of the two mechanisms, together with Pane (a), it demonstrates that the optimal $f$-DP and $(\epsilon,\delta)$-DP of GM cannot be achieved by a conversion from RDP. The limits of RDP. Let us first ask “is the RDP function a lossless description?” In particular, does it capture all information in the privacy-profile? Because if it is the case, then we could use RDP for composition, and then find the exact optimal $(\epsilon,\delta)$-DP by converting from RDP.

The answer is unfortunately “no”. The reasons are twofolds. First, there are mechanisms with non-trivial $(\epsilon,\delta)$-DP where RDP parameters partially or entirely do not exist. We give two concrete examples in Appendix A.

The second, and a more troubling issue is that even in the cases when RDP parameters exist everywhere and hence appears to be characterizing, it does not lead to a tight conversion to $(\epsilon,\delta)$-DP. Gaussian mechanism is such a candidate where its PLD is completely captured by its Renyi divergences. However, in Figure 1 we demonstrate that we cannot, in general, convert the RDP of Gaussian mechanism into an $(\epsilon,\delta)$-DP that matches the optimal accounting one can achieve through either the privacy profile or $f$-DP directly. Specifically, by an example due to (Dong et al., 2021, Proposition B.7), we know that a randomized response mechanism (RR) satisfies $1$-zCDP, thus the same RDP as that of a Gaussian mechanism (GM) with $\sigma=1$. If the RDP conversion is tight, then it will have to apply to RR too, but that will lead to a contradiction with the tradeoff function of RR. More explicitly, when we further convert the $f$-DP in Figure 1 to $(\epsilon,\delta)$-DP, this example shows that while both RR and GM satisfy an RDP with $\epsilon(\alpha)=\frac{\alpha}{2}$, GM obeys $(0.277,0.3)$-DP but RR does not satisfy $(\epsilon,0.3)$-DP with $\epsilon<0.471$.

This example certifies that the conversion rule we used (based on an extension of (Balle et al., 2020)) cannot be improved and that RDP is a lossy representation even for the Gaussian mechanism.

Trouble with Worst-Cases in the PLD formalism. Recent developments in the PLD formalism show great promises in computing tight ($\epsilon,\delta$)-DP with stable numerical algorithms and provable error bounds (Koskela et al., 2020, 2021). However, as we discussed earlier, PLD is specified for each pair of input datasets separately. To use PLD, the original authors (quoting verbatim) “require the privacy analyst interested in applying our results (PLD formalism) to provide worst-case distributions.” (Sommer et al., 2019, Section 2). In a subsequent work (Meiser and Mohammadi, 2018), a subset of the authors further derive the worst-case pair of distributions for basic mechanisms such as Gaussian mechanism and Laplace mechanism (Meiser and Mohammadi, 2018).

While these are valid arguments, the line of work on PLD formalism does not formally define the worst-case pair of distributions, nor do they provide general recipes for “privacy analysts” to determine which pair of inputs is the worst-case. The issue is more prominent when we consider mechanism-specific analysis, because the pairs of datasets that attain the argmax might be different in different regions of the privacy profile (see an example in Appendix A).

Moreover, in most typical use cases of the privacy accounting tools, the mechanism under consideration is constructed through the composition of a sequence of simpler mechanisms. Even if for each mechanism, we know the worst-case pair distributions, the composition of the individual PLDs may not correspond to the worst-case PLD of the composed mechanism This is an issue we will address later, which shows that it is OK even if it does not.. For this reason, it is unclear how to use PLD for deriving worst-case DP bound under composition except in highly specialized cases (e.g., Gaussian mechanisms and their compositions).

Summary. To reiterate, RDP is lossy when converting to $(\epsilon,\delta)$-DP and the PLD formalism cannot be used to handle the composition generically due to issues regarding worst-case distributions. The remainder of the paper will be dedicated to addressing this dilemma.

Main results

In this section, we develop a comprehensive solution towards tighter and more flexible mechanism-specific privacy accounting for $(\epsilon,\delta)$-DP with a data-structure that allows natural composition.

We first patch the PLD formalism by generalizing the idea of worst-case pair (which may not exist) to a dominating pair of distributions and prove a number of useful properties.

We say that $(P,Q)$ is a dominating pair of distributions for $\mathcal{M}$ (under neighboring relation $\simeq$) if for all $\alpha\geq 0$Note that $\alpha\geq 1$ corresponds to the typical range of $(\epsilon,\delta)$-DP, but the region for $\alpha<1$ is important for composition and lossless conversions to other representations.

Unless otherwise specified, all subsequent results we present hold for any definitions of neighbors (including asymmetric ones such as add-only and remove-only, which will be useful later).

A dominating pair of distributions always exists: one can trivially take $P$ and $Q$ that have disjoint supports. What is somewhat surprising is the following

Any mechanism has a tightly dominating pair of distributions.

Proposition 8 is the direct consequence of the following result which fully characterizes what hockey-stick divergences and privacy profiles look like.

Moreover, one can explicitly construct such $P$ and $Q$: $P$ has CDF $1+H^{*}(x-1)$ in $[0,1)$ and $Q=\textup{Uniform}()$.

The proof, presented in Appendix C, makes use of the Fenchel duality of the privacy profile with respect to a tradeoff function and a characterization of the tradeoff function due to Dong et al. (2021, Proposition 2.2).

What makes the specific construction in Lemma 9 (hence Proposition 8) appealing is that even if the output space is complex, the resulting dominating pair of distributions are of univariate random variables defined on $$. This resolves a limitation of Koskela et al. (2020) that requires the mechanism to have either univariate or discrete outputs.

So far, we have shown the existence of a tightly dominating pairs for all mechanisms (Proposition 8), and provided a recipe for constructing such a dominating pair for any valid upper bounds of the privacy profile (Lemma 9 and Corollary 25 in Appendix C). Next we will provide two general primitives on how to construct dominating pairs for more complex mechanisms created by composition and privacy amplification by sampling.

If $(P,Q)$ dominates $\mathcal{M}$ and $(P^{\prime},Q^{\prime})$ dominates $\mathcal{M}^{\prime}$$\mathcal{M}^{\prime}$ can be adaptively chosen in that it could depend on the output of $\mathcal{M}$, which requires $\sup_{o\in\textrm{Range}(\mathcal{M})}H_{\alpha}(\mathcal{M}^{\prime}(D,o)\|\mathcal{M}^{\prime}(D^{\prime},o))\leq H_{\alpha}(P^{\prime}\|Q^{\prime})$ for any value of $o$. , then $(P\times P^{\prime},Q\times Q^{\prime})$ dominates the composed mechanism $(\mathcal{M},\mathcal{M}^{\prime})$.

By induction, this theorem implies that if we construct the PLD using a dominating pair of distributions for each individual mechanism, then the composed PLD can be used to obtain a valid worst-case DP of the composed mechanism.

Next we present how we can construct a dominating pair of distributions (and datasets) for mechanisms under “privacy-amplification by sampling”. This is a powerful primitive that is used widely in differentially private ERM (Bassily et al., 2014), Bayesian learning (Wang et al., 2015) and deep learning (Abadi et al., 2016). We consider the following two schemes.

Denoted by $S_{\textbf{Poisson}}^{\gamma}$. $S_{\textbf{Poisson}}^{\gamma}$ takes a dataset of arbitrary size and return a dataset by including each data point with probability $0\leq\gamma\leq 1$ i.i.d. at random.

Denoted by $S_{\textbf{Subset}}^{\gamma}$. $S_{\textbf{Subset}}^{\gamma}$ takes a dataset with size $n$ or $n-1$ and return a subset of size $m<n$ uniformly at random. We define $\gamma:=m/n$ as a short-hand. Note that here $n,m$ are public and $\gamma:=m/n$ even if $(n-1)$ is the sample size.

Somewhat unconventionally, the following theorem not only considers add/remove neighboring relation but also treat them separately, which turns out to be crucial in retaining a tight dominating pair with a closed-form expressionSee the appendix for a construction of dominating pairs of subsampled mechanisms under “Add/Remove” or “Replace” neighbors and more detailed discussion on the advantage of treating “Add” and “Remove” separately.. Our choice of choosing $\alpha\geq 0$ in Definition 7 ensures that for any mechanism $(P,Q)$ dominates for add neighbors iff $(Q,P)$ dominates for removal neighbors. {restatable}[]theoremamp Let $\mathcal{M}$ be a randomized algorithm.

If $(P,Q)$ dominates $\mathcal{M}$ for add neighbors then $(P,(1-\gamma)P+\gamma Q)$ dominates $\mathcal{M}\circ S_{\textbf{{Poisson}}}$ for add neighbors and $((1-\gamma)Q+\gamma P,Q)$ dominates $\mathcal{M}\circ S_{\textbf{Poisson}}$ for removal neighbors.

If $(P,Q)$ dominates $\mathcal{M}$ for replacing neighbors, then $(P,(1-\gamma)P+\gamma Q)$ dominates $\mathcal{M}\circ S_{\textbf{{Subset}}}$ for add neighbors and $((1-\gamma)P+\gamma Q,P)$ dominates $\mathcal{M}\circ S_{\textbf{{Subset}}}$ for removal neighbors.

We can obtain the results for the standard "add/remove" for a $k$-fold composition of subsampled mechanism by a pointwise maximum of the two:

where $(P_{1},Q_{1})$ is the “remove only” version of dominating pair and $(P_{2},Q_{2})$ is the “add only” version of dominating pair. Existing literature that uses PLD for Poisson-sampled mechanisms while taking $(\gamma P+(1-\gamma)Q,Q)$ as an input are essentially providing privacy guarantees only for the “remove only” neighboring relationship. To the best of our knowledge, this is the first time a dominating pair of distributions under privacy-amplification by sampling is proven generically with an arbitrary base-mechanism $\mathcal{M}$ under the privacy-profile. The result, together with Theorem 10, allows PLD formalism to be applied to a broader family of mechanisms as well as their subsampled versions under adaptive composition.

2 Characteristic function representation

Having strengthened the foundation of the PLD formalism with “dominating distribution pairs” and two of its basic primitives, we can now put away RDP and its lossy $(\epsilon,\delta)$-DP conversion, then conduct mechanism-specific accounting under $(\epsilon,\delta)$-DP directly. Existing computational tools however, either require asymptotic approximation (Dong et al., 2021; Sommer et al., 2019), repeated convolution (Dong et al., 2021) or an a priori discretization of the output space (Koskela et al., 2021). This prompts us to ask:

“Can we compose mechanisms (with known dominating pairs) naturally just like in RDP? ”

To achieve this goal, we propose using the characteristic function of the privacy loss RV.

Let $(P,Q)$ be a dominating pair of $\mathcal{M}$, and $p,q$ be the probability density (or mass) function of $P,Q$. The two characteristic functions that describes the PLD are

PLDs are probability measures on the real line, and these $\phi$-functions are Fourier transforms of these measures. We provide $\phi$-functions for basic mechanisms (see Table 2) and the discrete mechanisms with closed-form expression. For other intricate and continuous mechanisms (e.g., subsample variants), we provide efficient discretization methods with error analysis in Section E.

Moreover, the adaptive composition over multiple heterogeneous mechanisms remains as straightforward as that of the RDP.

Lossless conversion rules. The $\phi$-function can be losslessly converted back and forth with other representation such as the privacy-profile, tradeoff function, moment-generating function as well as the distribution function of the privacy loss RV. The conversion rule with prominent interest is the conversion to $(\epsilon,\delta)$-DP. Specifically, for finding $\delta$ as a function of $\epsilon$ (i.e., privacy profile), we invoke the fourth equivalent definition of $(\epsilon,\delta)$-DP in Lemma 5, which depends on the cumulative distribution function (CDF) of the privacy loss random variables $L_{P,Q}$ and $L_{Q,P}$. In Appendix B, we establish that these CDFs can be evaluated through an integration of $\phi$-functions via Levy’s formula.

The lossless conversions to other quantities are summarized in Figure 2 and we provide more details in Appendix B. Moreover, most of the conversion formula correspond to well-known transforms such as the Fourier transform, Laplace transform and its double-sided variant. Except for those involve RDP and hence Laplace transform, numerical algorithms for implementing these transforms are often available.

3 Analytical Fourier Accountant and numerical algorithms

We now propose our analytical Fourier Accoutant (AFA) in Algorithm 1, which is a combination of the lossless conversion rules and the analytical composition rule (Proposition 12). Given a sequence of mechanisms (can be varied) applied to the same dataset, the data structure tracks the $\log$ characteristic function of each mechanism in a symbolic form. When there is a $\delta(\epsilon)$ query, the accountant first constructs two analytical CDFs (with respect to the privacy loss RV $L_{P,Q}$ and $L_{Q,P}$) using Theorem 17 in Appendix B. Then the conversion to $(\epsilon,\delta)$-DP is obtained using Lemma 5. For computing $\epsilon$ given $\delta$, we use bisection to solve $\delta_{\mathcal{M}}(\epsilon)=\delta$.

AFA vs FFT. Comparing to the FFT-accountant approach (Koskela et al., 2020, 2021; Koskela and Honkela, 2021), our approach decouples representation and numerical computation. We do not make any approximation when tracking the mechanisms, and use numerical computation only when converting to $(\epsilon,\delta)$-DP. This avoids the need for setting appropriate discretization parameters of FFT ahead of time before knowing which sequence $\mathcal{M}_{1},...,\mathcal{M}_{K}$ we will receive.

Gaussian quadrature For fast and numerically stable evaluation of the CDF, we propose to use Gaussian quadrature which adaptively selects the intervals between interpolation points, rather than the FFT approach which requires equally spaced discretization. When we apply this approach to efficiently evaluate integral in computing CDFs, where the numerical error is often negligible, i.e., $O(10^{-13})$ for CDFs in our experiments, even if we only sample a few hundreds points. We defer a more detailed error analysis to Section E.

Experiments

In this section, we conduct numerical experiments to illustrate the behaviors of our analytical Fourier Accountant. We will have three sets of experiments.

(Gaussian mechanism) We compare the privacy cost over compositions between RDP accountant and AFA accountant on Gaussian mechanism.

(Compositions of discrete and continuous mechanisms) We evaluate the Fourier accountant variants and RDP accountant on heterogeneous mechanisms.

(Compositions over Poisson Subsample mechanisms) Comparison of our AFA with discretization-based $\phi$-function to the Fourier accountant (FA) and the RDP accountant.

In Exp1, we compare our AFA method to the RDP-based accoutant(Mironov, 2017) and the exact accountant from the analytical Gaussian mechanism (Balle and Wang, 2018). In Figure 3(a), we evaluate $\epsilon$ with a fixed $\delta=10^{-4}$ and use $\sigma\in\{50,100\}$.

Observation: In Figure 3(a), our $\phi$ function-based AFA exactly matches the result from the analytical Gaussian mechanism and strictly outperforms the RDP accountant in different privacy regimes.

Unlike the FA, our AFA allows an analytical composition over discrete and continuous mechanisms without sampling discretisation points over the privacy loss distribution, therefore achieves an exact privacy accountant. In Figure 3(b), we plot the $\delta(\epsilon)$ over $k$ compositions given by FA and the moments accountant with RDP. We use $n=10^{5}$ discretisations points and $L=10$ for FA. Our numerical result matches FA as $n=10^{5}$ is already a very accurate estimation as stated in (Koskela and Honkela, 2021).

There are cases when the closed-form $\phi$-functions do not exist. In Exp 3, we consider this problem by analyzing the Poisson Subsample Gaussian mechanism using our discretization-based approach (Algorithm 2) and “Double quadrature” in Appendix E. We discuss the dominating distribution, the construction on $\phi$-function, and its discretization in Appendix E. Figure 3(c) shows a comparsion of our AFA to the Fourier accountant method (Koskela et al., 2021) and the moments accountant method (Zhu and Wang, 2019). The sampling probability is $\gamma=0.01$, the noise scale is $\sigma=2.0$ and we evaluate $\epsilon$ with $\delta=10^{-5}$. We use the tighter conversion rule from Balle et al. (2020) to convert the RDP back to $(\epsilon,\delta)$-DP. The numerical issues induced by Gaussian quadrature are at most $O(10^{-14})$. Our lower and upper bounds of $\delta(\epsilon)$ shown in Figure 3(c) already incorporate the error induced by discretization and ignoring the tail integral. We emphasize that the lower and upper bounds can match the bounds from FA by increasing sample points $n$. Moreover, “Double quadrature” is our proposed efficient approximation method. We only unevenly sample $700$ points for each $\phi$-function and the result of the “Double quadrature” lines between our lower and upper bounds and matches the result from FA. Lastly, all Fourier accountant-based approaches improve over the RDP-based accountant.

Runtime and space analysis of AFA We first compare the time complexity and memory when we have analytical expressions of $\phi$-functions. In Exp 2, each mechanism admits an analytical $\phi$-function and can be represented in $O(1)$ memory and evaluated in $O(1)$ time. Therefore, the memory cost is $O(\#$ unique mechanisms). We analyze the runtime by decomposing it into the “composition” and “conversion to $\delta(\epsilon)$” separately.

Let $k$ denote the number of compositions. Regarding the runtime in the conversion to $\delta(\epsilon)$ query, we apply Gaussian quadrature to compute the CDF, which requires $O(\frac{1}{\delta_{err}^{1/\alpha}})$ runtime complexity for the $\alpha$th order differentiable functions. The following composition runtime for Koskela and Honkela (2021) and Gopi et al. (2021) denote the runtime for discretization and convolution via FFT for a homogeneous composition of a mechanism for $k$ rounds. We use $n$ to denote the size of grid discretization in the FFT approximation.

Of course, this is by no means a fair discussion because the FFT approach computes the entire (discretized) PLD of the composed mechanisms together while AFA computes just one point. In terms of the approximation error, our method is the only approach that adapts to the structures of the $\phi$ functions being integrated and achieves a faster convergence rate.

For the cases when the analytical expressions of $\phi$-functions do not exist (see EXP3), we need to approximate the $\phi$ function too. Thus one single evaluation calls require $O(n)$, and our method is slower than Koskela and Honkela (2021); Gopi et al. (2021), because we do not use FFT. The space and time complexity of the adaptive discretization approach via double quadrature is unclear, though very fast in practice.

Conclusion

In this paper, we studied the problem of privacy accounting with mechanism-specific analysis. We introduced the notion of dominating pair distributions, showed that each mechanism’s privacy profile is characterized by a tight dominating pair, and derived a number of useful algebra of dominating pairs including adaptive composition and amplification by sampling. These results strengthen the foundation of the PLD formalism and make it more widely applicable. Algorithmically, we proposed an analytical Fourier accountant that represents the characteristic functions of a dominating pair symbolically, which features RDP-like natural composition and allows us to leverage off-the-shelf numerical tools. Our experiments demonstrate the merits of AFA and suggest that it can flexibly and efficiently fit into every DP application.

This work also leaves several open questions. Among those

As Lemma 9 demonstrates, the construction of the domaining pair is severely constrained when trade-off functions are not clear. For example, characterizing high-dimension discrete Gaussian mechanism remains a tricky open problem.

Moreover, there are cases where our approach requires much more quadrature points: We apply Gaussian quadrature to compute the CDF of the privacy loss RV through integration over $\phi$-functions. If the composed $\phi$ functions have large values at the tail of integral (e.g., near $\infty$), we need to sample more quadrature points. We hope to solve this issue using numerical tools in the next step.

Acknowledgments

The work was partially supported by NSF CAREER Award # 2048091, Google Research Scholar Award and a gift from NEC Labs. The authors thank the anonymous reviewers for catching a subtle issue in defining dominating pairs for $\alpha\geq 1$ only in an earlier version of the paper. In the hindsight, defining $\alpha\geq 0$ is more natural and elegant. We thank Antti Koskela and Thomas Steinke for helpful discussion. We also thank Salil Vadhan for sharing a shorter alternative proof of the composition theorem based on a deep result due to Blackwell.

References

Appendix A Limits of RDP and the PLD formalism

In Section 3 we omitted a few examples when we talk about the limitation of Renyi Differential Privacy (RDP) in describing common mechanisms. Specifically, we commented that there are mechanisms where RDP either does not exist or does not exist for most order $\alpha$ that implies stronger privacy guarantees.

In smooth sensitivity-based query release [Nissim et al., 2007], one perturbs the output with a noise with a data-dependent variance. Consider, for example, $P=\mathcal{N}(0,\sigma_{1}^{2}),Q=\mathcal{N}(0,\sigma_{2}^{2})$, then the Renyi-divergence $D_{\alpha}(P\|Q)$ is undefined for all $\alpha$ such that $\alpha\sigma_{2}^{2}+(1-\alpha)\sigma_{1}^{2}<0$. Specifically, if $\sigma_{1}^{2}=2,\sigma_{2}^{2}=1$, then $D_{\alpha}(P\|Q)=+\infty$ for all $\alpha\geq 2$.

These examples demonstrate the deficiency of RDP in analyzing flexible algorithm design tools such as the proposed-test-release [Dwork and Lei, 2009]), which typically introduces a heavier-tailed privacy-loss distributions for which the moment generating function is not defined.

On the contrary, the privacy-profile is well-defined in both examples and imply nontrivial $(\epsilon,\delta)$-DP. The characteristic function exists no matter how heavy-tailed the distribution of the privacy loss random variable is so it naturally handles the second example. In Section D.2, we describe how we can handle a probability mass at $+\inf$ in our approach.

We also omitted an example for which there are no single pair of neighboring datasets that attain the argmax might be different in different regions of the privacy profile.

Appendix B Conversion rules between functional representations

In this section we give the details of conversions between various functional representations of the privacy loss distribution (of a dominating pair of distributions). These conversions are summarized in Figure 2 and repeated here.

Before we proceed to the details of all these arrows, we would like to emphasize a important distinction:

These conversions rules are not about converting between different DP definitions, but rather converting between different representations of the privacy loss r.v. under the same DP definition — in our case, $(\epsilon,\delta)$-DP.

More precisely, we mean that the conversion from RDP to DP (leftmost grey arrow in the figure, which we will talk about in details in Section F) is qualitatively different from the conversion from Renyi divergence to Hockey-Stick divergence (red arrow labeled “Post’s inversion formula”).

Modulo some detailssuch as the symmetry of $P=M(D)$ and $Q=M(D^{\prime})$ and the domains of $\alpha$ and $\varepsilon$., a conversion from RDP to DP is about finding function $\delta(\cdot)$ that upper bounds the Hockey-stick divergence for all pairs of neighboring datasets using an RDP function $\epsilon(\cdot)$.

In contrast, a conversion from Renyi divergence to hockey-stick divergence is about a given pair of $P,Q$, and the input function $\epsilon(\alpha)$ is expected to be the exact Renyi-divergence of order $\alpha$. The goal of the divergence-to-divergence conversion rule is to find a different divergence of the same pair of distribuiton $P,Q$, i.e.

Both conversions aim to compute a function $\delta$ from a function $\epsilon$. The seemingly harmless distinction of inequalities and identities is actually the devil in the details. It has two major consequences

When applied to privacy, divergence conversion requires a dominating pair of distributions as a prerequisite, which may or may not be a tight dominating pair. In the figure, results that require a dominating pair are enclosed in the light yellow region labeled “When a dominating pair $(P,Q)$ is available”.

DP conversion is lossy even when converting the statement “standard randomized response is 1-zCDP” to $(\varepsilon,\delta)$-DP, as demonstrated by Figure 1. On the other hand, divergence conversion is generically lossless (under some regularity condition), though numerical issues often arise since the inverse Laplace transform is involved Epstein and Schotland .

In alignment with the focus of this paper, in this section we focus on the light yellow region assuming $(P,Q)$ is a dominating pair. DP conversion is discussed in more detail in Appendix F.

We recall some definitions. Let $P,Q$ be two probability distributions on the same measurable space. For $\alpha>0$, their hockey-stick divergence is defined as

For $\alpha>1$, their Renyi divergence is defined as

Let $F$ and $G$ be the CDFs of the privacy loss random variables. Namely,

The corresponding densities (if exist) will be $F^{\prime}$ and $G^{\prime}$. The corresponding characteristic functions (ch.f.) are the Fourier transforms of the two measures, i.e.

Trade-off functions are $T[P,Q]$ and $T[Q,P]$, which map the type I error to the corresponding minimal type II error in testing problems $P$ vs $Q$ and $Q$ vs $P$ respectively.

From these definitions we see that all five functional representations actually require two functions for each pair of distributions. Below we summarize how one determines the other.

$H_{\alpha}(Q\|P)=\alpha H_{\alpha^{-1}}(P\|Q)-\alpha+1$, which is stated as Lemma 45 in Appendix G.

For $\alpha\in(0,1)$, $\mathcal{D}_{\alpha}(Q\|P)=\frac{\alpha}{1-\alpha}\mathcal{D}_{1-\alpha}(P\|Q).$ See Proposition 2 of Van Erven and Harremos .

Using the above formula, $\phi^{\prime}$ can be obtained by the following process: $\phi\xrightarrow{\text{Levy's formula}}F\to G\to\phi^{\prime}$.

If $T[P,Q]=f$ then $T[Q,P]=f^{-1}$. See Lemma A.2 of Dong et al.

We now consider the conversion from the $\phi$-function to CDFs using the following Levy’s theorem.

Let $\phi$ be the ch.f. of the distribution function $F$ and $a<b$, then

Note that $\lim_{T\to\infty,\alpha\to\infty}\int_{-\infty}^{\infty}\frac{e^{-i\alpha a}}{i\alpha}\phi(\alpha)d\alpha=\pi$. To compute the CDF of the privacy loss RV $L_{P,Q}$ at $b$, we can substitude $a$ with $-\infty$ and obtain the following result.

The characteristic functions are determined by the trade-off function $f$ via the following formula:

Appendix C Omitted proofs in the main body

By Lemma 19, $H_{\alpha}(P\|Q)$ can be related to $f=T[Q,P]$ as follows:

where $\varepsilon$ ranges over the whole real line. By a simple change of variable, we see that $h\in\mathcal{H}$ iff there exists $f\in\mathcal{F}$ such that $h(\alpha)=1+f^{*}(-\alpha)$, or equivalently,

By Proposition 2.2 of Dong et al. , we know

Claim: Convex conjugacy is a bijection between $\mathcal{F}$ and $\mathcal{G}$.

With $y_{1}<y_{2}$, we have $y_{1}x-f(x)\leqslant y_{2}x-f(x)$. Taking supremum over $x\geqslant 0$, we have $f^{*}(y_{1})\leqslant f^{*}(y_{2})$. This shows $f^{*}$ is monotone and finite on $(-\infty,0]$. Let

Since $f\leqslant I$, we conclude that $f^{*}(x)\geqslant I^{*}(x)=\max\{x,-1\}$.

Now suppose $g\in\mathcal{G}$. Similarly, $g$ is extended to be $+\infty$ in $(0,+\infty)$. $g^{*}(y)=\sup_{x\leqslant 0}yx-g(x)$ and $g^{*}(y)=+\infty$ if $y<0$. By a similar argument, $g^{*}$ is increasing. Since $g\geqslant I^{*}$, we have $g^{*}\leqslant I^{**}=I$. That is, $g^{*}(x)\leqslant 1-x$. Let $J$ be zero on $(-\infty,0]$ and infinity otherwise. We have $J^{*}$ is zero on $[0,+\infty)$ and infinity otherwise. We know that $g(0)=0$ and $g$ is increasing so $g\leqslant J$. Hence $g^{*}\geqslant J^{*}$, i.e. $g^{*}(y)\geqslant 0$ if $y\geqslant 0$. This justifies that $g^{*}(y)\in$ if $y\in$ and $g^{*}(y)=0$ if $y\geqslant 1$. ∎

Now with the help of this claim, $\mathcal{H}$ and $\mathcal{G}$ are simply related: $h\in\mathcal{H}$ iff $\alpha\mapsto h(-\alpha)-1$ is in $\mathcal{G}$. Therefore we can get the description of $\mathcal{H}$. The proof of the first statement is complete.

Explicit construction. Next we derive the specific choice of $P,Q$ as stated works using the result from Dong et al. .

Continuing with the notations in the proof above, when $H$ satisfies the conditions, i.e. $H\in\mathcal{H}$, we know there is a $f\in\mathcal{F}$ such that $H(\alpha)=1+f^{*}(-\alpha)$. Let $g(\alpha)=H(-\alpha)-1$ and we will have $g=f^{*}$ and hence $f=g^{*}$ as $f$ is convex. Therefore,

From Dong et al. [2021, Proposition 2.2], we know that $f=T[Q,P]$ where $Q=U$ is the uniform distribution over $$and$P$ has CDF

Plugging in $f(x)=1+H^{*}(-x)$, we have the CDF of $P$ being

Note that when the infimum of $H$ is positive, $H^{*}(1-x)<0$ and $P$ has an atom at 1. This completes the proof. ∎

We know that $\delta_{\mathcal{M}}\in\mathcal{H}$. It suffices to show that

C.2 Composition theorem of dominating pairs

Let $P,Q$ be a dominating pair distributions for $\mathcal{M}$ and $P^{\prime},Q^{\prime}$ be a dominating pair distributions for $\mathcal{M}^{\prime}$$\mathcal{M}^{\prime}$ can be adaptively chosen in that it could depend on the output of $\mathcal{M}$, which requires $\sup_{o\in\textrm{Range}(\mathcal{M})}H_{e^{\epsilon}}(\mathcal{M}^{\prime}(D,o)\|\mathcal{M}^{\prime}(D^{\prime},o))\leq H_{e^{\epsilon}}(P^{\prime}\|Q^{\prime})$ for any value of $o$. , then $(P\times P^{\prime},Q\times Q^{\prime})$ is a dominating pair distributions for the composed mechanism $(\mathcal{M},\mathcal{M}^{\prime})$.

Integration with respect to a dominating measure of both $P$ and $Q$ and $p,q$ are the densities (Radon-Nikodym derivatives) for the probability measures $P,Q$ respectively.

Our goal is to show H_{\alpha}\big{(}M(D),M(D^{\prime})\big{)}\leqslant H_{\alpha}\big{(}P\times R,Q\times S\big{)}. We break it into the following two parts.

C.3 Privacy-amplification for dominating pairs

Recall we stated the following theorem in the main body: \amp*

The proof we present here is written in the language of trade-off functions [Dong et al., 2021]. However, with Lemma 19, everything can be conveniently translated to the language of $(\varepsilon,\delta)$. We made the choice because some parameters have slightly easier forms in the language of trade-off functions.

We begin with a lemma that cut our workload in half — dominance for removal neighbors is actually equivalent to the dominance of add neighbors, so it suffices to show either one of them.

$(P,Q)$ dominates mechanism $\mathcal{M}$ for add neighbors.

$(Q,P)$ dominates mechanism $\mathcal{M}$ for removal neighbors.

$T[M(S),M(S\cup\{x\})]\geqslant T[P,Q]$ for any dataset $S$ and data entry $x$.

Recall that Lemma 19 says for any $\alpha>0$,

Here $(*)$ uses the fact that $T[P,Q]$ and $T[Q,P]$ are inverse functions of each other. ∎

The next lemma plays the central role in both parts of Footnote 6. Suppose we have probability distributions $P_{1},\ldots,P_{n}$ and $Q_{1},\ldots,Q_{n}$, all on the same domain and let $\bar{P}=\sum_{i=1}^{n}p_{i}P_{i}$ and $\bar{Q}=\sum_{i=1}^{n}p_{i}Q_{i}$ be the corresponding mixture distributions with the same coefficients $p_{1},\ldots,p_{n}$ where $\sum_{i=1}^{n}p_{i}=1$ and all $p_{i}\geqslant 0$. Then we have

If $T[P_{i},Q_{i}]\geqslant T[P,Q]$ for all $i\in[n]$, then for any $\gamma\in$, we have

Expanding the convex combination, we have

The last inequality follows from the monotonicity of trade-off functions. Hence (3) is verified and the proof is complete. ∎

where $S=\{x_{1},\ldots,x_{n-1}\}$ and $S^{\prime}=S\cup\{x_{n}\}$. The outcome of repeated coin flips can be labeled as $\vec{b}\in\{0,1\}^{n-1}$. We use $S_{\vec{b}}$ to denote the corresponding subset of $S$ and $S_{\vec{b}0}^{\prime}$ or $S_{\vec{b}1}^{\prime}$ for that of $S^{\prime}$, depending on whether $x_{n}$ is included. Note that $S_{\vec{b}0}^{\prime}=S_{\vec{b}}$. Furthermore, let $p_{\vec{b}}$ be the probability of the outcome $\vec{b}$ (recall that each coin is a Bernoulli $\gamma$ random variable). In fact, $p_{\vec{b}}=\prod_{i=1}^{n-1}\gamma^{b_{i}}(1-\gamma)^{1-b_{i}}$ but we will not use it.

Both $M(S_{\textbf{{Poisson}}})$ and $M(S^{\prime}_{\textbf{{Poisson}}})$ are mixtures. We have the following decompositions

Now we are ready to use Lemma 28, with the family of $P_{i}$ being $M(S_{\vec{b}})$ and the family of $Q_{i}$ being $M(S_{\vec{b}1}^{\prime})$. By the calculation above, $M(S_{\textbf{{Poisson}}})$ will be the $\bar{P}$ in Lemma 28 and $M(S^{\prime}_{\textbf{{Poisson}}})$ is exactly the $(1-\gamma)\bar{P}+\gamma\bar{Q}$ in Lemma 28. We still need to verify the condition in Lemma 28: since $(P,Q)$ dominates $M$ for add neighbors, for each $\vec{b}\in\{0,1\}^{n-1}$ we have

Therefore, Lemma 28 gives us (4), which is exactly what we want. ∎

where $S=\{x_{1},\ldots,x_{n-1}\}$ and $S^{\prime}=S\cup\{x_{n}\}$.

Below we use notations such as $S_{I},S_{J\cup\{n\}}$ to denote the (obvious) subsets of $S$ where $I,J\subseteq[n-1]$ and $|I|=m,|J|=m-1$ consistently. Both $M(S_{\textbf{{Subset}}})$ and $M(S^{\prime}_{\textbf{{Subset}}})$ are mixtures. We have the following decompositions, where the latter is further decomposed into two parts depending on whether $n$ is selected.

It’s not in a ready shape to use Lemma 28. We need to further break the summands by carefully creating copies of the components. Let

That is, we create $m$ copies of each subset of $[n-1]$ of cardinality $m$ and collect as $\mathcal{I}$; create $n-m$ copies of each subset of $[n]$ of cardinality $m$ that includes $n$ and collect as $\mathcal{J}$. Now we claim two things

There is a bijection $F:\mathcal{I}\to\mathcal{J}$ such that $F(I)$ differs from $I$ by one element for all $I\in\mathcal{I}$.

Let $p_{I}=\frac{1}{\binom{n-1}{m}m}$ for all $I\in\mathcal{I}$ and $\gamma=\frac{m}{n}$. Then

Now we are ready to use Lemma 28: the collection $\{P_{i}\}$ is $\{M(S_{I})\}$ and $\{Q_{i}\}$ is $\{M(S_{F(I)})$. The conclusion is exactly (5).

Next we turn our attention to the proofs of the two claims.

For claim 2, (8) is easier and we only show (9). Since we have created copies, by splitting the summands of (7), we have

which are elementary combination identities. ∎

Renyi-DP and moments accountant are closely related concepts that are often considered identical. However, our results suggest that there is a distinction. The above pair of $P,Q$ we constructed are not necessarily attaining the Renyi-DP bounds (see a concrete example from Zhu and Wang , but as moments accountant focuses only on computing $(\epsilon,\delta)$-DP, it suffices use the Renyi-divergence functions $R_{\alpha}(P\|Q)$. Specifically, this closes the constant gap between the moments accountant for subsampled mechanisms and Poisson sampled mechanisms.

C.4 Other schemes in privacy-amplification for dominating pairs

Theorem 6 provides new results and a novel composition algorithm for the popular Poisson sampling under “add/remove” neighboring relations by treating “add” and “remove” separately. It also shows that the same result hold in a not-so-typical but practically relevant scheme of the random-subset sampled mechanism under the “add / remove” neighboring relation for the case when the base mechanism’s privacy is defined by the “replace” neighboring relation.

To avoid any confusion, for all practical purposes, the result in Theorem 6 suffices because we can always compose “Add” or “Remove” separately and only take the pointwise maximum in the end, while only incurring twice as much computation, but the results in this section are interesting from a purely scientific perspective and they are included for the completeness in our understanding of the problem.

If $(P,Q)$ is a dominating pair of $\mathcal{M}$ under “Add/remove” Relation, then

under the “Add/Remove” relation. Similarly, if $(P,Q)$ is a dominating pair of $\mathcal{M}$ under “Replace” relation for dataset of size $\gamma n$, then

under “Replace” relation for dataset of size $n$.

We plot $H_{\alpha}((1-\gamma)Q+\gamma P,Q)$ and $H_{\alpha}(P,(1-\gamma)P+\gamma Q)$ for $\delta_{\mathcal{M}\circ S_{\textbf{Poisson}}}(\alpha)$ in Figure 4(a).

1𝛾𝑄𝛾𝑃𝑄H_{\alpha}((1-\gamma)Q+\gamma P,Q) dominates the region $\alpha\geq 1$ and $H_{\alpha}(P,(1-\gamma)P+\gamma Q)$ dominates the region $\alpha<1$. The proof of the above result requires the use of the following general result that establishes the relationship between pairs that dominate only one half of the range for $\alpha$ and those that dominate the other half.

Let $\mathcal{M}$ be a mechanism and $\simeq$ be a symmetric neighboring relationships , i.e., $D\simeq D^{\prime}\Leftrightarrow D\simeq D^{\prime}$. Then

If $(P,Q)$ is a dominating pair of $\mathcal{M}$, then $(Q,P)$ is also a dominating pair of $\mathcal{M}$,

If $\sup_{D\simeq D^{\prime}}H_{\alpha}(\mathcal{M}(D)\|\mathcal{M}(D^{\prime}))\leq\min\{H_{\alpha}(P\|Q),H_{\alpha}(Q\|P)\}\text{ for all }\alpha\geq 1$, then $(P,Q)$ and $(Q,P)$ are both dominating pairs of $\mathcal{M}$.

The following two statements are equivalent.

$\sup_{D\simeq D^{\prime}}H_{\alpha}(\mathcal{M}(D)\|\mathcal{M}(D^{\prime}))\leq H_{\alpha}(P\|Q)\text{ for all }\alpha\geq 1.$

$\sup_{D\simeq D^{\prime}}H_{\alpha}(\mathcal{M}(D)\|\mathcal{M}(D^{\prime}))\leq H_{\alpha}(Q\|P)\text{ for all }0<\alpha\leq 1.$

First notice that the first and second statements are both implied by the third. For the first statement, notice that by the definition of the dominating pair, the upper bound applies for all $\alpha>0$. Thus by applying $(a)\Rightarrow(b)$ and $(b)\Rightarrow(a)$ for $(P,Q)$, we get that $(Q,P)$ is also a dominating pair. For the second statement, we apply $(a)\Rightarrow(b)$ for both $(P,Q)$ and $(Q,P)$, then the result extends the bound to the full range.

It remains to prove the third statement. For any pair of neighboring $D,D^{\prime}$ and $0<\alpha\leq 1$, by Lemma 45.

where the inequality uses the fact that $\alpha^{-1}\geq 1$, $\simeq$ is symmetric, and that $(P,Q)$ dominates for order $\geq 1$. The converse follows the same argument but starts with $\alpha>1$. ∎

We first prove the case for $\alpha\geq 1$. By Theorem 8 of [Balle et al., 2018] (Standard amplification by sampling bound in DP), we know that for any $D\simeq_{\textbf{add/remove}}D^{\prime}$ and all $\epsilon\geq 0$ (thus $\alpha\geq 1$!)

where the inequality in the second line is due to that $(P,Q)$ is a dominating pair of $\mathcal{M}$.

The same proof works line by line for the random subset sampling when we use Theorem 9 of [Balle et al., 2018] instead and adopt the $D\simeq_{\textbf{replace}}D^{\prime}$ neighboring relationship.

Next we prove the statement for $0<\alpha<1$. Check that we can apply Lemma 30 because both $\simeq_{\textbf{replace}}$ and $\simeq_{\textbf{add/remove}}$ are symmetric. By the third statement of Lemma 30, $(Q,(1-\gamma)Q+\gamma P)$ dominates the subsampled mechanism for $0<\alpha<1$. Also by the first statement of Lemma 30 we know that $(Q,P)$ is also a dominating pair for $\mathcal{M}$, thus by repeating the same argument, we get that $(P,(1-\gamma)P+\gamma Q)$ also dominates the subsampled mechanism for $0<\alpha<1$, which completes the proof. ∎

The above discussion characterizes the tightThey are tight for the reason we described in the Remark on the “Exact optimality of the bounds” above. upper bound of the privacy profile of subsampled mechanisms using two (ordered) pairs of distributions, rather than just one pair. This is insufficient for us to apply the composition theorem because the region between $\alpha>1$ and $\alpha<1$ in some sense “mixes with each other” during composition, as we have clearly seen from the proof of Theorem 10. What we do know is that neither $((1-\gamma)Q+\gamma P,Q)$ nor $(Q,(1-\gamma)Q+\gamma P)$ is a dominating pair for the sampled mechanism under “Add/Remove” or “Replace” neighboring relation. This is the reason why we proposed the more elegant approach for handling “add” and “remove” separately in the first place.

For completeness, and to also handle the case when we want the “replace one” neighboring relation for $\mathcal{M}\circ S_{\textbf{Subset}}$, we state the following result which constructs an explicit but not-so-clean dominating pair.

where \big{[}\cdot\big{]}^{*} denotes the Fenchel conjugate of a function.

The proof, which we omit, is a direct application of Proposition 29 with the generic approach of Proposition 9 for constructing the dominating pair.

Appendix D The characteristic function of basic mechanisms

We now derive $\phi$-function for three basic mechanisms: randomized response, Laplace and Gaussian mechanism. The results and their dominating distributions are summarized in Table 2.

Let $f$ be a predicate, i.e., $f:\mathcal{D}^{*}\to\{0,1\}$. The Randomized Response mechanism for $f$ is defined as

The $\phi$ function of Randomized Response mechanism $\mathcal{M}$ with the parameter $p$ satisfies $\phi_{\mathcal{M}}(\alpha)=\phi\textquoteright_{\mathcal{M}}(\alpha)=pe^{\alpha i\log(\frac{p}{1-p})}+(1-p)e^{\alpha i\log(\frac{1-p}{p}).}$

First of all, the dominating pair will be:

Then, follow the definition of $\phi$-function, we have

For Laplace and Gaussian mechanisms, we assume that $f:\mathcal{D}^{*}\to\mathcal{R}$ is a function of sensitivity 1.

we consider the dominating distribution $P(o)=\frac{1}{2\lambda}\exp(-|o|/\lambda)$ and $Q(o)=\frac{1}{2\lambda}\exp(-|o-1|/\lambda)$. We can show that the dominating pair for $\alpha\geq 1$ also dominates $0<\alpha<1$ using the third statement of Lemma 30 and the symmetry of Laplace mechanism. To calcuate the characteristic function $\phi_{\mathcal{M}}$, we define the privacy loss RV $L_{P,Q}$ as follows

The characteristic function $\phi_{\mathcal{M}}(\alpha)$ is calculated as follows

Similarly, for $\phi^{\prime}_{\mathcal{M}}$, we define privacy loss RV $L_{Q,P}$ as follows

Let Gaussian mechanism is defined as $\mathcal{M}(D)=f(D)+\mathcal{N}(0,\sigma^{2})$. For any $\alpha\in\mathcal{R}$ and $\sigma>0$, we have $\phi_{\mathcal{M}}(\alpha)=\phi\textquoteright_{\mathcal{M}}(\alpha)=e^{\frac{-1}{2\sigma^{2}}(\alpha^{2}-i\alpha)}.$

For Gaussian mechanism, no matter what the dimensionality of the output sapce is, the dominating distributions will always be 1D, and that extends to subsampled-gaussian as well. In the proof, we consider the worst-case pair $p(o)=\frac{1}{\sqrt{2\pi\sigma^{2}}}e^{-\frac{(o-1)^{2}}{2\sigma^{2}}},q(o)=\frac{1}{\sqrt{2\pi\sigma^{2}}}e^{-\frac{o^{2}}{2\sigma^{2}}}$.

Follow the definion of privacy loss RV, we have $L_{P,Q}(o)=\frac{2o-1}{2\sigma^{2}}$ and $L_{Q,P}(o)=\frac{1-2o}{2\sigma^{2}}$. Then we have

Besides basic mechanisms, all mechanisms with discrete outputs admit an analytical $\phi$ function by definition.

Let $p,q$ be the probability mass function induced by $\mathcal{M}$,

This function can be represented by two vectors that lists the probability masses at $o$ from $p$ and $q$. When evaluating $\log\phi_{\mathcal{M}}(\alpha)$ at a given $\alpha$, we could use the log-sum-exp trick to improve the numerical stability. Overall the space and time in representing these functions are linear in the size of the output space.

Provided that the worst-case pair of distributions are known, this procedure allows us to compose over exponential mechanisms [McSherry and Talwar, 2007], Report-noisy-max, as well as other complex mechanisms that arise out of post-processing of continuous output mechanisms, e.g., NoisyScreening [Zhu et al., 2020] that had been used as a practical alternative to sparse vector techniques.

D.2 Handling probability mass at ∞\infty

One of the motivations of the work is for us to handle the situations where there is a non-zero probability mass where the privacy loss r.v. is at infinity. This naturally happens in propose-test-rease-style algorithm [Dwork and Lei, 2009] where we first construct a differentially private upper bound of the local sensitivity (or other data-dependent quantities) then calibrate noise according to the local sensitivity. The issue is that there is always a non-zero probability where the upper bound is not valid. Standard $(\epsilon,\delta)$-DP handles this case at ease, but modern techniques such as RDP struggles as such a mechanism does not satisfy RDP for any $\alpha>0$.

In this case, Lemma 5 can be more explicitly rewritten into.

Let $D,D^{\prime}$ be the worst-case pair of datasets for $\mathcal{M}$, and $P=\mathcal{M}(D),Q=\mathcal{M}(D^{\prime})$ then

Let $L_{P,Q^{\prime}}^{(1)},...,L_{P,Q^{\prime}}^{(k)}$ be the privacy loss R.V. of mechanism $\mathcal{M}_{1},...,\mathcal{M}_{k}$ ($L_{Q^{\prime},P}^{(i)}$ is defined analogously). Then, the $\delta_{P}(\epsilon)$ and $\delta_{Q}(\epsilon)$ of the composed mechansims are as follow:

The above essentially says that we can handle the cases with $\infty$ separately, and compose the characteristic function of the sub-probability measure that excludes $\infty$.

Appendix E ϕitalic-ϕ\phi-function with discretization and experimental details

There are cases when the closed-form $\phi$-functions do not exist. For example, in the subsample mechanisms, the privacy loss distribution is complicated and continuous, suggesting that we cannot derive an exact closed-form expression naively. In this section, we first provide a discretization-based solution and analyze its error bound. Later, we develop an efficient approximation method, “Double quadrature”.

The main challenge in approximating $\phi$-function for continuous mechanisms is that an upper/lower bound of $\phi$-function does not necessarily attain the upper/lower bound of privacy costs. Motivated by recent work [Koskela et al., 2021] that truncates the privacy loss R.V. range to discretize subsample Gaussian mechanism, we consider discretizing the output domain. Our choice on the output domain instead of the privacy loss R.V. range is because many recent advances in communication-efficient private learning require the output space to be discrete. Note that the output domain is the output domain of the dominating pair. There always exists a one-dimension tightly dominating pair for any mechanisms as we have shown in the main results. The approximation procedure given in Algorithm 2 takes as input a truncated output domain $[-S,S]\subset\mathcal{O}$, the partition parameter $N$ and the pdf measure of two privacy loss random variables. The algorithm first introduces the grid approximation of privacy loss RVs using the following definition.

Given $N$ equidistant points $o_{1},...,o_{N}$ over the interval $[-S,S]$, We define $L_{P,Q}^{-}(o_{j})=\min_{t\in[j-1,j]}L_{P,Q}(o_{t})\text{ and }L_{P,Q}^{+}(o_{j})=\max_{t\in[j-1,j]}L_{P,Q}(o_{t})$ as the grid approximation of the original privacy loss R.V., where $L_{P,Q}(o_{t})$ denotes the density of $L_{P,Q}$ when evaluated at $o_{t}$.

$L_{Q,P}^{-}(o_{j})$ and $L_{Q,P}^{+}(o_{j})$ are defined analogously. Next, the algorithm constructs $\phi$-function approximations $\phi_{\mathcal{M}_{P}}^{-}$ and $\phi_{\mathcal{M}_{Q}}^{-}$ using similar ideas as that in Definition 35, except that we replace privacy loss R.V. with their approximation alternatives. The idea behinds the approximation is to construct Riemann sum style lower and upper bounds of $\delta_{\mathcal{M}}(\epsilon)$ using sampled points in the output interval. We formalize the idea using the following lemma.

Consider the truncation parameter goes to infinity, i.e., $S\to\infty,$ and privacy loss random variable $L_{P,Q}$ and $L_{Q,P}$ is a monotonical function of the output random variable $o$. We have for all $\epsilon>0$, the privacy profile $\delta(\epsilon)$ of a continuous mechanism $\mathcal{M}$ is bounded by

where $\delta_{\mathcal{M}_{min}}(\epsilon)$ is constructed using Algorithm 1 with$(\phi^{-}_{\mathcal{M}_{P}},\phi^{-}_{\mathcal{M}_{Q}})$ pair and $\delta_{\mathcal{M}_{max}}(\epsilon)$ is constructed using $(\phi^{+}_{\mathcal{M}_{P}},\phi^{+}_{\mathcal{M}_{Q}})$ pair.

The proof sketch is first to show that the CDF $F_{L_{P,Q}}(\epsilon)$ is always smaller bounded by $F_{L_{P,Q}^{-}}(\epsilon)$ when the monotonical condition is satisfied. Then we rewrite the privacy profile into the CDF forms and demonstrate that a larger CDF leads to a smaller $\delta$ for any $\epsilon>0$.

Note that the indicator function preserves the monotonic property, which implies that we can lower bound $F_{L_{P,Q}}(\epsilon)$ using the left Riemann sum. Analogously, the CDF $F_{L_{Q,P}}(-\epsilon)$ is smaller than $F_{L^{-}_{Q,P}}(-\epsilon)$ for all $\epsilon>0$. Therefore, we have

The following corollary allows us to upper and lower bound privacy cost over composition.

Consider a simple composition of $\mathcal{M}_{1}$ and $\mathcal{M}_{2}$ on datasets $D$ and $D^{\prime}$, we have

We overload the $L_{P,Q}$ to denote the privacy R.V. over composition. The lower bound of the CDF $F_{L_{P,Q}}$ is given as follows:

Gaussian quadrature: We apply Gaussian quadrature to efficiently evaluate integral in computing CDFs. Note that the integral is defined over an infinite integral (see Theorem 17), we will use the following lemma to convert the integral range to $$ before we apply Gaussian quadrature.

Let $f(x)$ is defined over the infinite interval. We have

By a change of variables, we can convert the infinite integral to a finite integral, which can be easily implemented using numerical integration methods.

Double quadrature: To improve the time complexity of Algorithm 2, which is linear with a sufficiently large $N$, we next apply Gaussian quadrature to approximate $\phi$-function when its closed-form expression is not available. We call this algorithm “Double quadrature”, as we use it twice, one is in the approximation for $\phi$-function, and another is for the CDF computation. In the experiment section, we show that the “Double quadrature” algorithm matches the Fourier Accountant approach [Koskela and Honkela, 2021] while only samples hundreds of points in evaluating Poisson Subsample Mechanisms.

In this section, we provide the end-to-end error analysis of AFA by looking into the following three scenarios.

$\phi$-functions have closed-form expressions.

$\phi$-functions with discretization is used (see Algorithm 2).

Double quadrature algorithm: $\phi$-function is approximated using Gaussian quarature.

Error analysis closed-form $\phi$ functions. When we have closed-form $\phi$-functions (see Exp1 and Exp2), the numerical error is only caused by the quadrature method, which is used to convert $\phi$-function to CDFs. Therefore, we can tap into the classical results from numerical analysis that bounds the error in quadrature methods (see, e.g., Chapter 7 of Conte and de Boor “Elementary Numerical Analysis”) with an asymptotic scaling more or less $O(1/n^{\alpha})$ for integrating an $\alpha$th times differentiable functions, and faster for more advanced rules, see the following Lemma.

[Stoer and Bulirsch, 2002] Let the function $f(\cdot)$ has $2n$ continuous derivatives over the integral $[a,b]$ and $n$ is the number sample points. We have the error estimate

From a practical standpoint, “Scipy.integrate” allows us to specify a desired error tolerance (e.g., $O(10^{-14})$ used in experiments). The error induced in CDFs will be amplified by $e^{\epsilon}$ in the final $\delta(\epsilon)$ evaluation according to Lemma 5, which is still negligible in practice. The inverse ($\epsilon$ as a function of $\delta$) requires an additional binary search, which calls $\delta(\epsilon)$ a handful of times.

In the cases when the $\phi$-function does not have a closed-form expression, we proposed two approaches to approximate the -function: Algorithm 2 and Double Quadrature. In Algorithm 2, we discretize the support of the dominating pairs using an equispaced grid approximation.

Error analysis with approximated $\phi$ functions. We analyzed the error caused by truncation, approximation of Algorithm 2 as follows.

The error caused by truncation (ignore $o\geq S$ or $o\leq-S$).

The error arising from Riemann Sum approximation.

The error caused by using Gaussian quadrature to compute CDF.

The first two errors arising from the approximation of $\phi$-function and the third error is the numerical error when we apply Gaussian quadrature to compute the integral in privacy profile. The third term is often negligible as we discuss earlier. When $p$ and $q$ are determined, we bound the tail integral $\int_{S}^{\infty}\max(p(o),q(o))do$ and $\int_{-S}^{-\infty}\max(p(o),q(o))do$ using the Chernoff bound and denote it is upper bounded by $\delta_{tail}$. Then a union bound over $k$ compositions will bound all bad events that the output happens to be out of $[-S,S]^{k}$. Lastly, we estimate the total error by subtracting and adding $k\delta_{tail}$ to the lower and the upper Riemann sums bound, respectively.

Double Quadrature For the second approach — adaptive approximation via double quadrature, we do not have an asymptotic analysis of the bounds but ‘scipy.integrate.dblquad’ does provide us valid bounds. The “double quadrature” approach is the best-performing algorithm we recommend in practice.

E.2 Experimental details in Exp 3

Theorem 6 allows us to consider the following one dimensionthe error analysis of the $(P,(1-\gamma)P+\gamma Q)$ dominating pair is similar distribution as the worst-case pair neighboring distribution for the Poisson subsampling Gaussian mechanism.

Therefore, the pairing privacy loss RV is given by

We cannot derive a closed-form expression of $\phi$-function naively for the above privacy loss RVs. Therefore, we consider the discretization method (Algorithm 2) to approximate the Poisson subsampling.

We set $S=100$ and $N=10^{5}$ to discretize the exact integral of $o$, which is $[-\infty,\infty]$ for the Gaussian mechanism. We use $\gamma=0.01$ and $\sigma=2.0$, for number of compositions up to $1500$. We now provide the error analysis of our Poisson subsample Gaussian experiments. Recall the error analysis in Theorem 43, we first bound the error caused by truncation (ignore $o\geq S$ or $o\leq-S$).

The error caused by trunction consists of the tail integral $t_{1}:=\int_{S}^{\infty}\max(p(o),q(o))do$ and $t_{2}:=\int_{-S}^{-\infty}\max(p(o),q(o))do$. We can upper bound $t_{1}$ and $t_{2}$ using the tail bound of Gaussian distribution.

We use $\delta_{tail}$ to denote the failure probability when $o$ happens to be out of the range $[-S,S]$. Here, we have $\delta_{tail}\leq e^{\frac{S^{2}}{-2\sigma^{2}}}+e^{\frac{(S-1)^{2}}{-2\sigma^{2}}}$. Substituting $S=100,k=1500$ and $\sigma=2.0$ into Theorem 43, we have $k\cdot\delta_{tail}$ is upper bounded by $e^{-1000}$, which is neglectable in the $\delta$ term. For the error caused by discretization, we plot the valid lower and upper bound using Algorithm 2.