Rényi Differential Privacy of the Sampled Gaussian Mechanism

Introduction and Definitions

The notion of differential privacy grounds a guarantee of individual privacy for input of a statistical procedure in non-determinism of the procedure’s output. The uncertainty, or randomness, can be achieved either explicitly, by injecting noise, or implicitly, by leveraging randomness intrinsic to the mechanism or its input. Developing a general framework that accounts for all sources of output stochasticity and distills them into a guarantee of differential privacy remains a significant open problem.

Following introduction of (pure) differential privacy , many of its relaxations, which we recall shortly, were motivated by the need to capture properties of the Gaussian additive noise and SGM.

The notion of approximate differential privacy, which includes an additive $\delta$ term, appeared in the work by Dwork et al. in order to support analysis of the Gaussian noise mechanism. Concentrated Differential Privacy (CDP) and its reformulation, zero-CDP, due to Bun and Steinke were developed to refine composition theorems using the Gaussian mechanism as their main motivating examples.

Another family of definitions and analytical techniques emerged as tools for handling the Sampled Gaussian mechanism. To track privacy loss budget over multiple applications of SGM, Abadi et al. developed a moments accountant, implemented a numerically stable and efficient algorithm for computing it, and analyzed the accountant’s asymptotic properties. A relaxation of CDP well-suited for analysis of SGM, called truncated CDP (tCDP), was introduced by Bun et al. . We compare these closely related notions in Section 4.

In this paper we revisit the moments accountant due to Abadi et al., restate it using the notion of Rényi differential privacy (RDP) , relax certain assumptions, and strengthen upper bounds. An open-source implementation of the RDP accountant for SGM is available from https://github.com/tensorflow/privacy.

We recall the definitions of Rényi divergence, Rényi differential privacy and the Sampled Gaussian mechanism.

Let $P$ and $Q$ be two distributions on $\mathcal{X}$ defined over the same probability space, and let $p$ and $q$ be their respective densities. The Rényi divergence of a finite order $\alpha\neq 1$ between $P$ and $Q$ is defined as

Rényi divergence at orders $\alpha=1,\infty$ are defined by continuity.

We refer the reader to van Erven and Harremoës for an introduction to the theory of Rényi divergence, including proof of its continuity and many other useful properties.

We say that a randomized mechanism $\mathcal{M}\colon\mathcal{S}\to\mathcal{R}$ satisfies $(\alpha,\varepsilon)$-Rényi differential privacy (RDP) if for any two adjacent inputs $S,S^{\prime}\in\mathcal{S}$ it holds that

The notion of adjacency between input datasets is domain-specific and is usually taken to mean that the inputs differ in contributions of a single individual. In this work, we will use this definition and call two datasets $S,S^{\prime}$ to be adjacent if $S^{\prime}=S\cup\{x\}$ for some $x$ (or vice versa).

The SGM has been studied in several incomparable settings. Broadly speaking, there are three approaches for deriving privacy bounds on the SGM: (1) asymptotic analyses that target tight bounds for $q\to 0$; (2) approaches that lead to numerically accurate estimates; and (3) a closed-form analysis that captures the right dependency on the order $\alpha$. These results, along with our contributions are summarized in Table 1.

Reducing to a simpler case

We first reduce the problem of proving the RDP bound for the Sampled Gaussian mechanism to a particularly simple special case of a mixture of single-dimensional Gaussians.

under the assumption $\|f(S)-f(S^{\prime})\|_{2}\leq 1$ for any adjacent $S,S^{\prime}\in\mathcal{S}$.

Let $T$ denote a set-valued random variable defined by taking a random subset of $\mathcal{S}$, where each element of $S$ is independently placed in $T$ with probability $q$. Conditioned on $T$, the mechanism $\mathcal{M}(S)$ samples from a Gaussian with mean $f(T)$. Thus

where the sum here denotes mixing of the distributions with the weights $p_{T}$. Similarly,

Rényi divergence is quasi-convex , allowing us to bound

