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.


extfieldsofstudy:
Computer Science
Mathematics

text:
Efficient Receive Beamformers for Secure Spatial Modulation Against a Malicious Full-Duplex Attacker With Eavesdropping Ability

In this paper, we consider a new secure spatial modulation scenario with a full-duplex (FD) malicious attacker Mallory owning eavesdropping capacity, where Mallory works on FD model and transmits a malicious jamming such as artificial noise (AN) to interfere with Bob. To suppress the malicious jamming on Bob from Mallory, a conventional maximum receive power (Max-RP) at Bob is presented firstly. Subsequently, to exploit the colored property of noise plus interference at Bob, a whitening-filter-based Max-RP (Max-WFRP) is proposed with an obvious performance enhancement over Max-RP. To completely remove the malicious jamming from Mallory, a Max-RP with a constraint of forcing the malicious jamming from Mallory to zero at Bob is proposed. To further improve secrecy rate (SR) by removing the ZF contraint (ZFC), the maximum signal-to-jamming-plus-noise ratio (Max-SJNR) is proposed. Our proposed methods have closed-form expressions. From simulation results, the four receive beamforming methods have an increasing order in performance: Max-RP, Max-RP with ZFC and Max-SJNR$\approx$Max-WFRP. Additionally, the latter two harvest a substantial performance gains over Max-RP and Max-RP with ZFC in the low and medium signal-to-noise ratio regions.

I. INTRODUCTION
In multiple-input multiple-output (MIMO) systems, spatial modulation (SM) [1] is a promising technology which exploits both the index of activated antenna and amplitude phase modulation (APM) symbol to transmit messages. Recently, SM has exhibited its benefits of increasing energy efficiency [2] and avoiding the inner-channel interference (ICI). However, due to the broadcasting characteristic of wireless transmission, confidential information might be eavesdropped by illegal receivers. This is a problem of physical layer security [3]- [7]. In [6], the author enhance the legitimate security by joint precoding optimization with and without eavesdroppong channel state information (CSI) . In [8], [9], security is enhanced by emitting the artificial noise (AN) onto the null-space of the desired channel to interfere unknown eavesdropper and the latter derived the closed-form approximated expression ESR with the aid of AN in perfect and imperfect CSI, respectively. In [10], the authors emit the AN by a full-duplex desired receiver, where the confidential information is received and at the same time efficiently interfere the eavesdropper. Moreover, the authors in [11] investigate the power allocation between confidential message and AN so that we can get a fixed power allocation factor to achieve higher SR performance.
As for secure SM, the authors in [12], [13] investigate the transmit antenna selection (TAS) schemes, the former proposed leakage-based and Max-SR schemes achieving a good balance between complexity and SR performance, and the latter selected two antennas each time to improve SR performance. In [14], the author proposed three active antennagroup (AAG) selection methods which performed well in the low, medium and high SNR regions with low complexity, respectively. In [15], the author jointly optimized the problem of maximizing SR over TAS and AN projection with joint and separate solutions. Meanwhile, the author in [16] proposed deterministic and random antenna selection methods with the aid of zero-forcing precoding and fast radio-frequency switches to enhance the security of the PSM system. However, in the aforementioned literature, the illegal receivers are all passive eavesdroppers, which only receive confidential message (CM) and don't emit malicious jamming to the desired receiver. In such a situation, Bob cannot measure the CSI from Eve to Bob. It is impractical to know the CSIs from Alice to Eve and Eve to Bob in advance. If Eve becomes Mallory, which means it can send a malicious jamming towards Bob, this dilemma will disappear. Why? Due to the fact that Mallory emits jamming, Bob can estimate the CSI from Mallory to Bob. These estimated CSI can be used to suppress the jamming from Mallory. Similarly, Alice also obtain the CSI from Alice to Mallory, and prevent the interception from Eve with the help of AN. To simplify the derivation process, the perfect CSIs from Mallory and Alice to Bob are available in the following.
Considering the worst scenario, we propose a novel secure SM (FDM-SSM) system with a FD malicious attacker Mallory having eavesdropping ability. In our FDM-SSM system, Mallory can simultaneously send malicious jamming signal and intercept the CMs from Alice. Therefore, how to optimize the receive beamforming (RBF) such that the malicious jamming is reduced efficiently and the performance is improved obviously is a challenging issue. This motivates us to propose several RBF methods, and our main contributions are summarized as follows: 1) To suppress the malicious interference from Mallory and achieve a high performance, the traditional maximum receive power (Max-RP) at Bob method is first presented via the system. However, consider the noise plus interference at Bob includes three parts: AN from Alice, malicious jamming from Mallory and receiver noise at Bob, which obviously is colored, the conventional Max-RP doesn't exploit this colored property. Therefore, we propose an improved whitening-filter-based Max-RP (Max-WFRP). First, we compute the covariance matrix of colored noise plus interference at Bob, multiply the original receive vector at Bob from left by the root of the inverse of covariance matrix to whiten the colored jamming plus noise. By simulation, we find the proposed Max-WFRP harvests substantial performance gains over the conventional Max-RP in terms of SR and BER. 2) To completely eliminate the malicious jamming signal from Mallory, a Max-RP with zero-forcing constraint (ZFC) is proposed to force the malicious jamming from Mallory to zero and meanwhile maximize the receive power of CMs at Bob. However, due to the strict ZFC, the transmit space of CMs is also reduced dramatically. To remove the ZFC, a maximum signalto-jamming-plus-noise ratio (Max-SJNR) is proposed to strike a good balance between suppressing jamming and improving performance. From simulation results, the proposed Max-SJNR performs much better than the proposed Max-RP with ZFC in terms of SR and BER performance.
The rest of this paper is organized as follows. Section II presents the FDM-SSM system model and gives a definition for its average SR. In Section III, the RBF schemes for Max-SR are proposed and their closed-form expression is given. In Section IV, numerical simulation results are presented. Finally, we draw our conclusions in Section V.

