Differential privacy mechanisms and composition

Put $A_{+}=A\cap (0,+\mathrm{\infty })$ and $A_{-}=A\cap (-\mathrm{\infty },0)$. By [F1] and [F2], the positive mixture half contributes $\frac{1}{2}{\int }_{A_{+}}{b}^{-1}{e}^{-x\mathrm{/}b}d\lambda (x)$. Applying [F3] to reflection $T(x)=-x$ and $y\mapsto {\mathbf{1}}_{A_{-}}(y)b^{-1}{e}^{y\mathrm{/}b}$ shows that the reflected half contributes $\frac{1}{2}{\int }_{A_{-}}{b}^{-1}{e}^{y\mathrm{/}b}d\lambda (y)$. On $A_{+}$, $e^{-x\mathrm{/}b}=e^{-\mathrm{\mid }x\mathrm{\mid }\mathrm{/}b}$; on $A_{-}$, $e^{y\mathrm{/}b}=e^{-\mathrm{\mid }y\mathrm{\mid }\mathrm{/}b}$. The singleton at zero has Lebesgue measure zero by [F4]. Hence $\mathrm{Lap}(b)(A)={\int }_A(2b{)}^{-1}{e}^{-\mathrm{\mid }z\mathrm{\mid }\mathrm{/}b}d\lambda (z)$.

The identity in step 1.1 holds for every Borel set $A$. Its integrand is nonnegative and measurable; thus every Lebesgue-null Borel set has zero $\mathrm{Lap}(b)$ measure, and the displayed function is the claimed Radon–Nikodym density.

Define $f(z)={\prod }_{i=1}^d{f}_b(z_i)=(2b{)}^{-d}\exp (-\mathrm{\parallel }z{\mathrm{\parallel }}_1\mathrm{/}b)$; the equality factoring the exponential of a finite sum uses [F8]. The function is nonnegative and product-measurable. Repeated application of [F4] gives ${\int }_{{\mathbb{R}}^d}f(z)d{\lambda }^d(z)={\prod }_{i=1}^d{\int }_{\mathbb{R}}{f}_b(x)d\lambda (x)=1$, using [F1] for each one-dimensional integral. By [F5], $\nu (A)={\int }_{A}fd{\lambda }^d$ is therefore a probability measure.

For a measurable rectangle $A={\prod }_{i=1}^d{A}_i$, repeated Tonelli integration [F4] gives $\nu (A)={\prod }_{i=1}^d{\int }_{A_i}{f}_{b}d\lambda ={\prod }_{i=1}^d\mathrm{Lap}(b)(A_i)$. The finite product law has this same rectangle value by [F3]. Rectangles form a generating pi-system by [F2], and the constant sequence of whole-space rectangles is an increasing exhaustion with mass one for both measures, so [F6] identifies $\nu$ with $\mathrm{Lap}(b{)}^{\otimes d}$ on the entire product sigma-algebra. Taking unrestricted factors equal to $\mathbb{R}$ gives the stated coordinate marginals and factorization for every finite subfamily of coordinate events. These are exactly the events in the generated coordinate sigma-algebras, so the projections are independent by [F7].

By [F2], ${\mathrm{\Delta }}_{1}f$ is finite and nonnegative, so the zero and positive branches cover every allowed input; if ${\mathrm{\Delta }}_{1}f>0$, the scale $b={\mathrm{\Delta }}_{1}f\mathrm{/}\epsilon$ is positive. By [A1], [F3], and [F4], the noise vector has a probability law $\nu =\mathrm{Lap}(b{)}^{\otimes d}$. For each database $D$, define the output law as the pushforward of $\nu$ under $z\mapsto f(D)+z$; the inverse translation is continuous, so [F7] makes the preimage of every Borel set Borel and this is a probability measure.

If ${\mathrm{\Delta }}_{1}f=0$, assign the point mass at $f(D)$, which is a probability measure on the Borel output space. For either branch and each Borel event $A$, the evaluation $D\mapsto K(D,A)$ is measurable because every subset of the database domain is measurable by [F1]. Thus the assignment is a probability kernel as required by [F6].

Suppose ${\mathrm{\Delta }}_{1}f>0$ and put $b={\mathrm{\Delta }}_{1}f\mathrm{/}\epsilon$. By [F2]–[F4], the output law at database $D$ has Lebesgue density $p_D(x)=(2b{)}^{-d}\exp (-\mathrm{\parallel }x-f(D){\mathrm{\parallel }}_1\mathrm{/}b)$, since [F4] translates the product noise density from [F3] by $f(D)$.

