Algorithm

In very generic terms, a privacy mechanism maps a set of ${\displaystyle n\,\!}$ inputs from domain ${\displaystyle {\mathcal {D}}\,\!}$ to a range ${\displaystyle {\mathcal {R}}\,\!}$. The map may be randomized, in which case each element of the domain ${\displaystyle {\mathcal {D}}\,\!}$ corresponds to a probability distribution over the range ${\displaystyle {\mathcal {R}}\,\!}$. The privacy mechanism makes no assumption about the nature of ${\displaystyle {\mathcal {D}}\,\!}$ and ${\displaystyle {\mathcal {R}}\,\!}$ apart from a base measure ${\displaystyle \mu \,\!}$ on ${\displaystyle {\mathcal {R}}\,\!}$. Let us define a function ${\displaystyle q:{\mathcal {D}}^{n}\times {\mathcal {R}}\rightarrow \mathbb {R} \,\!}$. Intuitively this function assigns a score to the pair ${\displaystyle (d,r)\,\!}$, where ${\displaystyle d\in {\mathcal {D}}^{n}\,\!}$ and ${\displaystyle r\in {\mathcal {R}}\,\!}$. The score reflects the appeal of the pair ${\displaystyle (d,r)\,\!}$, i.e. the higher the score, the more appealing the pair is. Given the input ${\displaystyle d\in {\mathcal {D}}^{n}\,\!}$, the mechanism's objective is to return an ${\displaystyle r\in {\mathcal {R}}\,\!}$ such that the function ${\displaystyle q(d,r)\,\!}$ is approximately maximized. To achieve this, set up the mechanism ${\displaystyle {\mathcal {E}}_{q}^{\varepsilon }(d)\,\!}$ as follows:
Definition: For any function ${\displaystyle q:({\mathcal {D}}^{n}\times {\mathcal {R}})\rightarrow \mathbb {R} \,\!}$, and a base measure ${\displaystyle \mu \,\!}$ over ${\displaystyle {\mathcal {R}}\,\!}$, define:

${\displaystyle {\mathcal {E}}_{q}^{\varepsilon }(d):=\,\!}$ Choose ${\displaystyle r\,\!}$ with probability proportional to ${\displaystyle e^{\varepsilon q(d,r)}\times \mu (r)\,\!}$, where ${\displaystyle d\in {\mathcal {D}}^{n},r\in {\mathcal {R}}\,\!}$.

This definition implies the fact that the probability of returning an ${\displaystyle r\,\!}$ increases exponentially with the increase in the value of ${\displaystyle q(d,r)\,\!}$. Ignoring the base measure ${\displaystyle \mu \,\!}$ then the value ${\displaystyle r\,\!}$ which maximizes ${\displaystyle q(d,r)\,\!}$ has the highest probability. Moreover, this mechanism is differentially private. Proof of this claim will follow. One technicality that should be kept in mind is that in order to properly define ${\displaystyle {\mathcal {E}}_{q}^{\varepsilon }(d)\,\!}$ the ${\displaystyle \int _{r}e^{\varepsilon q(d,r)}\times \mu (r)\,\!}$ should be finite.

Theorem (differential privacy): ${\displaystyle {\mathcal {E}}_{q}^{\varepsilon }(d)\,\!}$ gives ${\displaystyle (2\varepsilon \Delta q)\,\!}$-differential privacy.

Proof: The probability density of ${\displaystyle {\mathcal {E}}_{q}^{\varepsilon }(d)\,\!}$ at ${\displaystyle r\,\!}$ equals

${\displaystyle {\frac {e^{\varepsilon q(d,r)}\mu (r)}{\int e^{\varepsilon q(d,r)}\mu (r)\,dr}}.\,\!}$

Now, if a single change in ${\displaystyle d\,\!}$ changes ${\displaystyle q\,\!}$ by at most ${\displaystyle \Delta q\,\!}$ then the numerator can change at most by a factor of ${\displaystyle e^{\varepsilon \Delta q}\,\!}$ and the denominator minimum by a factor of ${\displaystyle e^{-\varepsilon \Delta q}\,\!}$. Thus, the ratio of the new probability density (i.e. with new ${\displaystyle d\,\!}$) and the earlier one is at most ${\displaystyle \exp(2\varepsilon \Delta q)\,\!}$.

