Wasserman Zhou 2010 - Exponential Mechanism and Small Ball Probabilities

Summary

For an exponential mechanism whose loss is $\rho ({\hat{F}}_x,{\hat{F}}_z)$, accuracy is controlled by a small ball probability $R(k,ϵ)=P^k(\rho (F,\hat{G})\le ϵ)$, the chance that an i.i.d. sample of size $k$ from $P$ has empirical cdf within $ϵ$ of $F$ (Thm. 5.3). Choosing $k$ is delicate: too large breaks privacy-accuracy, too small breaks accuracy. For the KS distance the mechanism achieves $\rho (F,{\hat{F}}_Z)=O_P(n^{-1/3})$ with $k_n\asymp n^{2/3}$ (Thm. 5.4), slower than the non-private $n^{-1/2}$. This is the first link the authors know between DP and small ball probabilities.

Overview

The paper establishes three facts about exponential mechanisms (p. 13): (1) choosing the released size $k$ is delicate (“Taking $k$ too large compromises privacy. Taking $k$ too small compromises accuracy”); (2) accuracy can be bounded by a simple formula containing a small ball probability, a well-studied object in probability theory; (3) the formula applies to the KS distance, the mean, and Sobolev-class density estimation, and in each case gives the choice of $k$ and the convergence rate. Because of Thm. 3.2 some assumption on $P$ is needed; here $P$ has a bounded density $p$ (weaker than Lipschitz).

Main Content

The exponential mechanism (2) is used with $\xi (x,z)=\rho ({\hat{F}}_x,{\hat{F}}_z)$:

$$g_x(z)=\exp (-\frac{\alpha \rho ({\hat{F}}_x,{\hat{F}}_z)}{2{\Delta }_{n,k}}),h(z\mid x)=\frac{g_x(z)}{{\int }_{[0,1{]}^{rk}}{g}_x(s)ds},\Delta \equiv {\Delta }_{n,k}=\underset{\begin{array}{c}x,y\in {\mathcal{X}}^n\\ \delta (x,y)=1\end{array}}{\sup }\underset{z\in {\mathcal{X}}^k}{\sup }|\rho ({\hat{F}}_x,{\hat{F}}_z)-\rho ({\hat{F}}_y,{\hat{F}}_z)|.\text{\hspace{1em}(9)}$$

Lemma 5.1 (p. 14)

For the KS distance, ${\Delta }_{n,k}\le 1/n$.

Proof (Sec. 9.9, p. 30)

By the triangle inequality, for all $z\in {\mathcal{X}}^k$ and all $x,y\in {\mathcal{X}}^n$: $|\rho ({\hat{F}}_x,{\hat{F}}_z)-\rho ({\hat{F}}_y,{\hat{F}}_z)|\le \rho ({\hat{F}}_x,{\hat{F}}_y)$. Changing one entry of $x$ changes ${\hat{F}}_x(t)$ by at most $1/n$ at every $t$, so ${\sup }_t|{\hat{F}}_x(t)-{\hat{F}}_y(t)|=1/n$.

(This framework is used in Blum et al. 2008.) For the rest of the section $Z=(Z_1,\dots ,Z_k)$ is drawn from an exponential mechanism $Q_n$.

Definition 5.2 - small ball probability (p. 14)

Let $F$ be the cdf of $P$ and $\hat{G}$ the empirical cdf of a sample of size $k$ from $P$. Then

$$R(k,ϵ)=P^k(\rho (F,\hat{G})\le ϵ)$$

is called the small ball probability associated with $\rho$.

Theorem 5.3 - accuracy of the exponential mechanism (p. 14)

Assume $P$ has a bounded density $p$ and that there is ${ϵ}_n\to 0$ with

$$\mathbb{P}(\rho (F,{\hat{F}}_X)>\frac{{ϵ}_n}{16})=O\left(\frac{1}{n^c}\right)\text{\hspace{1em}(10)}$$

for some $c>1$. Further suppose $\rho$ satisfies the triangle inequality. Let $Z=(Z_1,\dots ,Z_k)$ be drawn from $g_x(z)$ in (9). Then

$$\mathbb{P}(\rho (F,{\hat{F}}_Z)>{ϵ}_n)\le \frac{({\sup }_{x}p(x){)}^k\exp (-\frac{3\alpha {ϵ}_n}{16\Delta })}{R(k,{ϵ}_n/2)}+O\left(\frac{1}{n^c}\right).\text{\hspace{1em}(11)}$$

If $k=k_n$ can be chosen so the right-hand side tends to $0$, the mechanism is consistent.

Proof (Sec. 9.8, pp. 28-30)

