Dwork Roth 2014 - Report Noisy Max and the Exponential Mechanism

Summary

Two ways to privately select the best item from a discrete set. Report Noisy Max adds $\mathrm{Lap}(1/\epsilon )$ to each of $m$ counts and returns only the argmax index: $(\epsilon ,0)$-DP though the count vector has sensitivity $m$. The exponential mechanism samples $r$ with probability $\propto \exp (\epsilon u(x,r)/2\Delta u)$ for an arbitrary utility $u$: $(\epsilon ,0)$-DP, and with high probability the chosen element’s utility is within $O(\frac{\Delta u}{\epsilon }\ln |R|)$ of optimal. Instantiating noisy max with Gumbel noise reproduces the exponential mechanism exactly.

Overview

“Differentially private selection”: the space of outcomes is discrete and the task is to produce a “best” answer. Adding noise directly to the value is wrong when value and utility are not on a common scale (pricing, structured outputs), and releasing all noisy counts wastes budget. The principle at work in Report Noisy Max is information minimization: release only the index of the winner, not the noisy counts.

Main Content

Report Noisy Max (pp. 34-37)

Example 3.4 - Most common medical condition (p. 35)

Setup. Which of $m$ conditions is (approximately) most common in respondents’ medical histories? For each condition, query whether each individual has ever received the diagnosis. An individual can have many conditions, so the vector of $m$ counts has high sensitivity ($\Delta f=m$). Solution. Add $\mathrm{Lap}(1/\epsilon )$ noise to each count and publish only the index of the maximum (the noisy counts are not released; the “winning” count can be released at no extra privacy cost). The noise scale $1/\epsilon$ is independent of $m$.

Report Noisy Max

Given $m$ counting queries: add independent $\mathrm{Lap}(1/\epsilon )$ noise to each count and return the index of the largest noisy count (ties ignored).

Claim 3.9 (p. 35)

Report Noisy Max is $(\epsilon ,0)$-differentially private.

Proof (pp. 35-37)

Let $D=D_0\cup \{a\}$; let $c$ and $c^{\prime }$ be the count vectors on $D$ and $D_0$. Two properties: (1) Monotonicity of counts: $c_j\ge c_j^{\prime }$ for all $j$; (2) Lipschitz: $1+c_j^{\prime }\ge c_j$ for all $j$. Fix $i\in [m]$ and fix $r_{-i}$, a draw from $[\mathrm{Lap}(1/\epsilon ){]}^{m-1}$ for all coordinates except $i$; argue for each $r_{-i}$ separately.

Upper bound. Define $r^{\ast }=\min r_i$ such that $c_i+r_i>c_j+r_j$ for all $j\ne i$. On $D$, $i$ wins iff $r_i\ge r^{\ast }$. For every $j\ne i$: $c_i+r^{\ast }>c_j+r_j$ implies $(1+c_i^{\prime })+r^{\ast }\ge c_i+r^{\ast }>c_j+r_j\ge c_j^{\prime }+r_j$, so $c_i^{\prime }+(r^{\ast }+1)>c_j^{\prime }+r_j$. Hence if $r_i\ge r^{\ast }+1$, $i$ wins on $D^{\prime }$. Therefore

$$\mathrm{Pr}[i\mid D^{\prime },r_{-i}]\ge \mathrm{Pr}[r_i\ge 1+r^{\ast }]\ge e^{-\epsilon }\mathrm{Pr}[r_i\ge r^{\ast }]=e^{-\epsilon }\mathrm{Pr}[i\mid D,r_{-i}].$$