For every $x\in {\mathbb{R}}^d$, coordinatewise triangle inequalities give $\mathrm{\parallel }x-f(D^{\mathrm{\prime }}){\mathrm{\parallel }}_1-\mathrm{\parallel }x-f(D){\mathrm{\parallel }}_1\le \mathrm{\parallel }f(D)-f(D^{\mathrm{\prime }}){\mathrm{\parallel }}_1\le {\mathrm{\Delta }}_{1}f$. The densities in [F3] are positive, and [F6] gives $\exp (-u)\mathrm{/}\exp (-v)=\exp (v-u)$ for real $u,v$. Therefore $p_D(x)\mathrm{/}{p}_{D^{\mathrm{\prime }}}(x)=\exp ((\mathrm{\parallel }x-f(D^{\mathrm{\prime }}){\mathrm{\parallel }}_1-\mathrm{\parallel }x-f(D){\mathrm{\parallel }}_1)\mathrm{/}b)\le \exp ({\mathrm{\Delta }}_{1}f\mathrm{/}b)=e^{\epsilon }$, where the inequality uses monotonicity from [F6]. Interchanging $D,D^{\mathrm{\prime }}$ proves the reverse pointwise ratio bound; integrating both bounds over $A$ yields the two event inequalities.

If ${\mathrm{\Delta }}_{1}f=0$, [F1] forces $\mathrm{\parallel }f(D)-f(D^{\mathrm{\prime }}){\mathrm{\parallel }}_1=0$ for every neighboring pair, hence $f(D)=f(D^{\mathrm{\prime }})$. The deterministic output laws are identical, so both event inequalities hold with $\delta =0$ (and $\epsilon \ge 0$). Combining this case with step 2.1 and applying [F5] proves the result.

Since ${\mathrm{\Delta }}_u>0$ and each score $u(D,r)$ is real, [F2] makes every weight $w_D(r)$ finite and positive. The nonempty finite sum $Z_D$ is therefore finite and strictly positive. For $A\subseteq R$, define $K(D,A)={\sum }_{r\in A}{w}_D(r)\mathrm{/}{Z}_D$. This is nonnegative, equals one on $R$, and is countably additive because a disjoint family of subsets of finite $R$ has only finitely many nonempty members. Thus each section is a probability measure by [F3].

For every $A\subseteq R$, $D\mapsto K(D,A)$ is measurable because every subset of the database domain is measurable by [F4]. Hence the assignment satisfies both conditions in [F5] and is a probability kernel.

For every $r\in R$, [F2] and monotonicity and addition for $\exp$ from [F6] give $w_D(r)\le e^{\epsilon \mathrm{/}2}{w}_{D^{\mathrm{\prime }}}(r)$; summing gives $Z_D\le e^{\epsilon \mathrm{/}2}{Z}_{D^{\mathrm{\prime }}}$. Applying the same argument with $D,D^{\mathrm{\prime }}$ interchanged gives $Z_{D^{\mathrm{\prime }}}\le e^{\epsilon \mathrm{/}2}{Z}_D$. Since the weights and normalizers are positive, [F6] then yields $(w_D(r)\mathrm{/}{Z}_D)\mathrm{/}(w_{D^{\mathrm{\prime }}}(r)\mathrm{/}{Z}_{D^{\mathrm{\prime }}})\le e^{\epsilon }$. Interchanging $D,D^{\mathrm{\prime }}$ gives the reverse point-mass bound. Summing over any event $A\subseteq R$ gives both $(\epsilon ,0)$ event inequalities, so [F4] proves privacy.

By [F3], the maximizing set is nonempty and its elements each have weight $e^{\epsilon {\mathrm{OPT}}_u(D)\mathrm{/}(2{\mathrm{\Delta }}_u)}$. Let $B$ be the event in the Statement. For each $r\in B$, its defining score inequality, monotonicity and addition for $\exp$ from [F6], and [F5] imply $w_D(r)\le e^{\epsilon {\mathrm{OPT}}_u(D)\mathrm{/}(2{\mathrm{\Delta }}_u)}(\mathrm{\mid }{R}_{\mathrm{OPT}}\mathrm{\mid }\mathrm{/}\mathrm{\mid }R\mathrm{\mid })e^{-t}$. There are at most $\mathrm{\mid }R\mathrm{\mid }$ such elements, while the normalizer is at least the sum of the maximizing weights, namely $\mathrm{\mid }{R}_{\mathrm{OPT}}\mathrm{\mid }{e}^{\epsilon {\mathrm{OPT}}_u(D)\mathrm{/}(2{\mathrm{\Delta }}_u)}$. Therefore the probability of $B$ is at most $e^{-t}$. If $B$ is empty its probability is zero and the same bound holds.

