Hypothesis Testing Interpretations and Renyi Differential Privacy

Introduction

Differential privacy [Dwork et al., 2006] is a formal notion of data privacy that enables accurate statistical analyses on populations while preserving privacy for individuals contributing their data. Differential privacy is supported by a rich theory, with sophisticated algorithms for common data analysis tasks and composition theorems to simplify the design and formal analysis of new private algorithms. This theory has helped make differential privacy a de facto standard for privacy-preserving data analysis. Over the last years, differential privacy has found use in the private sector [Kenthapadi et al., 2019] by companies such as Google [Erlingsson et al., 2014, Papernot et al., 2018], Apple [team at Apple, 2017], and Uber [Johnson et al., 2018], and in the public sector by agencies such as the U.S. Census Bureau [Abowd, 2018, Garfinkel et al., 2018].

A common challenge faced across all uses of differential privacy is to explain its guarantees to users and policy makers. Indeed, differential privacy first emerged in the theoretical computer science community, and was only subsequently considered in other research areas interested in data privacy. For this reason, several works have attempted to provide different interpretations of the semantics of differential privacy in an effort to make it more accessible.

One approach that has been particularly successful, especially when introducing differential privacy to people versed in statistical data analysis, is the hypothesis testing interpretation of differential privacy [Wasserman and Zhou, 2010, Kairouz et al., 2015]. One can imagine an experiment where one wants to test, based on the output of a differentially private mechanism, the null hypothesis that an individual $I$ has contributed her data to a particular dataset $x_{0}$. One can also imagine that an alternative hypothesis is that the individual $I$ has not contributed her data. Then, the definition of differential privacy guarantees—and is in fact equivalent to requiring—that every hypothesis test has either low significance (it has a high rate of Type I errors), or low power (it has a high rate of Type II errors). Under this interpretation, the privacy parameters $(\epsilon,\delta)$ control the tradeoff between significance and power.

Recently, several variants of differential privacy have been proposed [Dwork and Rothblum, 2016, Bun and Steinke, 2016, Mironov, 2017, Bun et al., 2018, Dong et al., 2019]. Most of these new privacy definitions have been proposed as privacy notions with better composition properties than differential privacy. Having better composition can become a key advantage when a high number of data accesses is needed for a single analysis (e.g., in private deep learning [Abadi et al., 2016]). Technically, many of these variants are formulated as bounds on the Rényi divergence between the distribution obtained when running a private mechanism over a dataset where an individual $I$ has contributed her data versus the case when the private mechanism is run over the dataset where $I$’s data is removed.

In this work we develop some analytical tools to study the hypothesis testing interpretation of privacy definitions based on statistical divergences. The first notion we introduce is the concept of $k$-cut of a divergence. Intuitively this notion corresponds to restricting the distributions that are input to a divergence to a finite domain of cardinality $k$. We can think about the functions implementing the restrictions as (probabilistic) decision rules with $k$ possible outcomes. The second notion we introduce is the concept of $k$-generatedness for a divergence. Intuitively, a divergence is $k$-generated if it is equal to its $k$-cut. This notion expresses the number of decisions that are needed in decision rules to fully characterize the divergence.

We use these two analytical tools to show that a privacy definition based on a divergence has an hypothesis testing interpretation if and only if it is $2$-generated. We show that the divergence characterizing differential privacy is indeed $2$-generated and that the notion of $2$-generatedness corresponds to the notion of privacy regions introduced in [Kairouz et al., 2015]. On the negative side we show formally that variants of differential privacy based on the Rényi divergence do not admit directly a hypothesis testing interpretation because the Rényi divergence is exactly $\infty$-generated (where by $\infty$ we mean that it is infinitely, but countably generated). Nevertheless, we show that one can achieve the hypothesis testing interpretation by considering the $2$-cut of the Rényi divergence. Intuitively, this says that to characterize relaxations of differential privacy based on the Rényi divergence through an experiment similar to the one used in the hypothesis testing interpretation, one needs either to restrict the distinguishability power of the divergence or to consider an infinite number of possible hypothesis. This shows a semantics separation between standard differential privacy and relaxations based on Rényi divergence.

In addition, we use the analytical tools we develop to study the relations between different privacy definitions. Specifically, we use the $2$-cut of Rényi divergence to give better conversion rules from Rényi differential privacy to $(\epsilon,\delta)$-differential privacy, and to study the relations with Gaussian Differential Privacy [Dong et al., 2019] another formal definition of privacy inspired by the hypothesis testing interpretation which was recently proposed.

