“Exponential mechanism (differential privacy)”的意思、由来-开放百科全书

The exponential mechanism is a technique for designing differentially private algorithms. It was developed by Frank McSherry ^[1] and Kunal Talwar.^[2] Differential privacy is a technique for releasing statistical information about a database without revealing information about its individual entries.

Most of the initial research in the field of differential privacy revolved around real-valued functions which have relatively low sensitivity to change in the data of a single individual and whose usefulness is not hampered by small additive perturbations. A natural question is what happens in the situation when one wants to preserve more general sets of properties. The exponential mechanism helps to extend the notion of differential privacy to address these issues. Moreover, it describes a class of mechanisms that includes all possible differentially private mechanisms.

The exponential mechanism ^[3]

Algorithm

In very generic terms a privacy mechanism maps a set of

inputs from domain

, to a range

. The map may be randomized, in which case each element of the domain

corresponds to the probability distribution over the range

. The privacy mechanism makes no assumption about the nature of

and

apart from a base measure

. Let us define a function

. Intuitively this function assigns a score to the pair

, where

and

. The score reflects the appeal of the pair

, i.e. the higher the score, the more appealing the pair is.

Given the input

, the mechanism's objective is to return an

such that the function

is approximately maximized. To achieve this, set up the mechanism

as follows:

This definition implies the fact that the probability of returning an

increases exponentially with the increase in the value of

. Ignoring the base measure

then the value

which maximizes

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

the

should be finite.

Now, if a single change in

changes

by at most

then the numerator can change at most by a factor of

and the denominator minimum by a factor of

. Thus, the ratio of the new probability density (i.e. with new

) and the earlier one is at most

Accuracy

We would ideally want the random draws of

from the mechanism

to nearly maximize

. If we consider

to be

then we can show that the probability of the mechanism deviating from

is low, as long as there is a sufficient mass (in terms of

) of values

with value

close to the optimum.

Proof: The probability

is at most

, as the denominator can be at most one. Since both the probabilities have the same normalizing term so,

Proof: It follows from the previous lemma that the probability of the score being at least

. By hypothesis,

. Substituting the value of

we get this probability to be at least

. Multiplying with

yields the desired bound.

We can assume

for

to be less than or equal to one in all the computations, because we can always normalize with

Example application of the exponential mechanism ^[4]

Before we get into the details of the example let us define some terms which we will be using extensively throughout our discussion.

Definition (global sensitivity): The global sensitivity of a query

is its maximum difference when evaluated on two neighbouring datasets

Release mechanism

Definition (Usefulness): A mechanism

-useful for queries in class

with probability

, if

and every dataset

, for

Informally, it means that with high probability the query

will behave in a similar way on the original dataset

and on the synthetic dataset

Let us consider a common problem in Data Mining. Assume there is a database

with

entries. Each entry consist of

-tuples of the form

where

. Now, a user wants to learn a linear halfspace of the form

. In essence the user wants to figure out the values of

such that maximum number of tuples in the database satisfy the inequality. The algorithm we describe below can generate a synthetic database

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

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

-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:

we can output an

-useful dataset

that preserves

-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

. The algorithm outputs a dataset of size

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

Thus, if the RHS is less than one then we know for sure that the data set

exists. To bound the RHS to less than one we need

, where

is some positive constant. Since we stated earlier that we will output a dataset of size

, so using this bound on

we get

. Hence the lemma.

Definition: For any function

and input dataset

, the exponential mechanism outputs each dataset

with probability proportional to

From the exponential mechanism we know this preserves

-differential privacy. Let's get back to the proof of the Theorem.

To show that the mechanism satisfies the

-usefulness, we should show that it outputs some dataset

with

with probability

There are at most

output datasets and the probability that

is at most proportional to

. Thus by union bound, the probability of outputting any such dataset

is at most proportional to

Again, we know that there exists some dataset

for which

. Therefore, such a dataset is output with probability at least proportional to

The exponential mechanism in other domains

In the above example of the usage of exponential mechanism, one can output a synthetic dataset in a differentially private manner and can use the dataset to answer queries with good accuracy. Other private mechanisms, such as posterior sampling,^[5] which returns parameters rather than datasets, can be made equivalent to the exponential one.^[6]

Apart from the setting of privacy, the exponential mechanism has also been studied in the context of auction theory and classification algorithms.^[7] In the case of auctions the exponential mechanism helps to achieve a truthful auction setting.

References

1. ^Frank McSherry
2. ^Kunal Talwar
3. ^F.McSherry and K.Talwar. Mechanism Design via Differential Privacy. Proceedings of the 48th Annual Symposium of Foundations of Computer Science, 2007.
4. ^Avrim Blum,Katrina Ligett,Aaron Roth. A Learning Theory Approach to Non-Iteractive Database Privacy.In Proceedings of the 40th annual ACM symposium on Theory of computing, 2008
5. ^[https://arxiv.org/abs/1306.1066 Christos Dimitrakakis, Blaine Nelson, Aikaterini Mitrokotsa, Benjamin Rubinstein. Robust and Private Bayesian Inference. Algorithmic Learning Theory 2014]
6. ^[https://arxiv.org/abs/1502.07645 Yu-Xiang Wang, Stephen E. Fienberg, Alex Smola Privacy for Free: Posterior Sampling and Stochastic Gradient Monte Carlo. International Conference on Machine Learning, 2015.]
7. ^[https://arxiv.org/abs/0803.0924v2 Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim,Sofya Raskhodnikova, Adam Smith. What Can We Learn Privately? Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science.]

The exponential mechanism [3]