II. SYSTEM MODEL
As shown in Fig. 1, the FDM-SSM system considered consists of a legal transmitter (Alice) with N transmit antennas (TAs),a receiver (Bob) with N b receive antennas (RAs), and a FD malicious (Mallory) with N m antennas. Here, Mallory works on FD model. In other words, he intercepts the CMs from Alice and transmits a malicious jamming towards Bob.
In general, it is noted that N is not a power of 2. For a SM system, the number of active antennas are chosen from N , where N t is equal to 2 ⌊log 2 N ⌋ . And Alice activates one of N t TAs to emit M -ary APM symbol and uses the index of activated antenna to convey spatial bits. As a result, log 2 N t M bits per channel use can be transmitted. The transmit signal with the aid of AN from Alice and the jamming signal sent from Mallory can be expressed as and respectively, where β ∈ [0, 1] is the power allocation factor and P denotes the total transmit power of Alice. Accordingly, e n is the nth column of I Nt , indicating that the ith antenna is chosen to transmit symbol s m , which is equiprobably drawn from discrete M -ary APM constellation for m ∈ {1, 2, · · · , M } with E|s m | 2 = 1. Moreover, matrix P AN ∈ C Nt×Nt is the AN projection matrix and n a ∼ CN (0, σ 2 a I Nt ) is the AN vector. In (2), P M is the transmit power of Mallory and and M ∈ C Nm×Nm denote the channel gain matrices from Alice to Bob, from Alice to Mallory, from Mallory to Bob, and Mallory's self-interference, respectively. Then the receive signal at Bob and Mallory after receive beamforming can be respectively expressed as and where u br ∈ C N b ×1 and u er ∈ C Ner×1 are the receive beamforming vectors at Bob and Mallory. In addition, n b ∼ CN (0, σ 2 b I N b ) and n e ∼ CN (0, σ 2 e I Ne ) denote the complex additive white Gaussian noise (AWGN) vectors at Bob and Mallory, respectively. Meanwhile, T ∈ R N ×Nt is the transmit antennas selection matrix constituted by the specially selected N t columns of I N , which is determined by the leakagebased method in [12]. In (4), √ P M u H er MP JM n m is the selfinterference observed at Mallory. Consider Mallory design the matrix P JM by null-space projection method, i.e., P JM is the null-space of the RBF u er with N ′ m ≤ N m − 1. As a result, Mallory can eliminate the self-interference. The average SR is given as where and where and According to [8], it is known that premultiplying y b by W −1/2 B will not change the mutual information, which results in I(x; y b ) = I(x; y ′ b ) and I(x; y e ) = I(x; y ′ e ).

