Score:0

Is privacy loss a random variable?

us flag

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?

kodlu avatar
sa flag
Note that this is a classical function from probability theory, dating back to at least the early 20th century, the log likelihood.
Daniel S avatar
ru flag
@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: https://www.waterboards.ca.gov/water_issues/programs/tmdl/docs/303d_policydocs/207.pdf
John Doe avatar
us flag
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).
Score:1
ru flag

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.

John Doe avatar
us flag
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)$.
John Doe avatar
us flag
...which now also makes sense when one needs to compute divergences (like in your example = isn't it just a KL-divergence?)
Daniel S avatar
ru flag
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.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.