Let $B_{ϵ}=\{u\in {\mathcal{X}}^k:\rho (F,{\hat{F}}_u)\le ϵ\}$ and $A_n=\{\rho ({\hat{F}}_X,F)\le {ϵ}_n/16\}$, so $\mathbb{P}(A_n^c)=O(n^{-c})$ and $\mathbb{P}(\rho (F,{\hat{F}}_Z)>{ϵ}_n)\le \mathbb{P}(\rho (F,{\hat{F}}_Z)>{ϵ}_n,A_n)+O(n^{-c})$. Work on $A_n$. Upper bound on the bad mass. Triangle inequality: $\rho ({\hat{F}}_u,{\hat{F}}_X)\ge \rho ({\hat{F}}_u,F)-\rho ({\hat{F}}_X,F)$, so on $B_{ϵ}^c$ (where $\rho ({\hat{F}}_u,F)>ϵ$): ${\int }_{B_{ϵ}^c}{g}_X(u)du\le \exp \left(\frac{\alpha \rho ({\hat{F}}_X,F)}{2\Delta }\right)\exp (-\frac{\alpha ϵ}{2\Delta })$ (the volume of the cube is 1). Lower bound on the good mass. $\rho ({\hat{F}}_u,{\hat{F}}_X)\le \rho ({\hat{F}}_u,F)+\rho (F,{\hat{F}}_X)$, so on $B_{ϵ/2}$: ${\int }_{B_{ϵ/2}}{g}_X(u)du\ge \exp (-\frac{\alpha \rho (F,{\hat{F}}_X)}{2\Delta })\exp (-\frac{\alpha ϵ}{4\Delta })\mathrm{Vol}(B_{ϵ/2})$. Multiply and divide by ${\prod }_{i}p(u_i)$ and bound $\prod p(u_i)\le (\sup p{)}^k$: $\mathrm{Vol}(B_{ϵ/2})\ge \frac{1}{(\sup p{)}^k}{\int }_{B_{ϵ/2}}{\prod }_{i}p(u_i)du=\frac{R(k,ϵ/2)}{(\sup p{)}^k}$ (an i.i.d. draw from $p$ lies in $B_{ϵ/2}$ with probability $R(k,ϵ/2)$). Combine. The ratio of the two is at most $\frac{(\sup p{)}^k}{R(k,ϵ/2)}\exp (\frac{\alpha \rho ({\hat{F}}_X,F)}{\Delta }-\frac{\alpha ϵ}{4\Delta })$. On $A_n$, $\rho ({\hat{F}}_X,F)\le {ϵ}_n/16$, so the exponent is at most $\frac{\alpha {ϵ}_n}{16\Delta }-\frac{\alpha {ϵ}_n}{4\Delta }=-\frac{3\alpha {ϵ}_n}{16\Delta }$, giving (11).

5.1 The KS distance

Theorem 5.4 (p. 15)

Suppose $P$ has a bounded density $p$ and let $B:=\log {\sup }_{x}p(x)>0$. Let $Z$ be drawn from $g_x(z)$ in (9) with $\rho$ the KS distance. By requiring

$$k_n\asymp (\frac{3\alpha }{B}{)}^{2/3}{n}^{2/3},$$

we have, for ${ϵ}_n=2(\frac{B}{3\alpha }{)}^{1/3}{n}^{-1/3}$,

$$\rho (F,{\hat{F}}_Z)=O_P({ϵ}_n).\text{\hspace{1em}(12)}$$

So after sanitisation the rate is $n^{-1/3}$, slower than the non-private $n^{-1/2}$; “it is an open question whether this rate can be improved.”

Proof outline (Sec. 9.10, pp. 30-32)

(i) Condition (10). The VC dimension of orthants $(-\infty ,x_1]\times \cdots \times (-\infty ,x_r]$ is $r$, so $P({\sup }_t|{\hat{F}}_X(t)-F(t)|>{ϵ}_n/16)\le 8n^r\exp (-n({ϵ}_n/16{)}^2/32)$. With ${ϵ}_n\asymp n^{-1/3}$, $n{ϵ}_n^2\asymp n^{1/3}$, so this is $\exp \{-c{n}^{1/3}+r\log n\}=O(n^{-c})$ for every $c$, and (10) holds. (ii) Small ball probability. $\sqrt{k}({\hat{F}}_k-F)$ is approximated by a Brownian bridge ${\mathbb{B}}_k$ on $[0,1{]}^r$ (Csorgo and Revesz 1975): ${\sup }_t|\sqrt{k}({\hat{F}}_k-F)(t)-{\mathbb{B}}_k(t)|=O((\log k{)}^{3/2}{k}^{-\gamma })$ almost surely with $\gamma =1/(2(r+1))$, which is $o(1)$. The Brownian-sheet small ball estimate (Li and Shao 2001, Thm. 9.1 in the paper, stated for $r\ge 3$): for $0<ϵ\le 1$, $\log P({\sup }_{t\in [0,1{]}^r}|X_t|\le ϵ)\ge -C_r{ϵ}^{-2}{\log }^{2r-1}(1/ϵ)$, and the same bound holds for a Brownian bridge. Applying it with radius $\sqrt{k}ϵ/4$: $\log R(k,ϵ/2)\ge -C_1|\log (\sqrt{k}ϵ/4){|}^{2r-1}/(k{ϵ}^2)$. In the regime $\sqrt{k_n}{ϵ}_n\asymp 1$ (so $k_n{ϵ}_n^2\asymp 1$) the right side is a constant, so $R(k_n,{ϵ}_n/2)$ is bounded away from zero. (iii) Plug into (11). With $\Delta \le 1/n$ (Lemma 5.1) and $(\sup p{)}^k=e^{Bk}$, the first term of (11) is at most $\exp \{B{k}_n-3\alpha n{ϵ}_n/16\}\cdot O(1)$. For $k_n=\frac{1}{16}(3\alpha /B{)}^{2/3}{n}^{2/3}$ and ${ϵ}_n=2(B/3\alpha {)}^{1/3}{n}^{-1/3}$: $B{k}_n=\frac{1}{16}(3\alpha {)}^{2/3}{B}^{1/3}{n}^{2/3}$ while $3\alpha n{ϵ}_n/16=\frac{1}{8}(3\alpha {)}^{2/3}{B}^{1/3}{n}^{2/3}=2B{k}_n$. The exponent is therefore $-B{k}_n=-c{n}^{2/3}$ and the bound tends to $0$. Remark 9.2: any $k_n=C_4((3\alpha /B)n{)}^{2/3}$ with $C_4\ge 1/16$ (and ${ϵ}_n$ rescaled correspondingly) works with different constants, and in all cases $\sqrt{k_n}{ϵ}_n\asymp 1$.