III. PROPOSED THREE RECEIVE BEAMFORMING SCHEMES AT BOB
For the newly proposed FDM-SSM system, the design of receive beamforming at Bob is very important to improve the system performance. In this section, the conventional Max-RP is presented, and three high-performance RBF schemes are proposed as follows: Max-WFRP, Max-RP with ZFC, and Max-SJNR. Finally, complexity comparison is made among them.

A. Conventional Max-RP
As mentioned in Section II, E[s m s * m ] = 1, u H br u br = 1 and e n is the nth column of I Nt . To simplify the above optimization, w is approximated as a white noise, i.e., E[ww H ] = σ 2 ω I N b , (10) can be rewritten as Hence, the optimization problem of Max-SJNR reduces to which actually is a Max-RP. The Lagrangian function associated with the above optimization is defined as whose first-order derivative with respect to u br is set to be zero as follows which means the fact that u br is the eigenvector corresponding to the largest eigen-value of the matrix HTT H H H .

B. Proposed Max-WFRP
In fact, the malicious jamming signal plus interference plus noise w is colored not white. Therefore, the conventional Max-RP method in Subsection A may not perform optimally in terms of SNR. In what follows, we propose the Max-WFRP method, which first whitens the colored noise plus interference at Bob using their covariance matrix, and then apply Max-RP method to maximize the average SNR.
As n a , n m and n b are the independent and identically distributed i.e.,i.i.d, random vectors, w has a mean vector of all-zeros and covariance matrix Observing (15), it is evident that the covariance matrix R b is a positive definite matrix, its eigenvalue decomposition (EVD) is in the form R w = U w ΛU H w , where U w is an N b ×N b unitary matrix, and Λ = is a diagonal matrix diag(d 1 , · · · d N b ) with d i being the ith eigenvalue of matrix R w . Let us define the WF matrix satisfying W WF W H WF = R −1 w , which yields where Applying the WF matrix in (16) on y B = √ βP HTe n s m +ω yields a new system model, where w ′ has covariance matrix E(w ′ w ′H ) = I N b . Similar to (12), we have the form of Max-WFRP max u br Hence, u br can be set to be the eigenvector to the largest eigen-value of the matrix W F HTT H H H W H F .

C. Proposed Max-RP with ZFC
In order to completely eliminate the malicious jamming from Mallory, in that follows, we propose the ZF method of maximizing the receive power of confidential messages at Bob by projecting the malicious jamming signal onto the null-space of channel matrix from Alice to Bob. The corresponding Max-RP with ZFC optimization problem is formalized as To simplify the above optimization, let us define a new matrix F ′ = FP JM , and its singular value decomposition (SVD) is where U ⊥ spans the null-space of the column space of matrix F ′ . Now, to remove the first constraint, let us introduce a new beamforming vector u ′ br as follows u br = U ⊥ u ′ br , which satisfies u H br F ′ = 0 1×N ′ m . Substituting the above equation in (19) forms the following unstrained optimization Using the generalized Rayleigh-Ritz theorem, the new beamforming vector u ′H br is directly equal to the eigenvector corresponding to the largest eigen-value of the matrix i.e., η(A). Accordingly, the optimal value of u br is given by

D. Proposed Max-SJNR
The ZF constraint in (19) is extremely strict and reduces the degrees of freedom of transmit space of CMs. Below, after this constraint is removed, a Max-SJNR is proposed to maximize the average SJNR, which can make a good balance between reducing the malicious jamming and improving the performance, where SJNR is defined as Using the generalized Rayleigh-Ritz theorem, the beamforming vector u br of maximizing the SJNR can be directly obtained from the eigenvector corresponding to the largest eigen-value of the matrix Actually, the Max-SJNR is equivalent to the Max-WFRP proposed by us, which will be verified in the next section.