For each integer $m\ge 0$, put $n=2^m$ and define $g_m=\frac{1}{n}{\sum }_{j=1}^n{\mathbf{1}}_{\{g\ge j\mathrm{/}n\}}$. Each $g_m$ is a measurable simple function and $0\le g_m\le g$. Every level $j\mathrm{/}n$ counted at stage $m$ contributes the two levels $(2j-1)\mathrm{/}(2n)$ and $2j\mathrm{/}(2n)$ at stage $m+1$, so $g_{m+1}\ge g_m$. The largest dyadic level not exceeding any fixed $g(x)$ differs from $g(x)$ by less than $2^{-m}$, so $g_m(x)\uparrow g(x)$.

Apply the given event inequality to the $n$ level sets in step 1.1 and use [F3] on disjoint simple representations. Partition the range into $B_k=\{k\mathrm{/}n\le g<(k+1)\mathrm{/}n\}$ for $0\le k<n$ and $B_n=\{g=1\}$. Then $g_m={\sum }_{k=1}^{n-1}(k\mathrm{/}n){\mathbf{1}}_{B_k}+{\mathbf{1}}_{B_n}$, while each level set $\{g\ge j\mathrm{/}n\}$ is the disjoint union of $B_j,\dots ,B_n$. Rearranging these finite sums gives $\int g_{m}dP=\frac{1}{n}{\sum }_{j=1}^{n}P(g\ge j\mathrm{/}n)\le \frac{1}{n}{\sum }_{j=1}^n(e^{\epsilon }Q(g\ge j\mathrm{/}n)+\delta )=e^{\epsilon }\int g_{m}dQ+\delta$. This holds for every $m$.

Let $m\to \mathrm{\infty }$ in step 2.1. By [F4] and step 1.1, both nonnegative integrals converge to the corresponding integrals of $g$, so $\int gdP\le e^{\epsilon }\int gdQ+\delta$.

Fix ordered neighboring databases $D\sim D^{\mathrm{\prime }}$ and an event $B$ in the output sigma-algebra of $Z$. The function $g(y)=L(y,B)$ is measurable and takes values in $[0,1]$ by [F2].

Apply [F3] to the event inequality for $K(D,\cdot )$ and $K(D^{\mathrm{\prime }},\cdot )$ with this $g$. Then [F4] identifies the two integrals with $(KL)(D,B)$ and $(KL)(D^{\mathrm{\prime }},B)$, giving $(KL)(D,B)\le e^{\epsilon }(KL)(D^{\mathrm{\prime }},B)+\delta$. The pair and event were arbitrary, and [F5] makes $KL$ a probability kernel, so [F1] proves the claim.

The standard-Borel hypotheses are explicit as required by [F1]. Since $P(A)\le aQ(A)$ for every measurable $A$, $P\ll Q$. Choose a Radon–Nikodym density $r=dP\mathrm{/}dQ$ using [A1] and [F2].

By [F6], $a=e^{\epsilon }\ge 1$ and $a^{-1}>0$. The inequality $P(A)\le aQ(A)$ forces $r\le a$ $Q$-almost everywhere: otherwise some set $E_n=\{r\ge a+1\mathrm{/}n\}$ has positive $Q$-measure and violates the inequality after integration. Similarly $Q(A)\le aP(A)=a{\int }_{A}rdQ$ forces $r\ge a^{-1}$ $Q$-almost everywhere, since any positive-measure set where $r\le a^{-1}-1\mathrm{/}n$ violates that inequality. Thus $a^{-1}\le r\le a$ almost everywhere.

Let $E=\{r\ge 1\}$, $p=P(E)$, $q=Q(E)$, and $t=p-q$. Since $P(A)-Q(A)={\int }_A(r-1)dQ$, the set $E$ maximizes this difference and $E^c$ gives its negative. Hence $t={\sup }_A\mathrm{\mid }P(A)-Q(A)\mathrm{\mid }=\frac{1}{2}\int \mathrm{\mid }r-1\mathrm{\mid }dQ$. The event inequalities on $E$ and $E^c$ give $t\le (a-1)q$ and $at\le (a-1)(1-q)$, respectively. Adding yields $(a+1)t\le a-1$, so $t\le (a-1)\mathrm{/}(a+1)$.

