0
$\begingroup$

The "standard" book (Dwork & Roth, 2014) defines Privacy loss as follows (p. 18)

The quantity

$$ \mathcal{L}^{(\xi)}_{\mathcal{M}(x) || \mathcal{M}(y)} = \ln \left( \frac{\Pr[\mathcal{M}(x) = \xi]}{\Pr[\mathcal{M}(y) = \xi]} \right) $$

is important to us; we refer to it as the privacy loss incurred by observing $\xi$. [...] As always, the probability space is over the coins of the mechanism $\mathcal{M}$.

So it doesn't say that it's a random variable.

From my point of view, it is just a real-valued function $\mathcal{L}: (\mathcal{M} \times x \times y \times \xi) \to \mathbb{R}$ as it outputs log of the ratio of two probabilities (numbers betw. 0 and 1).

The "probability space is over the coins" is a bit confusing, but I guess they refer here to the $\Pr[.]$ functions, since $\mathcal{M}$ are probability densities or discrete distributions.

However, on many places I have encountered the privacy loss random variable, e.g. here:

Abadi, M., Chu, A., Goodfellow, I., McMahan, H. B., Mironov, I., Talwar, K., & Zhang, L. (2016). Deep Learning with Differential Privacy. Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, 308–318. https://doi.org/10.1145/2976749.2978318

Privacy loss is a random variable dependent on the random noise added to the algorithm. [...] We instead compute the log moments of the privacy loss random variable, which compose linearly. We then use the moments bound, together with the standard Markov inequality, to obtain the tail bound, that is the privacy loss in the sense of differential privacy.

Or here:

http://www.gautamkamath.com/CS860notes/lec5.pdf

Definition 2. Let $Y$ and $Z$ be two random variables. The privacy loss random variable $\mathcal{L}_{Y||Z}$ is [...]

My question is: If privacy loss is a random variable, it must have a corresponding probability distribution, that is to integrate to 1. But this doesn't seem to be the general case of a log of ratio of two PDFs (Laplace, Gaussian) or discrete distributions (Exponential mechanism, etc.). It is also never mentioned as a condition for the privacy loss.

So: Am I missing something or is it just a misleading (semantically wrong) name?

$\endgroup$
3
  • 1
    $\begingroup$ Note that this is a classical function from probability theory, dating back to at least the early 20th century, the log likelihood. $\endgroup$
    – kodlu
    Sep 11, 2021 at 2:40
  • 1
    $\begingroup$ @kodlu I think it was Good and Turing who first tidied up and formalised the use of logarithms. Good's own survey of the development of what he called "weight of evidence" is a good read: waterboards.ca.gov/water_issues/programs/tmdl/docs/… $\endgroup$
    – Daniel S
    Sep 11, 2021 at 5:45
  • $\begingroup$ Thanks, but I don't see why log-likelihood is somehow relevant to privacy loss here... I know it from machine learning for getting probability of data given the model's parameters (and taking log or negative for easier computations, such as minimizing). $\endgroup$
    – John Doe
    Sep 12, 2021 at 10:52

1 Answer 1

1
$\begingroup$

It's a function of your observation $\xi$, so if your observation is itself drawn from a sensible probability distribution (e.g. so that observations that are impossible values for $M(x)$ and $M(y)$ do not occur), it is a random variable. Usually we consider the case where observations are taken from a distribution matching either $M(x)$ or $M(y)$. Note that the function itself does not represent a probability distribution and so does not need to sum/integrate to 1.

An example might help here. Suppose I have 2 four-sided dice one of which (say die $x$) produces 1, 2, 3, 4 with probability 1/4, 1/4, 1/6, 1/3 respectively and the other (say die $y$) produces them with probabilities 1/4, 1/4, 1/3, 1/6 respectively. Taking $\xi$ as the number rolled by a die and using logarithms in base 2, then $\mathcal L(\xi)$ takes three possible values according to $\mathcal L(1)=0$, $\mathcal L(2)=0$, $\mathcal L(3)=-1$ and $\mathcal L(4)=1$.

If the die rolled is die $x$ then $\mathbb P(\mathcal L(\xi)=0)=1/2$, $\mathbb P(\mathcal L(\xi)=-1)=1/6$ and $\mathbb P(\mathcal L(\xi)=1)=1/3$. We confirm that the probabilities do sum to 1.

Likewise if the die rolled is die $y$ then $\mathbb P(\mathcal L(\xi)=0)=1/2$, $\mathbb P(\mathcal L(\xi)=-1)=1/3$ and $\mathbb P(\mathcal L(\xi)=1)=1/6$.

Note that the expected privacy loss in the first case is 1/6 and in the second it is -1/6. In both cases, it is a measure of the expected information (in bits) supporting a belief that the $x$ die was rolled gained per die roll.

$\endgroup$
3
  • $\begingroup$ Thanks for the example! So it is a random variable, indeed! It converts reals to reals (the $\xi$ param), and is distributed according to $\mathcal{M}(x)$. $\endgroup$
    – John Doe
    Sep 12, 2021 at 10:48
  • 1
    $\begingroup$ ...which now also makes sense when one needs to compute divergences (like in your example = isn't it just a KL-divergence?) $\endgroup$
    – John Doe
    Sep 12, 2021 at 10:55
  • 1
    $\begingroup$ The expectation of the privacy loss when $\xi$ is sampled from $M(x)$ is indeed KL-divergence. Of course, a random variable contains more information than its expectation. $\endgroup$
    – Daniel S
    Sep 12, 2021 at 23:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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