Was ist der Beweis für diese nicht standardmäßige Version von Azumas Ungleichung?

12

In Anhang B von Boosting and Differential Privacy von Dwork et al. Geben die Autoren das folgende Ergebnis ohne Beweis an und bezeichnen es als Azumas Ungleichung:

Lassen werden reellwertigen Zufallsvariablen , so dass für jedes , i [ k ]C1,,Cki[k]

  1. Pr[|Ci|α]=1 und
  2. für jedes haben wir \ text {E} [C_i \ mid C_1 = c_1 , \ dots, C_ {i-1} = c_ {i-1}] \ leq \ beta .(c1,,ci1)Supp(C1,,Ci1)E[CiC1=c1,,Ci1=ci1]β

Dann haben wir für jedes z> 0 \ Pr [\ sum_ {i = 1} ^ k C_i> k \ beta + z \ sqrt {k} \ cdot \ alpha] \ leq e ^ {- z ^ 2/2} .z>0Pr[i=1kCi>kβ+zkα]ez2/2

Ich habe Probleme, das zu beweisen. Die Standardversion der Azuma-Ungleichung besagt:

Angenommen, {X0,X1,,Xk} ist ein Martingal und |XiXi1|γi fast sicher. Dann haben wir für alle t> 0 \ Pr [X_k \ geq t] \ leq \ exp (-t ^ 2 / (2 \ sum_ {i = 1} ^ k \ gamma_i ^ 2)) .t>0Pr[Xkt]exp(t2/(2i=1kγi2))

Um die von Dwork et al. Version der Azuma-Ungleichung zu beweisen, habe ich angenommen, wir sollten und . Auf diese Weise halte ich für einen Martingal. Wir können aber nur sagen, dass ziemlicher Sicherheit, oder? Dieser Faktor zwei verursacht Probleme, weil es bedeutet, dass wir nach dem Ersetzen nur feststellen, dass , was schwächer ist als die Schlussfolgerung von Dwork et al.X i = X i - 1 + C i - E [ C iC 1 , C 2 , , C i - 1 ] { X 0 , , X k } | X i - X i - 1 | 2 α Pr [ k i = 1X0=0Xi=Xi1+CiE[CiC1,C2,,Ci1]{X0,,Xk}|XiXi1|2αPr[i=1kCi>kβ+zk2α]ez2/2

Gibt es einen einfachen Trick, den ich vermisse? Ist die Aussage von Dwork et al. Fehlt ein Faktor zwei?

William Hoza
quelle
Die Aussage in dem Papier ist wahr, folgt aber nicht aus der "üblichen" Version von Azumas Ungleichung. Das Problem ist, dass die übliche Anweisung annimmt aber jedes Intervall der gleichen Länge ausreicht. Es gibt keinen Grund, ein symmetrisches Intervall anzunehmen. XiXi1[a,a]
Thomas unterstützt Monica

Antworten:

13

Ich kann keine Referenz finden, deshalb skizziere ich hier nur den Beweis.

Satz. Sei echte Zufallsvariablen. Sei Konstanten. Angenommen, für alle und alle in der Unterstützung von , wir habenX1,,Xna1,,an,b1,,bni{1,,n}(x1,,xi1)(X1,,Xi1)

  1. E[Xi|X1=x1,,Xi1=xi1]0 und
  2. P[Xi[ai,bi]]=1 .

Dann wird für alle ,t0

P[i=1nXit]exp(2t2i=1n(biai)2).

Beweis. Definiere . Wir behaupten, dass Für alle und haben wir Angenommen, und für alle in der Unterstützung vonYi=j=1iXj

(*)i{1,,n} λ0     E[eλYi]e18λ2j=1i(bjaj)2.
iλ
E[eλYi]=E[eλYi1eλXi]=E[eλYi1E[eλXi|Yi1]].
μ(yi1):=E[Xi|Yi1=yi1]0P[Xi[ai,bi]]=1yi1Yi1. (Beachten Sie, dass .) Nach Höffding ' Lemma ist für alle zur Unterstützung von und all . Da , die wir haben, für alle , Nun ergibt die Induktion den obigen Anspruch (*).Yi1=X1++Xi1
E[eλXi|Yi1=yi1]eλμ(yi1)+18λ2(biai)2
yi1Yi1λRμ(yi1)0λ0
E[eλYi]E[eλYi1e0+18λ2(biai)2].

Nun wenden wir Markovs Ungleichung auf und verwenden unsere Behauptung (*). Für alle , Setzen Sie schließlich , um den Ausdruck für die rechte Hand zu minimieren und das Ergebnis zu erhalten. eλYnt,λ>0

P[i=1nXit]=P[Ynt]=P[eλYneλt]E[eλYn]eλte18λ2i=1n(biai)2eλt.
λ=4ti=1n(biai)2

Wie ich in meinem Kommentar erwähnt habe, erfordert der Hauptunterschied zwischen dieser und der "üblichen" Aussage von Azumas Ungleichung und nicht . Ersteres ermöglicht mehr Flexibilität und spart in einigen Fällen den Faktor 2.Xi[ai,bi]Xi[a,a]

Beachten Sie, dass die Zufallsvariablen im Beweis eine Supermartingale sind. Sie können die übliche Version von Azumas Ungleichung erhalten, indem Sie ein Martingal , und (wobei ) und dann Anwenden des obigen Ergebnisses.YiY1,,YnXi=YiYi1[ai,bi]=[ci,ci]P[|YiYi1|ci]=1

Thomas unterstützt Monica
quelle
In der ersten Zeile des Beweises sollte es vermutlich sein (obere Grenze der Summe als statt ) ....Yi=j=1iXjin
Dougal
1
Der Beweis ist auch in der Monographie von Dubhashi und Panconesi gegeben.
Kristoffer Arnsfelt Hansen
@KristofferArnsfeltHansen: Großartig. Hast du einen Link?
Thomas unterstützt Monica