The lower bound in step 2.1 makes $P$ and $Q$ equivalent. Define $s=1\mathrm{/}r$ on $\{r>0\}$ and $s=0$ on its null complement; [F7] makes it measurable. By [F3], ${\int }_{A}sdP={\int }_{A}srdQ=Q(A)$ for every measurable $A$, so $s=dQ\mathrm{/}dP$. The logarithm reciprocal identity in [F6] gives $\log s=-\log r$ almost everywhere, and both log densities are bounded in absolute value by $\epsilon$; [F4] therefore gives finite divergences and $D(P\mathrm{\parallel }Q)+D(Q\mathrm{\parallel }P)=\int (r-1)\log rdQ\le \epsilon \int \mathrm{\mid }r-1\mathrm{\mid }dQ=2\epsilon t$. By [F5], $D(Q\mathrm{\parallel }P)\ge 0$, and step 3.1 gives $2\epsilon t\le 2\epsilon (a-1)\mathrm{/}(a+1)\le \epsilon (a-1)$. Therefore $D(P\mathrm{\parallel }Q)\le \epsilon (a-1)=\epsilon (e^{\epsilon }-1)$.

Let $M(h,A)=(K(h,A)+L(h,A))\mathrm{/}2$, which is a probability kernel by [F2]. For every $h$, $M(h,A)=0$ implies $K(h,A)=L(h,A)=0$, so both sections are absolutely continuous with respect to $M(h,\cdot )$. Apply [F3] twice to obtain jointly measurable densities. Replace any value $+\mathrm{\infty }$ by $0$ in each density; this Borel operation preserves measurability by [F8] and changes no section measure on the common conull representation set, since each density has integral one. Call the resulting finite-valued functions $p(h,y)$ and $q(h,y)$. Let $\mathcal{C}$ be the countable generating algebra in [F4], containing $Y$. Define $G$ to be the set of $h$ for which, for every $C\in \mathcal{C}$, both $K(h,C)={\int }_{C}p(h,y)M(h,dy)$ and $L(h,C)={\int }_{C}q(h,y)M(h,dy)$ hold, and both DP inequalities hold for $C$. By [F2], [F5], and countability of $\mathcal{C}$, $G$ is measurable. It has full $\lambda$-measure by the joint representation property and the hypothesis. For $h\in G$, [F6] and [F7] make the density integrals finite measures; they agree with $K(h,\cdot )$ and $L(h,\cdot )$ on $\mathcal{C}$, so [F4] gives the density representations on every measurable event.

For fixed $h\in G$, put $\rho =K(h,\cdot )+L(h,\cdot )$, a finite measure. Let ${\mathcal{E}}_{\rho }$ be the measurable sets approximable in $\rho$-measure by members of $\mathcal{C}$. Complements preserve symmetric-difference measure, and $(A\cup B)\mathrm{△}(C\cup D)\subseteq (A\mathrm{△}C)\cup (B\mathrm{△}D)$ proves closure under finite unions. If $A_n\in {\mathcal{E}}_{\rho }$ and $A={\bigcup }_n{A}_n$, put $U_N={\bigcup }_{n\le N}{A}_n$ and $D_1=U_1$, $D_N=U_N\setminus U_{N-1}$ for $N>1$. The $D_N$ are disjoint and $A={\bigcup }_N{D}_N$, so countable additivity and finiteness of $\rho (A)$ give $\rho (A\setminus U_N)={\sum }_{j>N}\rho (D_j)\to 0$. Approximate each of the first $N$ sets closely enough that their finite union has arbitrarily small symmetric-difference measure from $U_N$. Thus ${\mathcal{E}}_{\rho }$ is a sigma-algebra containing $\mathcal{C}$, so it is the full target sigma-algebra. For any measurable $B$, choose $C_n\in \mathcal{C}$ with $\rho (B\mathrm{△}{C}_n)\to 0$. Then both $K(h,C_n)\to K(h,B)$ and $L(h,C_n)\to L(h,B)$, so the two inequalities on $\mathcal{C}$ pass to every measurable $B$.

Write $a=\exp (\epsilon )\ge 1$ and $c=\exp (-\epsilon )=1\mathrm{/}a>0$ by [F9]. On $G$, set $p_0=\min \{\max \{p,cq\},aq\}$, $\alpha =\int (p-aq{)}_{+}dM$, and $\beta =\int (cq-p{)}_{+}dM$. These quantities are finite and measurable in $h$ by [F5] and [F8]. The sets $A_h=\{y:p(h,y)>aq(h,y)\}$ and $B_h=\{y:p(h,y)<cq(h,y)\}$ are measurable by [F7]. Step 2.1 and the density identities give $\alpha =K(h,A_h)-aL(h,A_h)\le \delta$ and $a\beta =L(h,B_h)-aK(h,B_h)\le \delta$. Also $p_0=p-(p-aq{)}_{+}+(cq-p{)}_{+}$, so $m:=\int p_{0}dM=1-\alpha +\beta$. Hence $\max \{\alpha ,\beta \}\le \delta$.