I am trying to understand some of the papers that present identity query mechanisms that satisfies differential privacy, for example the compressive mechanism which uses what they call a universal mechanism. What I mean by identity query is: given a dataset the mechanism which returns dataset back with some noise added to it. The problem that I have is how can we define the sensitivity of such a query mechanism, $Q(D)=D$? If we look at neighboring datasets, $D'$, which differs by one entry, the sensitivity is defined as: $$ \max(|D-D'|_1) \text{ over all possible } D' $$ But this is confusing because to me this is a nonsensical statement since $D$ and $D'$ are not in the same dimension ($D'$ has one less row than $D$) and we cannot compute the $L_1$ norm. Could you please explain to me what I am missing?


There are two ways to define "neighboring databases" in differential privacy. One version is the one you are thinking of: we start with $D$ which has $n$ data points in it (for example) and we look at $D' \subset D$ with $n - 1$ data points.

The other (and IMHO more common) version is to define $D$ and $D'$ as neighboring if they have the same number of elements and differ in a single element, so: $|D \cap D'| = n-1$ and $|D| = |D'| = n$. This is often written as $d_{H}(D,D') = 1$, where $d_H$ is the Hamming distance between the data sets: the idea being that if $D$ and $D'$ were both bit-vectors then "differing in a a single entry" corresponds to Hamming distance 1.

When publishing noisy data (the example you mention), the latter definition is more natural.

  • $\begingroup$ Is there any ordering of the strength between the two adjacency definitions? I.e. can we claim that DP mechanisms satisfying second adjacency definition will inherit DP property according to the first adjacency definition? $\endgroup$ – Dionysis M Jan 21 '20 at 15:24
  • $\begingroup$ well, actually replacing an element in a dataset can be written as a composition of one addition and one removal of a datapoint - hence it seems to hold in general that if algorithm is $(\varepsilon, \delta)$-DP under second adjacency definition (Hamming distance equals 1), it will also be $(\frac{1}{2}\varepsilon, \frac{1}{2}\delta) $ under first adjacency definition. $\endgroup$ – Dionysis M Jan 21 '20 at 19:06

See this review paper, and the references therein. https://arxiv.org/pdf/1602.01063.pdf

In short, implementing the identity query is equivalent to producing a synthetic data set. Some methods make synthetic data sets by first making a lower-dimensional summary of the data. In the example of the Compressive Mechanism, the summary is the size-k compressive measurements from the full sample of size n. That summary has a maximum it can change, when data sets differ by only one entry. The noise is applied in the summary-space, according to the summary's sensitivity, then decoded back out to a full-size synthetic data set.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.