Finally, we study a sufficient condition to guarantee that a divergence is $k$-generated: divergences defined as a supremum of a quasi-convex function $F$ over probabilities of $k$-partitions are $k$-generated. This allows one to construct divergences supporting the hypothesis testing interpretation by requiring them to be defined through an function $F$ giving a $2$-generated divergence. The condition is also necessary for quasi-convex divergences, characterizing $k$-generation for all quasi-convex divergences.

We first introduce the notions of $k$-cut and $k$-generatedness for divergences. These notions allow one to measure the power of divergences in terms of the number of possible decisions that are needed in a test to fully characterize the divergence.

We show that the divergence used to characterize differential privacy is $2$-generated, supporting the usual hypothesis testing interpretation of differential privacy

We show that Rényi divergence is $\infty$-generated, ruling out a direct hypothesis testing interpretation for privacy notions based on it. Nevertheless, we show that one can achieve the hypothesis testing interpretation by considering the $2$-cut of Rényi divergence.

We use our analytic tools to study other notions of privacy and to give better conversion rules between Rényi differential privacy and $(\epsilon,\delta)$-differential privacy.

We give sufficient and necessary conditions for a quasi-convex divergence to be $k$-generated.

Background: hypothesis testing, privacy, and Rényi divergences

[Wasserman and Zhou, 2010, Kairouz et al., 2015] proposed a useful interpretation of this guarantee in terms of hypothesis testing. Suppose that $x_{0}$ and $x_{1}$ are adjacent inputs. The observer sees the output $y$ of running a private mechanism $\mathcal{M}$ on one of these inputs—but does not see the particular input—and wants to guess whether the input was $x_{0}$ or $x_{1}$.

In the terminology of hypothesis testing, let $y\in Y$ be an output of a randomized mechanism $\mathcal{M}$, and take the following null and alternative hypotheses:

H0 : $y$ came from $\mathcal{M}(x_{0})$, H1 : $y$ came from $\mathcal{M}(x_{1})$.

One simple way of deciding between the two hypotheses is to fix a rejection region $S\subseteq Y$; if the observation $y$ is in $S$ then the null hypothesis is rejected, and if the observation $y$ is not in $S$ then the null hypothesis is not rejected. This is an example of a deterministic decision rule.

Each decision rule can err in two possible ways. A false alarm (i.e. Type I error) is when the null hypothesis is true but rejected. This error rate is defined as ${\tt PFA}(x_{0},x_{1},\mathcal{M},S)\stackrel{{\scriptstyle\mathsf{def}}}{{=}}\mathsf{Pr}[\mathcal{M}(x_{0})\in S]$. On the other hand, the decision rule may incorrectly fail to reject the null hypothesis, a false negative (i.e. Type II error). The probability of missed detection is defined as ${\tt PMD}(x_{0},x_{1},\mathcal{M},S)\stackrel{{\scriptstyle\mathsf{def}}}{{=}}\mathsf{Pr}[\mathcal{M}(x_{1})\notin S]$. There is a natural tradeoff between these two errors—a rule with a larger rejection region will be less likely to incorrectly fail to reject but more likely to incorrectly reject, while a rule with a smaller rejection region will be less likely to incorrectly reject but more likely to incorrectly fail to reject.

Differential privacy can now be reformulated in terms of these error rates.

Intuitively, the lower bound on the sum of the two error rates means that no decision rule is capable of achieving low Type I error and low Type II error simultaneously. Thus, the output distributions from any two adjacent inputs are statistically hard to distinguish.

Following [Kairouz et al., 2015], we can also reformulate the definition of differential privacy in terms of a privacy region describing the attainable pairs of Type I and Type II errors.

where the privacy region $R(\varepsilon,\delta)$ is defined as:

Since the original introduction of differential privacy, researchers have proposed several other variants based on Rényi divergence. The central question of this paper is: can we give similar hypothesis testing interpretations to these (and other) variants of differential privacy?

2 Variants of differential privacy based on Rényi divergence

We recall here notions of differential privacy based on Rényi divergence.

Let $\alpha>1$. The Rényi divergence of order $\alpha$ between two probability distributions $\mu_{1}$ and $\mu_{2}$ on a space $X$ is defined by:

The above definition does not consider the cases $\alpha=1$ and $\alpha=+\infty$. However we can see $D^{\alpha}_{X}$ as a function of $\alpha$ for fixed distributions and consider the limits to get:

The first limit is the well-known KL divergence, while the second limit is the max divergence that bounds the pointwise ratio of probabilities; standard $(\varepsilon,0)$-differential privacy bounds this divergence on distributions from adjacent inputs.

