Optimal Accounting of Differential Privacy via Characteristic Function

Characterizing the privacy degradation over compositions, i.e., privacy accounting, is a fundamental topic in differential privacy (DP) with many applications to differentially private machine learning and federated learning. We propose a unification of recent advances (Renyi DP, privacy profiles, $f$-DP and the PLD formalism) via the \emph{characteristic function} ($\phi$-function) of a certain \emph{dominating} privacy loss random variable. We show that our approach allows \emph{natural} adaptive composition like Renyi DP, provides \emph{exactly tight} privacy accounting like PLD, and can be (often \emph{losslessly}) converted to privacy profile and $f$-DP, thus providing $(\epsilon,\delta)$-DP guarantees and interpretable tradeoff functions. Algorithmically, we propose an \emph{analytical Fourier accountant} that represents the \emph{complex} logarithm of $\phi$-functions symbolically and uses Gaussian quadrature for numerical computation. On several popular DP mechanisms and their subsampled counterparts, we demonstrate the flexibility and tightness of our approach in theory and experiments.


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).

Functional view Pros
Cons Renyi DP [Mironov, 2017] D α (P Q) ≤ (α), ∀α ≥ 1 Natural composition lossy conversion to ( , δ)-DP. Privacy profile [Balle and Wang, 2018] E q [( p q − e ) + ] ≤ δ(e ), ∀ ≥ 0 Interpretable. messy composition. f -DP [Dong et al., 2021] Trade-off function f Interpretable, CLT messy composition. PLD [Sommer et al., 2019, Koskela et al., 2020 Probability density of log(p/q) Natural composition via FFT Limited applicability. 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 ( , δ)-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. 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 φ 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 ( , δ)-DP [Dwork et al., 2010]; Kairouz et al. [2015] provides the optimal k-fold composition of an ( , δ)-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 ( i , δ 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 ( , δ)-DP type composition would allow [Bun and Steinke, 2016].
Definition 3 (Trade-off function). Let φ be a classifier to distinguish two distributions P and Q using a sample. α φ be its Type I error (false positive rate) and β φ be its Type II error (false negative rate). The tradeoff function T P,Q (α) : [0, 1] → [0, 1] is defined to be T P,Q (α) := inf φ {β φ | α φ ≤ α}. . 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.  We highlight that in all these definitions, it is required for the bound to cover all pairs of neighboring datasets D, D .
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 M. For instance, the privacy profile δ M ( ) upper bounds the HS-divergence for all and the f -DP lowerbounds the tradeoff function for all Type I error α (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.
The main advantage of RDP is that it composes naturally over multiple adaptively chosen mechanisms via a straightforward rule M 1 ×M 2 ≤ M 1 + M 2 . It recovers the advanced composition when converting to ( , δ)-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 the RDP and f -DP of a Gaussian mechanism with (normalized) σ = 1, and a randomized response mechanism with p = 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 α. 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 ( , δ)-DP of GM cannot be achieved by a conversion from RDP. 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.
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 ( , δ)-DP by converting from RDP.
The answer is unfortunately "no". The reasons are twofolds. First, there are mechanisms with non-trivial ( , δ)-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 ( , δ)-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 ( , δ)-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 σ = 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 ( , δ)-DP, this example shows that while both RR and GM satisfy an RDP with (α) = α 2 , GM obeys (0.277, 0.3)-DP but RR does not satisfy ( , 0.3)-DP with < 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 ( , δ)-DP with stable numerical algorithms and provable error bounds [Koskela et al., 2020[Koskela et al., , 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 2 . 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 ( , δ)-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 mechanismspecific privacy accounting for ( , δ)-DP with a data-structure that allows natural composition.

Dominating pair of distributions, composition and subsampling
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.
Definition 7 (Dominating pair of distributions). We say that (P, Q) is a dominating pair of distributions for M (under neighboring relation ) if for all α ≥ 0 3 (1) When P, Q is chosen such that (1) takes "=" for all α, we say that (P, Q) is a tight dominating pair of distributions or simply, tightly dominating. If in addition, there exists a neighboring (D,D ) such that (M(D), M(D )) is tightly dominating, and then we say (D,D ) is the worst-case pair of datasets for mechanism M.
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 Proposition 8. Any mechanism has a tightly dominating pair of distributions.
For example, the domintating pair for discrete Gaussian mechanism (DGM) [Canonne et al., 2020] will be two discrete Gaussian, e.g., P = N Z(0, σ 2 ), Q = N Z(∆, σ 2 ), ∆ ∈ Z + is the sensitivity of the integer-valued query. This follows because the probability mass of the discrete Gaussian is a log-concave sequence.
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 [0, 1]. 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 26 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.
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.
Poisson Sampling Denoted by S γ Poisson . S γ Poisson takes a dataset of arbitrary size and return a dataset by including each data point with probability 0 ≤ γ ≤ 1 i.i.d. at random.

Subset Sampling Denoted by S γ
Subset . S γ Subset takes a dataset with size n or n − 1 and return a subset of size m < n uniformly at random. We define γ := m/n as a short-hand. 5 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 expression 6 . Our choice of choosing α ≥ 0 in Definition 7 ensures that for any mechanism (P, Q) dominates for add neighbors iff (Q, P ) dominates for removal neighbors.
Theorem 11. Let M be a randomized algorithm.  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 (γP + (1 − γ)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 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.

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 ( , δ)-DP conversion, then conduct mechanism-specific accounting under ( , δ)-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.  Definition 12 (characteristic function of the privacy loss RV). Let (P, Q) be a dominating pair of M, and p, q be the probability density (or mass) function of P, Q. The two characteristic functions that describes the PLD are where i denotes the imaginary unit satisfying i 2 = −1 and α ∈ R.
PLDs are probability measures on the real line, and these φ-functions are Fourier transforms of these measures. We provide φ-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.
Advantages over MGF Comparing to the moment generating function used by the RDP, the characteristic function differs only in that we are taking the expectation of the complex exponential. At the price of bringing in complex arithmetics, it is now a complex-valued function supported on α ∈ R rather than the real-valued Renyi Divergence with order α > 1 as was defined in RDP. Unlike MGF, the characteristic function always exists and it characterizes the distribution of the privacy loss R.V., therefore it is always a lossless representation. MGF is also characteristic when it exists, but the conversion of MGF to the distribution function is numerically problematic [Epstein and Schotland, 2008].
Moreover, the adaptive composition over multiple heterogeneous mechanisms remains as straightforward as that of the RDP.
Proposition 13. Let M 1 and M 2 be two randomized algorithms. We have the φ-function of the composition (M 1 , M 2 ) with order α ∈ R satisfies: Lossless conversion rules. The φ-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 ( , δ)-DP. Specifically, for finding δ as a function of (i.e., privacy profile), we invoke the fourth equivalent definition of ( , δ)-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 φ-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.

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 13). 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 δ( ) query, the accountant first constructs two analytical CDFs (with respect to the privacy loss RV L P,Q and L Q,P ) using Theorem 18 in Appendix B. Then the conversion to ( , δ)-DP is obtained using Lemma 5. For computing given δ, we use bisection to solve δ M ( ) = δ.
if query ( , δ)-DP then 7: Compute the CDF F L P,Q (·) and F L Q,P (·) by integrating log φ (M) (α) and log φ (M) (α) using Theorem 18.  [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 ( , δ)-DP. This avoids the need for setting appropriate discretization parameters of FFT ahead of time before knowing which sequence M 1 , ..., 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.
Exp. 1 (Gaussian mechanism) We compare the privacy cost over compositions between RDP accountant and AFA accountant on Gaussian mechanism.
Exp. 2 (Compositions of discrete and continuous mechanisms) We evaluate the Fourier accountant variants and RDP accountant on heterogeneous mechanisms.
Exp. 3 (Compositions over Poisson Subsample mechanisms) Comparison of our AFA with discretizationbased φ-function to the Fourier accountant (FA) and the RDP accountant.
Observation: In Figure 3(a), our φ function-based AFA exactly matches the result from the analytical Gaussian mechanism and strictly outperforms the RDP accountant in different privacy regimes.
In Exp2, motivated by [Koskela and Honkela, 2021], we consider an adaptive composition of the with sensitivity 1, and eachM i is a randomized mechanism with probability p. We consider σ = 5.0, p = 0.52, = 2.0 and compare δ( ) between the RDP accountant, Fourier Accountant [Koskela and Honkela, 2021] and our AFA.
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 δ( ) 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 φ-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 φ-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 γ = 0.01, the noise scale is σ = 2.0 and we evaluate with δ = 10 −5 . We use the tighter conversion rule from Balle et al. [2020] to convert the RDP back to ( , δ)-DP. The numerical issues induced by Gaussian quadrature are at most O(10 −14 ). Our lower and upper bounds of δ( ) 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 φ-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 φ-functions. In Exp 2, each mechanism admits an analytical φ-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 δ( )" separately.
Let k denote the number of compositions. Regarding the runtime in the conversion to δ( ) query, we apply Gaussian quadrature to compute the CDF, which requires O( 1 δ 1/α err ) runtime complexity for the α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.

Privacy accountant
Composition runtime δ( ) conversion runtime Memory Choice of n

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 φ-functions. If the composed φ functions have large values at the tail of integral (e.g., near ∞), we need to sample more quadrature points. We hope to solve this issue using numerical tools in the next step.

Contents 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 α that implies stronger privacy guarantees.
We give two concrete examples below.
Example 14 (Distance-to-Instability). The stability-based argument of query release first add noise to a special integer-valued function dist q (D) which measures the number of data points to add / remove before the local sensitivity of query q(D) becomes non-zero. No matter that q is, dist q always has a global sensitivity of at most 1. The stability-based query release outputs ⊥ (nothing) if dist q (D) + Lap(1/ ) ≤ log(1/δ) / otherwise outputs the answer q(D) without adding noise. This algorithm is satisfies ( , δ)-DP [Thakurta and Smith, 2013], but since there is a probability mass at the +∞ for the case when q(D) = q(D ), RDP is +∞ for all α.
Example 15 (Gaussian-noise adding with data-dependent variance). 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, 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 ( , δ)-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.
Example 16 (Distance to Instability). Distance to instability dist q (D) is a special function that measures the number of data points to add / remove before the local sensitivity of query q(D) becomes non-zero. The stability-based query release outputs ⊥ (nothing) if dist q (D) + Lap(1/ ) ≤ log(1/δ) / otherwise outputs the answer q(D) without adding noise. In this algorithm, the privacy loss distribution has exactly two modes.
Mode 1 When dist q (D) > 0, then for all D neighboring to D, q(D) = q(D ), which implies that the PLD is from the post-processing of a Laplace mechanism (for releasing the perturbed dist q (D)), i.e., ( , 0)-DP.
Mode 2 When dist q (D) = 0, then for those neighboring D such that q(D) = q(D ), it must hold that dist q (D ) = 0, thus the privacy loss distribution is a point mass of 1 − δ at 0 (for outputting ⊥) and a point mass of δ at +∞, i.e., (0, δ)-DP.
Clearly, there is no single pair of datasets that attains the privacy-profile of this mechanism for all input parameter˜ . When˜ > , δ M (˜ ) = δ and is attained by the second mode. On the other hand, if we choose˜ such that δ Lap. Mech.(1/ ) (˜ ) > δ, then δ M (˜ ) = δ Lap. Mech.(1/ ) (˜ ) and the equal sign is attained by a pair of distributions in the first mode.

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.

HS-Divergence (Privacy-profile / CDF of PLD)
"Characteristic function" ( ) 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, ( , δ)-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 details 7 , a conversion from RDP to DP is about finding function δ(·) that upper bounds the Hockey-stick divergence for all pairs of neighboring datasets using an RDP function (·). In contrast, a conversion from Renyi divergence to hockey-stick divergence is about a given pair of P, Q, and the input function (α) is expected to be the exact Renyi-divergence of order α. 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 δ from a function . The seemingly harmless distinction of inequalities and identities is actually the devil in the details. It has two major consequences 1. 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".
2. DP conversion is lossy even when converting the statement "standard randomized response is 1-zCDP" to (ε, δ)-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 [2008].
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 α > 0, their hockey-stick 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 and G . 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.
• G (x) = e x F (x), which is stated as Lemma 47 in Appendix G.
• Using the above formula, φ can be obtained by the following process: φ

of Dong et al. [2021]
We now consider the conversion from the φ-function to CDFs using the following Levy's theorem.
Theorem 17 (Levy). Let φ be the ch.f. of the distribution function F and a < b, then To compute the CDF of the privacy loss RV L P,Q at b, we can substitude a with −∞ and obtain the following result.
Lemma 25. The characteristic functions are determined by the trade-off function f via the following formula: where ε ranges over the whole real line. By a simple change of variable, we see that h ∈ H iff there exists f ∈ F such that h(α) = 1 + f * (−α), or equivalently, Let G := {g : (−∞, 0] → R | g(0) = 0, g is convex, increasing, continuous and g(x) max{x, −1}}.
Claim: Convex conjugacy is a bijection between F and G.
Proof of the claim. Since both F and G consist of convex functions, double convex conjugacy brings back the function, it suffices to show that f ∈ F =⇒ f * ∈ G and g ∈ G =⇒ g * ∈ F. Now suppose f ∈ F. f is extended to be +∞ in (−∞, 0) and 0 in (1, +∞). Thus f is a convex function on R. By definition f * is convex, and we can calculate . This shows f * is monotone and finite on (−∞, 0]. Let It is straightforward to compute that Similarly, g is extended to be +∞ in (0, +∞). g * (y) = sup x 0 yx − g(x) and g * (y) = +∞ if y < 0. By a similar argument, g * is increasing. Since g I * , we have g * I * * = I. That is, g * (x) 1 − x. Let J be zero on (−∞, 0] and infinity otherwise. We have J * is zero on [0, +∞) and infinity otherwise. We know that g(0) = 0 and g is increasing so g J. Hence g * J * , i.e. g * (y) 0 if y 0. This justifies that g * (y) ∈ [0, 1] if y ∈ [0, 1] and g * (y) = 0 if y 1.
Now with the help of this claim, H and G are simply related: h ∈ H iff α → h(−α) − 1 is in G. Therefore we can get the description of 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. [2021].
Continuing with the notations in the proof above, when H satisfies the conditions, i.e. H ∈ H, we know there is a f ∈ F such that H(α) = 1 + f * (−α). Let g(α) = H(−α) − 1 and we will have g = f * and hence f = g * as f is convex. Therefore, 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.
Another interesting consequence of Lemma 9 is one can often get a stronger bound on the hockey-stick divergence or privacy profile for free. Recall that for a function g, its convex hull conv(g) (a.k.a., the lower convex envelope) is defined as the greatest convex lower bound of g and satisfies conv(g) = g * * where the double star means taking Fenchel conjugate twice.
For a function h : R + → R, let g(x) = inf y∈[0,x] h(y) and HS(h) = (min{1, g}) * * . It turns out that HS(h) is the greatest lower bound of h that lies in H, and we have Corollary 26 (Dominating pairs from any privacy profile upper bounds). If the privacy profile of a mechanism M is bounded by h : R + → R, i.e. δ M (α) h(α), ∀α 0, then δ M is also bounded by HS(h).
Note that HS(h) can be significantly smaller than the original bound h, and it admits a dominating pair by Proposition 9, even if h does not.

C.2 Composition theorem of dominating pairs
Theorem 27 (Restatement of Theorem 10 Adaptive composition of dominating pairs). Let P, Q be a dominating pair distributions for M and P , Q be a dominating pair distributions for M 8 , then (P × P , Q × Q ) is a dominating pair distributions for the composed mechanism (M, M ). Proof.
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 α M (D), M (D )
H α P × R, Q × S . We break it into the following two parts.
Starting from the first part, we have Continuing this argument, we have The proof is complete.

C.3 Privacy-amplification for dominating pairs
Recall we stated the following theorem in the main body: Theorem 11. Let M be a randomized algorithm.  The proof we present here is written in the language of trade-off functions [Dong et al., 2021]. However, with Lemma 20, everything can be conveniently translated to the language of (ε, δ). 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.
To see this, consider any testing rule φ such that E P [φ] = x. We need to show that .
Below we use notations such as S I , S J∪{n} to denote the ( It's not in a ready shape to use Lemma 29. We need to further break the summands by carefully creating copies of the components. Let Now we are ready to use Lemma 29: the collection . The conclusion is exactly (5).
Next we turn our attention to the proofs of the two claims.
For claim 1, let's first construct a (n − m)-to-one surjective mapF : is obtained by replacing the k-th element in I by n. We see that F (I (k) ) is indeed inJ . For any J ∪ {n} ∈J , it is hit byF exactly n − m times since the n could have been any of the (n − 1) − (m − 1) = n − m indices not already in J.
Since J contains n − m copies ofJ , the (n − m)-to-one mappingF : I →J can be "redirected" in an obvious way and become a bijection between I and J . By construction, F (I) and I differ in exactly one element.
Remark (Renyi DP and Optimal Moments Accountant for subsampled mechanisms). 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 [2019], but as moments accountant focuses only on computing ( , δ)-DP, it suffices use the Renyi-divergence functions R α (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 11 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.
What we left unspecified is whether there is a clean dominating pair under the two alternative schemes: (a) Poisson-sampling + "Add/remove" without treating "Add" or "Remove" separately; (b) Subset sampling + "Replace" neighboring relation for both M • Sample γ and M. It turns out that while we can construct these dominating pairs of M • Sample γ explicitly based on the dominating pair (P, Q) of M, but the expression is not simple. We present these results in this section.
To avoid any confusion, for all practical purposes, the result in Theorem 11 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.
Proposition 30. If (P, Q) is a dominating pair of M under "Add/remove" Relation, then under the "Add/Remove" relation. Similarly, if (P, Q) is a dominating pair of M under "Replace" relation for dataset of size γn, then under "Replace" relation for dataset of size n.
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 α and those that dominate the other half.
Lemma 31 (Properties for "symmetric neighbors"). Let M be a mechanism and be a symmetric 3. The following two statements are equivalent.
Proof. 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 α > 0. Thus by applying (a) ⇒ (b) and (b) ⇒ (a) for (P, Q), we get that (Q, P ) is also a dominating pair.
For the second statement, we apply (a) ⇒ (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 and 0 < α ≤ 1, by Lemma 46.
where the inequality uses the fact that α −1 ≥ 1, is symmetric, and that (P, Q) dominates for order ≥ 1. The converse follows the same argument but starts with α > 1.
Proof of Proposition 30. We first prove the case for α ≥ 1. By Theorem 8 of [Balle et al., 2018] (Standard amplification by sampling bound in DP), we know that for any D add/remove D and all ≥ 0 (thus α ≥ 1!) where the inequality in the second line is due to that (P, Q) is a dominating pair of 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 replace D neighboring relationship.
Next we prove the statement for 0 < α < 1. Check that we can apply Lemma 31 because both replace and add/remove are symmetric. By the third statement of Lemma 31, (Q, (1 − γ)Q + γP ) dominates the subsampled mechanism for 0 < α < 1. Also by the first statement of Lemma 31 we know that (Q, P ) is also a dominating pair for M, thus by repeating the same argument, we get that (P, (1 − γ)P + γQ) also dominates the subsampled mechanism for 0 < α < 1, which completes the proof.
The above discussion characterizes the tight 9 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 α > 1 and α < 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 − γ)Q + γP, Q) nor (Q, (1 − γ)Q + γ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 M • S Subset , we state the following result which constructs an explicit but not-so-clean dominating pair.
Corollary 32 (Dominating pair of sampled mechanisms under symmetric neighbor relations). Let (P, Q) be a dominating pair of M and is "Add/Remove" (or "Replace"). Then (P ,Q) is a dominating pair of M • S Poisson (or M • S Subset ) whereQ = Uniform[0, 1] andP has a CDF of where · * denotes the Fenchel conjugate of a function.
The proof, which we omit, is a direct application of Proposition 30 with the generic approach of Proposition 9 for constructing the dominating pair.

D.1 φ-function of basic mechanisms
We now derive φ-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 : D * → {0, 1}. The Randomized Response mechanism for f is defined as Proof. First of all, the dominating pair will be: For Laplace and Gaussian mechanisms, we assume that f : D * → R is a function of sensitivity 1.

Lemma 34 (Laplace Mechanism). Let Laplace Mechanism for f is defined as M(D) = f (D)+Lap(λ)
where Lap(λ) is Laplace dstribution with scale λ, i.e., its density function is 1 2λ exp(−|x|/λ). For any α ∈ R and λ > 0, we have Proof. we consider the dominating distribution P (o) = 1 2λ exp(−|o|/λ) and Q(o) = 1 2λ exp(−|o−1|/λ). We can show that the dominating pair for α ≥ 1 also dominates 0 < α < 1 using the third statement of Lemma 31 and the symmetry of Laplace mechanism. To calcuate the characteristic function φ M , we define the privacy loss RV L P,Q as follows The characteristic function φ M (α) is calculated as follows Similarly, for φ M , we define privacy loss RV L Q,P as follows Proof. 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 Follow the definion of privacy loss RV, we have L P,Q (o) = 2o−1 2σ 2 and L Q,P (o) = 1−2o 2σ 2 . Then we have Besides basic mechanisms, all mechanisms with discrete outputs admit an analytical φ function by definition.
Definition 36 (φ-function of mechanisms with discrete outputs). Let p, q be the probability mass function induced by M, This function can be represented by two vectors that lists the probability masses at o from p and q. When evaluating log φ M (α) at a given α, 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 ∞
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-testrease-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 ( , δ)-DP handles this case at ease, but modern techniques such as RDP struggles as such a mechanism does not satisfy RDP for any α > 0.
In this case, Lemma 5 can be more explicitly rewritten into.
P,Q be the privacy loss R.V. of mechanism M 1 , ..., M k (L (i) Q ,P is defined analogously). Then, the δ P ( ) and δ Q ( ) of the composed mechansims are as follow: whereL P,Q is defined as the privacy loss R.V. of the composed mechanisms that excludes ∞.
The above essentially says that we can handle the cases with ∞ separately, and compose the characteristic function of the sub-probability measure that excludes ∞.

E φ-function with discretization and experimental details
There are cases when the closed-form φ-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 φ-function for continuous mechanisms is that an upper/lower bound of φ-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] ⊂ 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. L − Q,P (o j ) and L + Q,P (o j ) are defined analogously. Next, the algorithm constructs φ-function approximations φ − M P and φ − M Q using similar ideas as that in Definition 36, 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 δ M ( ) using sampled points in the output interval. We formalize the idea using the following lemma.
Lemma 40. Consider the truncation parameter goes to infinity, i.e., S → ∞, 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 > 0, the privacy profile δ( ) of a continuous mechanism M is bounded by Proof. The proof sketch is first to show that the CDF F L P,Q ( ) is always smaller bounded by F L − P,Q ( ) 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 δ for any > 0.
Note that the indicator function preserves the monotonic property, which implies that we can lower bound F L P,Q ( ) using the left Riemann sum. Analogously, the CDF F L Q,P (− ) is smaller than The following corollary allows us to upper and lower bound privacy cost over composition.
Corollary 41. Consider a simple composition of M 1 and M 2 on datasets D and D , we have

E.2 Experimental details in Exp 3
Theorem 11 allows us to consider the following one dimension 10 distribution as the worst-case pair neighboring distribution for the Poisson subsampling Gaussian mechanism.
Therefore, the pairing privacy loss RV is given by L P,Q = log γe 2o−1 2σ 2 + 1 − γ , L Q,P = − log γe 2o−1 2σ 2 + 1 − γ We cannot derive a closed-form expression of φ-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 [−∞, ∞] for the Gaussian mechanism. We use γ = 0.01 and σ = 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 44, we first bound the error caused by truncation (ignore o ≥ S or o ≤ −S). The first inequality is because p(o) is a mixture of two Gaussian distribution N (0, σ 2 ) and N (1, σ 2 ). We use δ tail to denote the failure probability when o happens to be out of the range [−S, S]. Here, we have δ tail ≤ e S 2 −2σ 2 + e (S−1) 2 −2σ 2 . Substituting S = 100, k = 1500 and σ = 2.0 into Theorem 44, we have k · δ tail is upper bounded by e −1000 , which is neglectable in the δ term. For the error caused by discretization, we plot the valid lower and upper bound using Algorithm 2.
In "Double quadrature", we apply Gaussian quadrature to compute φ(M) and φ (M) directly. That is, we apply Gaussian quadrature to solve the integration F An "optimal" Renyi DP to DP conversion?
In this section, we provide the detailed description of how we generated the improved "optimal" conversion rule in Figure 1 based on an extension of the technique of Balle et al. [2020].
Then one can further convert this f -DP to ( , δ)-DP according to our formula in Section B (originally due to [Dong et al., 2021].) The main improvement that we propose is to consider the mechanism specific version of the same conversion rule, which converts the RDP function M (·) satisfied by a mechanism M to an f -DP of M, which involves taking the pointwise maximum of all f functions implied by each (α, M (α))-RDP.
The key to obtain the conversion that we have shown in Figure 1 was to consider and extended version of RDP that also includes 0 < α < 1, which we find to have a nontrivial effect in the resulting tradeoff function.
In the remainder of the section, we will first explain how the two-stage conversion works in Section F.1 and Section F.2 and then comment on whether the rule can be improved in Section F.3.

F.1 RDP to f -DP
The hypothesis testing interpretation (f -DP) of RDP is not entirely tight. Here we present a simplified derivation of the tradeoff function f implied by RDP via closedness to post-processing.
Consider any hypothesis testing procedure h : O → {0, 1} that uses the output o of an (α, )-RDP mechanism. "1" denotes "Rejecting the null hypothesis" that individual z is not in the dataset, indicating that h predicts that z is in the dataset. "0" denotes the complement event of "Failing to reject the null hypothesis", indicating that h predicts that z is not in the dataset. By the closure to post-processing property, h(o) satisfies (α, )-RDP. By definition of RDP, for all pairs of neighboring datasets that induce distributions p, q.
Let q be the distribution where individual z is not in the dataset and p otherwise. Let x denote the probability of false positive (Type I error)z is not in the dataset but the prediction is 1; and y denote the probability of false negative (Type II error)z is in the dataset but the prediction is 0.
Note that the only difference from the case when α > 1 is the direction of the inequality. Also note that the symmetry of the two inequalities ensures that it suffices to consider α ≥ 0.5 11 .
The f-DP of a mechanism satisfying (α)-RDP for a family α is therefore the pointwise maximum of the resulting f function for all α.
Lemma 45. Let f be the lower bound of Type II error given Type I error, then mechanisms that satisfy fDP with function f also obeys a family of ( (x), δ(x))-DP for all x ∈ [0, 1] such that where ∂f (x) is any subgradient of f at x. Recall that by definition of subgradient, g is a subgradient of f at x if for all y ∈ Dom(f ), f (y) ≥ f (x) + g · (y − x) (note that Dom(f ) = [0, 1] for trade-off function f ).
Numerically stable computation of given δ or δ given involves working with ∂f and 1 − f in logarithmic scale. Specifically, we find x such that there exists subgradient g ∈ ∂f (x) such that log(δ) ≥ log(e log(1−f (x)) − e log(−g)+log(x) ).
Then it is true that (δ) = log(−g). In fact, a more general procedure finds an x (why any feasible x works is left as an exercise) such that ∂f (x) contains g satisfying (14). It then follows that (δ) = min g∈∂f (x) log(−g).
In other word, provided that log(1 − f (x)) and log(−∂f (x)) admit an analytical implementation, we can convert f -DP to ( , δ)-DP in a numerically stable fashion. The second identity can be proved similarly.