3
$\begingroup$

I am trying to prove that if $r_i \sim Lap(0,1/\varepsilon)$ where $\varepsilon >0$ then:

$$Pr[r_i \geq 1+r^*] \geq e^{-\varepsilon}Pr[r_i \geq r^{*}]$$.

I know that for $r*>0$ it satisfies with equality. Even though, for $r <0$, I couldn't find out how to prove it.

Note $Lap \sim (\mu,b)$:

$$Pr[X \geq x] = 1-F(x)=\begin{cases} 1-\frac{1}{2}\exp(\frac{x-\mu}{b}) && \text{if }x< \mu \\ \frac{1}{2}\exp(-\frac{x-\mu}{b}) &&\text{if } x\geq \mu\end{cases},$$

$\endgroup$
4
  • 1
    $\begingroup$ Your equation is incomplete. What is $1/\epsilon$? The spread parameter? Unless the negative case is $-1\leq r* <0,$ such an inequality won't hold since the distribution is of the form $c \exp(-|r|)$ thus it is increasing for $r\leq 0.$ $\endgroup$
    – kodlu
    Commented Jul 31, 2020 at 23:08
  • $\begingroup$ I think what its happening is the contrary. When $r* <-1$ the inequality holds. I did some calculations and works very well. When $-1\leq r* <0$, is more complex because when $1+r*>0$, the cumulative distribution may change for some values $1+r*$ and $r*$. This inequality is from proof of Report Noisy Max in differential privacy. $\endgroup$ Commented Jul 31, 2020 at 23:26
  • 1
    $\begingroup$ well i hadnt seen your full equation. by the way your $x\geq \mu$ case is still looks wrong. The distribution is negative $\endgroup$
    – kodlu
    Commented Aug 1, 2020 at 0:19
  • $\begingroup$ Yeap, it's positive. If you maybe take some time thinking about it and find a way to solve it, will help me a lot !. Yeah, I just changed it to seem more clearly in the question. I have spent like two days already :( $\endgroup$ Commented Aug 1, 2020 at 1:16

1 Answer 1

1
$\begingroup$

OK, I did this quickly. Hope it’s correct.

When $r*\geq 0,$ the relationship holds as you observed. And when $r^*\leq -1,$ the same expression for both probabilities you want to compare enables a direct proof.

Let $r^*\in(-1,0),$ so that $1+r^* \in (0,1).$ Then what you want to show is $$\frac{1}{2} e^{-\epsilon(1+r^*)}\geq e^{-\epsilon}\left(1-\frac{1}{2} e^{\epsilon r^*}\right) $$ or $$ \frac{1}{2} e^{-\epsilon(r^*+1)}+ \frac{1}{2} e^{\epsilon (r^*-1)} \geq e^{-\epsilon} $$ or $$ e^{-\epsilon} \left( \frac{ e^{-\epsilon r^*}+ e^{\epsilon r^*}}{2} \right)\geq e^{-\epsilon} $$ which holds since the cosh function is lower bounded by $1.$


When $r*<-1$, a litlle more larger, we want to find the next inequality:

\begin{equation*} \begin{split} e^{\epsilon} \left(1-\frac{1}{2}e^{\epsilon(x+1)} \right) \geq 1-\frac{1}{2}e^{\epsilon(x)}\\ e^{\epsilon}-\frac{1}{2}e^{\epsilon x+ 2\epsilon}\geq 1-\frac{1}{2}e^{\epsilon(x)} \end{split} \end{equation*}

Which we will bounded by both inequalities using the fact that $r*\leq-1$

\begin{equation*} \begin{split} r* &\leq -1\\ e^{\epsilon r*} &\leq e^{-\epsilon}\\ e^{\epsilon x + 2\epsilon} &\leq e^{\epsilon}\\ -\frac{1}{2}e^{\epsilon r*+ 2\epsilon} &\geq -\frac{1}{2}e^{\epsilon}\\ e^{\epsilon}-\frac{1}{2}e^{\epsilon r*+ 2\epsilon} &\geq e^{\epsilon}-\frac{1}{2}e^{\epsilon}\\ \end{split} \end{equation*}

The same way we have:

\begin{equation*} \begin{split} r* &\leq -1\\ 1-\frac{1}{2}e^{\epsilon x} & \geq 1-\frac{1}{2}e^{-\epsilon} \end{split} \end{equation*}

Joining this inequalitys, we can obtain

\begin{equation*} \begin{split} e^{\epsilon}-\frac{1}{2}e^{\epsilon} > 1-\frac{1}{2}e^{-\epsilon}\\ 2(e^{\epsilon}-1) > e^{\epsilon}-e^{-\epsilon} \end{split} \end{equation*}

Where the inequalitie holds since $2>1$ and $-1 \leq - e^{-\epsilon}$

$\endgroup$
4
  • $\begingroup$ That proof seems correct ! But can you show also when $r* \leq -1$ ? I don't see the direct way. $\endgroup$ Commented Aug 1, 2020 at 5:39
  • $\begingroup$ Already did the proof of $r*<-1$, it's not so direct. Anyway thanks, for the tip :) $\endgroup$ Commented Aug 2, 2020 at 9:21
  • 1
    $\begingroup$ Been too busy with a deadline. Feel free to edit answer to include that case.. $\endgroup$
    – kodlu
    Commented Aug 2, 2020 at 9:56
  • $\begingroup$ Perfect, done. I think its correct $\endgroup$ Commented Aug 9, 2020 at 7:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.