Lower bound. Define $r^{\ast }=\min r_i$ such that $c_i^{\prime }+r_i>c_j^{\prime }+r_j$ for all $j\ne i$ (winning threshold on $D^{\prime }$). Then $1+c_i^{\prime }+r^{\ast }>1+c_j^{\prime }+r_j$ gives $c_i+(r^{\ast }+1)\ge c_i^{\prime }+(r^{\ast }+1)>(1+c_j^{\prime })+r_j\ge c_j+r_j$ so $i$ wins on $D$ if $r_i\ge r^{\ast }+1$, and $\mathrm{Pr}[i\mid D,r_{-i}]\ge e^{-\epsilon }\mathrm{Pr}[i\mid D^{\prime },r_{-i}]$. Multiply through by $e^{\epsilon }$ in both directions and integrate over $r_{-i}$.

The exponential mechanism (Sec. 3.4, pp. 37-41)

Motivation. Designed for situations where adding noise directly to the computed quantity “can completely destroy its value”, for example setting a price in an auction.

Example 3.5 - Pumpkins (p. 37)

Setup. An abundant supply of pumpkins and four bidders A, F, I, K; A, F, I each bid $1.00 and K bids $3.01. “What is the optimal price?” The text states: at $3.01 revenue is $3.01; at $3.00 and at $1.00 revenue is $3.00; at $3.02 the revenue is zero. Lesson. Adding a small amount of positive noise to the optimal price can drive revenue to zero, so noise must be added to the choice via a utility function, not to the optimal value. Arithmetic caveat (own check): revenue at a price $p$ is $p\times \#\{\text{bids}\ge p\}$; at $1.00 all four bidders buy, giving $4.00, which is the true revenue maximiser; the text’s “$3.00 at $1.00” appears to be a slip. The fragility at $3.02 (zero revenue) is unaffected.

Definition 3.4 - Exponential mechanism (pp. 37-38)

Given a range $R$ and a utility function $u:{\mathbb{N}}^{|\mathcal{X}|}\times R\to \mathbb{R}$ mapping database/output pairs to scores, define the sensitivity of $u$ with respect to its database argument (it may be arbitrarily sensitive in $r$):

$$\Delta u\equiv \underset{r\in R}{\max }\underset{x,y:\Vert x-y{\Vert }_1\le 1}{\max }|u(x,r)-u(y,r)|.$$

The exponential mechanism ${\mathcal{M}}_E(x,u,R)$ selects and outputs $r\in R$ with probability proportional to $\exp \left(\frac{\epsilon u(x,r)}{2\Delta u}\right)$.

Why the factor 2. The naive privacy loss is $\ln \frac{\exp (\epsilon u(x,r)/\Delta u)}{\exp (\epsilon u(y,r)/\Delta u)}=\epsilon [u(x,r)-u(y,r)]/\Delta u\le \epsilon$, but this overlooks the normalisation term, which can change when one person raises some utilities and lowers others. The actual mechanism reserves half the privacy budget for the normaliser. The range $R$ must be independent of the data (pumpkins: the price grid must not depend on actual bids, else some price has non-zero weight on one database and zero on a neighbour). The mechanism may be infeasible to implement if $R$ is super-polynomially large.

Theorem 3.10 (pp. 38-39)

The exponential mechanism preserves $(\epsilon ,0)$-differential privacy.

Proof (pp. 38-39; finite $R$, not necessary)

For neighbours $x,y$ and $r\in R$:

$$\frac{\mathrm{Pr}[{\mathcal{M}}_E(x,u,R)=r]}{\mathrm{Pr}[{\mathcal{M}}_E(y,u,R)=r]}=\frac{\exp \left(\frac{\epsilon u(x,r)}{2\Delta u}\right)}{\exp \left(\frac{\epsilon u(y,r)}{2\Delta u}\right)}\cdot \frac{{\sum }_{r^{\prime }}\exp \left(\frac{\epsilon u(y,r^{\prime })}{2\Delta u}\right)}{{\sum }_{r^{\prime }}\exp \left(\frac{\epsilon u(x,r^{\prime })}{2\Delta u}\right)}=\exp \left(\frac{\epsilon (u(x,r)-u(y,r))}{2\Delta u}\right)\cdot \frac{{\sum }_{r^{\prime }}\exp (\frac{\epsilon u(y,r^{\prime })}{2\Delta u})}{{\sum }_{r^{\prime }}\exp (\frac{\epsilon u(x,r^{\prime })}{2\Delta u})}\le \exp \left(\frac{\epsilon }{2}\right)\exp \left(\frac{\epsilon }{2}\right)\cdot 1=e^{\epsilon }.$$