where we have used the translation invariance of Rényi divergence. Since the covariances are symmetric, we can, by applying a rotation, assume that $f(T\cup\{x\})-f(T)=c_{T}\mathbf{e}_{1}$ for some constant $c_{T}\leq 1$. The two distributions at hand are then both product distributions that are identical in all coordinates except the first. By additivity of Rényi divergence for product distributions, we have that

For any $c\leq 1$, the noise $\mathcal{N}(0,(\sigma/c)^{2})$ can be obtained from $\mathcal{N}(0,\sigma^{2})$ by adding noise from $\mathcal{N}(0,(\sigma/c)^{2}-\sigma^{2})$, and the same operation allows us to to obtain $(1-q)\mathcal{N}(0,(\sigma/c)^{2})+q\mathcal{N}(1,(\sigma/c)^{2})$ from $(1-q)\mathcal{N}(0,\sigma^{2})+q\mathcal{N}(1,\sigma^{2})$. Thus by the data processing inequality for Rényi divergence, we conclude

In the next section, we bound these simpler one-dimensional Rényi divergences between mixtures of Gaussian distributions.

RDP Analysis of Single-Dimensional SGM

Let $\mu_{0}$ denote the pdf of $\mathcal{N}(0,\sigma^{2})$ and let $\mu_{1}$ denote the pdf of $\mathcal{N}(1,\sigma^{2})$. Let

We introduce the following notation used through the rest of this section. Define

In our first result (Section 3.1), we demonstrate that $A_{\alpha}\geq B_{\alpha}$. In fact, we prove a more general statement about centrally-symmetric distributions, from which the case of $\mu_{0}=\mathcal{N}(0,\sigma^{2})$ and $\mu_{1}=\mathcal{N}(1,\sigma^{2})$ follows as a corollary.

To upper bound $A_{\alpha}$ we pursue two complementary approaches. Section 3.2 derives a closed-form bound that is valid and reasonably tight within a wide range of parameters. Section 3.3 describes a numerically stable computational procedure for computing $A_{\alpha}$ exactly (to within any desired precision).

Looking ahead, $A_{\alpha}$ admits decomposition into a finite sum or a convergent series. By comparison, manipulating $B_{\alpha}$ is a similar manner is considerably more difficult, since we have a composite term $\mu$ in the denominator. Fortunately, it is not necessary as we demonstrate that $B_{\alpha}\leq A_{\alpha}$. In fact, we prove a more general statement, which may be of independent interest.

Let $P$ and $Q$ be two differentiable distributions on $\mathcal{X}$ such that there exists a differentiable mapping $\nu\colon\mathcal{X}\mapsto\mathcal{X}$ satisfying $\nu(\nu(x))=x$ and $P(x)=Q(\nu(x))$. Then the following holds for all $\alpha\geq 1$ and $q\in$:

