Let Xi∼Laplace(0,bi)X_i \sim Laplace(0, b_i), i∈[n]i \in [n] be independent random variables that follow Laplacian distributions, i.e., for each i∈[n]i \in [n], the probability density function of XiX_i is

p(Xi=x)=12biexp⁡(−∣x∣bi), ∀x∈R. p(X_i = x) = \frac{1}{ 2 b_i } \exp \left( - \frac{ |x| }{ b_i }\right),\, \forall x \in \mathbb{R}.

Moment Generating Function

Fact. For each i∈[n]i \in [n], the moment generating function of XiX_i is

E[exp⁡(tXi)]=11−bi2⋅t2, where ∣t∣<1/bi. \mathbb{E} [ \exp ( t X_i) ] = \frac{1}{1 - b_i^2 \cdot t^2 },\, \text{where } |t| < 1 / b_i.

Proof. Let ∣t∣<1/bi|t| < 1 / b_i. Via the definition of moment generating function, we get

E[exp⁡(tXi)]=∫exp⁡(tx)⋅12biexp⁡(−∣x∣bi)=12bi(∫−∞0exp⁡(tx+xbi)+∫0∞exp⁡(tx−xbi))=12bi(1t+1/biexp⁡(tx+xbi)∣−∞0+1t−1/biexp⁡(tx−xbi)∣0∞)=12bi(1t+1/bi−1t−1/bi)=12bi(−2/bit2−1/bi2)=11−bi2⋅t2. \begin{aligned} \mathbb{E}[ \exp (t X_i) ] &= \int \exp ( t x) \cdot \frac{1}{ 2 b_i } \exp \left( - \frac{ |x| }{ b_i } \right) \\ &= \frac{1}{ 2 b_i } \left( \int_{ -\infty }^0 \exp \left( tx + \frac{ x }{ b_i }\right) + \int_0^{ \infty } \exp \left( tx - \frac{ x }{ b_i }\right) \right) \\ &= \frac{1}{ 2 b_i } \left( \frac{1}{t + 1 / b_i }\exp \left( tx + \frac{ x }{ b_i } \right) \mid_{-\infty}^0 + \frac{1}{t - 1 / b_i } \exp \left( tx - \frac{ x }{ b_i } \right) \mid_0^\infty \right) \\ &= \frac{1}{ 2 b_i } \left( \frac{1}{t + 1 / b_i } - \frac{1}{t - 1 / b_i } \right) \\ &= \frac{1}{ 2 b_i } \left( \frac{ - 2 / b_i }{t^2 - 1 / b_i^2 } \right) \\ &= \frac{1}{ 1 - b_i^2 \cdot t^2 }. \end{aligned}

□\square

Concentration Inequalities

Define X=∑i∈[n]XiX = \sum_{i \in [n] } X_i. There are various ways to obtains concentration inequalities for XX.

One

Theorem. If 0≤λ≤(22⋅∑i∈[n]bi2)⋅min⁡i∈[n]1/bi0 \le \lambda \le \big( 2 \sqrt{2} \cdot \sum_{i \in [n] } b_i^2 \big) \cdot \min_{i \in [n] } 1 / b_i, then

Pr⁡[X≥λ]≤exp⁡(−λ28⋅∑i∈[n]bi2). \Pr[ X \ge \lambda ] \le \exp \left( - \frac{\lambda^2}{8 \cdot \sum_{i \in [n] } b_i^2 } \right).

If (22⋅∑i∈[n]bi2)⋅min⁡i∈[n]1/bi≤λ\big( 2 \sqrt{2} \cdot \sum_{i \in [n] } b_i^2 \big) \cdot \min_{i \in [n] } 1 / b_i \le \lambda, then

Pr⁡[X≥λ]≤exp⁡(−λ2⋅(min⁡i∈[n]1bi⋅2)). \Pr[ X \ge \lambda ] \le \exp \left( - \frac{\lambda}{2} \cdot \left( \min_{i \in [n] } \frac{ 1 }{ b_i \cdot \sqrt{2} } \right) \right).