The first factor is at most $e^{\epsilon /2}$ since $|u(x,r)-u(y,r)|\le \Delta u$. In the sum ratio, each term $\exp (\epsilon u(y,r^{\prime })/2\Delta u)\le \exp (\epsilon /2)\exp (\epsilon u(x,r^{\prime })/2\Delta u)$, giving the other $e^{\epsilon /2}$. The ratio $\ge e^{-\epsilon }$ follows by symmetry.

Theorem 3.11 - Utility of the exponential mechanism (pp. 39-40)

Fix a database $x$ and let $R_{\mathrm{OPT}}=\{r\in R:u(x,r)={\mathrm{OPT}}_u(x)\}$ with ${\mathrm{OPT}}_u(x)={\max }_{r\in R}u(x,r)$. Then

$$\mathrm{Pr}\left[u({\mathcal{M}}_E(x,u,R))\le {\mathrm{OPT}}_u(x)-\frac{2\Delta u}{\epsilon }(\ln \frac{|R|}{|R_{\mathrm{OPT}}|}+t)\right]\le e^{-t}.$$

Proof (p. 40)

Each $r$ with $u(x,r)\le c$ has unnormalised mass at most $\exp (\epsilon c/2\Delta u)$, so the “bad” set has total unnormalised mass at most $|R|\exp (\epsilon c/2\Delta u)$. At least $|R_{\mathrm{OPT}}|\ge 1$ elements have mass $\exp (\epsilon {\mathrm{OPT}}_u(x)/2\Delta u)$, a lower bound on the normaliser. Hence $\mathrm{Pr}[u({\mathcal{M}}_E)\le c]\le \frac{|R|}{|R_{\mathrm{OPT}}|}\exp \left(\frac{\epsilon (c-{\mathrm{OPT}}_u(x))}{2\Delta u}\right)$; plug in $c=\mathrm{OPT}-\frac{2\Delta u}{\epsilon }(\ln \frac{|R|}{|R_{\mathrm{OPT}}|}+t)$.

Corollary 3.12 (p. 40)

Since $|R_{\mathrm{OPT}}|\ge 1$: $\mathrm{Pr}[u({\mathcal{M}}_E(x,u,R))\le {\mathrm{OPT}}_u(x)-\frac{2\Delta u}{\epsilon }(\ln |R|+t)]\le e^{-t}$. The returned element is inferior to optimal by more than an additive $O(\frac{\Delta u}{\epsilon }\ln |R|)$ with only exponentially small probability.

Example 3.6 - Best of two (pp. 40-41)

Setup. Which of two conditions is more common? True counts are $0$ for condition A and $c>0$ for B. Utility is the count, $\Delta u=1$. Exponential mechanism. Corollary 3.12 gives $\mathrm{Pr}[\text{outcome A}]\le 2e^{-c\epsilon /(2\Delta u)}=2e^{-c\epsilon /2}$. Report Noisy Max is harder to analyse (it needs the probability-$1/4$ case where A’s noise is positive and B’s is negative). One-sided variant. Add one-sided exponential noise with parameter $\epsilon /\Delta u$ (monotonic utility) or $\epsilon /2\Delta u$ (non-monotone) and report the argmax; then A is exponentially less likely than B in $c\epsilon /\Delta u=c\epsilon$.

Theorem 3.13 (p. 41)

