Let d∈N+d \in \mathbb{N}^+ be a positive integer, and u⃗∈Nd\vec{u} \in \mathbb{N}^d be a vector.

Definition. Two vectors u⃗,v⃗∈Nd\vec{u}, \vec{v} \in \mathbb{N}^d are neighboring, denoted as u⃗∼v⃗\vec{u} \sim \vec{v}, if ∥u⃗−v⃗∥∞=1\Vert \vec{u} - \vec{v} \Vert_\infty = 1.

We are interested in the following research problem.

Problem. Design an ϵ\epsilon-differentially private algorithm to report

arg⁡max⁡i∈[d] ui. \underset{i \in [d]}{\arg\max} \, u_i.

Laplacian Mechanism

Since ∥u⃗−v⃗∥∞=1\Vert \vec{u} - \vec{v} \Vert_\infty = 1, it is possible that ∥u⃗−v⃗∥1=d\Vert \vec{u} - \vec{v} \Vert_1 = d. A naive approach would be adding independent Laplacian noise Xi∼Lap(ϵ/d)X_i \sim \mathcal{Lap}( \epsilon / d) to each coordinate of u⃗\vec{u}, and then return

M(u⃗)≐arg⁡max⁡i∈[d](ui+Xi). \mathcal{M}(\vec{u}) \doteq \underset{ i \in [d] }{\arg \max} \big( u_i + X_i \big).

Theorem (Privacy Guarantee). The algorithm is ϵ\epsilon-differentially private.

Proof.

This follows directly from Laplacian mechanism.

□\square

Theorem (Utility Guarantee). With probability at least 1−β1 - \beta, it holds that

uM(u⃗)≥(max⁡i∈[d]ui)−dϵln⁡dβ. u_{ \mathcal{M}(\vec{u}) } \ge \left( \max_{i \in [d] } u_i \right) - \frac{d}{\epsilon} \ln \frac{d}{\beta}.

Proof. For each i∈[d]i \in [d],

Pr⁡[∣Xi∣≥dϵln⁡dβ]≤βd. \Pr \left[ |X_i| \ge \frac{d}{\epsilon} \ln \frac{d}{\beta} \right] \le \frac{\beta}{d}.

Via union bound,

Pr⁡[∃i∈[d]:∣Xi∣≥dϵln⁡dβ]≤β. \Pr \left[ \exists i \in [d] : |X_i| \ge \frac{d}{\epsilon} \ln \frac{d}{\beta} \right] \le \beta.

□\square

Report Noisy Max

Laplacian Noise

It is possible to add Laplacian noise Xi∼Lap(2/ϵ)X_i \sim \mathcal{Lap}(2 / \epsilon) to each coordinate of u⃗\vec{u}, and then return

M(u⃗)≐arg⁡max⁡i∈[d](ui+Xi). \mathcal{M}(\vec{u}) \doteq \underset{ i \in [d] }{\arg \max} \big( u_i + X_i \big).

Theorem (Privacy Guarantee). The algorithm is ϵ\epsilon-differentially private.

Proof. We prove that for each k∈[d]k \in [d], and each u⃗,v⃗∈Nd\vec{u}, \vec{v} \in \mathbb{N}^d s.t., v⃗∼u⃗\vec{v} \sim \vec{u}, it holds that

e−ϵ⋅Pr⁡[M(v⃗)=k]≤Pr⁡[M(u⃗)=i]≤eϵ⋅Pr⁡[M(v⃗)=k]. e^{-\epsilon} \cdot \Pr[ \mathcal{M}(\vec{v}) = k] \le \Pr[ \mathcal{M}(\vec{u}) = i ] \le e^\epsilon \cdot \Pr[ \mathcal{M}(\vec{v}) = k].

By symmetry, we prove the claim for just k=nk = n.

For each u⃗∈Nd\vec{u} \in \mathbb{N}^d and each sequence s⃗=(s1,…,sn−1)∈Rn−1\vec{s} = (s_1, \ldots, s_{n - 1} ) \in \mathbb{R}^{n - 1}, define

z(u⃗,s⃗)=max⁡j∈[n−1](uj+sj). z (\vec{u}, \vec s) = \max_{j \in [n - 1] } \big( u_j + s_j \big).

