Hands-On Differential Privacy

Appendix C. The Exponential Mechanism Satisfies Bounded Range

An exponential mechanism $E{M}_S(·)$ with quality score $S$ satisfies bounded range with $2ϵ$. If $S$ is monotonic over the data, then $E{M}_S$ satisfies bounded range with $ϵ$.

Proof

When $M(·)$ is the exponential mechanism $E{M}_S(·)$, then given adjacent inputs $x$ and $x^{\prime }$ and outcomes $y$ and $y^{\prime }$, it suffices to show that:

$$\frac{Pr[M(x)=y]}{Pr[M(x^{\prime })=y]}\frac{Pr[M(x^{\prime })=y^{\prime }]}{Pr[M(x)=y^{\prime }]}\le e^{2ϵ}$$

By the definition of the exponential mechanism, this becomes:

$$\frac{\exp \left(\frac{ϵS(x,y)}{\Delta S}\right)}{\exp \left(\frac{ϵS(x^{\prime },y)}{\Delta S}\right)}\frac{\exp \left(\frac{ϵS(x^{\prime },y^{\prime })}{\Delta S}\right)}{\exp \left(\frac{ϵS(x,y^{\prime })}{\Delta S}\right)}$$

Since $\Delta S$ is the sensitivity of the scoring function, we know that $\left|\frac{S(x,y)-S(x^{\prime },y)}{\Delta S}\right|\le 1$ and $\left|\frac{S(x^{\prime },y^{\prime })-S(x,y^{\prime })}{\Delta S}\right|\le 1$:

$$\exp \left(\frac{ϵ(S(x,y)-S(x^{\prime },y))}{\Delta S}\right)\exp \left(\frac{ϵ(S(x^{\prime },y^{\prime })-S(x,y^{\prime }))}{\Delta S}\right)\le e^{ϵ}{e}^{ϵ}=e^{2ϵ}$$

To demonstrate that $E{M}_S$ satisfies bounded range with $ϵ$ when $S$ is monotonic, consider what this means for adjacent inputs $x$ and $x^{\prime }$. Monotonicity means that $S(a)\ge S(b^{\prime })$ when $a>b$, so there are two possible outcomes:

• If $x\ge x^{\prime }$, then $S(x,y)-S(x^{\prime },y)\ge 0$ and $S(x^{\prime },y^{\prime })-S(x,y^{\prime })\le 0$, meaning that:

  $$\exp \left(\frac{ϵ(S(x,y)-S(x^{\prime },y))}{\Delta S}\right)\exp \left(\frac{ϵ(S(x^{\prime },y^{\prime })-S(x,y^{\prime }))}{\Delta S}\right)\le e^{ϵ}·1=e^{ϵ}$$

• If $x\le x^{\prime }$, then $S(x,y)-S(x^{\prime },y)\le 0$ and $S(x^{\prime },y^{\prime })-S(x,y^{\prime })\ge 0$, meaning that:

  $$\exp \left(\frac{ϵ(S(x,y)-S(x^{\prime },y))}{\Delta S}\right)\exp \left(\frac{ϵ(S(x^{\prime },y^{\prime })-S(x,y^{\prime }))}{\Delta S}\right)\le 1·e^{ϵ}=e^{ϵ}$$

This concludes the proof.