There are several notions of differential privacy based on Rényi divergence, differing in whether the bound holds for all orders $\alpha$ or just some orders. The first notion we consider is Rényi Differential Privacy (RDP) [Mironov, 2017].

Renyi Differential privacy considers a fixed value of $\alpha$. In contrast, zero-Concentrated Differential Privacy (zCDP) [Bun and Steinke, 2016], a simplification of Concentrated Differential Privacy (CDP) [Dwork and Rothblum, 2016], quantifies over all possible $\alpha>1$.

Truncated Concentrated Differential Privacy (tCDP) [Bun et al., 2018] quantifies over all $\alpha$ below a given threshold.

These notions are all motivated by bounds on the privacy loss of a randomized algorithm. This quantity is defined by

where $x_{0}$ and $x_{1}$ are two adjacent inputs. Intuitively, the privacy loss measures how much information is revealed by an output $y$. While output values with a large privacy loss are highly revealing—they are far more likely to result from a private input $x_{0}$ rather than a different private input $x_{1}$—if these outputs are only seen with small probability then it may be reasonable to discount their influence. Each of the privacy definitions above bounds different moments of this privacy loss, treated as a random variable when $y$ is drawn from the output of the algorithm on input $x_{0}$. The following table summarizes these bounds.

In particular, DP bounds the maximum value of the privacy loss,Technically speaking, this is true only for sufficiently well-behaved distributions [Meiser, 2018]. $(\alpha,\cdot)$-RDP bounds the $\alpha$-moment, zCDP bounds all moments, and $(\cdot,\omega)$-tCDP bounds the moments up to some cutoff $\omega$. Many conversions are known between these definitions; for instance, RDP, zCDP, and tCDP are known to sit between $(\varepsilon,0)$ and $(\varepsilon,\delta)$-differential privacy in terms of expressivity, up to some modification in the parameters. While this means that RDP, zCDP, and tCDP can sometimes be analyzed by reduction to standard differential privacy, converting between the different notions requires weakening the parameters and often the privacy analysis is simpler or more precise when working with RDP, zCDP, or tCDP directly. The interested reader can refer to the original papers [Bun and Steinke, 2016, Mironov, 2017, Bun et al., 2018].

k𝑘k-generated divergences

2 Divergences between distributions

We start from a very general definition of divergences. Our notation includes the domain of definition of the divergence; this distinction will be important when introducing the concept of $k$-generatedness.

A divergence is a family $\Delta=\{\Delta_{X}\}_{X}$ of functions

We use the notation $\Delta_{X}(\mu_{1}||\mu_{2})$ to denote the divergence between distributions $\mu_{1}$ and $\mu_{2}$ over $X$.

Our notion of divergence subsumes the general notion of $f$-divergence from the literature [Csiszár, 1963, Csiszàr and Shields, 2004]. In particular, this includes the $\varepsilon$-divergence [Barthe and Olmedo, 2013] used to formulate $(\varepsilon,\delta)$-differential privacy:

Many useful properties of divergences have been explored in the literature. Our technical development will involve the following two properties.

A divergence $\Delta$ is quasi-convex iff for every $\alpha_{1},\ldots,\alpha_{m}\in$ such that $\textstyle{\sum_{m=1}^{N}}\alpha_{m}=1$ and every discrete set $X$,

These properties are satisfied by many common divergences. Besides Rényi divergences, they also hold for all $f$-divergences [Csiszár, 1963, Csiszàr and Shields, 2004]. We will consider only divergences satisfying them in the following.

3 k𝑘k-cuts of divergences

We now introduce a technical construction that will be useful in the rest of the paper.

For divergences $\Delta$ that satisfy the data-processing inequality, then the $k$-cut is well-defined: it does not depend on the choice of $Y$.

If a divergence $\Delta$ satisfies the data-processing inequality, we have the inequality $\overline{\Delta}^{k}\leq\Delta$ and the equality $\overline{\Delta}^{k}_{Y}=\Delta_{Y}$ for any set $Y$ with $|Y|=k$.

So, without loss of generality in the sequel we will refer to this as “the” $k$-cut.

Another interesting property of $k$-cuts is that a $k$-cut $\overline{\Delta}^{k}$ of a divergence $\Delta$ satisfies the data-processing inequality, even if the original divergence $\Delta$ does not satisfy it.

Without loss of generality, we can assume the function $\gamma$ in the definition of a $k$-cut to be deterministic. This can be proved by a weak version of Birkhoff-von Neumann theorem, which decomposes every probabilistic decision rule into a convex combination of deterministic ones.