Accuracy

We would ideally want the random draws of ${\displaystyle r\,\!}$ from the mechanism ${\displaystyle {\mathcal {E}}_{q}^{\varepsilon }(d)\,\!}$ to nearly maximize ${\displaystyle q(d,r)\,\!}$. If we consider ${\displaystyle \max _{r}q(d,r)\,\!}$ to be ${\displaystyle OPT\,\!}$ then we can show that the probability of the mechanism deviating from ${\displaystyle OPT\,\!}$ is low, as long as there is a sufficient mass (in terms of ${\displaystyle \mu }$) of values ${\displaystyle r\,\!}$ with value ${\displaystyle q\,\!}$ close to the optimum.

Lemma: Let ${\displaystyle S_{t}=\{r:q(d,r)>OPT-t\}\,\!}$ and ${\displaystyle {\bar {S}}_{2t}=\{r:q(d,r)\leq OPT-2t\}\,\!}$, we have ${\displaystyle p({\bar {S}}_{2t})\,\!}$ is at most ${\displaystyle \exp(-\varepsilon t)/\mu (S_{t})\,\!}$. The probability is taken over ${\displaystyle {\mathcal {R}}\,\!}$.

Proof: The probability ${\displaystyle p({\bar {S}}_{2t})\,\!}$ is at most ${\displaystyle p({\bar {S}}_{2t})/p(S_{t})\,\!}$, as the denominator can be at most one. Since both the probabilities have the same normalizing term so,

${\displaystyle {\frac {p({\bar {S}}_{2t})}{p(S_{t})}}={\frac {\int _{{\bar {S}}_{2t}}\exp(\varepsilon q(d,r))\mu (r)\,dr}{\int _{S_{t}}\exp(\varepsilon q(d,r))\mu (r)\,dr}}\leq \exp(-\varepsilon t){\frac {\mu ({\bar {S}}_{2t})}{\mu (S_{t})}}.}$

The value of ${\displaystyle \mu ({\bar {S}}_{2t})\,\!}$ is at most one, and so this bound implies the lemma statement.

Theorem (Accuracy): For those values of ${\displaystyle t\geq \ln \left({\frac {OPT}{t\mu (S_{t})}}\right)/\varepsilon \,\!}$, we have ${\displaystyle E[q(d,{\mathcal {E}}_{q}^{\varepsilon }(d))]\geq OPT-3t\,\!}$.

Proof: It follows from the previous lemma that the probability of the score being at least ${\displaystyle OPT-2t\,\!}$ is ${\displaystyle 1-\exp(-\varepsilon t)/\mu (S_{t})\,\!}$. By hypothesis, ${\displaystyle t\geq \ln \left({\frac {OPT}{t\mu (S_{t})}}\right)/\varepsilon \,\!}$. Substituting the value of ${\displaystyle t\,\!}$ we get this probability to be at least ${\displaystyle 1-t/OPT\,\!}$. Multiplying with ${\displaystyle OPT-2t\,\!}$ yields the desired bound.

We can assume ${\displaystyle \mu (A)\,\!}$ for ${\displaystyle A\subseteq {\mathcal {R}}\,\!}$ to be less than or equal to one in all the computations, because we can always normalize with ${\displaystyle \mu ({\mathcal {R}})\,\!}$ .

Release mechanism

The following is due to Avrim Blum, Katrina Ligett and Aaron Roth.

Definition (Usefulness): A mechanism ${\displaystyle {\mathcal {A}}\,\!}$ is ${\displaystyle (\alpha ,\delta )\,\!}$-useful for queries in class ${\displaystyle H\,\!}$ with probability ${\displaystyle 1-\delta \,\!}$, if ${\displaystyle \forall h\in H\,\!}$ and every dataset ${\displaystyle D\,\!}$, for ${\displaystyle {\widehat {D}}={\mathcal {A}}(D)\,\!}$, ${\displaystyle |Q_{h}({\widehat {D}})-Q_{h}(D)|\leq \alpha \,\!}$.

