13
$\begingroup$

In Appendix B of Boosting and Differential Privacy by Dwork et al., the authors state the following result without proof and refer to it as Azuma's inequality:

Let $C_1, \dots, C_k$ be real-valued random variables such that for every $i \in [k]$,

  1. $\Pr[|C_i| \leq \alpha] = 1$, and
  2. for every $(c_1, \dots, c_{i - 1}) \in \text{Supp}(C_1, \dots, C_{i - 1})$, we have $\text{E}[C_i \mid C_1 = c_1, \dots, C_{i - 1} = c_{i - 1}] \leq \beta$.

Then for every $z > 0$, we have $\Pr[\sum_{i = 1}^k C_i > k\beta + z \sqrt{k} \cdot \alpha] \leq e^{-z^2/2}$.

I'm having trouble proving this. The standard version of Azuma's inequality says:

Suppose $\{X_0, X_1, \dots, X_k\}$ is a martingale, and $|X_i - X_{i - 1}| \leq \gamma_i$ almost surely. Then for all $t > 0$, we have $\Pr[X_k \geq t] \leq \exp(-t^2/(2 \sum_{i = 1}^k \gamma_i^2))$.

To prove the version of Azuma's inequality stated by Dwork et al., I figured we should take $X_0 = 0$ and $X_i = X_{i - 1} + C_i - \text{E}[C_i \mid C_1, C_2, \dots, C_{i - 1}]$. That way, I think $\{X_0, \dots, X_k\}$ is a martingale. But all we can say is that $|X_i - X_{i - 1}| \leq 2\alpha$ almost surely, right? That factor of two causes trouble, because it means that after substituting, we merely find that $\Pr[\sum_{i = 1}^k C_i > k\beta + z\sqrt{k} \cdot 2\alpha] \leq e^{-z^2/2}$, which is weaker than the conclusion stated by Dwork et al.

Is there a simple trick I'm missing? Is the statement by Dwork et al. missing a factor of two?

$\endgroup$
  • $\begingroup$ The statement in the paper is true, but does not follow from the "usual" version of Azuma's inequality. The issue is that the usual statement assumes $X_i-X_{i-1}\in[-a,a]$ but any interval of the same length will do; there is no reason to assume a symmetric interval. $\endgroup$ – Thomas Sep 25 '17 at 23:44
13
$\begingroup$

I can't find a reference, so I'll just sketch the proof here.

Theorem. Let $X_1, \cdots, X_n$ be real random variables. Let $a_1, \cdots, a_n, b_1, \cdots, b_n$ be constants. Suppose that, for all $i \in \{1,\cdots,n\}$ and all $(x_1,\cdots,x_{i-1})$ in the support of $(X_1, \cdots, X_{i-1})$, we have

  1. $\mathbb{E}[X_i | X_1=x_1, \cdots, X_{i-1}=x_{i-1}] \leq 0$ and
  2. $\mathbb{P}[X_i \in [a_i,b_i]]=1$.

Then, for all $t\geq0$, $$\mathbb{P}\left[\sum_{i=1}^n X_i \geq t\right] \leq \exp\left(\frac{-2t^2}{\sum_{i=1}^n (b_i-a_i)^2}\right).$$

Proof. Define $Y_i = \sum_{j=1}^i X_j$. We claim that $$\forall i \in \{1,\cdots,n\}~\forall \lambda \geq 0 ~~~~~ \mathbb{E}\left[e^{\lambda Y_i}\right] \leq e^{\frac18 \lambda^2 \sum_{j=1}^i (b_j-a_j)^2}.\tag*{(*)}$$ For all $i$ and $\lambda$, we have $$\mathbb{E}\left[e^{\lambda Y_i}\right] = \mathbb{E}\left[e^{\lambda Y_{i-1}}\cdot e^{\lambda X_i}\right] = \mathbb{E}\left[e^{\lambda Y_{i-1}}\cdot \mathbb{E}\left[e^{\lambda X_i}\middle|Y_{i-1}\right]\right].$$ By assumption, $\mu(y_{i-1}):=\mathbb{E}[X_i|Y_{i-1}=y_{i-1}]\leq 0$ and $\mathbb{P}[X_i \in [a_i,b_i]] =1$ for all $y_{i-1}$ in the support of $Y_{i-1}$. (Note that $Y_{i-1}=X_1+\cdots+X_{i-1}$.) Thus, by Hoeffding's lemma, $$\mathbb{E}\left[e^{\lambda X_i}\middle|Y_{i-1}=y_{i-1}\right] \leq e^{\lambda\mu(y_{i-1})+\frac18 \lambda^2(b_i-a_i)^2}$$ for all $y_{i-1}$ in the support of $Y_{i-1}$ and all $\lambda \in \mathbb{R}$. Since $\mu(y_{i-1})\leq 0$, we have, for all $\lambda \geq 0$, $$\mathbb{E}\left[e^{\lambda Y_i}\right] \leq \mathbb{E}\left[e^{\lambda Y_{i-1}}\cdot e^{0+\frac18 \lambda^2(b_i-a_i)^2}\right].$$ Now induction yields the claim (*) above.

Now we apply Markov's inequality to $e^{\lambda Y_n}$ and use our claim (*). For all $t, \lambda > 0$, $$\mathbb{P}\left[\sum_{i=1}^n X_i \geq t\right]=\mathbb{P}[Y_n \geq t] = \mathbb{P}\left[e^{\lambda Y_n} \geq e^{\lambda t}\right] \leq \frac{\mathbb{E}\left[e^{\lambda Y_n}\right]}{e^{\lambda t}} \leq \frac{e^{\frac18 \lambda^2 \sum_{i=1}^n (b_i-a_i)^2}}{e^{\lambda t}}.$$ Finally, set $\lambda=\frac{4t}{\sum_{i=1}^n (b_i-a_i)^2}$ to minimize the right hand expression and obtain the result. $\tag*{$\blacksquare$}$

As I mentioned in my comment, the key difference between this and the "usual" statement of Azuma's inequality is requiring $X_i \in [a_i,b_i]$, rather than $X_i \in [-a,a]$. The former allows more flexibility and this saves a factor of 2 in some cases.

Note that the $Y_i$ random variables in the proof are a supermartingale. You can obtain the usual version of Azuma's inequality by taking a Martingale $Y_1, \cdots, Y_n$, setting $X_i=Y_i-Y_{i-1}$ and $[a_i,b_i]=[-c_i,c_i]$ (where $\mathbb{P}[|Y_i-Y_{i-1}|\leq c_i]=1$), and then applying the above result.

$\endgroup$
  • $\begingroup$ In the first line of the proof, it should presumably be $Y_i = \sum_{j=1}^i X_j$ (upper bound of the sum as $i$ rather than $n$).... $\endgroup$ – Dougal Sep 26 '17 at 2:12
  • 1
    $\begingroup$ The proof is also given in the monograph by Dubhashi and Panconesi. $\endgroup$ – Kristoffer Arnsfelt Hansen Sep 27 '17 at 8:01
  • $\begingroup$ @KristofferArnsfeltHansen: Great. Do you have a link? $\endgroup$ – Thomas Sep 27 '17 at 18:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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