Let (X,∥⋅∥)(\mathcal{X}, \|\cdot\|) be a metric space.

Definition. Two elements D,D′∈XD,D' \in \mathcal{X} are neighboring, denoted by D∼D′D \sim D', if

∥D−D′∥=1. \|D-D'\| = 1.

Definition. A function q:X→Rq : \mathcal{X} \to \mathbb{R} has sensitivity at most Δ\Delta if

sup⁡D∼D′∣q(D)−q(D′)∣≤Δ. \sup_{D \sim D'} |q(D)-q(D')| \le \Delta.

Problem

Let

qi:X→R,i∈N+, q_i : \mathcal{X} \to \mathbb{R}, \qquad i \in \mathbb{N}^+,

be a sequence of functions, each with sensitivity at most Δ\Delta. Let t∈Rt \in \mathbb{R} be a threshold.

Our goal is to design an ϵ\epsilon-differentially private algorithm that reports the first index i∈N+i \in \mathbb{N}^+ for which qi(D)q_i(D) is near or above tt.

Mechanism One

Definition. For b>0b>0, let Lap⁡(b)\operatorname{Lap}(b) denote the Laplace distribution with scale parameter bb, whose density is

pb(x)=12bexp⁡(−∣x∣b). p_b(x) = \frac{1}{2b}\exp\left(-\frac{|x|}{b}\right).

The algorithm is as follows.

Algorithm A\mathcal{A}.

  1. t^←t+Z\hat t \leftarrow t + Z where Z∼Lap(3Δ/ϵ)Z \sim \mathcal{Lap}(3 \Delta / \epsilon)
  2. for i∈N+i \in \mathbb{N}^+ do
  3. \qquad q^i(D)←qi(D)+Xi\hat q_i(D) \leftarrow q_i(D) + X_i, where Xi∼Lap(3Δ/ϵ)X_i \sim \mathcal{Lap}( 3 \Delta / \epsilon)
  4. \qquad if q^i(D)≥t^\hat q_i(D) \ge \hat t then
  5. \qquad\qquad output ⊥\bot
  6. \qquad\qquad halt
  7. \qquad else
  8. \qquad\qquad output ⊤\top

Note that it is necessary to add noise to tt, to obtain t^\hat{t}.