The proof applies similar techniques to the ones in the proofs of Chernoff Bounds.

The inequalities state that when λ\lambda is small, we have Gaussian like bounds. When λ\lambda is large, we have a exponential tail bound, which is much fatter than the Gaussian one.

The second one seems counter intuitive at the first glance. Consider the special case where the bib_i are identical, and bi=bb_i = b for all i∈[n]i \in [n]. Then the RHS of the inequality becomes exp⁡(−λ/(22⋅b))\exp( - \lambda / (2 \sqrt{2} \cdot b) ). It seems that the tail bound does not depend on nn! However it does. To apply the second tail bound, we need that

λ≥(22⋅∑i∈[n]b2)⋅min⁡i∈[n]1/b=22⋅n⋅b. \lambda \ge \big( 2 \sqrt{2} \cdot \sum_{i \in [n] } b^2 \big) \cdot \min_{i \in [n] } 1 / b = 2 \sqrt{2} \cdot n \cdot b.

Before proving the theorem, we need the following lemma.

Lemma. For each i∈[n]i \in [n], when 0≤t≤1/(bi⋅2)0 \le t \le 1 / (b_i \cdot \sqrt{2}), it holds that

11−bi2⋅t2≤exp⁡(2⋅bi2⋅t2). \frac{1}{ 1 - b_i^2 \cdot t^2 } \le \exp( 2 \cdot b_i^2 \cdot t^2 ).

Proof. For x∈[0,1/2]x \in [0, 1 / 2],

1+x≤ex≤11−x≤1+2x≤exp⁡(2x). 1 + x \le e^x \le \frac{1}{1 - x} \le 1 + 2 x \le \exp(2 x).

The tangent line of the function y=1/(1−x)y = 1 / (1 - x) at x=0x = 0 is given by y=1+xy = 1 + x. As y=1/(1−x)y = 1 / (1 - x) is a convex function, it is above the line y=1+xy = 1 + x for x≤1x \le 1. If we increase the slope of y=1+xy = 1 + x a little bit, then the new line should lie above y=1/(1−x)y = 1 / (1 - x), if xx is not "too far" away from 00. As x→1x \rightarrow 1, the function y=1/(1−x)y = 1 / (1 - x) approaches infty, we can't hope to upper bound it by a linear nor even exponential function.

□\square

Proof of the Theorem.

Let 0≤t≤min⁡i∈[n]1/(bi⋅2)0 \le t \le \min_{i \in [n] } 1 / (b_i \cdot \sqrt{2} ),

Pr⁡[X≥λ]=Pr⁡[exp⁡(tX)≥exp⁡(tλ)]≤exp⁡(−tλ)⋅E[exp⁡(tX)]=exp⁡(−tλ)⋅∏i∈[n]E[exp⁡(tXi)]≤exp⁡(−tλ+∑i∈[n]2⋅bi2⋅t2) \begin{aligned} \Pr[ X \ge \lambda ] &= \Pr[ \exp( t X) \ge \exp( t \lambda ) ] \\ &\le \exp( - t \lambda) \cdot \mathbb{E}[ \exp(t X) ] \\ &= \exp( - t \lambda) \cdot \prod_{i \in [n] } \mathbb{E}[ \exp(t X_i) ] \\ &\le \exp \left( - t \lambda + \sum_{i \in [n] } 2 \cdot b_i^2 \cdot t^2 \right) \end{aligned}

The function f(t)≐(∑i∈[n]2⋅bi2)⋅t2−λtf(t) \doteq \left( \sum_{i \in [n] } 2 \cdot b_i^2 \right) \cdot t^2 - \lambda t decreases when

t≤λ4⋅∑i∈[n]bi2, t \le \frac{\lambda}{4 \cdot \sum_{i \in [n] } b_i^2 },

and increases afterwards. If min⁡i∈[n]1/(bi⋅2)≥λ/(4⋅∑i∈[n]bi2)\min_{i \in [n] } 1 / (b_i \cdot \sqrt{2} ) \ge \lambda / \big( 4 \cdot \sum_{i \in [n] } b_i^2 \big), then