This fact, allow us to consider simplified formulations of a $k$-cut of a divergence. Examples of this fact that will be useful in the sequel are the $2$-cut and $3$-cut of the Rényi divergence of order $\alpha$. These can be reformulated as follows:

4 k𝑘k-generatedness of divergences

We now introduce the notion of $k$-generatedness. Informally, $k$-generatedness is a measure of the number of decisions that are needed in an hypothesis test to characterize a divergence.

$k$-generatedness can also be reformulated as follows:

The following basic properties hold for all $k$-generated divergences.

If $\Delta$ is $k$-generated, then it is also $k+1$-generated.

If $\Delta$ has the data-processing inequality, then it is at least $\infty$-generated.

Every $k$-cut of a divergence $\Delta$ is $k$-generated.

To compare a $k$-generated divergence and a divergence, we have the following lemma where all the inequalities are defined pointwise.

Consider a divergence $\Delta$ and a $k$-generated divergence $\Delta^{\prime}$. For any $k$-cut $\overline{\Delta}^{k}$ of $\Delta$,

Also, if $\Delta$ has the data-processing inequality, the $k$-cut is the greatest $k$-generated divergence below $\Delta$:

The divergence $\Delta^{\varepsilon}$ that can be used to characterize $(\varepsilon,\delta)$-DP is $2$-generated. This implies that DP can be characterized completely by its hypothesis testing interpretation.

The $\varepsilon$-divergence $\Delta^{\varepsilon}$ is $2$-generated.

Since $\Delta^{\varepsilon}$ is quasi-convex and satisfies data-processing inequality, the $2$-cut can be reformulated as:

It is easy to show that this is exactly the same as the original definition of $\Delta^{\varepsilon}$, from which follows that it is $2$-generated.

4.2 Rényi is ∞\infty-generated

In contrast to the divergence $\Delta^{\varepsilon}$, the 2-cut of the Rényi divergence is not complete with respect to the Rényi divergence.

We set $\beta>\alpha+1$ and $p=(1/2)^{\beta/(\alpha-1)}$, a simple calculation shows:

The difference is quantitatively small, but it is nevertheless strictly positive. This shows also that the Rényi divergence is not $2$-generated.

Similary, one can show that the 3-cut is not complete, that the 4-cut is not complete, etc. In fact, Rényi divergence is exactly $\infty$-generated. Indeed, Rényi divergence satisfies the data-processing inequality, hence it is at most $\infty$-generated. Moreover, any $f$-divergences whose weight function $f$ is strictly convex is not $k$-generated for any finite $k$. The formulation of Rényi divergence of order $\alpha$ given by $\exp((\alpha-1)D^{\alpha}_{X}(\mu_{1}||\mu_{2}))$ is an $f$-divergence related to the weight function $t\mapsto t^{\alpha}$, which is strictly convex. Since the logarithm function is continuous on $(0,\infty)$ and strictly monotone, we conclude that the Rényi divergence is $\infty$-generated. The formal details can be found in the appendix.

Hypothesis Testing Interpretation of Divergences

In this section, we give an hypothesis testing characterization similar to the one that differential privacy satisfies for the $2$-cut of an arbitrary divergence.

We first define privacy regions for divergences using their $2$-cuts.

For any divergence $\Delta$, we define its privacy region $R^{\Delta}(\rho)\subseteq\times$ by

Notice that if $\Delta$ satisfies the data-processing inequality, or is $2$-generated, then $\overline{\Delta}^{2}_{\{\mathtt{Acc},\mathtt{Rej}\}}$ in the definition above can be replaced by $\Delta_{\{\mathtt{Acc},\mathtt{Rej}\}}$.

As an example, we can give the privacy region of DP.

Privacy regions are intimately related to the hypothesis testing interpretation of privacy definitions based on divergences.

This give us the hypothesis testing characterization of DP, since the $\varepsilon$-divergence is $2$-generated and quasi-convex.

We conclude this section by stressing that Theorem 18 tell us two important things:

Every privacy definition similar to differential privacy but based on a $2$-generated divergence is characterized completely by its hypothesis testing interpretation.

For every privacy definition similar to differential privacy but based on an arbitrary divergence we can have an hypothesis testing interpretations by considering its $2$-cut. However, this characterization will not be necessarily complete.

The second remark applies in particular to relaxations of differential privacy based on the Rényi divergence: if we want to have the hypothesis testing interpretation for one of these relaxations we can use the $2$-cut of the Rényi divergence.

Applications

In this section we will use the technical tools we developed in the previous sections to better study the relations between different privacy definitions.