Let Xj∼Lap(ϵ/2),j∈[n]X_j \sim \mathcal{Lap}(\epsilon / 2), j \in [n], and denote X⃗n−1≐(X1,…,Xn−1)\vec X_{n - 1} \doteq (X_1, \ldots, X_{n - 1}). The event M(u⃗)=n\mathcal{M}(\vec{u}) = n happens if and only if

z(u⃗,X⃗n−1)<un+Xn. z( \vec{u} , \vec X_{n - 1} ) < u_n + X_n.

Fix a sequence s⃗=(s1,…,sn−1)∈Rn−1\vec s = (s_1, \ldots, s_{n - 1} ) \in \mathbb{R}^{n - 1}:

Pr⁡[M(u⃗)=n∥X⃗n−1=s⃗]=Pr⁡[Xn>z(u⃗,s⃗)−un]={12exp⁡(−ϵ2⋅∣z(u⃗,s⃗)−un∣), if z(u⃗,s⃗)−un>0,1−12exp⁡(−ϵ2⋅∣z(u⃗,s⃗)−un∣), if z(u⃗,s⃗)−un≤0. \begin{aligned} \Pr\big[ \mathcal{M}(\vec{u}) = n \Vert \vec X_{n - 1} = \vec s \big] &= \Pr \big[ X_n > z( \vec{u} , \vec{s} ) - u_n \big] \\ &= \begin{cases} \begin{aligned} \frac{1}{2} \exp \left( -\frac{\epsilon}{2} \cdot | z( \vec{u} , \vec{s} ) - u_n| \right), \end{aligned} &\text{ if } z( \vec{u} , \vec{s} ) - u_n > 0, \\ \begin{aligned} 1 - \frac{1}{2} \exp \left( -\frac{\epsilon}{2} \cdot | z( \vec{u} , \vec{s} ) - u_n| \right), \end{aligned} &\text{ if } z( \vec{u} , \vec{s} ) - u_n \le 0. \end{cases} \end{aligned}

Similarly,

Pr⁡[M(v⃗)=n∥X⃗n−1=s⃗]=Pr⁡[Xn>z(v⃗,s⃗)−vn]={12exp⁡(−ϵ2⋅∣z(v⃗,s⃗)−vn∣), if z(v⃗,s⃗)−vn>0,1−12exp⁡(−ϵ2⋅∣z(v⃗,s⃗)−vn∣), if z(v⃗,s⃗)−vn≤0. \begin{aligned} \Pr\big[ \mathcal{M}(\vec{v}) = n \Vert \vec X_{n - 1} = \vec s \big] &= \Pr \big[ X_n > z( \vec{v} , \vec{s} ) - v_n \big] \\ &= \begin{cases} \begin{aligned} \frac{1}{2} \exp \left( -\frac{\epsilon}{2} \cdot | z( \vec{v} , \vec{s} ) - v_n | \right), \end{aligned} &\text{ if } z( \vec{v} , \vec{s} ) - v_n > 0, \\ \begin{aligned} 1 - \frac{1}{2} \exp \left( -\frac{\epsilon}{2} \cdot | z( \vec{v} , \vec{s} ) - v_n| \right), \end{aligned} &\text{ if } z( \vec{v} , \vec{s} ) - v_n \le 0. \end{cases} \end{aligned}

Let Δ≐z(u⃗,s⃗)−un−(z(v⃗,s⃗)−vn)\Delta \doteq z( \vec{u} , \vec{s} ) - u_n - (z( \vec{v} , \vec{s} ) - v_n). The assumption ∥u⃗−v⃗∥∞=1\Vert \vec{u} - \vec{v} \Vert_\infty = 1 implies that ∣Δ∣≤2|\Delta| \le 2. WLOG, assume that z(u⃗,s⃗)−un≤z(v⃗,s⃗)−vnz( \vec{u} , \vec{s} ) - u_n \le z( \vec{v} , \vec{s} ) - v_n. Then

Pr⁡[Xn>z(v⃗,s⃗)−vn]=Pr⁡[Xn+Δ>z(u⃗,s⃗)−un]. \Pr \big[ X_n > z( \vec{v} , \vec{s} ) - v_n \big] = \Pr \big[ X_n + \Delta > z( \vec{u} , \vec{s} ) - u_n \big].

Define Yn≐Xn+ΔY_n \doteq X_n + \Delta, which is also a Laplacian random variable with distribution Lap(Δ,2/ϵ)\mathcal{L}ap (\Delta, 2 / \epsilon). It follows that YnY_n is (ϵ,0)(\epsilon, 0)-close to XnX_n, and

Pr⁡[M(u⃗)=n∥X⃗n−1=s⃗]Pr⁡[M(v⃗)=n∥X⃗n−1=s⃗]=Pr⁡[Xn>z(u⃗,s⃗)−un]Pr⁡[Yn>z(u⃗,s⃗)−un]≤eϵ. \begin{aligned} \frac{ \Pr\big[ \mathcal{M}(\vec{u}) = n \Vert \vec X_{n - 1} = \vec s \big] }{ \Pr \big[ \mathcal{M}(\vec{v}) = n \Vert \vec X_{n - 1} = \vec s \big] } = \frac{ \Pr \big[ X_n > z( \vec{u} , \vec{s} ) - u_n \big] }{ \Pr \big[ Y_n > z( \vec{u} , \vec{s} ) - u_n \big] } \le e^\epsilon. \end{aligned}

Remark 1. We can also verifies this via the close form expressions.

If 0≤z(u⃗,s⃗)−un0 \le z( \vec{u} , \vec{s} ) - u_n, clearly we have

Pr⁡[M(u⃗)=n∥X⃗n−1=s⃗]Pr⁡[M(v⃗)=n∥X⃗n−1=s⃗]≤exp⁡(ϵ). \begin{aligned} \frac{\Pr\big[ \mathcal{M}(\vec{u}) = n \Vert \vec X_{n - 1} = \vec s \big] }{ \Pr \big[ \mathcal{M}(\vec{v}) = n \Vert \vec X_{n - 1} = \vec s \big] } \le \exp(\epsilon). \end{aligned}

Consider z(v⃗,s⃗)−vn≤0z( \vec{v} , \vec{s} ) - v_n \le 0. Let a≐∣z(u⃗,s⃗)−un∣a \doteq |z( \vec{u} , \vec{s} ) - u_n|, ∣b≐z(v⃗,s⃗)−vn∣|b \doteq z( \vec{v} , \vec{s} ) - v_n|, and c=1/2⋅exp⁡(−ϵ/2⋅b)∈[0,1/2]c = 1 / 2 \cdot \exp \left( - {\epsilon} / {2} \cdot b \right) \in [0, 1 / 2]. Then a,b≥0a, b \ge 0, a−b≤2a - b \le 2, and

Pr⁡[M(u⃗)=n∥X⃗n−1=s⃗]Pr⁡[M(v⃗)=n∥X⃗n−1=s⃗]=1−12exp⁡(−ϵ2⋅a)1−12exp⁡(−ϵ2⋅b)=1−c⋅exp⁡(−ϵ2⋅(a−b))1−c≤1−c⋅exp⁡(−ϵ)1−c=1eϵeϵ−1+1−c1−c=1eϵ(eϵ−11−c+1)≤1eϵ(eϵ−11−1/2+1)=1eϵ(2eϵ−1)≤exp⁡(ϵ). \begin{aligned} \frac{\Pr\big[ \mathcal{M}(\vec{u}) = n \Vert \vec X_{n - 1} = \vec s \big] }{ \Pr \big[ \mathcal{M}(\vec{v}) = n \Vert \vec X_{n - 1} = \vec s \big] } &= \frac{ 1 - \frac{1}{2} \exp \left( -\frac{\epsilon}{2} \cdot a \right) }{ 1 - \frac{1}{2} \exp \left( -\frac{\epsilon}{2} \cdot b \right) } \\ &= \frac{ 1 - c \cdot \exp \left( -\frac{\epsilon}{2} \cdot (a - b) \right) }{ 1 - c } \\ &\le \frac{ 1 - c \cdot \exp \left( -\epsilon \right) }{ 1 - c } \\ &= \frac{1}{e^\epsilon} \frac{ e^\epsilon - 1 + 1 - c }{ 1 - c } \\ &= \frac{1}{e^\epsilon} \left( \frac{ e^\epsilon - 1 }{ 1 - c } + 1 \right) \\ &\le \frac{1}{e^\epsilon} \left( \frac{ e^\epsilon - 1 }{ 1 - 1 / 2 } + 1 \right) \\ &= \frac{1}{e^\epsilon} \left( 2 e^\epsilon - 1 \right) \\ &\le \exp(\epsilon). \end{aligned}

Finally, consider z(u⃗,s⃗)−un<0,z(v⃗,s⃗)−vn>0z( \vec{u} , \vec{s} ) - u_n < 0, z( \vec{v} , \vec{s} ) - v_n > 0. Let a≐∣z(u⃗,s⃗)−un∣a \doteq |z( \vec{u} , \vec{s} ) - u_n|, ∣b≐z(v⃗,s⃗)−vn∣|b \doteq z( \vec{v} , \vec{s} ) - v_n|, and c=1/2⋅exp⁡(−ϵ/2⋅b)∈[0,1/2]c = 1 / 2 \cdot \exp \left( - {\epsilon} / {2} \cdot b \right) \in [0, 1 / 2]. Then a,b≥0a, b \ge 0, a+b≤2a + b \le 2, and

Pr⁡[M(u⃗)=n∥X⃗n−1=s⃗]Pr⁡[M(v⃗)=n∥X⃗n−1=s⃗]=1−12exp⁡(−ϵ2⋅a)12exp⁡(−ϵ2⋅b)=1−c⋅exp⁡(−ϵ2⋅(a−b))c≤1−c⋅exp⁡(−ϵ)c=1c−1eϵ≤2−exp⁡(−ϵ)≤exp⁡(ϵ). \begin{aligned} \frac{\Pr\big[ \mathcal{M}(\vec{u}) = n \Vert \vec X_{n - 1} = \vec s \big] }{ \Pr \big[ \mathcal{M}(\vec{v}) = n \Vert \vec X_{n - 1} = \vec s \big] } &= \frac{ 1 - \frac{1}{2} \exp \left( -\frac{\epsilon}{2} \cdot a \right) }{ \frac{1}{2} \exp \left( -\frac{\epsilon}{2} \cdot b \right) } \\ &= \frac{ 1 - c \cdot \exp \left( -\frac{\epsilon}{2} \cdot (a - b) \right) }{ c } \\ &\le \frac{ 1 - c \cdot \exp \left( -\epsilon \right) }{ c } \\ &= \frac{1}{c} - \frac{ 1 }{ e^\epsilon } \\ &\le 2 - \exp(-\epsilon) \\ &\le \exp(\epsilon). \end{aligned}

Integrating over X⃗n−1=s⃗\vec X_{n - 1} = \vec s for all possible s⃗\vec s finishes the proof.

□\square

Theorem (Utility Guarantee). With probability at least 1−β1 - \beta, it holds that

uM(u⃗)≥(max⁡i∈[d]ui)−1ϵln⁡dβ. u_{ \mathcal{M}(\vec{u}) } \ge \left( \max_{i \in [d] } u_i \right) - \frac{1}{\epsilon} \ln \frac{d}{\beta}.

Proof. For each i∈[d]i \in [d],

Pr⁡[∣Xi∣≥1ϵln⁡dβ]≤βd. \Pr \left[ |X_i| \ge \frac{1}{\epsilon} \ln \frac{d}{\beta} \right] \le \frac{\beta}{d}.

Via union bound,

Pr⁡[∃i∈[d]:∣Xi∣≥1ϵln⁡dβ]≤β. \Pr \left[ \exists i \in [d] : |X_i| \ge \frac{1}{\epsilon} \ln \frac{d}{\beta} \right] \le \beta.

□\square

Exponential Noise

It is possible to add Exponential noise Xi∼Exp(2/ϵ)X_i \sim \mathcal{Exp}(2 / \epsilon) to each coordinate of u⃗\vec{u}, and then return

M(u⃗)≐arg⁡max⁡i∈[d](ui+Xi). \mathcal{M}(\vec{u}) \doteq \underset{ i \in [d] }{\arg \max} \big( u_i + X_i \big).

Following the same vein, we have

Pr⁡[M(u⃗)=n∥X⃗n−1=s⃗]=Pr⁡[Xn>z(u⃗,s⃗)−un]={exp⁡(−ϵ2⋅∣z(u⃗,s⃗)−un∣), if z(u⃗,s⃗)−un>0,1, if z(u⃗,s⃗)−un≤0. \begin{aligned} \Pr\big[ \mathcal{M}(\vec{u}) = n \Vert \vec X_{n - 1} = \vec s \big] &= \Pr \big[ X_n > z( \vec{u} , \vec{s} ) - u_n \big] \\ &= \begin{cases} \begin{aligned} \exp \left( -\frac{\epsilon}{2} \cdot | z( \vec{u} , \vec{s} ) - u_n| \right), \end{aligned} &\text{ if } z( \vec{u} , \vec{s} ) - u_n > 0, \\ \begin{aligned} 1 , \end{aligned} &\text{ if } z( \vec{u} , \vec{s} ) - u_n \le 0. \end{cases} \end{aligned}

And

Pr⁡[M(v⃗)=n∥X⃗n−1=s⃗]=Pr⁡[Xn>z(v⃗,s⃗)−vn]={exp⁡(−ϵ2⋅∣z(v⃗,s⃗)−vn∣), if z(v⃗,s⃗)−vn>0,1, if z(v⃗,s⃗)−vn≤0. \begin{aligned} \Pr\big[ \mathcal{M}(\vec{v}) = n \Vert \vec X_{n - 1} = \vec s \big] &= \Pr \big[ X_n > z( \vec{v} , \vec{s} ) - v_n \big] \\ &= \begin{cases} \begin{aligned} \exp \left( -\frac{\epsilon}{2} \cdot | z( \vec{v} , \vec{s} ) - v_n | \right), \end{aligned} &\text{ if } z( \vec{v} , \vec{s} ) - v_n > 0, \\ \begin{aligned} 1 , \end{aligned} &\text{ if } z( \vec{v} , \vec{s} ) - v_n \le 0. \end{cases} \end{aligned}

It is straightforward to check that

Pr⁡[M(u⃗)=n∥X⃗n−1=s⃗]Pr⁡[M(v⃗)=n∥X⃗n−1=s⃗]≤exp⁡(ϵ). \begin{aligned} \frac{\Pr\big[ \mathcal{M}(\vec{u}) = n \Vert \vec X_{n - 1} = \vec s \big] }{ \Pr \big[ \mathcal{M}(\vec{v}) = n \Vert \vec X_{n - 1} = \vec s \big] } \le \exp(\epsilon). \end{aligned}

Exponential Mechanism

The exponential mechanism is defined by its output distribution:

Pr⁡[M(u⃗)=i]∝exp⁡(ϵ⋅ui/2),∀i∈[d]. \Pr[\mathcal{M}(\vec{u}) = i] \propto \exp \left( \epsilon \cdot u_i / 2 \right), \quad \forall i \in [d].

Normalizing these probabilities give

Pr⁡[M(u⃗)=i]=exp⁡(ϵ⋅ui/2)∑j∈[d]exp⁡(ϵ⋅uj/2),∀i∈[d]. \Pr[\mathcal{M}(\vec{u}) = i] = \frac{ \exp \left( \epsilon \cdot u_i / 2 \right) }{ \sum_{j \in [d] } \exp \left( \epsilon \cdot u_j / 2 \right) }, \quad \forall i \in [d].

Theorem (Privacy Guarantee). The algorithm is ϵ\epsilon-differentially private.

Proof. Fix a u⃗∈Nd\vec{u} \in \mathbb{N}^d. We prove that for each i∈[d]i \in [d], and each v⃗∼u⃗\vec{v} \sim \vec{u}, it holds that

e−ϵ⋅Pr⁡[M(v⃗)=i]≤Pr⁡[M(u⃗)=i]≤eϵ⋅Pr⁡[M(v⃗)=i]. e^{-\epsilon} \cdot \Pr[ \mathcal{M}(\vec{v}) = i] \le \Pr[ \mathcal{M}(\vec{u}) = i ] \le e^\epsilon \cdot \Pr[ \mathcal{M}(\vec{v}) = i].

By symmetry, we prove the claim for just i=ni = n.

Pr⁡[M(u⃗)=n]Pr⁡[M(v⃗)=n]=exp⁡(ϵ⋅un/2)exp⁡(ϵ⋅vn/2)⋅∑j∈[d]exp⁡(ϵ⋅vj/2)∑j∈[d]exp⁡(ϵ⋅uj/2)≤exp⁡(ϵ/2)⋅exp⁡(ϵ/2)=exp⁡(ϵ). \begin{aligned} \frac{\Pr[ \mathcal{M}(\vec{u}) = n] }{\Pr[ \mathcal{M}(\vec{v}) = n] } &= \frac{ \exp \left( \epsilon \cdot u_n / 2 \right) }{ \exp \left( \epsilon \cdot v_n / 2 \right) } \cdot \frac{ \sum_{j \in [d] } \exp \left( \epsilon \cdot v_j / 2 \right) }{ \sum_{j \in [d] } \exp \left( \epsilon \cdot u_j / 2 \right) } \\ &\le \exp( \epsilon / 2 ) \cdot \exp( \epsilon / 2 ) \\ &= \exp( \epsilon ). \end{aligned}

The inequality follows since

ui−vi≤∥u⃗−v⃗∥∞≤1,  ⟹  exp⁡(ϵ(ui−vi)/2)≤exp⁡(ϵ/2), ∀i∈[d]. \begin{aligned} u_i - v_i \le \Vert \vec{u} - \vec{v} \Vert_\infty \le 1, \implies \exp( \epsilon (u_i - v_i) / 2) \le \exp( \epsilon / 2), \, \forall i \in [d]. \end{aligned}

□\square

Theorem (Utility Guarantee). With probability at least 1−β1 - \beta, it holds that

uM(u⃗)≥(max⁡i∈[d]ui)−2ϵ⋅ln⁡∣S∣∣SOPT∣⋅β. u_{ \mathcal{M}(\vec{u}) } \ge \left( \max_{i \in [d] } u_i \right) - \frac{2}{\epsilon} \cdot \ln \frac{|S|}{|S_{OPT}| \cdot \beta}.

Proof. For each t∈Rt \in \mathbb{R}, the un-normalized probability mass assigned to the set S≐{i∈[d]:ui≤t}S \doteq \{ i \in [d] : u_i \le t \} is at most ∣S∣⋅exp⁡(ϵ⋅t/2)|S| \cdot \exp \left( \epsilon \cdot t / 2\right).

On the other hand, the un-normalized probability mass assigned to the set SOPT⊆[d]S_{OPT} \subseteq [d] consisting of optimal solutions is ∣SOPT∣⋅exp⁡(ϵ⋅(max⁡i∈[d]ui)/2)|S_{OPT}| \cdot \exp \left( \epsilon \cdot \left( \max_{i \in [d] } u_i \right) / 2\right).

Pr⁡[uM(u⃗)≤t]≤∣S∣⋅exp⁡(ϵ⋅t/2)∣SOPT∣⋅exp⁡(ϵ⋅(max⁡i∈[d]ui)/2)≤∣S∣∣SOPT∣exp⁡(ϵ(t−max⁡i∈[d]ui)/2). \begin{aligned} \Pr \left[ u_{ \mathcal{M}(\vec{u}) } \le t \right] &\le \frac{ |S| \cdot \exp \left( \epsilon \cdot t / 2\right) } { |S_{OPT}| \cdot \exp \left( \epsilon \cdot \left( \max_{i \in [d] } u_i \right) / 2 \right) } \\ &\le \frac{|S|}{|S_{OPT}|} \exp \left( \epsilon \left( t - \max_{i \in [d] } u_i \right) / 2 \right). \end{aligned}

To bound the last term by β\beta, we can set

t=(max⁡i∈[d]ui)−2ϵ⋅ln⁡∣S∣∣SOPT∣⋅β. t = \left( \max_{i \in [d] } u_i \right) - \frac{2}{\epsilon} \cdot \ln \frac{|S|}{|S_{OPT}| \cdot \beta}.

□\square

Gumbel Noise

A random variable XX follows the Gumbel distribution Gumbel(μ,b)\mathcal{Gumbel}(\mu, b) if its density is given by

p(x)≐1b⋅exp⁡(−(x−μ)/b−e−(x−μ)/b)=1b⋅e−(x−μ)/b⋅exp⁡(−e−(x−μ)/b),∀x∈R. p(x) \doteq \frac{1}{b} \cdot \exp \left( - (x - \mu) / b - e^{- (x - \mu) / b} \right) = \frac{1}{b} \cdot e^{ - (x - \mu) / b } \cdot \exp \left(- e^{- (x - \mu) / b} \right), \forall x \in \mathbb{R}.

It follows that the cumulative distribution of XX is

Pr⁡[X≤t]=∫−∞t1b⋅e−(x−μ)/b⋅exp⁡(−e−(x−μ)/b) dx=−∫−∞texp⁡(−e−(x−μ)/b) de−(x−μ)/b=∫exp⁡(−(t−μ)/b)∞exp⁡(−y) dy=exp⁡(−e−(t−μ)/b). \begin{aligned} \Pr[ X \le t ] &= \int_{-\infty}^t \frac{1}{b} \cdot e^{ - (x - \mu) / b } \cdot \exp \left(- e^{- (x - \mu) / b} \right) \, d x \\ &= - \int_{-\infty}^t \exp \left(- e^{- (x - \mu) / b} \right) \, d e^{ - (x - \mu) / b } \\ &= \int^{\infty}_{\exp(- (t - \mu) / b)} \exp \left(- y \right) \, d y \\ &= \exp \left(- e^{ - (t - \mu) / b } \right). \end{aligned}

Theorem. If we add Gumbel noise Xi∼Gumbel(0,2/ϵ)X_i \sim \mathcal{Gumbel}(0, 2 / \epsilon) to each coordinate of u⃗\vec{u}, and then return

M(u⃗)≐arg⁡max⁡i∈[d](ui+Xi), \mathcal{M}(\vec{u}) \doteq \underset{ i \in [d] }{\arg \max} \big( u_i + X_i \big),

the output has the same distribution as the one of exponential mechanism.

Proof. Let b=2/ϵb = 2 / \epsilon, and Zi≐ui+XiZ_i \doteq u_i + X_i. Then Zi∼Gumbel(ui,b)Z_i \sim \mathcal{Gumbel}(u_i, b), and

Pr⁡[M(u⃗)=n]=∫−∞∞(p(zn)⋅∏i∈[n−1]Pr⁡[Zi≤zn]) dzn=∫−∞∞(1b⋅e−(zn−un)/b⋅exp⁡(−e−(zn−un)/b)⋅∏i∈[n−1]exp⁡(−e−(zn−ui)/b)) dzn=eun/b⋅∫−∞∞(1b⋅e−zn/b⋅exp⁡(−e−zn/b⋅∑i∈[n]eui/b)) dzn=−eun/b⋅∫∞0exp⁡(−y⋅∑i∈[n]eui/b) dy(y≐e−zn/b)=exp⁡(un/b)∑i∈[n]exp⁡(ui/b). \begin{aligned} \Pr[ \mathcal{M}(\vec{u}) = n] &= \int_{-\infty}^\infty \left( p(z_n) \cdot \prod_{i \in [n - 1]} \Pr[ Z_i \le z_n ] \right) \, d z_n \\ &= \int_{-\infty}^\infty \left( \frac{1}{b} \cdot e^{ - (z_n - u_n) / b } \cdot \exp \left(- e^{- (z_n - u_n) / b} \right) \cdot \prod_{i \in [n - 1]} \exp \left(- e^{- (z_n - u_i) / b } \right) \right) \, d z_n \\ &= e^{ u_n / b } \cdot \int_{-\infty}^\infty \left( \frac{1}{b} \cdot e^{ - z_n / b } \cdot \exp \left(- e^{- z_n / b} \cdot \sum_{i \in [n ]} e^{ u_i / b } \right) \right) \, d z_n \\ &= - e^{ u_n / b } \cdot \int_{\infty}^0 \exp \left( - y \cdot \sum_{i \in [n ]} e^{ u_i / b } \right) \, d y & (y \doteq e^{-z_n/b} ) \\ &= \frac{ \exp \left( u_n / b \right) }{ \sum_{i \in [n]} \exp \left( u_i / b \right) }. \end{aligned}

□\square

Reference

[1] C. Dwork and A. Roth, “The Algorithmic Foundations of Differential Privacy,”

[2] The Gumbel-Max Trick for Discrete Distributions

[3] D. Durfee and R. M. Rogers, “Practical Differentially Private Top-k Selection with Pay-what-you-get Composition,” in Advances in Neural Information Processing Systems, 2019, vol. 32. Accessed: Sep. 13, 2022.