Qual é a prova dessa versão fora do padrão da desigualdade de Azuma?

12

No Apêndice B de Boosting and Differential Privacy, de Dwork et al., Os autores declaram o seguinte resultado sem prova e se referem a ele como a desigualdade de Azuma:

Sejam C1,,Ck variáveis ​​aleatórias com valor real, de modo que para cada i[k] ,

  1. Pr[|Ci|α]=1
  2. para cada , temos .(c1,,ci1)Supp(C1,,Ci1)E[CiC1=c1,,Ci1=ci1]β

Então, para cada , temos .z>0Pr[i=1kCi>kβ+zkα]ez2/2

Estou tendo problemas para provar isso. A versão padrão da desigualdade de Azuma diz:

Suponha que seja um martingale e quase certamente. Então, para todo , temos .{X0,X1,,Xk}|XiXi1|γit>0Pr[Xkt]exp(t2/(2i=1kγi2))

Para provar a versão da desigualdade de Azuma declarada por Dwork et al., que deveríamos tomar e . Dessa forma, acho que é um martingale. Mas tudo o que podemos dizer é que quase certamente, certo? Esse fator de dois causa problemas, porque significa que, após a substituição, simplesmente descobrimos que , que é mais fraca que a conclusão afirmada por Dwork et al.X0=0Xi=Xi1+CiE[CiC1,C2,,Ci1]{X0,,Xk}|XiXi1|2αPr[i=1kCi>kβ+zk2α]ez2/2

Falta um truque simples? É a afirmação de Dwork et al. faltando um fator de dois?

William Hoza
fonte
A afirmação no artigo é verdadeira, mas não segue a versão "usual" da desigualdade de Azuma. O problema é que a instrução usual assume mas qualquer intervalo do mesmo tamanho será necessário; não há razão para assumir um intervalo simétrico. XiXi1[a,a]
Thomas suporta Monica

Respostas:

13

Não consigo encontrar uma referência, então vou esboçar a prova aqui.

Teorema. Seja sejam variáveis ​​aleatórias reais. Seja sejam constantes. Suponha que, para todos os e todos no suporte de , temosX1,,Xna1,,an,b1,,bni{1,,n}(x1,,xi1)(X1,,Xi1)

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

Então, para todos ,t0

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

Prova. Defina . Afirmamos que Para todos os e , temos Por suposição, e para todos os no suporte deYi=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. (Observe que .) Assim, pelo lema de Hoeffding , para todos os no suporte de e todos os . Como , temos, para todos , Agora a indução produz a reivindicação (*) acima.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].

Agora aplicamos a desigualdade de Markov em e usamos nossa reivindicação (*). Para todos os , Por fim, defina para minimizar a expressão da mão direita e obter o resultado. 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

Como mencionei no meu comentário, a principal diferença entre esta e a afirmação "usual" da desigualdade de Azuma está exigindo , em vez de . O primeiro permite mais flexibilidade e isso economiza um fator de 2 em alguns casos.Xi[ai,bi]Xi[a,a]

Observe que as variáveis ​​aleatórias na prova são um supermartingale. Você pode obter a versão usual da desigualdade de Azuma usando um Martingale , configurando e (onde ) e depois aplique o resultado acima.YiY1,,YnXi=YiYi1[ai,bi]=[ci,ci]P[|YiYi1|ci]=1

Thomas apoia Monica
fonte
Na primeira linha da prova, ele deve ser presumivelmente (limite superior da soma como em vez de ) ....Yi=j=1iXjin
Dougal
1
A prova também é dada na monografia por Dubhashi e Panconesi.
Kristoffer Arnsfelt Hansen
@KristofferArnsfeltHansen: Ótimo. Você tem um link?
Thomas apoia Monica