Otherwise, assume that A(D)=A(D′)=⊤…⊤⏟n occurrences⊥\mathcal{A} (D) = \mathcal{A} (D') = \underbrace{\top \ldots \top}_{ n \text{ occurrences} } \bot for some n∈Nn \in \mathbb{N} and neighboring datasets DD and D′D'.

Assume further that t=0t = 0, qi(D)=Δq_i(D) = \Delta and qi(D′)=0q_i(D') = 0 for all i∈Ni \in \mathbb{N}. Then

Pr⁡[A(D)=⊤…⊤⏟n occurrences⊥]=(12)n+1exp⁡(−ϵ⋅n3)(1−exp⁡(−ϵ3)).Pr⁡[A(D′)=⊤…⊤⏟n occurrences⊥]=(12)n+1. \begin{align*} \Pr[ \mathcal{A} (D) = \underbrace{\top \ldots \top}_{ n \text{ occurrences} } \bot ] &= \left( \frac{1}{2} \right)^{n + 1} \exp \left( - \frac{\epsilon \cdot n }{3} \right) \left( 1 - \exp \left( - \frac{\epsilon}{3} \right)\right). \\ \Pr[ \mathcal{A} (D') = \underbrace{\top \ldots \top}_{ n \text{ occurrences} } \bot ] &= \left( \frac{1}{2} \right)^{n + 1}. \end{align*}

Privacy Guarantee

Let D′D' be a neighboring dataset of DD.

Theorem. For each i∈N+i \in \mathbb{N}^+, let si≐⊤…⊤⏟i−1 occurrences⊥s_i \doteq \underbrace{\top \ldots \top}_{ i - 1 \text{ occurrences} } \bot. Then

e−ϵ≤Pr⁡[A(D)=si]Pr⁡[A(D′)=si]≤eϵ. e^{-\epsilon} \le \frac{\Pr[ \mathcal{A}(D) = s_i ]}{\Pr[ \mathcal{A}(D') = s_i ]} \le e^{\epsilon}.

Proof 1.

Fix an i∈N+i \in \mathbb{N}^+. For each dataset DD and each x⃗i−1=(x1,…,xi−1)∈Ri−1\vec x_{i - 1} = (x_1, \ldots, x_{i - 1} ) \in \mathbb{R}^{i - 1}, define

M(D,x⃗i−1)=max⁡j∈[i−1](qj(D)+xj). M(D, \vec x_{i - 1}) = \max_{j \in [i - 1]} \Big( q_j(D) + x_j \Big).

Denote X⃗i−1≐(X1,…,Xi−1)\vec X_{i - 1} \doteq (X_1, \ldots, X_{i - 1}), and the event A(D)=si\mathcal{A}(D) = s_i happens if and only if

M(D,X⃗i−1)<t^≤q^i(D). M(D, \vec X_{i - 1}) < \hat t \le \hat q_i(D).

Fix a sequence x⃗i−1=(x1,…,xi−1)∈Ri−1\vec x_{i - 1} = (x_1, \ldots, x_{i - 1} ) \in \mathbb{R}^{i - 1}. Let μ\mu be a shorthand of Lap(3Δ/ϵ)\mathcal{Lap}(3 \Delta / \epsilon), and FF be its cumulative function. Since the random variables Z,X⃗i−1,XiZ, \vec X_{i - 1}, X_i are independent, via Fubini's theorem,

Pr⁡[A(D)=si∥X⃗i−1=x⃗i−1]=Pr⁡[M(D,x⃗i−1)<t^≤q^i(D)]=Pr⁡[M(D,x⃗i−1)<t+Z≤qi(D)+Xi]=Ez∼μ[I[M(D,x⃗i−1)<t+z]⋅(1−F(t+z−qi(D)))]=Ez∼μ[I[M(D,x⃗i−1)<t+z]⋅F(−t−z+qi(D))]=∫M(D,x⃗i−1)−t∞p(z)⋅F(−t−z+qi(D)) dz=∫M(D′,x⃗i−1)−t∞p(z+κ)⋅F(−t−z−κ+qi(D)) dz, \begin{aligned} \Pr \big[ \mathcal{A}(D) = s_i \Vert \vec X_{i - 1} = \vec x_{i - 1} \big] &= \Pr \big[ M(D, \vec x_{i - 1}) < \hat t \le \hat q_i(D) \big] \\ &= \Pr \big[ M(D, \vec x_{i - 1}) < t + Z \le q_i(D) + X_i \big] \\ &= \mathbb{E}_{z \sim \mu} \left[ \mathbb{I} \Big[ M(D, \vec x_{i - 1}) < t + z \Big] \cdot \big( 1 - F ( t + z - q_i(D) ) \big) \right] \\ &= \mathbb{E}_{z \sim \mu} \left[ \mathbb{I} \Big[ M(D, \vec x_{i - 1}) < t + z \Big] \cdot F \big( - t - z + q_i(D) \big) \right] \\ &= \int_{M(D, \vec x_{i - 1}) - t}^\infty p(z) \cdot F \big( - t - z + q_i(D) \big) \, d z \\ &= \int_{M(D', \vec x_{i - 1}) - t}^\infty p\big( z + \kappa \big) \cdot F \big( - t - z - \kappa + q_i(D) \big) \, d z, \end{aligned}

where κ≐M(D,x⃗i−1)−M(D′,x⃗i−1)\kappa \doteq M(D, \vec x_{i - 1}) - M(D', \vec x_{i - 1}).

Similarly, the conditional probability density of Pr⁡[A(D′)=si]\Pr\big[ \mathcal{A}(D') = s_i \big] is given by

Pr⁡[A(D′)=si∥X⃗i−1=x⃗i−1]=∫M(D′,x⃗i−1)−t∞p(z)⋅F(−t−z+qi(D′)) dz. \begin{aligned} \Pr \big[ \mathcal{A}(D') = s_i \Vert \vec X_{i - 1} = \vec x_{i - 1} \big] &= \int_{M(D', \vec x_{i - 1}) - t}^\infty p(z) \cdot F \big( - t - z + q_i(D') \big) \, d z. \end{aligned}

Comparing p(z)p(z) and p(z+κ)p(z + \kappa), F(−t−z−κ+qi(D))F \big( - t - z - \kappa + q_i(D) \big) and F(−t−z+qi(D′))F \big( - t - z + q_i(D') \big) finishes the proof.

□\square

Proof 2.

Fix an i∈N+i \in \mathbb{N}^+. For each dataset DD and each x⃗i−1=(x1,…,xi−1)∈Ri−1\vec x_{i - 1} = (x_1, \ldots, x_{i - 1} ) \in \mathbb{R}^{i - 1}, define

M(D,x⃗i−1)=max⁡j∈[i−1](qj(D)+xj). M(D, \vec x_{i - 1}) = \max_{j \in [i - 1]} \Big( q_j(D) + x_j \Big).

Denote X⃗i−1≐(X1,…,Xi−1)\vec X_{i - 1} \doteq (X_1, \ldots, X_{i - 1}), and the event A(D)=si\mathcal{A}(D) = s_i happens if and only if

M(D,X⃗i−1)<t^≤q^i(D). M(D, \vec X_{i - 1}) < \hat t \le \hat q_i(D).

Fix a sequence x⃗i−1=(x1,…,xi−1)∈Ri−1\vec x_{i - 1} = (x_1, \ldots, x_{i - 1} ) \in \mathbb{R}^{i - 1}. Since the random variables Z,X⃗i−1,XiZ, \vec X_{i - 1}, X_i are independent,

Pr⁡[A(D)=si∥X⃗i−1=x⃗i−1]=Pr⁡[M(D,x⃗i−1)<t^≤q^i(D)]=Pr⁡[M(D,x⃗i−1)<t+Z≤qi(D)+Xi]=∫∫p(z)⋅p(xi)⋅I[M(D,x⃗i−1)<t+z≤qi(D)+xi] dxi dz, \begin{aligned} \Pr \big[ \mathcal{A}(D) = s_i \Vert \vec X_{i - 1} = \vec x_{i - 1} \big] &= \Pr \big[ M(D, \vec x_{i - 1}) < \hat t \le \hat q_i(D) \big] \\ &= \Pr \big[ M(D, \vec x_{i - 1}) < t + Z \le q_i(D) + X_i \big] \\ &= \int \int p(z) \cdot p(x_i) \cdot \mathbb{I} \Big[ M(D, \vec x_{i - 1}) < t + z \le q_i(D) + x_i \Big] \, d x_i \, dz, \end{aligned}

where p(z)p(z) and p(xi)p(x_i) are probability densities of ZZ and XiX_i, respectively. Similarly, the conditional probability density of Pr⁡[A(D′)=si]\Pr\big[ \mathcal{A}(D') = s_i \big] is given by

Pr⁡[A(D′)=si∥X⃗i−1=x⃗i−1]=Pr⁡[M(D′,x⃗i−1)<t^≤q^i(D′)]=Pr⁡[M(D′,x⃗i−1)<t+Z≤qi(D′)+Xi]=∫∫p(z′)⋅p(xi′)⋅I[M(D′,x⃗i−1)<t+z′≤qi(D′)+xi′] dxi′ dz′. \begin{aligned} \Pr \big[ \mathcal{A}(D') = s_i \Vert \vec X_{i - 1} = \vec x_{i - 1} \big] &= \Pr \big[ M(D', \vec x_{i - 1}) < \hat t \le \hat q_i(D') \big] \\ &= \Pr \big[ M(D', \vec x_{i - 1}) < t + Z \le q_i(D') + X_i \big] \\ &= \int \int p(z') \cdot p(x_i') \cdot \mathbb{I} \Big[ M(D', \vec x_{i - 1}) < t + z' \le q_i(D') + x_i' \Big] \, d x_i' \, dz'. \end{aligned}

Suppose that the following equations holds:

t+z′−M(D′,x⃗i−1)=t+z−M(D,x⃗i−1),qi(D′)+xi′−(t+z′)=qi(D)+xi−(t+z). \begin{aligned} t + z' - M(D', \vec x_{i - 1}) &= t + z - M(D, \vec x_{i - 1}), \\ q_i(D') + x_i' - (t + z') &= q_i(D) + x_i - (t + z). \end{aligned}

Then

I[M(D′,x⃗i−1)<t+z′≤qi(D′)+xi′]=I[M(D,x⃗i−1)<t+z≤qi(D)+xi]. \mathbb{I} \Big[ M(D', \vec x_{i - 1}) < t + z' \le q_i(D') + x_i' \Big] = \mathbb{I} \Big[ M(D, \vec x_{i - 1}) < t + z \le q_i(D) + x_i \Big].

But this implies that

∣z′−z∣=∣M(D′,x⃗i−1)−M(D,x⃗i−1)∣≤Δ∣xi′−xi∣=∣z′−qi(D′)−z+qi(D)∣=∣M(D′,x⃗i−1)−M(D,x⃗i−1)+qi(D)−qi(D′)∣≤2⋅Δ. \begin{aligned} |z' - z| &= |M(D', \vec x_{i - 1}) - M(D, \vec x_{i - 1})| \le \Delta \\ |x_i' - x_i| &= |z' - q_i(D') - z + q_i(D)| \\ &= |M(D', \vec x_{i - 1}) - M(D, \vec x_{i - 1}) + q_i(D) - q_i(D')| \\ &\le 2 \cdot \Delta. \end{aligned}

Further, observe that

∣dxi′dxi,dxi′dzdz′dxi,dz′dz∣=∣1,00,1∣=1, \begin{vmatrix} \begin{aligned} \frac{d x_i'}{d_{x_i}}, &\frac{d x_i'}{d_z} \\ \frac{d z'}{d_{x_i}}, &\frac{d z'}{d_z} \end{aligned} \end{vmatrix} = \begin{vmatrix} 1, &0 \\ 0, &1 \end{vmatrix} = 1,

Therefore, by integration by substitution,

Pr⁡[A(D)=si∥X⃗i−1=x⃗i−1]Pr⁡[A(D′)=si∥X⃗i−1=x⃗i−1]=∫∫p(z)⋅p(xi)⋅I[M(D,x⃗i−1)<t+z≤qi(D)+xi] dxi dz∫∫p(z′)⋅p(xi′)⋅I[M(D′,x⃗i−1)<t+z′≤qi(D′)+xi′] dxi′ dz′=∫∫p(z)⋅p(xi)⋅I[M(D,x⃗i−1)<t+z≤qi(D)+xi] dxi dz∫∫p(z′)⋅p(xi′)⋅I[M(D,x⃗i−1)<t+z≤qi(D)+xi] dxi dz≤exp⁡(Δ⋅ϵ3Δ)⋅exp⁡(2⋅Δ⋅ϵ3Δ)≤exp⁡(ϵ). \begin{aligned} \frac{\Pr \big[ \mathcal{A}(D) = s_i \Vert \vec X_{i - 1} = \vec x_{i - 1} \big]}{\Pr \big[ \mathcal{A}(D') = s_i \Vert \vec X_{i - 1} = \vec x_{i - 1} \big] } &= \frac{ \int \int p(z) \cdot p(x_i) \cdot \mathbb{I} \Big[ M(D, \vec x_{i - 1}) < t + z \le q_i(D) + x_i \Big] \, d x_i \, dz } { \int \int p(z') \cdot p(x_i') \cdot \mathbb{I} \Big[ M(D', \vec x_{i - 1}) < t + z' \le q_i(D') + x_i' \Big] \, d x_i' \, dz' } \\ &= \frac{ \int \int p(z) \cdot p(x_i) \cdot \mathbb{I} \Big[ M(D, \vec x_{i - 1}) < t + z \le q_i(D) + x_i \Big] \, d x_i \, dz } { \int \int p(z') \cdot p(x_i') \cdot \mathbb{I} \Big[ M(D, \vec x_{i - 1}) < t + z \le q_i(D) + x_i \Big] \, d x_i \, dz } \\ &\le \exp \Big( \Delta \cdot \frac{\epsilon}{3\Delta}\Big) \cdot \exp \Big( 2 \cdot \Delta \cdot \frac{\epsilon}{3\Delta} \Big) \\ &\le \exp(\epsilon). \end{aligned}

Integrating over X⃗i−1=x⃗i−1\vec X_{i - 1} = \vec x_{i - 1} for all possible x⃗i−1\vec x_{i - 1} proves that Pr⁡[A(D)=si]≤eϵ⋅Pr⁡[A(D′)=si]\Pr\big[ \mathcal{A}(D) = s_i \big] \le e^\epsilon \cdot \Pr\big[ \mathcal{A}(D') = s_i \big].

□\square

Mechanism Two

Definition. For each b∈R+b \in \mathbb{R}^+, let Exp(b)\mathcal{Exp}(b) be the exponential distribution with parameter bb.

The algorithm is described as follows.

Algorithm A\mathcal{A}.

  1. t^←t+Z\hat t \leftarrow t + Z where Z∼Exp(3Δ/ϵ)Z \sim \mathcal{Exp}(3 \Delta / \epsilon)
  2. for i∈N+i \in \mathbb{N}^+ do
  3. \qquad q^i(D)←qi(D)+Xi\hat q_i(D) \leftarrow q_i(D) + X_i, where Xi∼Exp(3Δ/ϵ)X_i \sim \mathcal{Exp}( 3 \Delta / \epsilon)
  4. \qquad if q^i(D)≥t^\hat q_i(D) \ge \hat t then
  5. \qquad\qquad output ⊥\bot
  6. \qquad\qquad halt
  7. \qquad else
  8. \qquad\qquad output ⊤\top

Privacy Guarantee

Let D′D' be a neighboring dataset of DD.

Theorem. For each i∈N+i \in \mathbb{N}^+, let si≐⊤…⊤⏟i−1 occurrences⊥s_i \doteq \underbrace{\top \ldots \top}_{ i - 1 \text{ occurrences} } \bot. Then

e−ϵ≤Pr⁡[A(D)=si]Pr⁡[A(D′)=si]≤eϵ. e^{-\epsilon} \le \frac{\Pr[ \mathcal{A}(D) = s_i ]}{\Pr[ \mathcal{A}(D') = s_i ]} \le e^{\epsilon}.

THe analysis is very similar to the one for report noisy max. Informally speaking, we are applying report noisy max twice, one for t^\hat t being max among (t^,q^(D1),…,q^(Di−1))(\hat t, \hat q(D_1), \ldots, \hat q(D_{i - 1})), one for q^(Di)\hat q(D_i) being max among (t^,q^(D1),…,q^(Di))(\hat t, \hat q(D_1), \ldots, \hat q(D_{i})).

Proof.

Fix an i∈N+i \in \mathbb{N}^+. For each dataset DD and each x⃗i−1=(x1,…,xi−1)∈Ri−1\vec x_{i - 1} = (x_1, \ldots, x_{i - 1} ) \in \mathbb{R}^{i - 1}, define

M(D,x⃗i−1)=max⁡1≤j≤i−1(qj(D)+xj). M(D, \vec x_{i - 1}) = \max_{1 \le j \le i - 1} \Big( q_j(D) + x_j \Big).

Denote X⃗i−1≐(X1,…,Xi−1)\vec X_{i - 1} \doteq (X_1, \ldots, X_{i - 1}), and The event A(D)=si\mathcal{A}(D) = s_i happens if and only if

M(D,X⃗i−1)<t^≤q^i(D). M(D, \vec X_{i - 1}) < \hat t \le \hat q_i(D).

Fix a sequence x⃗i−1=(x1,…,xi−1)∈Ri−1\vec x_{i - 1} = (x_1, \ldots, x_{i - 1} ) \in \mathbb{R}^{i - 1}. Since the random variables Z,X⃗i−1,XiZ, \vec X_{i - 1}, X_i are independent,

Pr⁡[A(D)=si∥X⃗i−1=x⃗i−1]=Pr⁡[M(D,x⃗i−1)<t^≤q^i(D)]=Pr⁡[M(D,x⃗i−1)<t+Z≤qi(D)+Xi]=∫M(D,x⃗i−1)−t∞(p(z)⋅∫t+z−qi(D)∞p(xi) dxi) dz=∫M(D,x⃗i−1)−t∞p(z)⋅exp⁡(−ϵ3Δ⋅max⁡{0,t+z−qi(D)}) dz \begin{aligned} \Pr \big[ \mathcal{A}(D) = s_i \Vert \vec X_{i - 1} = \vec x_{i - 1} \big] &= \Pr \big[ M(D, \vec x_{i - 1}) < \hat t \le \hat q_i(D) \big] \\ &= \Pr \big[ M(D, \vec x_{i - 1}) < t + Z \le q_i(D) + X_i \big] \\ &= \int_{M(D, \vec x_{i - 1}) - t}^\infty \left( p(z) \cdot \int_{t + z - q_i (D)}^\infty p(x_i) \, d x_i \right) \, dz \\ &= \int_{M(D, \vec x_{i - 1}) - t}^\infty p(z) \cdot \exp \left( -\frac{\epsilon}{3 \Delta} \cdot \max \big\{ 0, t + z - q_i (D) \big\} \right) \, dz \end{aligned}

where p(z)p(z) and p(xi)p(x_i) are probability densities of ZZ and XiX_i, respectively. For now, let

κ≐M(D,x⃗i−1)−M(D′,x⃗i−1)∈[−Δ,Δ]. \kappa \doteq M(D, \vec x_{i - 1}) - M(D', \vec x_{i - 1}) \in [- \Delta, \Delta] .

Following similar vein, the conditional probability density of Pr⁡[A(D′)=si]\Pr\big[ \mathcal{A}(D') = s_i \big] is given by

Pr⁡[A(D′)=si∥X⃗i−1=x⃗i−1]=Pr⁡[M(D′,x⃗i−1)<t^≤q^i(D′)]=Pr⁡[M(D′,x⃗i−1)<t+Z≤qi(D′)+Xi]=∫M(D′,x⃗i−1)−t∞(p(z)⋅∫t+z−qi(D′)∞p(xi) dxi) dz=∫M(D′,x⃗i−1)−t∞p(z)⋅exp⁡(−ϵ3Δ⋅max⁡{0,t+z−qi(D′)}) dz=y≐z+κ∫M(D,x⃗i−1)−t∞p(y−κ)⋅exp⁡(−ϵ3Δ⋅max⁡{0,t+y−κ−qi(D′)}) dy \begin{aligned} \Pr \big[ \mathcal{A}(D') = s_i \Vert \vec X_{i - 1} = \vec x_{i - 1} \big] &= \Pr \big[ M(D', \vec x_{i - 1}) < \hat t \le \hat q_i(D') \big] \\ &= \Pr \big[ M(D', \vec x_{i - 1}) < t + Z \le q_i(D') + X_i \big] \\ &= \int_{M(D', \vec x_{i - 1}) - t}^\infty \left( p(z) \cdot \int_{t + z - q_i (D')}^\infty p(x_i) \, d x_i \right) \, dz \\ &= \int_{M(D', \vec x_{i - 1}) - t}^\infty p(z) \cdot \exp \left( -\frac{\epsilon}{3 \Delta} \cdot \max \big\{ 0, t + z - q_i (D') \big\} \right) \, dz \\ &\stackrel{y \doteq z + \kappa}{=} \int_{M(D, \vec x_{i - 1}) - t}^\infty p(y - \kappa) \cdot \exp \left( -\frac{\epsilon}{3 \Delta} \cdot \max \big\{ 0, t + y - \kappa - q_i (D') \big\} \right) \, dy \end{aligned}

Comparing the integrands we have

Pr⁡[A(D)=si∥X⃗i−1=x⃗i−1]Pr⁡[A(D′)=si∥X⃗i−1=x⃗i−1]≤exp⁡(ϵ). \begin{aligned} \frac{\Pr \big[ \mathcal{A}(D) = s_i \Vert \vec X_{i - 1} = \vec x_{i - 1} \big]}{\Pr \big[ \mathcal{A}(D') = s_i \Vert \vec X_{i - 1} = \vec x_{i - 1} \big] } &\le \exp(\epsilon). \end{aligned}

Integrating over X⃗i−1=x⃗i−1\vec X_{i - 1} = \vec x_{i - 1} for all possible x⃗i−1\vec x_{i - 1} proves that Pr⁡[A(D)=si]≤eϵ⋅Pr⁡[A(D′)=si]\Pr\big[ \mathcal{A}(D) = s_i \big] \le e^\epsilon \cdot \Pr\big[ \mathcal{A}(D') = s_i \big].

□\square

Utility Guarantee

Suppose that the algorithm outputs ⊤\top at the ii-th query, we measure the empirical error by max⁡{0,qi(D)−t}\max \{0, q_i(D) - t \}, i.e., if qi(D)q_i(D) does not exceed tt, then we regards the empirical error as 00. Similarly, for an output ⊥\bot, the empirical error is measured by max⁡{0,t−qi(D)}\max \{0, t - q_i(D) \}.

Theorem. Fix a sequence of kk queries q1,…,qkq_1, \ldots, q_k to be performed by the algorithm. With probability at most β\beta, the maximum empirical error exceeds

6⋅Δϵln⁡k+1β. \frac{6 \cdot \Delta}{\epsilon}\ln \frac{k + 1}{\beta}.

Proof.

Pr⁡[∣Z∣≥2⋅Δϵln⁡k+1β]≤exp⁡(2⋅ln⁡k+1β)=βk+1. \Pr \left[ |Z| \ge \frac{2 \cdot \Delta}{\epsilon}\ln \frac{k + 1}{\beta} \right] \le \exp \left( 2 \cdot \ln \frac{k + 1}{\beta} \right) = \frac{\beta}{k + 1}.

Similarly, for each i∈[k]i \in [k],

Pr⁡[∣Xi∣≥2⋅Δϵln⁡k+1β]≤exp⁡(2⋅ln⁡k+1β)=βk+1. \Pr \left[ |X_i| \ge \frac{2 \cdot \Delta}{\epsilon}\ln \frac{k + 1}{\beta} \right] \le \exp \left( 2 \cdot \ln \frac{k + 1}{\beta} \right) = \frac{\beta}{k + 1}.

By union bound, with probability at most β\beta, it holds that

∣Z∣+max⁡i∈[k]∣Xi∣≥6⋅Δϵln⁡k+1β. |Z| + \max_{i \in [k]} |X_i| \ge \frac{6 \cdot \Delta}{\epsilon}\ln \frac{k + 1}{\beta}.

□\square

Reference

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