This means that to find a good conversion law we can just compare the privacy regions.

Using privacy regions, we can refine Mironov’s conversion law from RDP to DP in a simple way.

If a mechanism $\mathcal{M}$ is $(\alpha,\rho)$-RDP then the mechanism is also $(\rho-\log\delta/(\alpha-1),\delta)$-DP for any $0<\delta<1$.

The privacy region of Rényi divergence is given by

By an extension of Lemma 15, to find $\varepsilon$ satisfying

it is necessary and sufficient to find $\varepsilon$ satisfying

By Theorem 18, this is equivalent to find $\varepsilon$ satisfying $R^{D^{\alpha}}(\rho)\subseteq R^{\Delta^{\varepsilon}}(\delta)$. Inspired from Mironov’s proof of conversion law from RDP to DP [Mironov, 2017, Propisition 3]: we obtain,

The equality (‡) derives original Mironov’s result [Mironov, 2017, Propisition 3]. Now, starting from (†), we have a better bound for DP as follows: consider a curve $C$ given by the equation

. We have the derivative of $x$ as follows:

We can take the tangent of the curve $C$ by

We will find parameters that a tangent of $C$ meets $(1-x)=e^{\varepsilon}y+\delta$. $x=-e^{\varepsilon}y-\delta+1$ We first solve

By the symmetry of $R^{D^{\alpha}}(\rho)$ and $R^{\Delta^{\varepsilon}}(\delta)$, we have

Therefore, we have the following better conversion law:

If a mechanism $\mathcal{M}$ is $(\alpha,\rho)$-RDP then it is $(\rho+\log((\alpha-1)/\alpha)-(\log\delta+\log\alpha)/(\alpha-1),\delta)$-DP for any $0<\delta<1$.

As a conjecture, if we calculate tangents of the boundary of the privacy region $R^{D^{\alpha}}(\rho)$, we have optimal conversion law from $(\alpha,\rho)$-RDP to DP. The boundary of $R^{D^{\alpha}}(\rho)$ is given by the equation

2 On Gaussian Differential Privacy

Gaussian differential privacy (GDP) [Dong et al., 2019, Def. 2.6] has been recently proposed as a privacy definition trading-off PMD and PFA. This can be characterized by means of privacy regions. We have seen that privacy regions correspond to $2$-generated divergence. Thus, a natural question is: can we characterize GDP using a $2$-generated divergence. The answer is yes. We can characterize GDP by the following divergence:

3 Informativeness of k𝑘k-cuts

The concept of $k$-cut can be related to the ability that a divergence has of distinguishing two distributions.

A characterization of k𝑘k-generated divergences

As we have seen, $k$-generated divergences satisfy a number of useful properties; known divergences from the literature can be classified according to this parameter $k$ - we have shown some examples here, more examples are in the supplemental material. In the other direction, we give a simple condition to ensure that a divergence is $k$-generated: the suprema of quasi-convex functions over size $k$-partitions determine $k$-generated divergences.

Let $F\colon^{2k}\to[0,\infty]$ be a quasi-convex function. Then the divergence $\Delta^{F}$ defined below is $k$-generated and quasi-convex.

We have $\overline{\Delta^{F}}^{k}_{X}(\mu_{1}||\mu_{2})\leq\Delta^{F}_{X}(\mu_{1}||\mu_{2})$. Conversely, by equality $({\dagger})$, we also have $\overline{\Delta^{F}}^{k}_{X}(\mu_{1}||\mu_{2})\geq\Delta^{F}_{X}(\mu_{1}||\mu_{2})$. This completes the proof. ∎

This result characterizes $k$-generated quasi-convex divergences. It also serves as a useful tool to construct new divergences with a hypothesis testing interpretation, by varying the quasi-convex function $F$.

Conclusion

In this paper we have developed analytical tools to study the hypothesis testing interpretation of privacy definitions similar to differential privacy but measured with another statistical divergence. We introduced the notions of $k$-cut and $k$-generatedness for divergences. These notions quantifies the number of decisions that are needed in an experiment similar to the ones used in hypothesis testing to fully characterize the divergence. We used these notions to study the hypothesis testing interpretation of relaxations of differential privacy based on the Rényi divergence. These notions give a measure of the complexity that tools for formal verification may have. We leave the study of this connection for future work.

Appendix A Weak version of Birkhoff-von Neumann Theorem

The cardinal $k$ can be relaxed to countable infinite cardinal $\omega$, and then the families $\{\gamma_{j}\}_{j}$ and $\{a_{j}\}_{j}$ may be countable infinite.

