In McSherry and Talwar's paper which introduces the exponential mechanism for differential privacy, they say that the Laplace mechanism can be captured by choosing the score function as $q(d,r) = - |f(d) - r|$ in the exponential mechanism.

However, choosing such a score function creates the following mechanism (assuming a uniform base measure $\mu$):

$$ \mathcal{E}^\epsilon_q(d) := \text{choose $r$ with probability $\propto e^{\frac{- \epsilon |f(d) - r|}{2 \Delta q}}$} $$

whereas the Laplace mechanism is defined as:

$$ \mathcal{L}(d) := \text{choose $r$ with probability $\propto e^{\frac{- \epsilon |f(d) - r|}{\Delta f}}$} $$

As I think that $\Delta q$ and $\Delta f$ are equal for this choice of function $q$, it seems that those two mechanisms are different. Where did I make a mistake ?

  • $\begingroup$ Can you add a link to the paper you're referring to? $\endgroup$ – Ted Mar 3 '19 at 21:09

Your Answer

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

Browse other questions tagged or ask your own question.