マクディアミドの不等式に対する東の不等式？
Azumas Inequality Mcdiarmids Inequality
解決：
違いは、有界変数の劣ガウスノルム/パラメーターの定数がより鋭いことです。あなたはまだ東のテクニックを使ってより鋭い境界を得ることができます。これが私が少し前に書いたいくつかのメモです：
劣ガウステールバウンド
$ mathbb {E} e ^ { lambda X} le e ^ { sigma ^ 2 lambda ^ 2/2} $は、次のテールバウンドを意味することを思い出してください（$ mathbb {E} X = 0 $） begin {align *} mathbb {P}（X ge t） le exp Big（{- frac {t ^ 2} {2 sigma ^ 2}} Big） end {align *}そのような確率変数は、パラメーター$ sigma $を持つ劣ガウス確率変数と呼ばれます。
有界変数$ X in [a、b] $は、サブGパラメーター$ sigma ^ 2 =（b-a）^ 2/4 $の2乗を持っています。この鋭い境界は、表示するためにいくつかの作業が必要です（演習として残します）。
Azuma-Hoeffding approach
$ Z = f（X）= f（X_1、 dots、X_n）$の濃度限界を提供したいと思います。
$ mathbb {E} _i [Z]：= mathbb {E} [Z | X_1、 dots、X_i] $および$ Delta_i = mathbb {E} _i [Z]- mathbb {E} _ {i-1} [Z] $。次に、$ { Delta_i } $はマルチンゲール差分シーケンスです：$ mathbb {E} _ {i-1} [ Delta_i] = 0 $。 $ S_j：= sum_ {i = 1} ^ j Delta_i $とします。これは、$ X_i、i le j $の関数のみです。 begin {align *} S_n = sum_ {i = 1} ^ n Delta_i = Z- mathbb {E} Z end {align *}（*）$ mathbb {E} _ {i -1} [e ^ { lambda Delta_i}] le e ^ { sigma_i ^ 2 lambda ^ 2/2} $すべての$ lambda ge 0 $とすべての$ i $について、ほぼ確実に。次に、 begin {align *} mathbb {E} _ {n-1} [e ^ { lambda S_n}] = e ^ { lambda S_ {n-1}} mathbb {E} _ {n- 1} [e ^ { lambda Delta_n}] le e ^ { lambda S_ {n-1}} e ^ { sigma_n ^ 2 lambda ^ 2/2} end {align *} $ mathbbを取る両側の{E} _ {n-2} $： begin {align *} mathbb {E} _ {n-2} [e ^ { lambda S_n}] le e ^ { sigma_n ^ 2 lambda ^ 2/2} mathbb {E} _ {n-2} [e ^ { lambda S_ {n-1}}] le e ^ { lambda S_ {n-2}} e ^ {（ sigma_n ^ 2 + sigma_ {n-1} ^ 2） lambda ^ 2/2} end {align *}このプロセスを繰り返すと、$ mathbb {E} _ {0} [e ^ { lambda S_n }] le exp（（ sum_ {i = 1} ^ n sigma_i ^ 2） lambda ^ 2/2）$。 $ S_n $がsquared-paramのサブGであることを示しています。 $ sigma ^ 2 = sum_ {i = 1} ^ n sigma_i ^ 2 $。
限界の違い
条件付きサブGの仮定（*）は、制限された差の下で成り立ちます begin {align *} | f（x_1、 dots、x_ {i-1}、x_i、x_ {i + 1}、 dots、x_n）-f（ x_1、 dots、x_ {i-1}、x_i '、x_ {i + 1}、 dots、x_n）| le L_i end {align *} Let $ g_i（x_1、 dots、x_i）：= mathbb {E} [f（x_1、 dots、x_ {i-1}、x_i、X_ {i + 1} 、 dots、X_n）] $なので、$ mathbb {E} _i [Z] = g_i（X_1、 dots、X_i）$になります。これは独立性を使用します。つまり、残りの分布は条件付けによって変化しません。 Jensenのアプリケーションにより、$ g_i $が定数$（L_1、 dots、L_i）$で有界差分条件を満たすことは簡単にわかります。
ナイーブバウンド： begin {align *} Delta_i = mathbb {E} _i [Z]- mathbb {E} _ {i-1} [ mathbb {E} _i [Z]] = g_i（X_1、 dots 、X_i）- mathbb {E} _ {i-1} [g_i（X_1、 dots、X_i）] end {align *} $ X_1、 dots、X_ {i-1} $を条件として、次のようになります。効果的に見る（$ X'_i $は$ X_i $の独立したコピーです） begin {align *} g_i（x_1、 dots、x_ {i-1}、X_i）- mathbb {E} [g_i（x_1 、 dots、x_ {i-1}、X'_i）] end {align *}は、$ {X_i } $の独立性のためです。したがって、$ | Delta_i | le L_i $条件（$ X_1、 dots、X_ {i-1} $）。つまり、$ mathbb {E} _ {i-1} [e ^ { lambda Delta_i}] le e ^ { sigma_i ^ 2 lambda ^ 2/2} $ここで、$ sigma_i ^ 2 =（ 2L_i）^ 2/4 = L_i ^ 2 $。
より良い限界： $ Delta_i in I_i $ここで、$ | I_i | le L_i $、定数を$ 4 $改善：$ X_1、 dots、X_i $を条件として、 begin {align *} Delta_i = g_i（x_1、 dots、x_ {i-1} 、X_i）- mu_i end {align *}ここで、$ mu_i $は定数です（$ x_1、 dots、x_ {i-1} $の関数のみ）。次に、$ Delta_i + mu_i in [a_i、b_i] $ここで、$ a_i = inf_x g_i（x_1、 dots、x_ {i-1}、x）$および$ b_i = sup_x g_i（x_1、ドット、x_ {i-1}、x）$。 begin {align *} b_i --a_i = sup_ {x、y} big [g_i（x_1、 dots、x_ {i-1}、x）-g_i（x_1、 dots、x_ {i- 1}、y） big] le L_i end {align *}したがって、$ mathbb {E} _ {i-1} [e ^ { lambda Delta_i}] le e ^ { sigma ^ 2 lambda ^ 2/2} $ここで、$ sigma_i ^ 2 =（b_i-a_i）^ 2/4 le L_i ^ 2/4 $。