Apa bukti ketidaksetaraan Azuma versi tidak standar ini?

Dalam Lampiran B dari Meningkatkan dan Privasi Diferensial oleh Dwork et al., Penulis menyatakan hasil berikut tanpa bukti dan menyebutnya sebagai ketidaksetaraan Azuma:

Biarkan $C_1, \dots, C_k$ variabel acak akan bernilai real sehingga untuk setiap $i \in [k]$ ,

$\Pr[|C_i| \leq \alpha] = 1$

untuk setiap , kami memiliki . $(c_1, \dots, c_{i - 1}) \in \text{Supp}(C_1, \dots, C_{i - 1})$ $\text{E}[C_i \mid C_1 = c_1, \dots, C_{i - 1} = c_{i - 1}] \leq \beta$

Kemudian untuk setiap , kita memiliki . $z > 0$ $\Pr[\sum_{i = 1}^k C_i > k\beta + z \sqrt{k} \cdot \alpha] \leq e^{-z^2/2}$

Saya kesulitan membuktikan ini. Versi standar ketidaksetaraan Azuma mengatakan:

Misalkan $\{X_0, X_1, \dots, X_k\}$ adalah martingale, dan $|X_i - X_{i - 1}| \leq \gamma_i$ hampir pasti. Kemudian untuk semua $t > 0$ , kita memiliki $\Pr[X_k \geq t] \leq \exp(-t^2/(2 \sum_{i = 1}^k \gamma_i^2))$ .

Untuk membuktikan versi ketidaksamaan Azuma yang dinyatakan oleh Dwork et al., Saya pikir kita harus mengambil $X_0 = 0$ dan $X_i = X_{i - 1} + C_i - \text{E}[C_i \mid C_1, C_2, \dots, C_{i - 1}]$ . Dengan begitu, saya pikir $\{X_0, \dots, X_k\}$ adalah martingale. Tapi yang bisa kita katakan adalah bahwa $|X_i - X_{i - 1}| \leq 2\alpha$ hampir pasti, bukan? Faktor dua penyebab masalah itu, karena itu berarti bahwa setelah penggantian, kami hanya menemukan bahwa $\Pr[\sum_{i = 1}^k C_i > k\beta + z\sqrt{k} \cdot 2\alpha] \leq e^{-z^2/2}$ , yang lebih lemah dari kesimpulan yang dinyatakan oleh Dwork et al.

Apakah ada trik sederhana yang saya lewatkan? Apakah pernyataan oleh Dwork et al. melewatkan faktor dua?

pr.probability William Hoza
sumber

Pernyataan di koran itu benar, tetapi tidak mengikuti versi "biasa" dari ketidaksetaraan Azuma. Masalahnya adalah bahwa pernyataan yang biasa mengasumsikan tetapi setiap interval dengan panjang yang sama akan dilakukan; tidak ada alasan untuk mengasumsikan interval simetris.

X_{i} - X_{i - 1} \in [- a, a]

$X_i-X_{i-1}\in[-a,a]$

Thomas mendukung Monica

Saya tidak dapat menemukan referensi, jadi saya hanya akan membuat sketsa buktinya di sini.

Dalil. Biarkan menjadi variabel acak nyata. Biarkan menjadi konstanta. Misalkan, untuk semua dan semua dalam dukungan , kita punya $X_1, \cdots, X_n$ $a_1, \cdots, a_n, b_1, \cdots, b_n$ $i \in \{1,\cdots,n\}$ $(x_1,\cdots,x_{i-1})$ $(X_1, \cdots, X_{i-1})$

$\mathbb{E}[X_i | X_1=x_1, \cdots, X_{i-1}=x_{i-1}] \leq 0$ dan

$\mathbb{P}[X_i \in [a_i,b_i]]=1$ .

Kemudian, untuk semua , $t\geq0$
$P [\sum_{i = 1}^{n} X_{i} \geq t] \leq \exp (\frac{- 2 t^{2}}{\sum_{i = 1}^{n} (b_{i} - a_{i})^{2}}) .$ $\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).$

Bukti. Tentukan . Kami mengklaim bahwa Untuk semua dan , kita memiliki Dengan asumsi, dan untuk semua dalam dukungan $Y_i = \sum_{j=1}^i X_j$

\begin{matrix} (*) & \forall i \in {1, \dots, n} \forall λ \geq 0 E [e^{λ Y_{i}}] \leq e^{\frac{1}{8} λ^{2} \sum_{j = 1}^{i} (b_{j} - a_{j})^{2}} . \end{matrix}