Informally, it means that with high probability the query ${\displaystyle Q_{h}\,\!}$ will behave in a similar way on the original dataset ${\displaystyle D\,\!}$ and on the synthetic dataset ${\displaystyle {\widehat {D}}\,\!}$.
Consider a common problem in Data Mining. Assume there is a database ${\displaystyle D\,\!}$ with ${\displaystyle n\,\!}$ entries. Each entry consist of ${\displaystyle k\,\!}$-tuples of the form ${\displaystyle (x_{1},x_{2},\dots ,x_{k})\,\!}$ where ${\displaystyle x_{i}\in \{0,1\}\,\!}$. Now, a user wants to learn a linear halfspace of the form ${\displaystyle \pi _{1}x_{1}+\pi _{2}x_{2}+\cdots +\pi _{k-1}x_{k-1}\geq x_{k}\,\!}$. In essence the user wants to figure out the values of ${\displaystyle \pi _{1},\pi _{2},\dots ,\pi _{k-1}\,\!}$ such that maximum number of tuples in the database satisfy the inequality. The algorithm we describe below can generate a synthetic database ${\displaystyle {\widehat {D}}\,\!}$ which will allow the user to learn (approximately) the same linear half-space while querying on this synthetic database. The motivation for such an algorithm being that the new database will be generated in a differentially private manner and thus assure privacy to the individual records in the database ${\displaystyle D\,\!}$.

In this section we show that it is possible to release a dataset which is useful for concepts from a polynomial VC-Dimension class and at the same time adhere to ${\displaystyle \varepsilon \,\!}$-differential privacy as long as the size of the original dataset is at least polynomial on the VC-Dimension of the concept class. To state formally:

Theorem: For any class of functions ${\displaystyle H\,\!}$ and any dataset ${\displaystyle D\subset \{0,1\}^{k}\,\!}$ such that

${\displaystyle |D|\geq O\left({\frac {k\cdot \operatorname {VCDim} (H)\log(1/\alpha )}{\alpha ^{3}\varepsilon }}+{\frac {\log(1/\delta )}{\alpha \varepsilon }}\right)\,\!}$

we can output an ${\displaystyle (\alpha ,\delta )\,\!}$-useful dataset ${\displaystyle {\widehat {D}}\,\!}$ that preserves ${\displaystyle \varepsilon \,\!}$-differential privacy. As we had mentioned earlier the algorithm need not be efficient.

One interesting fact is that the algorithm which we are going to develop generates a synthetic dataset whose size is independent of the original dataset; in fact, it only depends on the VC-dimension of the concept class and the parameter ${\displaystyle \alpha \,\!}$. The algorithm outputs a dataset of size ${\displaystyle {\tilde {O}}(\operatorname {VCDim} (H)/\alpha ^{2})\,\!}$

We borrow the Uniform Convergence Theorem from combinatorics and state a corollary of it which aligns to our need.

Lemma: Given any dataset ${\displaystyle D\,\!}$ there exists a dataset ${\displaystyle {\widehat {D}}\,\!}$ of size ${\displaystyle =O(\operatorname {VCDim} (H)\log(1/\alpha ))/\alpha ^{2}\,\!}$ such that ${\displaystyle \max _{h\in H}|Q_{h}(D)-Q_{h}({\widehat {D}})|\leq \alpha /2\,\!}$.

Proof:

We know from the uniform convergence theorem that

${\displaystyle {\begin{aligned}&\Pr \left[\,\left|Q_{h}(D)-Q_{h}({\widehat {D}})\right|\geq {\frac {\alpha }{2}}{\text{ for some }}h\in H\right]\\[5pt]\leq {}&2\left({\frac {em}{\operatorname {VCDim} (H)}}\right)^{\operatorname {VCDim} (H)}\cdot e^{-\alpha ^{2}m/8},\end{aligned}}}$