E. Computational Complexity Analysis
Now, the approximate computational complexities of the four RBF methods are analyzed. First, the complexity of the traditional Max-RP method is about C Max−RP = O(129N 3 b ) floating-point operations (FLOPs). For the proposed Max-WFRP, its computational complexity is approximated as Besides, the computational complexity of the proposed Max-SJNR is approximated asC Max−SJNR = O(268N 3 b + 3N b ), which is slightly higher than proposed Max-WFRP method. Generally, their complexities have an increasing order as follows: Max-RP, Max-RP with ZFC, Max-WFRP, Max-SJNR.

IV. SIMULATION AND DISCUSSION
In this section, numerical simulations are presented to make a performance comparison among three proposed methods and conventional Max-RP from three different aspects: average SR, cumulative density function (CDF) of SR and the BER. Simulation parameters are set as follows: N b = 6, N t = 8, P = 10W, σ 2 b = σ 2 e , and modulation scheme being QPSK. Fig. 2 plots the curves of SR versus SNR for two different interference power: P M = 1W and P M = 10W. From Fig. 2, it is seen that the proposed Max-WFRP and Max-SJNR methods perform much better than Max-RP with ZFC and Max-RP. The conventional Max-RP is the worst one among all beamformers in terms of SR due to the fact that it omits the colored property of noise plus interference at Bob. Conversely, Max-WFRP achieves the best one among four methods. Additionally, the SR performance of the proposed Max-RP with ZFC method approaches those of Max-SJNR, Max-WFRP, and conventional Max-RP in the high SNR region. In summary, they have an increasing order in SR performance: Max-RP, Max-RP with ZFC, and Max-WFRP≈ Max-SJNR. Fig. 3 illustrates the curves of average BER versus SNR for the above four methods. From Fig. 3, it is seen that the proposed Max-SJNR and the proposed Max-WFRP still obviously exceed the remaining two methods Max-RP with SNR(dB) ZFC and conventional Max-RP in terms of BER performance. Similarly, Max-SJNR is still overlapped with Max-WFRP and the performance difference between them is trivial. In particular, as SNR increases, the BER performance gains achieved by Max-WFRP and Max-SJNR over Max-RP with ZFC and conventional Max-RP become more significant. Similar to Fig. 2, there is the same increasing order in BER performance: Max-RP, Max-RP with ZFC, and Max-WFRP≈ Max-SJNR. Fig. 4 shows the CDF curves of SR for the four methods with two different value of SNRs: -5dB and 5dB. From Fig. 4 , we find the same performance tendency as shown in Fig. 3.

V. CONCLUSION
In this paper, we have made an investigation of RBF methods in the newly proposed SSM system with a malicious full-duplex attacker having an eavedropping ability. First, the conventional Max-RP method was derived to design RBF, after that, three high-performance RBF design methods, Max-WFRP, Max-RP with ZF constraint, and Max-SJNR have been proposed to improve the SR performance of the system. From simulation results, the proposed Max-WFRP achieves the same performance as Max-SJNR. They are much better than conventional Max-RP and Max-RP with ZFC in terms of SR and BER performance and have the same order computational complexity as Max-RP and Max-RP with ZFC. Interestingly, the proposed Max-WFRP has a slightly lower complexity compared to the proposed Max-SJNR.


extfieldsofstudy:
Computer Science
Engineering

text:
Policy Augmentation: An Exploration Strategy for Faster Convergence of Deep Reinforcement Learning Algorithms

Despite advancements in deep reinforcement learning algorithms, developing an effective exploration strategy is still an open problem. Most existing exploration strategies either are based on simple heuristics, or require the model of the environment, or train additional deep neural networks to generate imagination-augmented paths. In this paper, a revolutionary algorithm, called Policy Augmentation, is introduced. Policy Augmentation is based on a newly developed inductive matrix completion method. The proposed algorithm augments the values of unexplored state-action pairs, helping the agent take actions that will result in high-value returns while the agent is in the early episodes. Training deep reinforcement learning algorithms with high-value rollouts leads to the faster convergence of deep reinforcement learning algorithms. Our experiments show the superior performance of Policy Augmentation. The code can be found at: https://github.com/arashmahyari/PolicyAugmentation.