Report One-Sided Noisy Arg-Max, run with parameter $\epsilon /2\Delta u$, is $\epsilon$-differentially private. (Proof “almost identical” to Report Noisy Max, losing a factor of 2 when the utility is not monotonic. A utility is monotonic if adding an element cannot decrease it, as with counting queries or revenue from a fixed price.)

Remark 3.1 - Gumbel max trick (p. 41)

Report noisy max with Laplace or exponential noise has guarantees similar to the exponential mechanism but yields distinct distributions. Instantiating it with Gumbel noise samples exactly from the exponential-mechanism distribution (folklore in machine learning).

Examples

Pumpkin pricing by the exponential mechanism (own simulation). Price grid $\{0.00,0.01,\dots ,5.00\}$ (data independent), utility = revenue, $\Delta u=5$ (the maximum price: adding one bidder can add at most the price). The true optimum is revenue $4.00 at price $1.00.

$\epsilon$	mean revenue of sampled price	$P(\text{price}>$$3.01$)$ (revenue zero)
0.5	1.27	0.37
2	1.49	0.30
10	2.51	0.06

With only four bidders and $\Delta u=5$ the privacy-utility trade-off is harsh, since one bidder can swing revenue by up to the whole price range; accuracy improves with more bidders. Best-of-two numerics. With $c=20$, $\epsilon =0.5$ the exponential-mechanism bound is $2e^{-5}\approx 0.0135$; a Monte Carlo of Report Noisy Max with Laplace noise gives an error probability near $10^{-4}$ (much smaller than the loose bound); one-sided exponential noise gives $\frac{1}{2}{e}^{-c\epsilon }=2.3\times 10^{-5}$, matching simulation ($2.5\times 10^{-5}$).

import numpy as np
rng = np.random.default_rng(0)
 
def exponential_mechanism(utilities, eps, sensitivity, rng=rng):
    """Sample index i with prob proportional to exp(eps*u_i/(2*sensitivity))."""
    logits = eps * np.asarray(utilities, float) / (2 * sensitivity)
    p = np.exp(logits - logits.max()); p /= p.sum()
    return rng.choice(len(p), p=p)
 
def exponential_mechanism_gumbel(utilities, eps, sensitivity, rng=rng):
    """Same distribution via report-noisy-max with Gumbel noise (Remark 3.1)."""
    scores = eps * np.asarray(utilities, float) / (2 * sensitivity) + rng.gumbel(size=len(utilities))
    return int(np.argmax(scores))
 
def report_noisy_max(counts, eps, rng=rng):
    return int(np.argmax(np.asarray(counts, float) + rng.laplace(0, 1/eps, len(counts))))
 
u = np.array([0, 3, 10, 10.5, 2])
a = np.bincount([exponential_mechanism(u, 1.0, 1.0) for _ in range(50_000)], minlength=5) / 50_000
b = np.bincount([exponential_mechanism_gumbel(u, 1.0, 1.0) for _ in range(50_000)], minlength=5) / 50_000
print(a.round(3), b.round(3))        # the two empirical distributions agree

Connections

• Marketing measurement. Choosing the top-performing creative, geo or channel from many candidates without publishing every score is differentially private selection; the winner can be released at cost $\epsilon$ regardless of the number of candidates, while releasing all scores would cost sensitivity-$m$ noise. Compare the winner’s-curse problem: a naive “best of $m$” estimate is biased upward (Multiple Testing Corrections); privatising the selection adds noise but the selection bias remains if the winning noisy value is reported.
• The pumpkin example is the pricing analogue of budget optimisation: noise on the decision (via utility) is safer than noise on an optimum that is brittle.

See Also

• Dwork Roth 2014 - Laplace Mechanism
• Dwork Roth 2014 - Sparse Vector Technique (selection among a stream of queries)
• Dwork 2006 - Sensitivity in General Metric Spaces (precursor of the exponential mechanism)
• Wasserman Zhou 2010 - Exponential Mechanism and Small Ball Probabilities (statistical accuracy of the exponential mechanism for density estimation)