min⁡0≤t≤min⁡i∈[n]1/(bi⋅2)f(t)=(∑i∈[n]2⋅bi2)⋅(λ4⋅∑i∈[n]bi2)2−λ⋅λ4⋅∑i∈[n]bi2=−λ28⋅∑i∈[n]bi2. \begin{aligned} \min_{ 0 \le t \le \min_{i \in [n] } 1 / (b_i \cdot \sqrt{2} ) } f(t) &= \left( \sum_{i \in [n] } 2 \cdot b_i^2 \right) \cdot \left( \frac{\lambda}{4 \cdot \sum_{i \in [n] } b_i^2 } \right)^2 - \lambda \cdot \frac{\lambda}{4 \cdot \sum_{i \in [n] } b_i^2 } \\ &= - \frac{\lambda^2}{8 \cdot \sum_{i \in [n] } b_i^2 }. \end{aligned}

Otherwise, min⁡i∈[n]1/(bi⋅2)≤λ/(4⋅∑i∈[n]bi2)\min_{i \in [n] } 1 / (b_i \cdot \sqrt{2} ) \le \lambda / \big( 4 \cdot \sum_{i \in [n] } b_i^2 \big), then

min⁡0≤t≤min⁡i∈[n]1/(bi⋅2)f(t)=(∑i∈[n]2⋅bi2)⋅(min⁡i∈[n]1bi⋅2)2−λ⋅(min⁡i∈[n]1bi⋅2)=((∑i∈[n]2⋅bi2)⋅(min⁡i∈[n]1bi⋅2)−λ)⋅(min⁡i∈[n]1bi⋅2)≤(λ2−λ)⋅(min⁡i∈[n]1bi⋅2)=−λ2⋅(min⁡i∈[n]1bi⋅2). \begin{aligned} \min_{ 0 \le t \le \min_{i \in [n] } 1 / (b_i \cdot \sqrt{2} ) } f(t) &= \left( \sum_{i \in [n] } 2 \cdot b_i^2 \right) \cdot \left( \min_{i \in [n] } \frac{ 1 }{ b_i \cdot \sqrt{2} } \right)^2 - \lambda \cdot \left( \min_{i \in [n] } \frac{ 1 }{ b_i \cdot \sqrt{2} } \right) \\ &= \left( \left( \sum_{i \in [n] } 2 \cdot b_i^2 \right) \cdot \left( \min_{i \in [n] } \frac{ 1 }{ b_i \cdot \sqrt{2} } \right) - \lambda \right) \cdot \left( \min_{i \in [n] } \frac{ 1 }{ b_i \cdot \sqrt{2} } \right) \\ &\le \left( \frac{\lambda}{2} - \lambda \right) \cdot \left( \min_{i \in [n] } \frac{ 1 }{ b_i \cdot \sqrt{2} } \right) \\ &= - \frac{\lambda}{2} \cdot \left( \min_{i \in [n] } \frac{ 1 }{ b_i \cdot \sqrt{2} } \right). \end{aligned}

□\square

Two

There is a trick to combine the two cases into to one. We can choose arbitrary ν∈R\nu \in \mathbb{R}, such that

ν≥∑i∈[n]bi2,  ν≥λ2⋅max⁡i∈[n](bi⋅2). \nu \ge \sqrt{\sum_{i \in [n] } b_i^2 },\, \quad\, \nu \ge \sqrt{ \frac{\lambda }{ 2 } \cdot \max_{i \in [n] } (b_i \cdot \sqrt{2}) }.

Then, for 0≤t≤min⁡i∈[n]1/(bi⋅2)0 \le t \le \min_{i \in [n] } 1 / (b_i \cdot \sqrt{2} ),

Pr⁡[X≥λ]≤exp⁡(−tλ+∑i∈[n]2⋅bi2⋅t2)≤exp⁡(−tλ+2⋅ν2⋅t2) \begin{aligned} \Pr[ X \ge \lambda ] &\le \exp \left( - t \lambda + \sum_{i \in [n] } 2 \cdot b_i^2 \cdot t^2 \right) \\ &\le \exp \left( - t \lambda + 2 \cdot \nu^2 \cdot t^2 \right) \end{aligned}