INTRODUCTION
Reinforcement learning (RL) has shown significant success in recent years [1,2,3,4,5]. RL studies how an agent can maximize its cumulative rewards in a previously unknown environment through experience. RL algorithms maximize their long-term cumulative rewards by exploring new states, and their short-term (immediate) cumulative rewards by exploiting their learned policy.
The main challenge with RL algorithms is balancing between exploration and exploitation. While exploitation is critical to maximize the agent's immediate reward, the exploration ensures that the agent's overall (long-term) reward is maximized. Agents must explore most states to learn which states are more rewarding. However, the random exploration of the environment leads to a long convergence time. Depending on the problem and the environment, RL algorithms may require millions of episodes to explore all states and learn the policy. The -greedy algorithm-a simple exploration strategy-takes either random actions (exploration) or actions according to the policy (exploitation). The simple strategies such as -greedy well behave in situations where the reward is well-shaped. In more complicated tasks with sparse rewards, these strategies are not efficient.
More recently, several exploration strategies, e.g., curiositydriven exploration [6], count-based exploration [7], etc., have been proposed to improve the exploration of RL algorithms. The Uniform sampling strategy draws a random sample uniformly from the stored samples to update the action-value function-Q functions [2]. Trust region policy optimization (TRPO) was proposed to generate a number of trajectories and randomly select a subset of states from these trajectories [8]. The count-based exploration strategy [7] encourages agents to explore the less-visited states. These algorithms fail to perform optimally for tasks with sparse rewards. Besides, they simulate the future returns of rollout sets according to the current approximated policy. The performance of these algorithms depends on the approximated action-value functions according to previously explored state-action pairs. While these strategies are different from each other, they share a common idea that agents must be encouraged to visit less-explored states. These strategies take actions randomly from less-visited states, which may or may not lead to a reward. The existing exploration strategies do not encourage exploring state-action pairs that will return higher values.
In this paper, we propose Policy Augmentation to predict the values of unexplored state-action pairs by augmenting the action-value function, Q, using Inductive Matrix Completion (IMC). Matrix completion recovers the underlying low-rank matrix from a given subset of its entities [9]. IMC extends this idea to the association inference prediction using the available side information about the columns and rows of the underlying low-dimensional matrix [10]. In this paper, IMC recovers the Q function from the limited observed entities-the limited number of explored state-action pairs-using the features of states and actions. Figure 1 shows an example of recovered Q function for the Mountain car environment. The agent, then, takes actions according to the recovered action-value functions-the augmented policy. Taking actions according to the recovered Q function results in generating high-value rollouts for training deep reinforcement learning (DRL) algorithms. The purpose of Policy Augmentation is to generate high-value rollouts and train the agent with them during early episodes, which reduces the training time significantly. After training with high-value rollouts, the agent explores and exploits according to the existing DRL approaches, e.g., Proximal Policy Optimization (PPO) [11]. Fig. 3.a shows the classical Mountain Car control problem [12]. The environment is described in details in Section 4. The optimal policy must accelerate to the right when the car moves in the direction of the positive velocity, and accelerate to the left when the car is moving in the direction of the negative velocity. The existing exploration methods may apply negative, positive, or zero force when the car moves in the direction of the positive velocity. Policy Augmentation explores the pairs that are predicted to have high values, e.g., positive force in the direction of the positive velocity. Our proposed strategy is different from [13], in that our method requires neither training nor the model of the environment, whereas the deep learning model used in [13] requires training.