The key balance: privacy-weighted loss $\alpha n{ϵ}_n$ must beat the entropy cost $B{k}_n$ of specifying $k$ points, and the small ball probability must not decay: $k_n{ϵ}_n^2\asymp 1$ gives ${ϵ}_n\asymp k_n^{-1/2}$, and $\alpha n{ϵ}_n\gtrsim k_n$ gives $k_n\lesssim \alpha n{ϵ}_n$; solving yields $k_n\asymp n^{2/3}$, ${ϵ}_n\asymp n^{-1/3}$.

5.2 The mean

Take $\rho (F,{\hat{F}}_Z)=\Vert \mu -\bar{Z}{\Vert }^2$ with $\mu =\int xdP(x)$ and $\bar{Z}$ the sample mean of $Z$. Then $\Delta \le r/n$ and $h(u\mid x)\approx e^{-n\Vert \bar{X}-\bar{Z}{\Vert }^2/(2\alpha )}$, so (approximately) $Z_1,\dots ,Z_k\sim N(\bar{X},k\alpha /n)$. It suffices to take $k=1$: then $\bar{Z}=\bar{X}+O_P(1/\sqrt{n})$, so $\bar{Z}$ converges at the same rate as $\bar{X}$. “This is not surprising: preserving a single piece of information requires a database of size $k=1$.”

Examples

KS constants (own computation). $n=10^4$, $\alpha =1$, density bound $\sup p=e$ ($B=1$): $k_n\asymp (3{)}^{2/3}{n}^{2/3}\approx 2.08\times 464\approx 966$ released points; ${ϵ}_n=2(1/3{)}^{1/3}{n}^{-1/3}\approx 0.064$ versus the non-private rate scale $n^{-1/2}=0.01$. Doubling the privacy budget ($\alpha =2$) raises $k_n$ by a factor $2^{2/3}=1.59$ and lowers ${ϵ}_n$ by $2^{-1/3}=0.79$.

import math
def ks_exponential_mechanism_design(n, alpha, B):
    k = (3*alpha/B)**(2/3) * n**(2/3)
    eps = 2*(B/(3*alpha))**(1/3) * n**(-1/3)
    return k, eps
print(ks_exponential_mechanism_design(10_000, 1.0, 1.0))   # about (966, 0.064)
print(ks_exponential_mechanism_design(10_000, 2.0, 1.0))

Connections

• Marketing measurement. The exponential mechanism releases structured objects (a whole synthetic dataset, a selected model) rather than noisy numbers. The slower rate $n^{-1/3}$ illustrates the price of generality: methods that release a reusable synthetic dataset pay more statistical accuracy than methods that release noisy sufficient statistics. For measurement practice, prefer releasing the specific aggregates (counts, sums, covariance) the analysis needs; use synthetic-data releases when exploratory flexibility is essential (Dwork 2006 - Interactive versus Non-Interactive Separation Results shows why).
• Small ball probabilities are a general tool for how many samples a mechanism can afford to release; for $k$ points to be informative they must be able to reproduce the truth within $ϵ$ with non-negligible probability.

See Also

• Wasserman Zhou 2010 - Orthogonal Series Density Estimation
• Wasserman Zhou 2010 - Rate Tables, Simulation and Open Questions
• Dwork Roth 2014 - Report Noisy Max and the Exponential Mechanism (generic utility analysis, $O(\frac{\Delta u}{\epsilon }\ln |R|)$)