We will repeatedly use the fact that $Q(x)=Q(\nu(\nu(x))=P(\nu(x))$. Furthermore, since the inverse of $\nu$ is $\nu$, it is continuously differentiable and its Jacobian satisfies $\det\mathbf{J}_{\nu}=\pm 1$.

Let $P_{q}\stackrel{{\scriptstyle\Delta}}{{=}}(1-q)P+qQ$ and $Q_{q}\stackrel{{\scriptstyle\Delta}}{{=}}(1-q)Q+qP$. Then, substituting $x=\nu(y)$, we have

We proceed by arguing a stronger statement: the integrand of the right-hand side of (1) dominates the integrand of (2) pointwise. In other words, we prove the following lemma, from which the theorem claim follows:

For all $x\in\mathcal{X}$, and any $\alpha>1$, $q\in$:

where $P_{q}(x)=(1-q)P(x)+qQ(x)$ and $Q_{q}(x)=(1-q)Q(x)+qP(x)$.

Let $u\stackrel{{\scriptstyle\Delta}}{{=}}P(x)$ and $v\stackrel{{\scriptstyle\Delta}}{{=}}Q(x)$. Assume wlog $u\geq v$ (the claim is symmetric with respect to $P$ and $Q$). Then the two sides become, respectively,

Dividing by $v$ and letting $y\stackrel{{\scriptstyle\Delta}}{{=}}(1-q)+q\frac{u}{v}$ and $z\stackrel{{\scriptstyle\Delta}}{{=}}(1-q)+q\frac{v}{u}$, we need to compare

subject to $y\geq 1/z\geq 1\geq z$. (The bound $y\geq 1$ follows from $u\geq v$ and $y\geq 1/z$ from $yz=(1-q)^{2}+q(1-q)(\frac{u}{v}+\frac{v}{u})+q^{2}\geq(1-q)^{2}+2q(1-q)+q^{2}=1$.)

Collecting the $y$ terms on the left and the $z$ terms on the right we have

The left-hand side dominates, since the two expressions are equal for $y=1/z$ and the left expression is monotonically increasing in $y$ over $[1,\infty)$:

which holds due to $(y^{\alpha}-y^{-\alpha})/\alpha\geq(y^{\alpha-1}-y^{1-\alpha})/(\alpha-1)$, in turn implied by monotonicity of $\sinh(\alpha\ln y)/\alpha$ in $\alpha$ for $y\geq 1$. ∎

This concludes the proofs of the lemma and of the theorem. ∎

$A_{\alpha}\geq B_{\alpha}$ for any $\alpha\geq 1$.

Let $\nu(x)\stackrel{{\scriptstyle\Delta}}{{=}}1-x$. Then, the pdf of $\mu_{0}$ is $\propto\exp(-x^{2}/2\sigma^{2})=\exp(-(\nu(x)-1)^{2}/2\sigma^{2})$ as required. The claim follows. ∎

Theorem 5 holds for any additive noise whose distribution is centrally symmetric, which also includes Laplace, sinh-normal , their discretized and multi-dimensional variants.

2 Closed-Form Bound

We write $A_{\alpha}$ as an integral over the real line, break it into two parts (at $z_{0}$ to be chosen shortly) and bound them separately as follows:

We define $z_{0}\stackrel{{\scriptstyle\Delta}}{{=}}\frac{1}{2}+\sigma^{2}\ln\left(1+\frac{1}{q(\alpha-1)}\right)$, chosen to satisfy $(1-q)+q\frac{\mu_{1}(z_{0})}{\mu_{0}(z_{0})}=\alpha/(\alpha-1)$. For notational convenience we also introduce $r_{0}\stackrel{{\scriptstyle\Delta}}{{=}}\frac{\mu_{1}(z_{0})}{\mu_{0}(z_{0})}=1+\frac{1}{q(\alpha-1)}$. Note that $z_{0}>\frac{1}{2}$ and $r_{0}>1$. We repeatedly use the facts that $\mu_{0}(z)=\mu_{1}(1-z)$ everywhere and the ratio $\mu_{0}(z)/\mu_{1}(z)$ is monotonically decreasing in $z$. It follows that for all $z\leq z_{0}$ the ratio $\mu_{1}(z)/\mu_{0}(z)\leq r_{0}$ and for $z\geq 1-z_{0}$ the ratio $\mu_{0}(z)/\mu_{1}(z)\leq r_{0}$. In particular, for $z\in[1-z_{0},z_{0}]$ the ratios $\mu_{1}(z)/\mu_{0}(z)$ and $\mu_{1}(z)/\mu_{0}(z)$ are confined to $[1/r_{0},r_{0}]$.

For any $\alpha\geq 1$, $q\in$ and positive $x,y$ such that $1/r_{0}\leq x/y\leq r_{0}$ where $r_{0}=1+\frac{1}{q(\alpha-1)}$:

Recall the following Lemma 15 in Bun et al. :

Let $r=x/y\in[1/r_{0},r_{0}]$. By setting $w\stackrel{{\scriptstyle\Delta}}{{=}}q(1/r-1)$ and $w\stackrel{{\scriptstyle\Delta}}{{=}}q(r-1)$ we obtain, respectively,

The claim follows by simple addition and multiplication of both sides by $y$. ∎

A useful fact that facilitates application of Lemma 8 is that for positive $x$ and $y$

It implies that all terms in the claim of the lemma are non-negative.

Similarly to the argument in the previous section, we “double over” the integral, by using the symmetry between $\mu_{0}$ and $\mu_{1}$:

Note that $(1-q)+q\frac{\mu_{1}(z)}{\mu_{0}(z)}<1$ for $z\leq 1-z_{0}$ and $(1-q)+q\frac{\mu_{0}(z)}{\mu_{1}(z)}<1$ for $z\geq z_{0}$. Furthermore, $1/r_{0}\leq\frac{\mu_{1}(z)}{\mu_{0}(z)}\leq r_{0}$ for $z\in[1-z_{0},z_{0}]$.

Applying Lemma 8 and inequality (3), we bound $A_{\alpha}^{(1)}$:

as claimed (we use the identities $\int_{-\infty}^{\infty}\frac{\mu_{0}(z)^{2}}{\mu_{1}(z)}\,\mbox{d}z=\int_{-\infty}^{\infty}\frac{\mu_{1}(z)^{2}}{\mu_{0}(z)}\,\mbox{d}z=\exp(1/\sigma^{2})$ elaborated in Section 3.3). ∎

Lemma 9 is unconditional, mildly behaved, and it yields an asymptotically right dependency of the bound on the parameters $q$, $\alpha$, and $\sigma$ (after taking the logarithm, it is non-tight by a factor close to 2). We next consider the integral to the right of $z_{0}$ that is responsible for the conditions on $\alpha$.

If $q\leq\frac{1}{5}$, $\sigma\geq 4$, and $\alpha$ satisfy

where $L\stackrel{{\scriptstyle\Delta}}{{=}}\ln\left(1+\frac{1}{q(\alpha-1)}\right)$, then

We observe (similarly to [2, Lemma 16]) that for $z\geq z_{0}$, it holds that

The inequality (6) follows from the Gaussian tail bound $\int_{t}^{\infty}\mu_{0}(x)\,\mbox{d}x<\exp(-t^{2}/(2\sigma^{2}))$ for $t\geq 0$. To apply the bound it is necessary to check that the lower limit of the integral $t=z_{0}-\alpha\geq 0$. Recall that $z_{0}=\frac{1}{2}+\sigma^{2}\ln\left(1+\frac{1}{q(\alpha-1)}\right)=\frac{1}{2}+\sigma^{2}L$. Together, the definition of $z_{0}$ and condition (4) imply that

which, given that $\sigma>1$, guarantees that $z_{0}>2\alpha$.

It is convenient to take the logarithm of both sides of Eq. (7) resulting in the following:

We will argue that the right-hand side of the above is less than $\ln(0.9\cdot q^{2}\alpha(\alpha-1)/\sigma^{2})$. Subtracting the two quantities, we need to demonstrate that

The rest of the proof proceeds by case analysis.

Observing that $\ln q+\ln(\alpha-1)+L=\ln(q(\alpha-1)+1)>0$, it suffices to verify that

From $q<1/5$ and $1<\alpha<2<1/q$ we conclude that the first summand is positive. Since $L>\ln(1+\frac{1}{q})\geq\ln 6$ and $\sigma\geq 4$, the second summand is larger than $1-\ln(0.9)$, by direct computation.

Case IIa: α≥2𝛼2\alpha\geq 2 and q​(α−1)<1/3𝑞𝛼113q(\alpha-1)<1/3

The inequality holds since the first term is non-negative ($q\alpha=q(\alpha-1)\cdot\frac{\alpha}{\alpha-1}<2/3$), $\ln(\alpha-1)-\ln\alpha\geq-\ln 2$, $L>\ln 4$, and $\sigma\geq 4$.

Case IIb: α≥2𝛼2\alpha\geq 2 and q​(α−1)≥1/3𝑞𝛼113q(\alpha-1)\geq 1/3

Continue Eq. (7), taking the logarithm of both sides:

The last inequality follows from Eq. (5) and by the fact that $L+\ln(q\alpha)=\ln(q\alpha+\frac{\alpha}{\alpha-1})>0$.

Our main theorem holds under the conditions of Lemmas 9 and 10:

If $q\leq\frac{1}{5}$, $\sigma\geq 4$, and $\alpha$ satisfy

Recall that to state an RDP guarantee on SGM it is sufficient to bound $A_{\alpha}$. Applying the results of Lemmas 9 and 10,

(The last inequality due to $\exp(1/\sigma^{2})-1\leq 1.1/\sigma^{2}$ for $\sigma\geq 4$.)

Finally, since $\ln(1+x)<x$ for $x\geq 0$, we conclude that SGM satisfies $(\alpha,\varepsilon)$-RDP where $\varepsilon=\frac{1}{\alpha-1}\ln A_{\alpha}\leq 2q^{2}\alpha/\sigma^{2}$ as needed. ∎

3 Numerically Stable Computation

Naïvely, $A_{\alpha}$ can be approximated as an integral using standard numerical libraries. It however leads to the problem of computing an integral over the whole real line of a quantity that can vary a lot. We sidestep this difficulty by expressing $A_{\alpha}$ as a finite sum (or a convergent series), swap the order of the integration and summation operators, and compute the integrals analytically.

Applying the binomial expansion to (11), we have

Thus it suffices to compute for $k\in\{0,\dots,\alpha\}$ the expectation

Case II. Fractional α𝛼\alpha.

To rewrite (11) as a convergent series, consider two cases depending on how $1-q$ compares with $q\mu_{1}(z)/\mu_{0}(z)$. The inflection point is $z_{1}$ where the two quantities are equal:

Analogously to the case of integer $\alpha$, we compute the expectations of both series under $z\sim\mu_{0}$, where the integrals are taken over the half lines $(-\infty,z_{1}]$ and $[z_{1},+\infty)$:

The computation done in the privacy accountant proceeds by plugging in these quantities into the series (12), and carrying out the summation to convergence.

Upper bounds (Theorem 11) and exact computations are compared in Figure 1.

Discussion

The notions of CDP, zCDP, Moments accountant and Rényi DP are closely related in that they control the moments of the privacy loss random variable. In this section, we clarify their differences.

For two adjacent datasets $S$ and $S^{\prime}$, the privacy loss of a mechanism $\mathcal{M}$ at an outcome $z$ is defined as

For continuous output spaces, the probability above is replaced by the probability density function. The various definitions deal with moment generating function of the privacy loss random variable. Define

Recalling the definition of Rényi divergence between distributions:

The following are equivalent definitions of CDP, zCDP, tCDP and RDP:

A mechanism $\mathcal{M}$ satisfies $(\mu,\tau)$-CDP if for all adjacent datasets $S,S^{\prime}$ and for all $\alpha\geq 1$

A mechanism $\mathcal{M}$ satisfies $(\xi,\rho)$-zCDP if for all adjacent datasets $S,S^{\prime}$,

A shorthand for $(0,\rho)$-zCDP is $\rho$-zCDP. Thus a mechanism $\mathcal{M}$ satisfies $\rho$-zCDP if for all adjacent datasets $S,S^{\prime}$,

A mechanism $\mathcal{M}$ satisfies $(\rho,\omega)$-tCDP if for all adjacent datasets $S,S^{\prime}$,

A mechanism $\mathcal{M}$ satisfies $(\alpha,\varepsilon)$-RDP if for all adjacent datasets $S,S^{\prime}$,

While here we have stated the definitions in terms of $M_{\alpha}$, using (14), one can translate these to bounds on the Rényi divergence; in some cases that leads to cleaner looking definitions. Going down the list, the definitions get less restrictive and have more parameters. While zCDP suffices for many purposes, SGM is an important mechanism that does not satisfy zCDP, but satisfies RDP for a suitable range of $\alpha$.

While the above were proposed as standalone privacy definitions, the moments accountant was proposed as an accounting mechanism that tracks (the logarithm of) $M_{\alpha}$ directly and converts the resulting bound to an $(\varepsilon,\delta)$-DP bound.

References