Dong Roth Su 2022 - Privacy Amplification by Subsampling

Summary

If $M$ is $f$-DP on datasets of size $m$, then running $M$ on a uniformly random $m$-subset of an $n$-dataset is $C_p(f)$-DP with $p=m/n$ and $C_p(f)=\min \{f_p,f_p^{-1}{\}}^{\ast \ast }$, $f_p=pf+(1-p)\text{Id}$. For $(\epsilon ,\delta )$-DP this is strictly stronger than the classical $(\log (1-p+p{e}^{\epsilon }),p\delta )$ bound. The theorem is proved by converting to $(\epsilon ,\delta )$ guarantees, applying the classical result, and converting back.

Overview

Subsampling before a private mechanism amplifies privacy: a person not in the subsample enjoys perfect privacy, which happens with probability $1-p$. This was formalized for $(\epsilon ,\delta )$-DP by Kasiviswanathan et al. It fails for concentrated DP (CDP, zCDP), which motivated truncated CDP at the cost of complexity, and for Renyi DP it holds in a complex form (Wang-Balle-Kasiviswanathan). $f$-DP admits a simple, general statement.

Main Content

Setup. For $1\le m\le n$ and a dataset $S$ of $n$ individuals, ${\text{Sample}}_m(S)$ is a uniformly random $m$-subset. For $M$ defined on $X^m$, the subsampled mechanism is $M\circ {\text{Sample}}_m$ (the intermediate subset is not released, which distinguishes it from composition).

Definition 4.1 ( $p$-sampling operator)

For $0\le p\le 1$ write $f_p=pf+(1-p)\text{Id}$, where $\text{Id}(x)=1-x$. The $p$-sampling operator is

$$C_p(f)\triangleq \min \{f_p,f_p^{-1}{\}}^{\ast \ast },$$

where $f_p^{-1}$ is the inverse defined in (4) and $h^{\ast \ast }$ is the biconjugate (the greatest convex lower bound of $h$).

$C_p$ is a two-step transformation: symmetrization (min of $f_p$ and its inverse) and convexification (biconjugate). $C_p(f)$ is a symmetric trade-off function and $C_p(f)\le \min \{f_p,f_p^{-1}\}\le f_p$.

Theorem 4.2 (subsampling)

If $M$ is $f$-DP on $X^m$, then the subsampled mechanism $M\circ {\text{Sample}}_m$ is $C_p(f)$-DP on $X^n$, where the sampling ratio is $p=m/n$.

Properties of $C_p$ (qualitative amplification).

1. For $0\le p\le q\le 1$ and $f$ symmetric: $f=C_1(f)\le C_q(f)\le C_p(f)\le C_0(f)=\text{Id}$. As the sampling ratio falls from 1 to 0, privacy interpolates monotonically from $f$ to perfect privacy.
2. If $f\ge g$ then $C_p(f)\ge C_p(g)$ (more private stays more private).
3. $C_p(\text{Id})=\text{Id}$.

Closed form (Eq. 14)

For symmetric $f$, let $x^{\ast }$ be the unique fixed point $f(x^{\ast })=x^{\ast }$. Then