where probability is over the distribution of the dataset. Thus, if the RHS is less than one then we know for sure that the data set ${\displaystyle {\widehat {D}}\,\!}$ exists. To bound the RHS to less than one we need ${\displaystyle m\geq \lambda (\operatorname {VCDim} (H)\log(m/\operatorname {VCDim} (H))/\alpha ^{2})\,\!}$, where ${\displaystyle \lambda \,\!}$ is some positive constant. Since we stated earlier that we will output a dataset of size ${\displaystyle {\tilde {O}}(\operatorname {VCDim} (H)/\alpha ^{2})\,\!}$, so using this bound on ${\displaystyle m\,\!}$ we get ${\displaystyle m\geq \lambda (\operatorname {VCDim} (H)\log(1/\alpha )/\alpha ^{2})\,\!}$. Hence the lemma.

Now we invoke the exponential mechanism.

Definition: For any function ${\displaystyle q:((\{0,1\}^{k})^{n}\times (\{0,1\}^{k})^{m})\rightarrow \mathbb {R} \,\!}$ and input dataset ${\displaystyle D\,\!}$, the exponential mechanism outputs each dataset ${\displaystyle {\widehat {D}}\,\!}$ with probability proportional to ${\displaystyle e^{q(D,{\widehat {D}})\varepsilon n/2}\,\!}$.

From the exponential mechanism we know this preserves ${\displaystyle (\varepsilon nGS_{q})\,\!}$-differential privacy. Let's get back to the proof of the Theorem.

We define ${\displaystyle (q(D),q({\widehat {D}}))=-\max _{h\in H}|Q_{h}(D)-Q_{h}({\widehat {D}})|\,\!}$.

To show that the mechanism satisfies the ${\displaystyle (\alpha ,\delta )\,\!}$-usefulness, we should show that it outputs some dataset ${\displaystyle {\widehat {D}}\,\!}$ with ${\displaystyle q(D,{\widehat {D}})\geq -\alpha \,\!}$ with probability ${\displaystyle 1-\delta \,\!}$. There are at most ${\displaystyle 2^{km}\,\!}$ output datasets and the probability that ${\displaystyle q(D,{\widehat {D}})\leq -\alpha \,\!}$ is at most proportional to ${\displaystyle e^{-\varepsilon \alpha n/2}\,\!}$. Thus by union bound, the probability of outputting any such dataset ${\displaystyle {\widehat {D}}\,\!}$ is at most proportional to ${\displaystyle 2^{km}e^{-\varepsilon \alpha n/2}\,\!}$. Again, we know that there exists some dataset ${\displaystyle {\widehat {D}}\in (\{0,1\}^{k})^{m}\,\!}$ for which ${\displaystyle q(D,{\widehat {D}})\geq -\alpha /2\,\!}$. Therefore, such a dataset is output with probability at least proportional to ${\displaystyle e^{-\alpha \varepsilon n/4}\,\!}$.

Let ${\displaystyle A:=\,\!}$ the event that the exponential mechanism outputs some dataset ${\displaystyle {\widehat {D}}\,\!}$ such that ${\displaystyle q(D,{\widehat {D}})\geq -\alpha /2\,\!}$.

${\displaystyle B:=\,\!}$ the event that the exponential mechanism outputs some dataset ${\displaystyle {\widehat {D}}\,\!}$ such that ${\displaystyle q(D,{\widehat {D}})\leq -\alpha \,\!}$.

${\displaystyle \therefore {\frac {\Pr[A]}{\Pr[B]}}\geq {\frac {e^{-\alpha \varepsilon n/4}}{2^{km}e^{-\alpha \varepsilon n/2}}}={\frac {e^{\alpha \varepsilon n/4}}{2^{km}}}.\,\!}$

Now setting this quantity to be at least ${\displaystyle 1/\delta \geq (1-\delta )/\delta \,\!}$, we find that it suffices to have

${\displaystyle n\geq {\frac {4}{\varepsilon \alpha }}\left(km+\ln {\frac {1}{\delta }}\right)\geq O\left({\frac {d\cdot \operatorname {VCDim} (H)\log(1/\alpha )}{\alpha ^{3}\varepsilon }}+{\frac {\log(1/\delta )}{\alpha \varepsilon }}\right).\,\!}$

And hence we prove the theorem.