$\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*{(*)}$

i

$i$

λ

$\lambda$

E [e^{λ Y_{i}}] = E [e^{λ Y_{i - 1}} \cdot e^{λ X_{i}}] = E [e^{λ Y_{i - 1}} \cdot E [e^{λ X_{i}} | Y_{i - 1}]] .

$\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].$

μ (y_{i - 1}) := E [X_{i} | Y_{i - 1} = y_{i - 1}] \leq 0

$\mu(y_{i-1}):=\mathbb{E}[X_i|Y_{i-1}=y_{i-1}]\leq 0$

P [X_{i} \in [a_{i}, b_{i}]] = 1

$\mathbb{P}[X_i \in [a_i,b_i]] =1$

y_{i - 1}

$y_{i-1}$

Y_{i - 1}

$Y_{i-1}$ . (Perhatikan bahwa .) Dengan demikian, oleh lemma Hoeffding , untuk semua mendukung dan semua . Karena , kami memiliki, untuk semua , Sekarang induksi menghasilkan klaim (*) di atas.

Y_{i - 1} = X_{1} + \dots + X_{i - 1}

$Y_{i-1}=X_1+\cdots+X_{i-1}$

E [e^{λ X_{i}} | Y_{i - 1} = y_{i - 1}] \leq e^{λ μ (y_{i - 1}) + \frac{1}{8} λ^{2} (b_{i} - a_{i})^{2}}

$\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}$

y_{i - 1}

$y_{i-1}$

Y_{i - 1}

$Y_{i-1}$

λ \in R

$\lambda \in \mathbb{R}$

μ (y_{i - 1}) \leq 0

$\mu(y_{i-1})\leq 0$

λ \geq 0

$\lambda \geq 0$

E [e^{λ Y_{i}}] \leq E [e^{λ Y_{i - 1}} \cdot e^{0 + \frac{1}{8} λ^{2} (b_{i} - a_{i})^{2}}] .

$\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].$

Sekarang kami menerapkan ketidaksetaraan Markov pada dan menggunakan klaim kami (*). Untuk semua , Akhirnya, atur untuk meminimalkan ekspresi tangan kanan dan mendapatkan hasilnya. $e^{\lambda Y_n}$ $t, \lambda > 0$

P [\sum_{i = 1}^{n} X_{i} \geq t] = P [Y_{n} \geq t] = P [e^{λ Y_{n}} \geq e^{λ t}] \leq \frac{E [e^{λ Y_{n}}]}{e^{λ t}} \leq \frac{e^{\frac{1}{8} λ^{2} \sum_{i = 1}^{n} (b_{i} - a_{i})^{2}}}{e^{λ t}} .

$\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}}.$

λ = \frac{4 t}{\sum_{i = 1}^{n} (b_{i} - a_{i})^{2}}

$\lambda=\frac{4t}{\sum_{i=1}^n (b_i-a_i)^2}$

\begin{matrix} ◼ \end{matrix}

$\tag*{$\blacksquare$}$

Seperti yang saya sebutkan dalam komentar saya, perbedaan utama antara ini dan pernyataan "biasa" tentang ketimpangan Azuma membutuhkan , daripada . Yang pertama memungkinkan lebih banyak fleksibilitas dan ini menyimpan faktor 2 dalam beberapa kasus. $X_i \in [a_i,b_i]$ $X_i \in [-a,a]$

Perhatikan bahwa variabel acak dalam buktinya adalah supermartingale. Anda dapat memperoleh versi ketimpangan Azuma yang biasa dengan mengambil Martingale , pengaturan dan (di mana ), dan kemudian menerapkan hasil di atas. $Y_i$ $Y_1, \cdots, Y_n$ $X_i=Y_i-Y_{i-1}$ $[a_i,b_i]=[-c_i,c_i]$ $\mathbb{P}[|Y_i-Y_{i-1}|\leq c_i]=1$

Thomas mendukung Monica
sumber

Pada baris pertama buktinya, mungkin seharusnya (batas atas penjumlahan sebagai daripada ) ....

Y_{i} = \sum_{j = 1}^{i} X_{j}

$Y_i = \sum_{j=1}^i X_j$

i

$i$

n

$n$

Dougal

Buktinya juga diberikan dalam monograf oleh Dubhashi dan Panconesi.

Kristoffer Arnsfelt Hansen

@KristofferArnsfeltHansen: Hebat. Apakah Anda memiliki tautan?

Thomas mendukung Monica

Apa bukti ketidaksetaraan Azuma versi tidak standar ini?

Jawaban: