Dwork 2006 - Proof of the Separation Lemma

Summary

Both separation results use a hybrid argument over $2n$ steps; each step is bounded by Lemma 4.3: if a randomized map $Z$ is $\epsilon$-DP across all pairs of inputs, then for most $r$ the output distribution on the half-space $D_r=\{x:r\odot x=0\}$ is statistically within $O(({\epsilon }^2/(\alpha 2^d){)}^{1/3})$ of the output on the uniform distribution. The proof estimates $p(z)$ by pairwise-independent subsampling, uses DP to get tiny multiplicative variance (Claim 4.4), then Chebyshev and Markov.

Overview

Intuition (p. 41-42). Given $Z:D\to \{0,1{\}}^{\ast }$, we want $\mathrm{Pr}[Z(D_r)=z]$ to estimate $\mathrm{Pr}[Z(D)=z]$ with multiplicative error much smaller than $1+\epsilon$; then total variation is small “without having to pay a factor proportional to the domain size”. Two facts: (i) for random $r$, $D_r$ consists of $0^d$ plus $2^{d-1}-1$ pairwise-independent points of $\{0,1{\}}^d$; (ii) $\epsilon$-DP forces each $\mathrm{Pr}[Z(x)=z]$ into a small multiplicative interval around its mean $\mathrm{Pr}[Z(D)=z]$, so the subsample average has small variance.

Notation. $D=\{0,1{\}}^d$ with uniform random variable $D$; $D_r=\{x:r\odot x=0\}$, ${\bar{D}}_r=D\setminus D_r$; "$D_r$" also denotes a uniform random vector from $D_r$. $\mathrm{SD}(\cdot ,\cdot )$ is statistical difference (total variation). $p_x(z)=\mathrm{Pr}[Z(x)=z]$; $p(z)=2^{-d}{\sum }_x{p}_x(z)=\mathrm{Pr}[Z(D)=z]$. $D_{r,b}=\{x:r\odot x=b\}$ for $b\in \{0,1\}$.

Main Content

Lemma 4.3 - random subsets approximate the output distribution (pp. 42-43)

Let $Z:D\to \{0,1{\}}^{\ast }$ be a randomized map such that for all pairs $x,x^{\prime }\in D$ and all outputs $z$: $\mathrm{Pr}[Z(x)=z]\le e^{\epsilon }\mathrm{Pr}[Z(x^{\prime })=z]$. Let $0<\alpha$. With probability at least $1-\alpha$ over $r{\in }_R\{0,1{\}}^d\setminus 0^d$,

$$\mathrm{SD}(Z(D_r),Z(D))\le O\left((\frac{{\epsilon }^2}{\alpha \cdot 2^d}{)}^{1/3}\right).$$

Similarly, with probability at least $1-\alpha$, $\mathrm{SD}(Z({\bar{D}}_r),Z(D))\le O(({\epsilon }^2/(\alpha 2^d){)}^{1/3})$.

Claim 4.4 - variance of the subset estimator (p. 44)

Let $\tilde{\epsilon }=e^{\epsilon }-1$ and $\hat{p}(z;r,b)=\mathrm{Pr}[Z(D_{r,b})=z]$. Then over uniform $r,b$,

$$\mathbb{E}[\hat{p}(z;r,b)]=p(z),{\mathrm{Var}}_{r,b}[\hat{p}(z;r,b)]\le \frac{2{\tilde{\epsilon }}^{2}p(z{)}^2}{2^d}.$$

Proof of Claim 4.4 (p. 44)

Let $p^{\ast }={\min }_x{p}_x(z)$, $q_x=p_x(z)-p^{\ast }$, $\bar{q}=p(z)-p^{\ast }$. Variance of $\hat{p}$ equals that of $\hat{p}-p^{\ast }=\frac{2}{2^d}{\sum }_x{q}_x{\chi }^{\prime }(x)$, where ${\chi }^{\prime }(x)=1$ if $x\in D_{r,b}$ and $0$ otherwise; its mean is $\bar{q}=2^{-d}{\sum }_x{q}_x$. Then

$$\mathrm{Var}[\hat{p}]=\mathbb{E}\left[\right(\frac{1}{2^d}\sum _x{q}_x(2{\chi }^{\prime }(x)-1){)}^2].$$

Now $2{\chi }^{\prime }(x)-1=(-1{)}^{r\odot x\oplus b}$ has expectation $0$, and for $x\ne y$ the expectation of $(2{\chi }^{\prime }(x)-1)(2{\chi }^{\prime }(y)-1)$ is exactly $1/2^d$ (it would be $0$ for unrestricted $r$; the restriction $r\ne 0^d$ produces a small correlation of order $2^{-d}$). Checking this step: for $x\ne y$ and $w=x\oplus y\ne 0$, ${\sum }_{r\in \{0,1{\}}^d}(-1{)}^{r\odot w}=0$, so removing the term $r=0^d$ gives ${\mathbb{E}}_{r\ne 0}[(-1{)}^{r\odot w}]=-1/(2^d-1)$. The sign is negative rather than the printed $+1/2^d$ (numerically confirmed for $d=10$). Since all $q_x\ge 0$ a negative cross term only lowers the variance, so the bound below holds either way. Expanding the square:

$$\mathrm{Var}[\hat{p}]=\frac{1}{2^{2d}}\sum _x{q}_x^2+\frac{1}{2^{3d}}\sum _{x\ne y}{q}_x{q}_y=\frac{1-2^{-d}}{2^{2d}}\sum _x{q}_x^2+\frac{1}{2^d}(\frac{1}{2^d}\sum _x{q}_x{)}^2\le \frac{1}{2^d}(\underset{x}{\max }{q}_x^2+{\bar{q}}^2).$$

By the indistinguishability condition ${\max }_x{q}_x$ and $\bar{q}$ are both at most $(e^{\epsilon }-1)p^{\ast }\le \tilde{\epsilon }p(z)$. Plugging in gives the claim.

Proof of Lemma 4.3 (pp. 44)

Call $z$ $\delta$-good for $(r,b)$ if $|\hat{p}(z)-p(z)|\le \delta p(z)$. By Chebyshev and Claim 4.4, for all $z$,

$$\underset{r,b}{\mathrm{Pr}}[z\text{ not }\delta \text{-good}]\le \frac{\mathrm{Var}[\hat{p}(z)]}{{\delta }^{2}p(z{)}^2}\le \frac{2{\tilde{\epsilon }}^2}{{\delta }^2{2}^d}.$$

Draw $z$ from $p(\cdot )$. The expected fraction of non-good $z$ (weighted by $p$) is at most $2{\tilde{\epsilon }}^2/({\delta }^2{2}^d)$, so by Markov, with probability at least $1-\alpha$ over $(r,b)$, at most a fraction $\gamma =\frac{2{\tilde{\epsilon }}^2}{\alpha {\delta }^2{2}^d}$ of the mass is not $\delta$-good. If a $1-\gamma$ fraction of $z$ is $\delta$-good, the statistical difference between $\hat{p}$ and $p$ is at most $2(\gamma +\delta )$. Balancing $\gamma \approx \delta$ gives $\delta \approx (\frac{2{\tilde{\epsilon }}^2}{\alpha 2^d}{)}^{1/3}$ (the printed text writes the constant inside the cube root with $\alpha$ in the numerator, which appears to be a typesetting garble; the exponent $1/3$ and the ${\epsilon }^{2/3}{2}^{-d/3}$ scaling are unaffected), total distance at most $4\delta$, and $\tilde{\epsilon }<2\epsilon$ for $\epsilon \le 1$ gives the stated $O(({\epsilon }^2/(\alpha 2^d){)}^{1/3})$. The bit $b$ is irrelevant: $D_{r,1}={\bar{D}}_r$ swaps the two halves, and $Z(D)$ is the midpoint of $Z(D_r)$ and $Z({\bar{D}}_r)$, so $\mathrm{SD}(Z(D_r),Z(D))=\mathrm{SD}(Z({\bar{D}}_r),Z(D))$. Hence the statement holds over pairs $(r,0)$.

Proof of Theorem 4.1 (hybrid over $2n$ steps, pp. 42-43)

Distribution 0 is $\mathcal{M}(D_{r_1},\dots ,D_{r_n})$; show it is close to $\mathcal{M}(D,\dots ,D)$ by hybrids. After fixing $r_1,\dots ,r_i$ define the $i$-th hybrid $\mathcal{M}(D_{r_1},\dots ,D_{r_i},D,D,\dots ,D)$ and the $(i+1)$-st by replacing the next $D$ by $D_{r_{i+1}}$. Consider the randomized map $Z(x)=\mathcal{M}(D_{r_1},\dots ,D_{r_i},x,D,\dots ,D)$ with the $(i+1)$-th coordinate fixed to $x$. Then $Z(D)$ is the $i$-th hybrid and $Z(D_{r_{i+1}})$ the $(i+1)$-st. Because $\mathcal{M}$ is $\epsilon$-DP, $\mathrm{Pr}[Z(x)=z]\le e^{\epsilon }\mathrm{Pr}[Z(x^{\prime })=z]$ for all $x,x^{\prime }\in D$, so Lemma 4.3 with failure probability $\frac{1}{6n}$ per step gives $\mathrm{SD}=\sigma =O((n{\epsilon }^2/2^d{)}^{1/3})$. A union bound over $n$ steps: with probability at least $5/6$ every step is within $\sigma$, so $\mathrm{SD}(\mathcal{M}(D_{r_1},\dots ,D_{r_n}),\mathcal{M}(D,\dots ,D))\le n\sigma$. Repeating from Distribution 1 (using ${\bar{D}}_{r_i}$) gives the same bound with probability $5/6$. With probability at least $2/3$ both hold and the distance between Distributions 0 and 1 is at most $2n\sigma =O(n^{4/3}{\epsilon }^{2/3}{2}^{-d/3})$. $■$

Proof of Proposition 4.2

A local scheme gives ${\mathcal{M}}_Z(x_1,\dots ,x_n)=(Z(x_1),\dots ,Z(x_n))$ with $\mathrm{Pr}[Z(x)=z]\le e^{\epsilon }\mathrm{Pr}[Z(x^{\prime })=z]$ for all $x,x^{\prime },z$. It suffices that, with probability at least $2/3$ over $r\ne 0$, $Z(D_r)$ and $Z({\bar{D}}_r)$ are within $O({\epsilon }^{2/3}{2}^{-d/3})$ (Lemma 4.3 with $\alpha =1/3$, plus the midpoint argument). A hybrid argument across the $n$ independent coordinates gives difference $O(n{\epsilon }^{2/3}{2}^{-d/3})$. $■$

Examples

Checking Claim 4.4 numerically on a toy $Z$ (own code). Take $d=10$, a randomized response $Z$ that outputs a noisy version of $x$ with each bit flipped w.p. $1/(e^{\epsilon /d}+1)$ (which is $\epsilon$-DP over all pairs). Estimate the variance of $\hat{p}(z;r,b)$ over random $(r,b)$ for a fixed $z$ and compare with the bound $2{\tilde{\epsilon }}^{2}p(z{)}^2/2^d$.

import numpy as np
rng = np.random.default_rng(4)
d, eps = 10, 1.0
xs = np.array([[(i >> j) & 1 for j in range(d)] for i in range(2**d)])
flip = 1 / (np.exp(eps / d) + 1)                       # per-bit flip prob => eps-DP over all pairs x, x'
z = xs[rng.integers(2**d)]
dist = (xs != z).sum(1)
px = flip**dist * (1 - flip)**(d - dist)               # Pr[Z(x) = z]
p = px.mean()
est = []
for _ in range(20000):
    r = rng.integers(1, 2**d); rv = np.array([(r >> j) & 1 for j in range(d)]); b = rng.integers(2)
    mask = ((xs @ rv) % 2) == b
    est.append(px[mask].mean())
print(np.var(est), 2 * (np.exp(eps) - 1)**2 * p**2 / 2**d)   # empirical variance (~2e-11) is far below the bound (~5e-9)

Connections

• The proof technique (pairwise independence plus bounded multiplicative range implies small variance) is a clean example of how DP constraints convert to concentration. The same idea underlies later lower bounds for non-interactive query release.
• For measurement practitioners the take-away is not the proof but the conclusion: a privately released synopsis built for unknown future queries is expensive in sample size; define the reporting schema first.

See Also

• Dwork 2006 - Interactive versus Non-Interactive Separation Results
• Dwork 2006 - Calibrating Noise to Sensitivity - Overview
• Wasserman Zhou 2010 - Informative Mechanisms and the Impossibility Theorem (a related impossibility argument for consistency)