REINFORCEMENT LEARNING
An infinite-horizon discounted Markov decision process (MDP) is defined by (S ; A ; P, r, ρ 0 , γ), where S is a set of finite states, A is a finite set of actions, P : S ×A ×S → R is the transition probability distribution, r : S → R is the reward function, ρ 0 : S → R is the distribution of the initial state s 0 , and γ ∈ (0, 1) is the discount factor.
Let π represents the stochastic policy of an agent that maps the action a t for a given s t to the future state s t+1 , and R(π) represents the expected discounted reward of the policy: , and s t+1 ∼ P(s t+1 |s t , a t ). The stateaction value function, Q π , is defined as [14]: An agent interacts with an environment by sequentially selecting actions, observing states, and receiving rewards to find the optimal policy that maximizes the cumulative discounted reward R t = ∞ l=0 γ l r t+l . Different algorithms have been proposed to approximate Q π (s t , a t ), e.g., Q-Learning, Deep Q-Learning [14,1]:

PROPOSED METHOD
In this section, we describe the proposed exploration strategy with Policy Augmentation. The goal of the proposed method is to augment the policy based on what the agent has experienced so far using IMC methods. Our assumption is that the agent has neither any previous experiences, nor the model of the environment. We describes the proposed IMC method for recovering the Q function in Section 3.1.
The goal of IMC methods is to recover the underlying low-rank matrix representation of the action-value function from the values of a small given subset of state-action pairs. If either state spaces or action spaces are continuous, we use hashing, e.g., SimHash function [7], to discretize their spaces and form the Q matrix.
Let Q ∈ R M ×N be the actual action-value matrix that the agent will learn, andQ ∈ R M ×N represents the recovered action-value function by the IMC method, where M is the total number of states and N is the total number of actions. Let Ω t represents the set of the observed entities of the action-value matrix-Q Ωt -at time step t, and Q Ωt (s, a) refers to the value of the state s and action a. After each time step, the agent receives a reward from the environment, R t+1 , that changes the value of either an observed entity of Q t or add a new member to the observed set Ω t .
IMC methods incorporate additional information about actions and states, making them appropriate for predicting the values of state-action pairs that have not been explored. Let X ∈ R M ×m and Y ∈ R N ×n represent the state and action features (additional information), respectively. The sth row of X represents the features of the sth state, and the ath row of Y is the features of the ath action. Algorithm 1 shows the proposed exploration strategy for training DRL algorithms. The strategy gets the DRL algorithm, state and action features (X and Y ), the total number of time steps (τ ), and initial state s 0 as its input. Because the goal is to generate high-value rollouts during the early episodes, we set a threshold τ e . The proposed algorithm uses the recovered augmentedQ to take actions while t < τ e . During this time period, DRL collects high-value rollouts for training. For t > τ e , the exploration and exploitation of RL Take a t , receive s t+1 and r t .

11
Collect rollouts for training the DRL algorithm. 12 if t < τ q then 13 UpdateQ t using Eq. 1 and Q t (s, a) = Q t (s, a)/N q t (s, a).
14 Initialize U t and V t . 15 repeat 16 Update U t using Eq.3.

18
until convergence criterion is met; 19 Augment the policyQ = X T U t V T t Y T . 20 Train the DRL algorithm using the rollouts. 21 end agents is similar to other previously proposed methods, e.g., PPO, TROPO, Curiosity-based, etc. Note that Policy Augmentation cannot replace a learned policy by DRL because it is only a prediction. It is used during the first τ e episodes.
The main assumption of matrix completion and IMC methods is that the underlying matrix-Q function-is low rank. Thus, we calculate the IMC method for the first τ q steps (τ q < τ e ) while the Q function is still low-rank. As the agent visits more state-action pairs, the rank of the Q increases. The computational complexity of the proposed method is associated with the complexity of the proposed IMC method.