We can always set

t=λ4⋅ν2≤min⁡i∈[n]1bi⋅2, t = \frac{\lambda}{4 \cdot \nu^2 } \le \min_{i \in [n] } \frac{1}{ b_i \cdot \sqrt{2} },

and obtain

Pr⁡[X≥λ]≤exp⁡(−λ28ν2). \Pr[ X \ge \lambda ] \le \exp \left( - \frac{\lambda^2}{ 8 \nu^2 } \right).

To make the bound as tight as possible, we would like ν\nu to be as small as possible. Therefore, the best choice would be

ν=max⁡{∑i∈[n]bi2,λ2⋅max⁡i∈[n](bi⋅2)}. \nu = \max \left\{ \sqrt{ \sum_{i \in [n] } b_i^2 }, \sqrt{ \frac{\lambda }{ 2 } \cdot \max_{i \in [n] } (b_i \cdot \sqrt{2}) } \right\}.

The bound is indeed equivalent to the one in the previous section.

Can We Do Better

Can we improve the bound, if we have better approximation of y=1/(1−x)y = 1 / (1 - x)? Observe that

exp⁡(−tλ)⋅∏i∈[n]E[exp⁡(tXi)]=exp⁡(−tλ)⋅∏i∈[n]11−bi2⋅t2 \begin{aligned} \exp( - t \lambda) \cdot \prod_{i \in [n] } \mathbb{E}[ \exp(t X_i) ] &= \exp( - t \lambda) \cdot \prod_{i \in [n] } \frac{1}{1 - b_i^2 \cdot t^2 } \end{aligned}

Previously, we apply the approximation 1/(1−x)≤exp⁡(2x)1 / (1 - x) \le \exp(2 x) to upper bound the RHS.

On the other hand, as 1/(1−x)≥ex1 / (1 - x) \ge e^x for x∈[0,1]x \in [0, 1], any upper bound for the RHS is lower bounded by

exp⁡(−tλ+∑i∈[n]bi2⋅t2) \begin{aligned} \exp \left( - t \lambda + \sum_{i \in [n] } b_i^2 \cdot t^2 \right) \end{aligned}

Even if we give maximum freedom to tt by allowing it to take any value in [0,min⁡i∈[n]1/bi][0, \min_{i \in [n] } 1/ b_i ], the above term is minimized to

{exp⁡(−λ2/(4⋅∑i∈[n]bi2)),λ/(2⋅∑i∈[n]bi2)≤min⁡i∈[n]1/biexp⁡(−λ⋅(min⁡i∈[n]1/bi)+∑i∈[n]bi2⋅(min⁡i∈[n]1/bi)2),λ/(2⋅∑i∈[n]bi2)>min⁡i∈[n]1/bi \begin{cases} \exp \left( - \lambda^2 / \big( 4 \cdot \sum_{i \in [n] } b_i^2 \big) \right), & \lambda / \big( 2 \cdot \sum_{i \in [n] } b_i^2 \big) \le \min_{i \in [n] } 1/ b_i \\ \exp \left( - \lambda \cdot ( \min_{i \in [n] } 1 / b_i ) + \sum_{i \in [n] } b_i^2 \cdot ( \min_{i \in [n] } 1 / b_i )^2 \right), & \lambda / \big( 2 \cdot \sum_{i \in [n] } b_i^2 \big) > \min_{i \in [n] } 1/ b_i \end{cases}

This implies that, even if we find some better approximation for y=1/(1−x)y = 1 / (1 - x) to derive a concentration inequality, we can only improve it by a constant (in the exponent), compared to the ones we prove in the previous section.

Reference

[1]. Chan, T.H.H., Shi, E. and Song, D., 2011. Private and continual release of statistics. ACM Transactions on Information and System Security (TISSEC), 14(3), pp.1-24.