---
# System prepended metadata

title: Numerical implementation of Exp Mechanism

---

 # Numerical implementation of Exp Mechanism 
(final project proposal, due  April  14, 2022.)
 # Motivation - what is the problem you are working on/why does it matter 

As professor mentioned in class, exponential mechanism is generic in theory yet computationally hard. So, it is worthwhile to study how this mechanism is used in practice. In particular, straightforward implementation (see below) suffers from numerical issues.

**We want to make implementation more robust and study how numerical factors effect the algorithm.**
![](https://i.imgur.com/nJwSMik.png)




# Related work - is there an existing body of literature aimed at this problem 

https://www.microsoft.com/en-us/research/wp-content/uploads/2012/10/lsbs.pdf
studies the numerical issue in laplace mechanism

https://arxiv.org/abs/1912.04222
Proposed to replace  base-$\epsilon$ DP with an equivalent base-2 DP in DP definition, in order to implement exponential mechanism exactly.

# Implementation - what dataset are you using? What approach or algorithm are you using?


## Algorithm (pseudocode)
Input: $s_1,..,s_k$ utility scores in descending order
Ouput: $\tilde{P_i},..,\tilde{P_k}$ noramlized probablity mass 

for i=1; i<=k; i++
// transform to new score

$$ s_i^{\prime} := s_i - s_1$$

endfor 

for j=1; j<=k; j++
// calculate probability

$$
\hat{P_j} = \frac{e^{\epsilon \cdot s_j^{\prime} }}{ \Sigma_i { e^{\epsilon \cdot s_i^{\prime} }}}
$$


endfor 

for j=2; j<=k; j++
// normalize
$$
\tilde{P_j} = \frac{\hat{P_j}}{ \Sigma_i {\hat{P_i}}}
$$ 

endfor 

$$
\tilde{P_1} = 1 -  \Sigma_{i,i \neq 1} {\tilde{P_i}}
$$

## Dataset
1. We can run exponential mechanism directly, using mocked utility function as input.
2. We can also run exponential mechanism-based queries, on mocked data.


# Evaluation - either empirical or theoretical depending on your project

**Theoretical result**: see if (or how far) we can formally analyze the privacy guarantee of numerical implementation, e.g. using $\epsilon-\delta$ DP framework

**Simulation**: Study  (1) How the number of bits affect the probability mass.(2) how the number of bits in implementation affect  the trade off between utility and privacy.