Policy Augmentation
The proposed IMC method recovers the Q function from a given set of observed state-action pairs. We assume that Q t is a low-rank matrix (during the first τ q time steps) while the agent is in the early stages of exploration and the set Ω t is very small: |Ω t | M × N , where |Ω t | is the size of the set Ω t . The normalized state-action value matrix is written asQ t = XW t Y T , where W t is an unknown, low-rank matrix W t = U t V T t ∈ R m×n with the unknown rank r min(m, n). Our goal is to recoverQ t fromQ Ωt by solving min Ut,Vt [9]. There exists a unique solution to this optimization problem if at least nm log(nm) state-action values are explored [15], and U t and V t are incoherent [16] 1 . 1 Interested readers may refer to [15,16] for the proof.
The contribution of our proposed IMC method is that it racks the changing set Ω t as new pairs are revealed during the exploration. Moreover, the values of the observed set Ω t changes with time because the agent receives more rewards (either positive, negative, or neutral) from the environment for repeating the previously taken actions (Eq. 1). Following the definition in [17,9,18], we consider Q 1 ,Q 2 , . . . ,Q t as a set of linear subspaces on the Grassmann manifold, forming a geodesic.Q i is a point in the Grassmann manifold and is represented as a pair (U i , V i ) [16,9]. At each time step, only one element of Q t is changing. Thus, the linear subspaces ofQ t−1 andQ t remain close to each other. The distance between two subspaces is defined by the canonical distance (geodesic or arc-length distance) [16]. We use a set of principal angles {θ j } r j=1 , r = min(m, n) to quantify d(U t , U t−1 ) and d(V t , V t−1 ) as the projection distance: . The augmented action-value matrix,Q is recovered by minimizing the cost function J with respect to U t and V t [10]: By taking the partial derivative of the cost function J with respect to U t and V t and set them to zero [9], the closed form expressions are obtained. Then, the values of U t and V t are updated iteratively similar to [10]. The matrices U t and V t are initialized with random dense matrices. The algorithms updates U t and V t in Eq.3 and 4 alternatively until the convergence criteria meets.
where (i, j) indicates the element of the matrix in the ith row and the jth column. We selected λ 1 = λ 2 = 1 here.

RESULTS
The OpenAI Gym toolkit [20] and the Stable-baseline package [21] are used to evaluate the proposed algorithm. Two environments, Mountain Car and CartPole, are selected. Policy Augmentation is integrated with Proximal Policy Optimization (PPO) [11] (PPO+ Policy Augmentation), and Deep Q-Learning (DQN) [1] (DQN+ Policy Augmentation). The performances of PPO+Policy Augmentation and DQN+Policy Augmentation are compared with PPO [11], DQN [1], PPO+ Counting [7], and AttA2C (Att+ Curiosity) [22] in both environments. The experiment is repeated 10 times with 10 random initialization, and each time for 2, 500, 000 rollouts. The performances of different methods and exploration strategies are compared using their cumulative rewards. Because the  We used Car Position and Car Velocity as the columns of X (state features), and Y = [−10 + , 0 + , 10 + ] T . epsilon is a small non-zero value, e.g., 1, that prevents multiplying W by zero. Figure 3.b shows the cumulative rewards of different agents. The darker lines represent the mean of the cumulative rewards of 10 repetitions, and the shaded areas represent one standard deviation of the cumulative rewards over 10 repetitions. The PPO+ Policy Augmentation and the DQN+Policy Augmentation have the best and the second best performances, respectively. Other methods are not able to generate high-value rollouts during the first 100 episodes.
The experiments showed that the performance of the proposed Policy Augmentation exploration strategy depends on the first taken action. In the beginning, the Q matrix is zero and the agent chooses randomly an action from all zerovalued actions. The estimation ofQ values are affected by which action is taken in the first step. To achieve a superior performance, the proposed strategy observes the cumulative reward. If the cumulative rewards during the first few episodes are below a predefined value, Q is reset to zero and the agent takes a new action randomly.

CONCLUSION
Policy Augmentation predicts the values of unexplored stateaction pairs using IMC methods. By taking actions at early stages according to the predicted state-action values, agents collect rollouts with high values. Deep reinforcement learning algorithms trained with the high-value rollouts learn policies faster than existing exploration strategies. Policy Augmentation results in faster training of deep reinforcement learning algorithms, which makes deploying deep reinforcement learning algorithms in new environments more practical.
Future work will consider developing more computationally efficient IMC algorithms that update the previously augmented policy after each step from the new observed entity. The future work will also develop DRL algorithms that balance the number of high-value and low-value rollouts for training in environments with sparse rewards.