Consider the following matrix representation $f$ of $\gamma$:

where $f_{i,j}=\gamma(i)(j)$ and $\sum_{j=1}^{N}f_{i,j}=1$ for any $1\leq i\leq l$.

For any $h\colon k\to l$, the matrix representation $g$ of $(\{x\mapsto\mathbf{d}_{x}\}\circ h)$ is

satisfying that for any $1\leq i\leq l$, there is exactly $1\leq j\leq k$ such that $g_{i,j}=1$ and $g_{i,s}=0$ for $s\neq j$. Conversely, any matrix $g$ satisfying this condition corresponds to some function $h\colon k\to l$. Consider the family $G$ of matrix representations of maps of the form $(\{x\mapsto\mathbf{d}_{x}\}\circ h)$. We give an algorithm decomposing $f$ to a convex sum of $g$:

(g_m+1)_i,j = {1 j = argmaxs(~fm)i,s0 (otherwise) ,

If $r_{s+1}=0$ then we terminate. Otherwise, we repeat the previous step.

In each step, we obtain the following conditions:

We have $0<\alpha_{m+1}$ whenever $0<r_{m}$ because

Appendix B Omitted Proofs

Thanks to the unit law and associativity of $\bullet$ as an abuse of notations, we define

B.2 Proof of the data-processing inequality of k𝑘k-cuts

For any divergence $\Delta$, every $k$-cut $\overline{\Delta}^{k}$ satisfies data-processing inequality.

We consider the $k$-cut of $\Delta$ with respect to a set $Y$ satisfying $|Y|=k$

The inequality is obtained by the inclusion

B.3 Proof of Lemma 10

If a divergence $\Delta$ has the data-processing inequality, we have the inequality $\overline{\Delta}^{k}\leq\Delta$ and the equality $\overline{\Delta}^{k}_{Y}=\Delta_{Y}$ for any set $Y$ with $|Y|=k$.

We consider the $k$-cut of $\Delta$ with respect to a set $W$ satisfying $|W|=k$

The first and second inequalities are obtained by the dataprocessing inequality and the definition of $k$-cut respectively. ∎

B.4 Proof of Lemma 13

Suppose that $\Delta$ is equal to the $k$-cut of $\Delta$ with respect to a set $W$ satisfying $|W|=k$.

Here, the first and last inequalities are obtained from the data-processing inequality of $\Delta$. The second inequality is proved from the inclusion

B.5 Proof of Basic Properties of k𝑘k-generatedness (Lemma 14)

If $\Delta$ is $k$-generated, then it is also $k+1$-generated.

Suppose that $\Delta$ is equal to the $k$-cut of $\Delta$ with respect to a set $W$ satisfying $|W|=k$.

Let $V$ be an arbitrary set with $|V|=k+1$. We define the $k+1$-cut of $\overline{\Delta}^{k}$ with respect to the set $V$.

If $\Delta$ has the data-processing inequality, then it is at least $\infty$-generated.

Every $k$-cut of a divergence $\Delta$ is always $k$-generated.

We can prove $\overline{\overline{\Delta}^{k}}^{k}=\overline{\Delta}^{k}$ in a almost the same way as Lemma 14 (2). ∎

If $\Delta$ is continuous and satisfies data-processing inequality we have $\infty$-generatedness (moreover we show the “countable”-generatedness) as follows:

The first and last inequalities are obtained from data-processing inequality. The second inequality is obvious.

B.6 Proof of Lemma 15

Consider a divergence $\Delta$ and a $k$-generated divergence $\Delta^{\prime}$. For any $k$-cut $\overline{\Delta}^{k}$ of $\Delta$,

Also, if $\Delta$ has the data-processing inequality, the $k$-cut is the greatest $k$-generated divergence below $\Delta$:

Since $\Delta^{\prime}$ is $k$-generated, for any choice of $Y$ with $|Y|=k$, we have

The second statement is proved as follows: From the first statement of this lemma and Lemma 3 (Lemma 10 in the paper), We have

We can extend this theorem to more suitable for conversion laws of differential privacy.

Consider a divergence $\Delta$ satisfying data-processing inequality and a $k$-generated divergence $\Delta^{\prime}$.

($\impliedby$) Obvious from Lemma 3 (Lemma 10 in the paper). ($\implies$) From the assumption, we obtain

Thanks to the $k$-generatedness of $\Delta^{\prime}$, we conclude the statement of this lemma. ∎

B.7 Proof of 222-generatedness of ε𝜀\varepsilon-divergence

The $\varepsilon$-divergence $\Delta^{\varepsilon}$ is $2$-generated for all $\varepsilon$.

We recall that the $\varepsilon$-divergence $\Delta^{\varepsilon}$ is quasi-convex (moreover, jointly convex) and satisfies data-processing inequality. We choose a set $Y=\{\mathtt{Acc},\mathtt{Rej}\}$, and take the $2$-cut of $\Delta^{\varepsilon}$ by

We show this is equal to the original $\Delta^{\varepsilon}_{X}(\mu_{1}||\mu_{2})$. Without loss of generality we may assume $X$ is at most countable. If $X$ is an arbitrary set, we can restrict it to countable set in a similar way as the proof of Lemma 7 (Lemma 14(3) in the paper).

We have the $2$-generatedness: $\overline{\Delta^{\varepsilon}}^{2}=\Delta^{\varepsilon}$. The equality $(*)$ is proved as follows: for given $\gamma$ and $A$, we take $S={\gamma}^{-1}$. Conversely, for any $S\subseteq X$ we take $A=\{\mathtt{Acc}\}$ and $\gamma=\chi_{S}$, which is the indicator function of $S$ defined by $\chi_{S}(x)=1$ if $x\in S$ and $\chi_{S}(x)=0$ otherwise. ∎

B.8 Counterexample: Rényi-divergence is not 222-generated

There are $\mu_{1},\mu_{2}\in{\tt Prob}(\{a,b,c\})$ such that

Let $p=(1/2)^{\beta/(\alpha-1)}$ and $\alpha+1<\beta$ and define

Since Rényi divergence is quasi-convex and satisfies data-processing inequality, it suffices to show the proper inequality $D^{\alpha}_{\{\mathtt{Acc},\mathtt{Rej}\}}(\gamma(\mu_{1})||\gamma(\mu_{2}))<D^{\alpha}_{\{a,b,c\}}(\mu_{1}||\mu_{2})$ holds for any deterministic decision rule $\gamma\colon\{a,b,c\}\to\{\mathtt{Acc},\mathtt{Rej}\}$. There are $8$ cases of $\gamma\colon\{a,b,c\}\to\{\mathtt{Acc},\mathtt{Rej}\}$, but thanks to the data-processing inequality and reflexivity of Rényi divergence, it suffices to consider $3$ cases: $(\gamma(a),\gamma(b),\gamma(c))=(\mathtt{Acc},\mathtt{Acc},\mathtt{Rej}),(\mathtt{Acc},\mathtt{Rej},\mathtt{Acc}),(\mathtt{Rej},\mathtt{Acc},\mathtt{Acc})$. Hence,

holds for any $\gamma\colon\{a,b,c\}\to\{\mathtt{Acc},\mathtt{Rej}\}$. By the data-processing inequality of Rényi divergence, this discussion does not depend on the choice of $\{\mathtt{Acc},\mathtt{Rej}\}$. By weak Birkhoff-von Neumann theorem, and the quasi-convexity Rényi divergence, we conclude

B.9 Proof of ∞\infty-generatedness of Rényi-divergence

The $\alpha$-Rényi divergence $D^{\alpha}$ can also be characterized using $f$-divergence as follows:

Remark that every $f$-divergence is quasi-convex (moreover jointly convex) and continuous, and satisfies data-processing inequality (see also [Liese and Vajda, 2006, Theorems 14–16]).

Since the mapping $t\mapsto\frac{1}{\alpha-1}\log t$ is monotone, every $\alpha$-Rényi divergence $D^{\alpha}$ is also quasi-convex and satisfies data-processing inequality. Thanks to the data-processing inequality, every $\alpha$-Rényi divergence $D^{\alpha}$ is at least $\infty$-generated. We need to prove that for every finite $k$, every $\alpha$-Rényi divergence $D^{\alpha}$ is not $k$-generated. To prove this, we use that the mapping $t\mapsto t^{\alpha}$ is strictly convex.

If a weight function is strictly convex, its $f$-divergence $\Delta^{f}$ is not $k$-generated for every finite $k$.

Without loss of generality, we may assume $k>1$.

Since $k+1>k$, by Dirichlet’s pigeonhole principle, for any $\gamma\colon\{0,1,2,\ldots,k\}\to\{0,1,2,\ldots,k-1\}$, for some $j\in\{0,1,2,\ldots,k\}$, there are at least two different $i_{1},i_{2}\in\{0,1,2,\ldots,k-1\}$ such that $\gamma(i_{1})=j$ and $\gamma(i_{2})=j$. From the assumption on $\mu_{1}$ and $\mu_{2}$, we have $(\mu_{1}(i_{1})/\mu_{2}(i_{1}))\neq(\mu_{1}(i_{2})/\mu_{2}(i_{2}))$ Since the function $f$ is strictly convex, by the condition for equality of Jensen’s inequality, we have the strict inequality

Therefore, for any $\gamma\colon\{0,1,2,\ldots,k\}\to\{0,1,2,\ldots,k-1\}$, we have

Since there only finite case of $\gamma\colon\{0,1,2,\ldots,k\}\to\{0,1,2,\ldots,k-1\}$, we conclude $\overline{\Delta^{f}}^{k}_{\{0,1,2,\ldots,k\}}(\mu_{1}||\mu_{2})<\Delta^{f}_{\{0,1,2,\ldots,k\}}(\mu_{1}||\mu_{2})$. Since every $f$-divergence satisfies data-processing inequality, this discussion does not depend on the choice of set $Y$ with $|Y|=k$ in the construction of the $k$-cut $\overline{\Delta^{f}}^{k}$. Thus, $\Delta^{f}$ is not $k$-generated for any finite $k$. ∎

Since the mapping $t\mapsto\frac{1}{\alpha-1}\log t$ is strict, we conclude,

For any $alpha>1$, the $\alpha$-Rényi divergence $D^{\alpha}$ is not $k$-generated for every finite $k$.

B.10 Proof of Theorem 18

We fix a $2$-cut $\overline{\Delta}^{2}$ of a divergence $\Delta$. Suppose that it is defined with a set $W$ satisfying $|W|=2$.

We recall the definition of privacy region

($\implies$) Obvious by the data-processing inequality of the $2$-cut $\overline{\Delta}^{2}$.

($\impliedby$) The assumption is equivalent to

Since $|W|=|\{\mathtt{Acc},\mathtt{Rej}\}|=2$, this is equivalent to

B.11 Proof of Theorem 23 in general setting

If the quasi-convex function $F\colon^{2k}\to[0,\infty]$ is also continuous, we can extend Theorem 23 to general measurable setting.

Assume that $F\colon^{2k}\to[0,\infty]$ is quasi-convex and continuous. For any measurable space $X$, we have

We easily calculate as follows (functions are assumed to be measurable):

Note that we treat $\{1,2,\ldots,k\}$ as a finite discrete space. Consider the family $\{J_{n}\}_{n=1}^{\infty}$ of finite sets (discrete spaces) defined as follows:

Hence the sequence of probability measures $\{(\gamma\circ m_{n}\circ m^{\ast}_{n})(\mu_{1})\}_{n=1}^{\infty}$ converges to the probability measure $\gamma(\mu_{1})$. Similarly, $\{(\gamma\circ m_{n}\circ m^{\ast}_{n})(\mu_{2})\}_{n=1}^{\infty}$ converges to $\gamma(\mu_{2})$.

Appendix C Additional Results

We recall the definition of the total variation distance

In a similar way as $\varepsilon$-divergence $\Delta^{\varepsilon}$, we can prove $2$-generatedness of the total variation distance $\mathtt{TV}$, but we can prove it easily by applying Theorems 16–17 (Theorem 23 in the paper).

Define $F\colon^{4}\to[0,\infty]$ by $F(x,x^{\prime},y,y^{\prime})=|x-y|$. It is easy to check that the function is obviously quasi-convex, and that we have $\mathtt{TV}=\Delta^{F}$.

C.2 An optimal conversion law from Hellinger to DP

We recall the definition of the Hellinger distance

Since it is the $f$-divergence of weight function $w(t)=\sqrt{t}-1$ (strict convex), the Hellinger distance is exactly $\infty$-generated, quasi-convex and continuous.

Here is the essense of an optimal conversion law from the Hellinger distance to DP.

The degree of this equation is $2$, so we can solve it. For given $x\in$, we have

The tangent of the curve $y=f(x)$ that passes the point $(t,f(t))$ is given by the equation $x-\frac{y}{g(t)}=t-\frac{f(t)}{g(t)}$ where $g(x)=\frac{df}{dx}(x)$. We next find $t$ and $\delta$ that the lower boundary

of $R^{\Delta^{\varepsilon}}(\delta(\varepsilon,\rho))$ is the same as the line $x-\frac{y}{g(t)}=t-\frac{f(t)}{g(t)}$. We solve the equation $e^{\varepsilon}=\frac{1}{g(t)}$ on $t$ about the slope as (5). Finally, we obtain $\delta$ as (4). ∎

We conclude an optimal conversion law from the Hellinger distance to DP.

References