SmallDB

Let $U = \{x_1, x_2, ... , x_n \} \subset \mathcal{X}^n$ be a set of $n$ points from a domain $\mathcal{X}$ and $Q = \{ f_1, f_2, ... \mid f_i : \mathcal{X} \rightarrow [0, 1] \}$ be a finite set of queries (functions). For any $f \in Q$ and finite set $S$ with domain $\mathcal{X}$, define

as the average over the values $\{ f(x) : x \in S \}$. Our goal is to find a subset $S$ with size

in a $(2 \epsilon, 0)$ differentially private manner, such that with probability at least $1 - \delta$, it holds simultaneously $\forall f \in Q$,

Existence of Small Representative

Let $X$ be a random element sampled uniformly from $U$. Then for a fixed $f \in Q$,

By Hoeffding, if we take $m = \frac{\ln |Q|}{\lambda^2}$ independent copies of $X$, denoted as $X_1, X_2, ..., X_m$, then

By union bound, this happens for some $f \in Q$ with probability less than 1. Therefore, if we enumerate over all sets $S \subset \mathcal{X}^m$ (which takes exponential time), then it is guaranteed that we can find one such that

This is tighter than the bound we would like to prove. The additional error is due to the privacy protection mechanism.

Release Representative Differential-Privately

We can just release the $S$ blatantly.

Counter Example

Suppose $\mathcal{X} = \{0, 1\}$, and $U = \{0, 0, ..., 0\} \subset \mathcal{X}^n$. Further, the set $Q$ contains two copies of the function $f$, defined as

Assume that $\lambda = \sqrt{\frac{ 2 \ln 2 }{ n } }$. Then $m = \frac{n \ln 2}{2 \ln 2} = n / 2$. Any $S \subset \mathcal{X}^m$ that contains no more than

ones, will satisfies

Now, consider a neighboring set $U' = \{0, 0, ..., 1\}$, obtained by replacing the last zero with one in $U$. Any $S$ with no more than $\lfloor \sqrt{\frac{ n \ln 2 }{ 2 } } + 1 \rfloor$ ones satisfies $|f(S) - f(U') | \le \lambda$.

Consider the scenario where we know the underlying set is either $U$ or $U'$. If a set in $\mathcal{X}^m$ with exactly $\lfloor \sqrt{\frac{ n \ln 2 }{ 2 } } + 1 \rfloor$ is released as an representative of the underlying set, we can infer immediately that the underlying set is $U'$.

Exponential Mechanism

One remedy for the above problem is that, for a set $S \subset \mathcal{X}^m$, even if $\exists f \in Q$, s.t., $|f(S) - f(U)| > \lambda$, we output $S$ as the representative of $U$ with some probability, because $S$ might be a feasible solution for $U$'s neighbors. This motivates the exponential mechanism. In particular,

1. It outputs the $S \in \mathcal{X}^m$ that minimizes $\max_{f \in Q} |f(S) - f(U)|$ with highest probability.
2. It outputs other $S \in \mathcal{X}^m$ with probability exponentially and inversely proportional to its error $\max_{f \in Q} | f(S) - f(U) |$.

The mechanism, termed $M$, is as follows.

1. For $S \in \mathcal{X}^m$, define weight $w(U, S) \doteq \exp(- \epsilon n \max_{f \in Q} | f(S) - f(U) | )$.
2. Sample and output an $S \in \mathcal{X}^m$ with probability

$$\frac{ w(U, S) }{ \sum_{T \in \mathcal{X}^m} w(U, T)}$$

Privacy

The mechanism $M$ is $(2\epsilon, 0)$ differentially private.

Proof. Let $U' \in \mathcal{X}^n$ be obtained by replacing exactly one element in $U$. For any $T \in \mathcal{X}^m$, by definition,

By symmetry, $\max_{f \in Q} |f(U) - f(T)| - \max_{f \in Q} |f(T) - f(U') | \in [- 1 / n, 1 / n ]$ and

For an $S \in \mathcal{X}^m$, it holds that

Error

For a set $U$, although we might assign probabilities to bad $S \in \mathcal{X}^m$, as long as the probability mass assigned is small, we are unlikely to get a bad representative.

Theorem. With probability at most $\delta$, $M$ returns an $S$, such that

$$\max_{f \in Q} | f(S) - f(U) | \ge \lambda + \frac{m \log |\mathcal{X}| + \log (1 / \delta) } {\epsilon n }$$

Proof. Let $S^* \in \mathcal{X}^m$ be the set that minimizes $\max_{f \in Q} |f(S) - f(U)|$.

For a $S \in \mathcal{X}^m$, if $\max_{f \in Q} |f(S) - f(U)| \ge \lambda + t$ for some $t > 0$, then

By union bound,

By requiring this probability to be bounded by some $\delta > 0$, we get

$\square$.

Substituting $m$ with $\frac{\log |Q| }{\lambda^2}$, the error is then

When $\lambda = (\frac{\log |Q| \log |\mathcal{X}| }{ \epsilon n})^{1 / 3}$, the error is given by

Reference

[1] S. Vadhan, “The Complexity of Differential Privacy,” in Tutorials on the Foundations of Cryptography, Y. Lindell, Ed. Cham: Springer International Publishing, 2017, pp. 347–450.