Dong Roth Su 2022 - Post-Processing, Blackwell, Primal-Dual and Group Privacy

Summary

$f$-DP is closed under post-processing, is the most informative privacy notion compatible with post-processing (its induced order equals the Blackwell order), is dual to an infinite family of $(\epsilon ,\delta )$ guarantees via the convex conjugate ($\delta (\epsilon )=1+f^{\ast }(-e^{\epsilon })$), and degrades under groups of size $k$ as $1-(1-f{)}^{\circ k}$, which turns $\mu$-GDP into $k\mu$-GDP.

Overview

Sections 2.3-2.5 establish the structural properties that make $f$-DP a complete privacy framework: post-processing, informativeness (Blackwell), a lossless dictionary with $(\epsilon ,\delta )$-DP (used later to import subsampling), and group privacy.

Main Content

Post-processing and informativeness (Sec. 2.3)

Proposition 2.8 and Lemma 2.9

If $M$ is $f$-DP, then $\text{Proc}\circ M$ is $f$-DP for any (randomized) $\text{Proc}:Y\to Z$. This follows from: for any distributions $P,Q$, $T(\text{Proc}(P),\text{Proc}(Q))\ge T(P,Q)$.

Theorem 2.10 (Blackwell, 1950)

For $P,Q$ on $Y$ and $P^{\prime },Q^{\prime }$ on $Z$ the following are equivalent: (a) $T(P,Q)\le T(P^{\prime },Q^{\prime })$; (b) there exists a randomized algorithm $\text{Proc}:Y\to Z$ with $\text{Proc}(P)=P^{\prime }$, $\text{Proc}(Q)=Q^{\prime }$.

Post-processing induces the Blackwell order ${⪯}_{\text{Blackwell}}$ on pairs of distributions (“easier to distinguish in the Blackwell sense”); $T(P,Q)\le T(P^{\prime },Q^{\prime })$ defines the testing order. Any privacy notion with post-processing has an induced order containing Blackwell’s, but should not be much larger: the trivial divergence $D_0\equiv 0$ has the largest order and is uninformative. $f$-DP is the most informative notion in that $\text{Ineq}({⪯}_{\text{trade-off}})=\text{Ineq}({⪯}_{\text{Blackwell}})$, whereas this fails for Renyi DP and $(\epsilon ,\delta )$-DP (proved in Appendix B, see Dong Roth Su 2022 - Divergence Conversion, Discussion and Limitations).

Primal-dual perspective (Sec. 2.4)

Proposition 2.11 (dual to primal)

Let $I$ be an index set with ${\epsilon }_i\in [0,\infty )$, ${\delta }_i\in [0,1]$. A mechanism is $({\epsilon }_i,{\delta }_i)$-DP for all $i\in I$ if and only if it is $f$-DP with $f={\sup }_{i\in I}{f}_{{\epsilon }_i,{\delta }_i}$.

Proposition 2.12 (primal to dual)

For a symmetric trade-off function $f$ (extended by $f(x)=\infty$ for $x<0$ and $x>1$), with convex conjugate $g^{\ast }(y)={\sup }_x\{yx-g(x)\}$, a mechanism is $f$-DP if and only if it is $(\epsilon ,\delta (\epsilon ))$-DP for all $\epsilon \ge 0$ with

$$\delta (\epsilon )=1+f^{\ast }(-e^{\epsilon }).$$

Corollary 2.13 (GDP to $(\epsilon ,\delta )$)

A mechanism is $\mu$-GDP if and only if it is $(\epsilon ,\delta (\epsilon ))$-DP for all $\epsilon \ge 0$, where

$$\delta (\epsilon )=\Phi (-\frac{\epsilon }{\mu }+\frac{\mu }{2})-e^{\epsilon }\Phi (-\frac{\epsilon }{\mu }-\frac{\mu }{2}).$$

The conversion is exact: any $(\epsilon ,\delta )$ guarantee derived for the Gaussian mechanism is implied by this corollary (it appeared earlier in Balle-Wang; “privacy profile” of Balle-Barthe-Gaboardi is an infinite collection of $(\epsilon ,\delta )$). Figure 4: each $(\epsilon ,\delta (\epsilon ))$ guarantee corresponds to two supporting lines (symmetric to each other) of the trade-off function, so keeping only a subset of $(\epsilon ,\delta )$ pairs (say, only small $\delta$) loses information. The primal view is easier for composition; the dual view (lower complexity of two parameters) is convenient for importing subsampling results (Dong Roth Su 2022 - Privacy Amplification by Subsampling).

Group privacy (Sec. 2.5)

Datasets $S,S^{\prime }$ are $k$-neighbors if there is a chain $S=S_0,\dots ,S_k=S^{\prime }$ with consecutive datasets neighboring or identical. $M$ is $f$-DP for groups of size $k$ if $T(M(S),M(S^{\prime }))\ge f$ for all $k$-neighbors.

Theorem 2.14 (group privacy)

If a mechanism is $f$-DP then it is $[1-(1-f{)}^{\circ k}]$-DP for groups of size $k$, where $h^{\circ k}$ is the $k$-fold iterated composition ($h^{\circ 2}(x)=h(h(x))$). In particular, if a mechanism is $\mu$-GDP then it is $k\mu$-GDP for groups of size $k$.

$1-(1-f{)}^{\circ k}$ is a trade-off function, symmetric if $f$ is; the bound is closed and tight (cannot be improved in general), and $1-(1-f{)}^{\circ k}\le 1-(1-f{)}^{\circ (k-1)}$, consistent with larger groups being easier to detect (proved in Appendix A).

Proposition 2.15 (Laplace limit of group pure DP)

Fix $\mu \ge 0$ and set $\epsilon =\mu /k$. As $k\to \infty$, $1-(1-f_{\epsilon ,0}{)}^{\circ k}\to T(\text{Lap}(0,1),\text{Lap}(\mu ,1))$ uniformly on $[0,1]$.

Two remarks: $T(\text{Lap}(0,1),\text{Lap}(\mu ,1))$ is not equal to $f_{\epsilon ,\delta }$ for any $(\epsilon ,\delta )$, so $(\epsilon ,\delta )$-DP is not expressive enough for the group operation; and the approximation is accurate even for small $k$: for $\mu =1,k=4$ it is within 0.005 uniformly. ($\text{Lap}(\mu ,b)$ has density $\frac{1}{2b}{e}^{-|x-\mu |/b}$.)

Examples

Group privacy for a household

Setup: a release is $0.5$-GDP per individual; a household has $k=4$ members whose records are correlated and all enter the dataset. Solution: Theorem 2.14 gives $4\times 0.5=2$-GDP for the group. At $\delta =10^{-5}$, 0.5-GDP corresponds to $\epsilon \approx 1.99$ and 2-GDP to $\epsilon \approx 10.0$ (recomputed from Corollary 2.13). Interpretation: protecting a group of four costs a fivefold increase in $\epsilon$ at the same $\delta$ here, but only a linear increase in $\mu$, which is the natural scale. For marketing data where one household contributes many devices, group size matters for the claimed level.

Connections

• RDP post-processing and group privacy are weaker analogues (order halves, $\epsilon$ triples): Mironov 2017 - RDP Properties and Composition.
• The Blackwell/Neyman-Pearson viewpoint is the basis for the composition theorem: Dong Roth Su 2022 - Composition Theorem and Central Limit Theorems.
• Subsampling uses the dual representation: Dong Roth Su 2022 - Privacy Amplification by Subsampling.

See Also

• Dong Roth Su 2022 - Gaussian Differential Privacy - Overview
• Dong Roth Su 2022 - Divergence Conversion, Discussion and Limitations