$$C_p(f)(x)=\{\begin{array}{ll}{f}_p(x),& x\in [0,x^{\ast }],\\ x^{\ast }+f_p(x^{\ast })-x,& x\in [x^{\ast },f_p(x^{\ast })],\\ f_p^{-1}(x),& x\in [f_p(x^{\ast }),1].\end{array}$$

(Proof in Appendix F.) The middle segment is the line of slope $-1$ joining the two curves, which is what the convexification produces.

Corollary 4.3 (amplification for $(\epsilon ,\delta )$-DP)

If $M$ is $(\epsilon ,\delta )$-DP on $X^m$ then $M\circ {\text{Sample}}_m$ is $C_p(f_{\epsilon ,\delta })$-DP on $X^n$, where

$$C_p(f_{\epsilon ,\delta })(\alpha )=\max \{f_{{\epsilon }^{\prime },{\delta }^{\prime }}(\alpha ),1-p\delta -p\frac{e^{\epsilon }-1}{e^{\epsilon }+1}-\alpha \},{\epsilon }^{\prime }=\log (1-p+p{e}^{\epsilon }),{\delta }^{\prime }=p\delta ,p=\frac{m}{n}.$$

Lemma 4.4 (classical, Ullman)

If $M$ is $(\epsilon ,\delta )$-DP then $M\circ {\text{Sample}}_m$ is $({\epsilon }^{\prime },{\delta }^{\prime })$-DP with ${\epsilon }^{\prime },{\delta }^{\prime }$ as above, i.e. $f_{{\epsilon }^{\prime },{\delta }^{\prime }}$-DP. Corollary 4.3 improves on it since $C_p(f_{\epsilon ,\delta })\ge f_{{\epsilon }^{\prime },{\delta }^{\prime }}$ by (15).

The improvement cannot be expressed in the $(\epsilon ,\delta )$ framework, and the loss from forcing the subsampled guarantee into $({\epsilon }^{\prime },{\delta }^{\prime })$ form compounds under composition. The paper states that the theorem holds for any subsampling scheme for which Lemma 4.4 holds, including independent coin flips per record.

Proof of Theorem 4.2 (Sec. 4.2)

1. By Proposition 2.12, $M$ is $(\epsilon ,\delta (\epsilon ))$-DP for all $\epsilon \ge 0$ with $\delta (\epsilon )=1+f^{\ast }(-e^{\epsilon })$.
2. By Lemma 4.4, $M\circ {\text{Sample}}_m$ satisfies, for each $\epsilon \ge 0$, $({\epsilon }^{\prime },{\delta }^{\prime })$-DP with ${\epsilon }^{\prime }=\log (1-p+p{e}^{\epsilon })$, ${\delta }^{\prime }=p(1+f^{\ast }(-e^{\epsilon }))$.
3. Eliminating $\epsilon$ gives ${\delta }^{\prime }=1+f_p^{\ast }(-e^{{\epsilon }^{\prime }})$ (Eq. 16, proved in Appendix F).
4. $f_p$ is asymmetric, so Proposition 2.12 cannot be applied directly; the paper extends it. Proposition 4.5 (special case of Proposition F.2): for a generic trade-off function $g$ let $\bar{x}=\inf \{x:g^{\prime }(x)=-1\}$. If $g(\bar{x})\ge \bar{x}$ and $M$ is $(\epsilon ,1+g^{\ast }(-e^{\epsilon }))$-DP for all $\epsilon \ge 0$, then $M$ is $\min \{g,g^{-1}{\}}^{\ast \ast }$-DP.
5. The condition holds for $g=f_p$: with $x^{\ast }$ the fixed point of $f$, $f^{\prime }(x^{\ast })=-1$ by symmetry about the $45^{\circ }$ line, so $f_p^{\prime }(x^{\ast })=-1$ and $\bar{x}\le x^{\ast }$; then $f_p(\bar{x})\ge f_p(x^{\ast })\ge f(x^{\ast })=x^{\ast }\ge \bar{x}$ because $f_p$ is decreasing and $f_p\ge f$.

Tightness: the bound is tight if $f=0$ (the original mechanism is blatantly non-private), shown in Appendix F (Discussion, Sec. 6).

Examples

Figure 6 (right): $\epsilon =3,\delta =0.1,p=0.2$

Setup: an $(3,0.1)$-DP mechanism applied to a 20% subsample. Solution: ${\epsilon }^{\prime }=\log (0.8+0.2e^3)=1.572$, ${\delta }^{\prime }=0.02$. At type I level $\alpha =0.3$: the classical bound gives $f_{{\epsilon }^{\prime },{\delta }^{\prime }}(0.3)=\max \{0,0.98-4.816(0.3),0.2076\times 0.68\}=0.141$, whereas Corollary 4.3 gives $\max \{0.141,0.799-0.3\}=0.499$. The smallest guaranteed sum of type I and II errors is $0.799$ with Corollary 4.3, $0.337$ with the classical bound, and $0.086$ with no subsampling (all recomputed). Interpretation: the paper’s remark that the improvement is “the shaded triangle” between $C_p(f_{\epsilon ,\delta })$ and $f_{{\epsilon }^{\prime },{\delta }^{\prime }}$ corresponds to a much higher guaranteed floor on the attacker’s total error. (The paper’s text describes this as the minimal error sum “can be significantly lower than the prediction of Lemma 4.4”; since $C_p\ge f_{{\epsilon }^{\prime },{\delta }^{\prime }}$ the guaranteed minimum is higher, so “lower” here is best read as a wording slip about the attacker’s advantage being lower. This is this note’s reading.)

import numpy as np
 
def f_eps_delta(a, eps, delta):
    return max(0.0, 1 - delta - np.exp(eps) * a, np.exp(-eps) * (1 - delta - a))
 
def Cp_eps_delta(a, eps, delta, p):      # Corollary 4.3
    e0, d0 = np.log(1 - p + p * np.exp(eps)), p * delta
    line = 1 - p * delta - p * (np.exp(eps) - 1) / (np.exp(eps) + 1) - a
    return max(f_eps_delta(a, e0, d0), line)
 
eps, delta, p = 3.0, 0.1, 0.2
grid = np.linspace(0, 1, 2001)
print(np.log(1 - p + p * np.exp(eps)), p * delta)                          # 1.572, 0.02
print(min(a + Cp_eps_delta(a, eps, delta, p) for a in grid))               # 0.799 (Cor. 4.3)
print(min(a + f_eps_delta(a, np.log(1 - p + p * np.exp(eps)), p * delta) for a in grid))  # 0.337 (Lemma 4.4)
print(min(a + f_eps_delta(a, eps, delta) for a in grid))                   # 0.086 (no subsampling)

Connections

• Used to analyze noisy SGD, where every step is a subsampled Gaussian mechanism: Dong Roth Su 2022 - Noisy SGD Privacy Analysis. The moments accountant had to bypass the missing amplification statement for divergence-based notions: Abadi 2016 - Moments Accountant Theorems and Proofs.
• Experiments/surveys that sample users (e.g. sampled user panels for lift studies) are subsampled mechanisms; whether DP amplification applies depends on the sampling being secret and independent of the data; see Conversion Lift Studies on Ad Platforms. This is a mapping, not a claim of the paper.

See Also

• Dong Roth Su 2022 - Gaussian Differential Privacy - Overview
• Dong Roth Su 2022 - Composition Theorem and Central Limit Theorems