The exponential mechanism is a technique for designing differentially private algorithms.
It was developed by Frank McSherry[1] and Kunal Talwar[2] in 2007.
Their work was recognized as a co-winner of the 2009 PET Award for Outstanding Research in Privacy Enhancing Technologies.
[3] 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.
Source:[4] In very generic terms, a privacy mechanism maps a set of
Intuitively this function assigns a score to the pair
, define: This definition implies the fact that the probability of returning an
is low, as long as there is a sufficient mass (in terms of
Proof: It follows from the previous lemma that the probability of the score being at least
Source:[5] Before we get into the details of the example let us define some terms which we will be using extensively throughout our discussion.
The following is due to Avrim Blum, Katrina Ligett and Aaron Roth.
Definition (Usefulness): A mechanism[permanent dead link]
Now, a user wants to learn a linear halfspace of the form
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.
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: Theorem: For any class of functions
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
We borrow the Uniform Convergence Theorem from combinatorics and state a corollary of it which aligns to our need.
Proof: We know from the uniform convergence theorem that where probability is over the distribution of the dataset.
Since we stated earlier that we will output a dataset of size
the event that the exponential mechanism outputs some dataset
the event that the exponential mechanism outputs some dataset
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,[6] which returns parameters rather than datasets, can be made equivalent to the exponential one.
[7] Apart from the setting of privacy, the exponential mechanism has also been studied in the context of auction theory and classification algorithms.