声明 関数f : X 1 × X 2 × ⋯ × X n → R {\displaystyle f:{\mathcal {X}}_{1}\times {\mathcal {X}}_{2}\times \cdots \times {\mathcal {X}}_{n}\rightarrow \mathbb {R} } 境界差の性質 を満たします。私 {\displaystyle i} x 私 {\displaystyle x_{i}} f {\displaystyle f} c 私 {\displaystyle c_{i}} c 1 、 c 2 、 … 、 c n {\displaystyle c_{1},c_{2},\dots ,c_{n}} 私 ∈ [ n ] {\displaystyle i\in [n]} x 1 ∈ X 1 、 x 2 ∈ X 2 、 … 、 x n ∈ X n {\displaystyle x_{1}\in {\mathcal {X}}_{1},\,x_{2}\in {\mathcal {X}}_{2},\,\ldots ,\,x_{n}\in {\mathcal {X}}_{n}}
すする x 私 ′ ∈ X 私 | f （ x 1 、 … 、 x 私 − 1 、 x 私 、 x 私 + 1 、 … 、 x n ） − f （ x 1 、 … 、 x 私 − 1 、 x 私 ′ 、 x 私 + 1 、 … 、 x n ） | ≤ c 私 。 \displaystyle \sup _{x_{i}'\in {\mathcal {X}}_{i}}\left|f(x_{1},\dots ,x_{i-1},x_{i},x_{i+1},\ldots ,x_{n})-f(x_{1},\dots ,x_{i-1},x_{i}',x_{i+1},\ldots ,x_{n})\right|\leq c_{i}.} マクディアミッドの不等式[ 2 ] — としますf : X 1 × X 2 × ⋯ × X n → R {\displaystyle f:{\mathcal {X}}_{1}\times {\mathcal {X}}_{2}\times \cdots \times {\mathcal {X}}_{n}\rightarrow \mathbb {R} } c 1 、 c 2 、 … 、 c n {\displaystyle c_{1},c_{2},\dots ,c_{n}}
独立な確率変数を考えるX 1 、 X 2 、 … 、 X n {\displaystyle X_{1},X_{2},\dots ,X_{n}} X 私 ∈ X 私 {\displaystyle X_{i}\in {\mathcal {X}}_{i}} 私 {\displaystyle i} ε > 0 {\displaystyle \varepsilon >0}
P （ f （ X 1 、 X 2 、 … 、 X n ） − E [ f （ X 1 、 X 2 、 … 、 X n ） ] ≥ ε ） ≤ exp （ − 2 ε 2 ∑ 私 = 1 n c 私 2 ） 、 {\displaystyle {\text{P}}\left(f(X_{1},X_{2},\ldots ,X_{n})-\mathbb {E} [f(X_{1},X_{2},\ldots ,X_{n})]\geq \varepsilon \right)\leq \exp \left(-{\frac {2\varepsilon ^{2}}{\sum _{i=1}^{n}c_{i}^{2}}}\right),} P （ f （ X 1 、 X 2 、 … 、 X n ） − E [ f （ X 1 、 X 2 、 … 、 X n ） ] ≤ − ε ） ≤ exp （ − 2 ε 2 ∑ 私 = 1 n c 私 2 ） 、 {\displaystyle {\text{P}}(f(X_{1},X_{2},\ldots ,X_{n})-\mathbb {E} [f(X_{1},X_{2},\ldots ,X_{n})]\leq -\varepsilon )\leq \exp \left(-{\frac {2\varepsilon ^{2}}{\sum _{i=1}^{n}c_{i}^{2}}}\right),} そしてその直接的な結果として、
P （ | f （ X 1 、 X 2 、 … 、 X n ） − E [ f （ X 1 、 X 2 、 … 、 X n ） ] | ≥ ε ） ≤ 2 exp （ − 2 ε 2 ∑ 私 = 1 n c 私 2 ） 。 {\displaystyle {\text{P}}(|f(X_{1},X_{2},\ldots ,X_{n})-\mathbb {E} [f(X_{1},X_{2},\ldots ,X_{n})]|\geq \varepsilon )\leq 2\exp \left(-{\frac {2\varepsilon ^{2}}{\sum _{i=1}^{n}c_{i}^{2}}}\right).}
拡張機能
不均衡な分布 関数の引数が不均衡な分布からサンプリングされる場合、単一の引数を再サンプリングしても関数値が大きく変化することはまれであるため、より強い境界を与えることができる。
マクディアミッドの不等式（不均衡）[ 3 ] [ 4 ] — とするf : X n → R {\displaystyle f:{\mathcal {X}}^{n}\rightarrow \mathbb {R} } c 1 、 c 2 、 … 、 c n {\displaystyle c_{1},c_{2},\dots ,c_{n}}
独立な確率変数を考えるX 1 、 X 2 、 … 、 X n ∈ X {\displaystyle X_{1},X_{2},\ldots ,X_{n}\in {\mathcal {X}}} χ 0 ∈ X \displaystyle \chi _{0}\in {\mathcal {X}} 1 − p {\displaystyle 1-p} ε > 0 {\displaystyle \varepsilon >0}
P （ | f （ X 1 、 … 、 X n ） − E [ f （ X 1 、 … 、 X n ） ] | ≥ ε ） ≤ 2 exp （ − ε 2 2 p （ 2 − p ） ∑ 私 = 1 n c 私 2 + 2 3 ε 最大 私 c 私 ） 。 {\displaystyle {\text{P}}(|f(X_{1},\ldots ,X_{n})-\mathbb {E} [f(X_{1},\ldots ,X_{n})]|\geq \varepsilon )\leq 2\exp \left({\frac {-\varepsilon ^{2}}{2p(2-p)\sum _{i=1}^{n}c_{i}^{2}+{\frac {2}{3}}\varepsilon \max _{i}c_{i}}}\right).} これは、例えば、疎なランダムグラフ やハイパーグラフ 上で関数を評価したときのグラフ 上の関数の値を特徴付けるために使用できます。なぜなら、疎なランダムグラフでは、特定のエッジが存在するよりも存在しない可能性の方がはるかに高いからです。
高い確率で境界が定められた差異 マクディアミッドの不等式は、解析対象の関数が厳密には有界差の性質を満たさない場合にも拡張できるが、大きな差が生じることは非常にまれである。
マクディアミッドの不等式（高い確率で差が制限される）[ 5 ] — とするf : X 1 × X 2 × ⋯ × X n → R {\displaystyle f:{\mathcal {X}}_{1}\times {\mathcal {X}}_{2}\times \cdots \times {\mathcal {X}}_{n}\rightarrow \mathbb {R} } Y ⊆ X 1 × X 2 × ⋯ × X n \displaystyle {\mathcal {Y}}\subseteq {\mathcal {X}}_{1}\times {\mathcal {X}}_{2}\times \cdots \times {\mathcal {X}}_{n}} c 1 、 c 2 、 … 、 c n ≥ 0 {\displaystyle c_{1},c_{2},\dots ,c_{n}\geq 0} （ x 1 、 … 、 x n ） ∈ Y {\displaystyle (x_{1},\ldots ,x_{n})\in {\mathcal {Y}}} （ x 1 ′ 、 … 、 x n ′ ） ∈ Y {\displaystyle (x'_{1},\ldots ,x'_{n})\in {\mathcal {Y}}}
| f （ x 1 、 … 、 x n ） − f （ x 1 ′ 、 … 、 x n ′ ） | ≤ ∑ 私 : x 私 ≠ x 私 ′ c 私 。 \displaystyle \left|f(x_{1},\ldots ,x_{n})-f(x'_{1},\ldots ,x'_{n})\right|\leq \sum _{i:x_{i}\neq x'_{i}}c_{i}.} 独立な確率変数を考えるX 1 、 X 2 、 … 、 X n {\displaystyle X_{1},X_{2},\dots ,X_{n}} X 私 ∈ X 私 {\displaystyle X_{i}\in {\mathcal {X}}_{i}} 私 {\displaystyle i} p = 1 − P （ （ X 1 、 … 、 X n ） ∈ Y ） {\displaystyle p=1-\mathrm {P} ((X_{1},\ldots ,X_{n})\in {\mathcal {Y}})} m = E [ f （ X 1 、 … 、 X n ） ∣ （ X 1 、 … 、 X n ） ∈ Y ] {\displaystyle m=\mathbb {E} [f(X_{1},\ldots ,X_{n})\mid (X_{1},\ldots ,X_{n})\in {\mathcal {Y}}]} ε > 0 {\displaystyle \varepsilon >0}
P （ f （ X 1 、 … 、 X n ） − m ≥ ε ） ≤ p + exp （ − 2 最大 （ 0 、 ε − p ∑ 私 = 1 n c 私 ） 2 ∑ 私 = 1 n c 私 2 ） 、 {\displaystyle {\text{P}}\left(f(X_{1},\ldots ,X_{n})-m\geq \varepsilon \right)\leq p+\exp \left(-{\frac {2\max \left(0,\varepsilon -p\sum _{i=1}^{n}c_{i}\right)^{2}}{\sum _{i=1}^{n}c_{i}^{2}}}\right),} そしてその直接的な結果として、
P （ | f （ X 1 、 … 、 X n ） − m | ≥ ε ） ≤ 2 p + 2 exp （ − 2 最大 （ 0 、 ε − p ∑ 私 = 1 n c 私 ） 2 ∑ 私 = 1 n c 私 2 ） 。 {\displaystyle {\text{P}}(|f(X_{1},\ldots ,X_{n})-m|\geq \varepsilon )\leq 2p+2\exp \left(-{\frac {2\max \left(0,\varepsilon -p\sum _{i=1}^{n}c_{i}\right)^{2}}{\sum _{i=1}^{n}c_{i}^{2}}}\right).} 分布に依存するシナリオの中には、学習理論 で生じるような、この分析に対するより高度な改良が存在する[ 6 ]
サブガウス分布およびサブ指数分布のノルム にk {\displaystyle k} th 中心化された条件付きバージョン f {\displaystyle f}
f k （ X ） （ x ） := f （ x 1 、 … 、 x k − 1 、 X k 、 x k + 1 、 … 、 x n ） − E X k ′ f （ x 1 、 … 、 x k − 1 、 X k ′ 、 x k + 1 、 … 、 x n ） 、 {\displaystyle f_{k}(X)(x):=f(x_{1},\ldots ,x_{k-1},X_{k},x_{k+1},\ldots ,x_{n})-\mathbb {E} _{X'_{k}}f(x_{1},\ldots ,x_{k-1},X'_{k},x_{k+1},\ldots ,x_{n}),} となることによってf k （ X ） {\displaystyle f_{k}(X)} x 1 、 … 、 x k − 1 、 x k + 1 、 … 、 x n {\displaystyle x_{1},\ldots ,x_{k-1},x_{k+1},\ldots ,x_{n}}
マクディアミッドの不等式をベネットの不等式 やバーンスタインの不等式 のような形で改良するには、各関数引数に対して分散項を定義する必要がある。
B := 最大 k ∈ [ n ] すする x 1 、 … 、 x k − 1 、 x k + 1 、 … 、 x n | f （ x 1 、 … 、 x k − 1 、 X k 、 x k + 1 、 … 、 x n ） − E X k f （ x 1 、 … 、 x k − 1 、 X k 、 x k + 1 、 … 、 x n ） | 、 V k := すする x 1 、 … 、 x k − 1 、 x k + 1 、 … 、 x n E X k （ f （ x 1 、 … 、 x k − 1 、 X k 、 x k + 1 、 … 、 x n ） − E X k f （ x 1 、 … 、 x k − 1 、 X k 、 x k + 1 、 … 、 x n ） ） 2 、 σ ～ 2 := ∑ k = 1 n V k 。 {\displaystyle {\begin{aligned}B&:=\max _{k\in [n]}\sup _{x_{1},\dots ,x_{k-1},x_{k+1},\dots ,x_{n}}\left|f(x_{1},\dots ,x_{k-1},X_{k},x_{k+1},\dots ,x_{n})-\mathbb {E} _{X_{k}}f(x_{1},\dots ,x_{k-1},X_{k},x_{k+1},\dots ,x_{n})\right|,\\V_{k}&:=\sup _{x_{1},\dots ,x_{k-1},x_{k+1},\dots ,x_{n}}\mathbb {E} _{X_{k}}\left(f(x_{1},\dots ,x_{k-1},X_{k},x_{k+1},\dots ,x_{n})-\mathbb {E} _{X_{k}}f(x_{1},\dots ,x_{k-1},X_{k},x_{k+1},\dots ,x_{n})\right)^{2},\\{\tilde {\sigma }}^{2}&:=\sum _{k=1}^{n}V_{k}.\end{aligned}}} マクディアミッドの不等式（ベネット形式）[ 4 ] — とするf : X n → R {\displaystyle f:{\mathcal {X}}^{n}\rightarrow \mathbb {R} } c 1 、 c 2 、 … 、 c n {\displaystyle c_{1},c_{2},\dots ,c_{n}} X 1 、 X 2 、 … 、 X n {\displaystyle X_{1},X_{2},\dots ,X_{n}} X 私 ∈ X 私 {\displaystyle X_{i}\in {\mathcal {X}}_{i}} 私 {\displaystyle i} B {\displaystyle B} σ ～ 2 {\displaystyle {\tilde {\sigma }}^{2}}
そして、どんなε > 0 {\displaystyle \varepsilon >0}
P （ f （ X 1 、 … 、 X n ） − E [ f （ X 1 、 … 、 X n ） ] ≥ ε ） ≤ exp （ − ε 2 B ログ （ 1 + B ε σ ～ 2 ） ） 。 {\displaystyle {\text{P}}(f(X_{1},\ldots ,X_{n})-\mathbb {E} [f(X_{1},\ldots ,X_{n})]\geq \varepsilon )\leq \exp \left(-{\frac {\varepsilon }{2B}}\log \left(1+{\frac {B\varepsilon }{{\tilde {\sigma }}^{2}}}\right)\right).}
証拠 マクディアミッドの不等式[ 2 ] 条件付き期待値 を追跡するドゥーブ・マルチンゲール を構築し、マルチンゲール集中不等式 (アズマの不等式 ) を適用します。マルチンゲールの使用を避ける別の議論も存在し、関数の引数の独立性を利用してチェルノフ境界の ような議論を提供します。[ 4 ]
読みやすさを向上させるため、表記法の簡略化を導入します。z 私 ⇁ j {\displaystyle z_{i\rightharpoondown j}} z 私 、 … 、 z j {\displaystyle z_{i},\dots ,z_{j}} z ∈ X n {\displaystyle z\in {\mathcal {X}}^{n}} 1 ≤ 私 ≤ j ≤ n {\displaystyle 1\leq i\leq j\leq n}
f （ X 1 ⇁ （ 私 − 1 ） 、 y 、 x （ 私 + 1 ） ⇁ n ） := f （ X 1 、 … 、 X 私 − 1 、 y 、 x 私 + 1 、 … 、 x n ） 。 {\displaystyle f(X_{1\rightharpoondown (i-1)},y,x_{(i+1)\rightharpoondown n}):=f(X_{1},\ldots ,X_{i-1},y,x_{i+1},\ldots ,x_{n}).} どれでも選んでくださいx 1 ′ 、 x 2 ′ 、 … 、 x n ′ {\displaystyle x_{1}',x_{2}',\ldots ,x_{n}'} x 1 、 x 2 、 … 、 x n {\displaystyle x_{1},x_{2},\ldots ,x_{n}} 三角不等式 により、
| f （ x 1 ⇁ n ） − f （ x 1 ⇁ n ′ ） | ≤ | f （ x 1 ⇁ n ） − f （ x 1 ⇁ （ n − 1 ） ′ 、 x n ） | + c n ≤ | f （ x 1 ⇁ n ） − f （ x 1 ⇁ （ n − 2 ） ′ 、 x （ n − 1 ） ⇁ n ） | + c n − 1 + c n ≤ … ≤ ∑ 私 = 1 n c 私 、 {\displaystyle {\begin{aligned}&|f(x_{1\rightharpoondown n})-f(x'_{1\rightharpoondown n})|\\[6pt]\leq {}&|f(x_{1\rightharpoondown \,n})-f(x'_{1\rightharpoondown (n-1)},x_{n})|+c_{n}\\\leq {}&|f(x_{1\rightharpoondown n})-f(x'_{1\rightharpoondown (n-2)},x_{(n-1)\rightharpoondown n})|+c_{n-1}+c_{n}\\\leq {}&\ldots \\\leq {}&\sum _{i=1}^{n}c_{i},\end{aligned}}} そしてこうしてf {\displaystyle f}
以来f {\displaystyle f} { Z 私 } {\displaystyle \{Z_{i}\}} Z 私 {\displaystyle Z_{i}} X 1 、 … 、 X 私 {\displaystyle X_{1},\ldots ,X_{i}}
Z 私 := E [ f （ X 1 ⇁ n ） ∣ X 1 ⇁ 私 ] {\displaystyle Z_{i}:=\mathbb {E} [f(X_{1\rightharpoondown n})\mid X_{1\rightharpoondown i}]} すべての人々のために私 ≥ 1 {\displaystyle i\geq 1} Z 0 := E [ f （ X 1 ⇁ n ） ] {\displaystyle Z_{0}:=\mathbb {E} [f(X_{1\rightharpoondown n})]} Z n = f （ X 1 ⇁ n ） {\displaystyle Z_{n}=f(X_{1\rightharpoondown n})}
次に、それぞれの確率変数を定義します。私 {\displaystyle i}
U 私 := すする x ∈ X 私 E [ f （ X 1 ⇁ （ 私 − 1 ） 、 x 、 X （ 私 + 1 ） ⇁ n ） ∣ X 1 ⇁ （ 私 − 1 ） 、 X 私 = x ] − [ f （ X 1 ⇁ （ 私 − 1 ） 、 X 私 ⇁ n ） ∣ X 1 ⇁ （ 私 − 1 ） ] 、 L 私 := 情報 x ∈ X 私 E [ f （ X 1 ⇁ （ 私 − 1 ） 、 x 、 X （ 私 + 1 ） ⇁ n ） ∣ X 1 ⇁ （ 私 − 1 ） 、 X 私 = x ] − [ f （ X 1 ⇁ （ 私 − 1 ） 、 X 私 ⇁ n ） ∣ X 1 ⇁ （ 私 − 1 ） ] 。 {\displaystyle {\begin{aligned}U_{i}&:=\sup _{x\in {\mathcal {X}}_{i}}\mathbb {E} [f(X_{1\rightharpoondown (i-1)},x,X_{(i+1)\rightharpoondown n})\mid X_{1\rightharpoondown (i-1)},X_{i}=x]-\mathbb {[} f(X_{1\rightharpoondown (i-1)},X_{i\rightharpoondown n})\mid X_{1\rightharpoondown (i-1)}],\\L_{i}&:=\inf _{x\in {\mathcal {X}}_{i}}\mathbb {E} [f(X_{1\rightharpoondown (i-1)},x,X_{(i+1)\rightharpoondown n})\mid X_{1\rightharpoondown (i-1)},X_{i}=x]-\mathbb {[} f(X_{1\rightharpoondown (i-1)},X_{i\rightharpoondown n})\mid X_{1\rightharpoondown (i-1)}].\\\end{aligned}}} 以来X 私 、 … 、 X n {\displaystyle X_{i},\ldots ,X_{n}} X 私 = x {\displaystyle X_{i}=x}
U 私 = すする x ∈ X 私 E [ f （ X 1 ⇁ （ 私 − 1 ） 、 x 、 X （ 私 + 1 ） ⇁ n ） − f （ X 1 ⇁ （ 私 − 1 ） 、 X 私 ⇁ n ） ∣ X 1 ⇁ （ 私 − 1 ） ] 、 L 私 = 情報 x ∈ X 私 E [ f （ X 1 ⇁ （ 私 − 1 ） 、 x 、 X （ 私 + 1 ） ⇁ n ） − f （ X 1 ⇁ （ 私 − 1 ） 、 X 私 ⇁ n ） ∣ X 1 ⇁ （ 私 − 1 ） ] 。 {\displaystyle {\begin{aligned}U_{i}&=\sup _{x\in {\mathcal {X}}_{i}}\mathbb {E} [f(X_{1\rightharpoondown (i-1)},x,X_{(i+1)\rightharpoondown n})-f(X_{1\rightharpoondown (i-1)},X_{i\rightharpoondown n})\mid X_{1\rightharpoondown (i-1)}],\\L_{i}&=\inf _{x\in {\mathcal {X}}_{i}}\mathbb {E} [f(X_{1\rightharpoondown (i-1)},x,X_{(i+1)\rightharpoondown n})-f(X_{1\rightharpoondown (i-1)},X_{i\rightharpoondown n})\mid X_{1\rightharpoondown (i-1)}].\\\end{aligned}}} ご了承くださいL 私 ≤ Z 私 − Z 私 − 1 ≤ U 私 {\displaystyle L_{i}\leq Z_{i}-Z_{i-1}\leq U_{i}}
U 私 − L 私 = すする u ∈ X 私 、 ℓ ∈ X 私 E [ f （ X 1 ⇁ （ 私 − 1 ） 、 u 、 X （ 私 + 1 ） ⇁ n ） ∣ X 1 ⇁ （ 私 − 1 ） ] − E [ f （ X 1 ⇁ （ 私 − 1 ） 、 ℓ 、 X （ 私 + 1 ） ⇁ n ） ∣ X 1 ⇁ （ 私 − 1 ） ] = すする u ∈ X 私 、 ℓ ∈ X 私 E [ f （ X 1 ⇁ （ 私 − 1 ） 、 u 、 X （ 私 + 1 ） ⇁ n ） − f （ X 1 ⇁ （ 私 − 1 ） 、 l 、 X （ 私 + 1 ） ⇁ n ） ∣ X 1 ⇁ （ 私 − 1 ） ] ≤ すする x u ∈ X 私 、 x l ∈ X 私 E [ c 私 ∣ X 1 ⇁ （ 私 − 1 ） ] ≤ c 私 {\displaystyle {\begin{aligned}U_{i}-L_{i}&=\sup _{u\in {\mathcal {X}}_{i},\ell \in {\mathcal {X}}_{i}}\mathbb {E} [f(X_{1\rightharpoondown (i-1)},u,X_{(i+1)\rightharpoondown n})\mid X_{1\rightharpoondown (i-1)}]-\mathbb {E} [f(X_{1\rightharpoondown (i-1)},\ell ,X_{(i+1)\rightharpoondown n})\mid X_{1\rightharpoondown (i-1)}]\\[6pt]&=\sup _{u\in {\mathcal {X}}_{i},\ell \in {\mathcal {X}}_{i}}\mathbb {E} [f(X_{1\rightharpoondown (i-1)},u,X_{(i+1)\rightharpoondown n})-f(X_{1\rightharpoondown (i-1)},l,X_{(i+1)\rightharpoondown n})\mid X_{1\rightharpoondown (i-1)}]\\&\leq \sup _{x_{u}\in {\mathcal {X}}_{i},x_{l}\in {\mathcal {X}}_{i}}\mathbb {E} [c_{i}\mid X_{1\rightharpoondown (i-1)}]\\[6pt]&\leq c_{i}\end{aligned}}} 次に、東の不等式の一般形 を{ Z 私 } {\displaystyle \left\{Z_{i}\right\}}
P （ f （ X 1 、 … 、 X n ） − E [ f （ X 1 、 … 、 X n ） ] ≥ ε ） = P （ Z n − Z 0 ≥ ε ） ≤ exp （ − 2 ε 2 ∑ 私 = 1 n c 私 2 ） 。 {\displaystyle {\text{P}}(f(X_{1},\ldots ,X_{n})-\mathbb {E} [f(X_{1},\ldots ,X_{n})]\geq \varepsilon )=\operatorname {P} (Z_{n}-Z_{0}\geq \varepsilon )\leq \exp \left(-{\frac {2\varepsilon ^{2}}{\sum _{i=1}^{n}c_{i}^{2}}}\right).} 反対方向の片側境界は、東の不等式を適用することによって得られる。{ − Z 私 } {\displaystyle \left\{-Z_{i}\right\}} 集合境界 から導かれる。◻ {\displaystyle \square }
参考文献 ↑ McDiarmid, Colin (1989). 「有界差分法について」. Surveys in Combinatorics, 1989: Invited Papers at the Twelfth British Combinatorial Conference : 148– 188. doi : 10.1017/CBO9781107359949.008 . ISBN 978-0-521-37823-9 。 1 2 Doob, JL (1940). "特定の確率変数族の正則性特性" (PDF) . Transactions of the American Mathematical Society . 47 (3): 455– 486. doi : 10.2307/1989964 . JSTOR 1989964 . ↑ Chou, Chi-Ning; Love, Peter J.; Sandhu, Juspreet Singh; Shi, Jonathan (2022). "Limitations of Local Quantum Algorithms on Random MAX-k-XOR and Beyond" . 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) . 229 . Schloss Dagstuhl – Leibniz-Zentrum für Informatik: 41:13. arXiv : 2108.06049 . doi : 10.4230/LIPIcs.ICALP.2022.41 . 2022年 7月8日 取得 . 1 2 3 4 Ying, Yiming (2004). "McDiarmidのBernstein形式とBennett形式の不等式" (PDF) . 香港城市大学. 2022年 7月10日 取得 . ↑ Combes, Richard (2015). "An extension of McDiarmid's inequality". arXiv : 1511.05240 [ cs.LG ]. ↑ Wu, Xinxing; Zhang, Junping (2018年4月) 「より厳密な一般化境界のための分布依存集中不等式」 . Science China Information Sciences . 61 (4): 048105:1–048105:3. arXiv : 1607.05506 . doi : 10.1007/s11432-017-9225-2 . S2CID 255199895 . 2022年 7月10日 取得 。 ↑ Kontorovich, Aryeh (2014年6月22日). 「非有界距離空間における集中とアルゴリズムの安定性」 . 第31回国際機械学習会議議事録 . 32 (2): 28– 36. arXiv : 1309.1007 . 2022年 7月10日 取得 . 1 2 Maurer, Andreas; Pontil, Pontil (2021). "Concentration inequalities under sub-Gaussian and sub-exponential conditions" (PDF) . Advances in Neural Information Processing Systems . 34 : 7588– 7597 . 2022年 7月10日 取得 . 
![{\displaystyle i\in [n]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1b389a8f1ad8a43d2bcf5194acf34e934f806311)
![{\displaystyle {\text{P}}\left(f(X_{1},X_{2},\ldots ,X_{n})-\mathbb {E} [f(X_{1},X_{2},\ldots ,X_{n})]\geq \varepsilon \right)\leq \exp \left(-{\frac {2\varepsilon ^{2}}{\sum _{i=1}^{n}c_{i}^{2}}}\right),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dcec32c891eaf7e6f8fb7c99d8749928ad1636e1)
![{\displaystyle {\text{P}}(f(X_{1},X_{2},\ldots ,X_{n})-\mathbb {E} [f(X_{1},X_{2},\ldots ,X_{n})]\leq -\varepsilon )\leq \exp \left(-{\frac {2\varepsilon ^{2}}{\sum _{i=1}^{n}c_{i}^{2}}}\right),}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7e8acf5ba6be8dd3cf27f282bc328b17bfd23a93)
![{\displaystyle {\text{P}}(|f(X_{1},X_{2},\ldots ,X_{n})-\mathbb {E} [f(X_{1},X_{2},\ldots ,X_{n})]|\geq \varepsilon )\leq 2\exp \left(-{\frac {2\varepsilon ^{2}}{\sum _{i=1}^{n}c_{i}^{2}}}\right).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a60a6951869cfdf72d6bf5c6f1f2f2b38abef530)
![{\displaystyle {\text{P}}(|f(X_{1},\ldots ,X_{n})-\mathbb {E} [f(X_{1},\ldots ,X_{n})]|\geq \varepsilon )\leq 2\exp \left({\frac {-\varepsilon ^{2}}{2p(2-p)\sum _{i=1}^{n}c_{i}^{2}+{\frac {2}{3}}\varepsilon \max _{i}c_{i}}}\right).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/855bb934c5e7f34c95fa713da1fd5e828ad36d07)
![{\displaystyle m=\mathbb {E} [f(X_{1},\ldots ,X_{n})\mid (X_{1},\ldots ,X_{n})\in {\mathcal {Y}}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c965758a80ff46edb71c1959ec2d13526340986b)
![{\displaystyle {\text{P}}\left(f(X_{1},\ldots ,X_{n})-m\geq \varepsilon \right)\leq \exp \left({\frac {-\varepsilon ^{2}}{32e\left\|\sum _{k\in [n]}\|f_{k}(X)\|_{\psi _{2}}^{2}\right\|_{\infty }}}\right).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/40a7e2c7fc75956f303ed25c04ee7b1bf107ca93)
![{\displaystyle {\text{P}}\left(f(X_{1},\ldots ,X_{n})-m\geq \varepsilon \right)\leq \exp \left({\frac {-\varepsilon ^{2}}{4e^{2}\left\|\sum _{k\in [n]}\|f_{k}(X)\|_{\psi _{1}}^{2}\right\|_{\infty }+2\varepsilon e\max _{k\in [n]}\left\|\|f_{k}(X)\|_{\psi _{1}}\right\|_{\infty }}}\right).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/70ee2d217ef648fe22a5cf860623582e53091c4c)
![{\displaystyle {\begin{aligned}B&:=\max _{k\in [n]}\sup _{x_{1},\dots ,x_{k-1},x_{k+1},\dots ,x_{n}}\left|f(x_{1},\dots ,x_{k-1},X_{k},x_{k+1},\dots ,x_{n})-\mathbb {E} _{X_{k}}f(x_{1},\dots ,x_{k-1},X_{k},x_{k+1},\dots ,x_{n})\right|,\\V_{k}&:=\sup _{x_{1},\dots ,x_{k-1},x_{k+1},\dots ,x_{n}}\mathbb {E} _{X_{k}}\left(f(x_{1},\dots ,x_{k-1},X_{k},x_{k+1},\dots ,x_{n})-\mathbb {E} _{X_{k}}f(x_{1},\dots ,x_{k-1},X_{k},x_{k+1},\dots ,x_{n})\right)^{2},\\{\tilde {\sigma }}^{2}&:=\sum _{k=1}^{n}V_{k}.\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/312deb5dc1b54e6b3c651089e825980a2443a6a6)
![{\displaystyle {\text{P}}(f(X_{1},\ldots ,X_{n})-\mathbb {E} [f(X_{1},\ldots ,X_{n})]\geq \varepsilon )\leq \exp \left(-{\frac {\varepsilon }{2B}}\log \left(1+{\frac {B\varepsilon }{{\tilde {\sigma }}^{2}}}\right)\right).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7704caf7a037657bf4a425383f9885ca8a7596e6)
![{\displaystyle {\text{P}}(f(X_{1},\ldots ,X_{n})-\mathbb {E} [f(X_{1},\ldots ,X_{n})]\geq \varepsilon )\leq \exp \left(-{\frac {\varepsilon ^{2}}{2\left({\tilde {\sigma }}^{2}+{\frac {B\varepsilon }{3}}\right)}}\right).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ea6a82ec74188846989046b43328b95a5eaa0a12)
![{\displaystyle {\begin{aligned}&|f(x_{1\rightharpoondown n})-f(x'_{1\rightharpoondown n})|\\[6pt]\leq {}&|f(x_{1\rightharpoondown \,n})-f(x'_{1\rightharpoondown (n-1)},x_{n})|+c_{n}\\\leq {}&|f(x_{1\rightharpoondown n})-f(x'_{1\rightharpoondown (n-2)},x_{(n-1)\rightharpoondown n})|+c_{n-1}+c_{n}\\\leq {}&\ldots \\\leq {}&\sum _{i=1}^{n}c_{i},\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e8a3d4618dccde1175f60e840012985638c2eb28)
![{\displaystyle Z_{i}:=\mathbb {E} [f(X_{1\rightharpoondown n})\mid X_{1\rightharpoondown i}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d282a3f3a353ad3afae9d483afcc6fbc0e62f27b)
![{\displaystyle Z_{0}:=\mathbb {E} [f(X_{1\rightharpoondown n})]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cef2ef327bad57acbfa735e645bd71bab6461f01)
![{\displaystyle {\begin{aligned}U_{i}&:=\sup _{x\in {\mathcal {X}}_{i}}\mathbb {E} [f(X_{1\rightharpoondown (i-1)},x,X_{(i+1)\rightharpoondown n})\mid X_{1\rightharpoondown (i-1)},X_{i}=x]-\mathbb {[} f(X_{1\rightharpoondown (i-1)},X_{i\rightharpoondown n})\mid X_{1\rightharpoondown (i-1)}],\\L_{i}&:=\inf _{x\in {\mathcal {X}}_{i}}\mathbb {E} [f(X_{1\rightharpoondown (i-1)},x,X_{(i+1)\rightharpoondown n})\mid X_{1\rightharpoondown (i-1)},X_{i}=x]-\mathbb {[} f(X_{1\rightharpoondown (i-1)},X_{i\rightharpoondown n})\mid X_{1\rightharpoondown (i-1)}].\\\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6308d303b73a83754d872be0edcc317e817bea53)
![{\displaystyle {\begin{aligned}U_{i}&=\sup _{x\in {\mathcal {X}}_{i}}\mathbb {E} [f(X_{1\rightharpoondown (i-1)},x,X_{(i+1)\rightharpoondown n})-f(X_{1\rightharpoondown (i-1)},X_{i\rightharpoondown n})\mid X_{1\rightharpoondown (i-1)}],\\L_{i}&=\inf _{x\in {\mathcal {X}}_{i}}\mathbb {E} [f(X_{1\rightharpoondown (i-1)},x,X_{(i+1)\rightharpoondown n})-f(X_{1\rightharpoondown (i-1)},X_{i\rightharpoondown n})\mid X_{1\rightharpoondown (i-1)}].\\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b12e9453887e3a63e513cc3eb6d88641987f6fe0)
![{\displaystyle {\begin{aligned}U_{i}-L_{i}&=\sup _{u\in {\mathcal {X}}_{i},\ell \in {\mathcal {X}}_{i}}\mathbb {E} [f(X_{1\rightharpoondown (i-1)},u,X_{(i+1)\rightharpoondown n})\mid X_{1\rightharpoondown (i-1)}]-\mathbb {E} [f(X_{1\rightharpoondown (i-1)},\ell ,X_{(i+1)\rightharpoondown n})\mid X_{1\rightharpoondown (i-1)}]\\[6pt]&=\sup _{u\in {\mathcal {X}}_{i},\ell \in {\mathcal {X}}_{i}}\mathbb {E} [f(X_{1\rightharpoondown (i-1)},u,X_{(i+1)\rightharpoondown n})-f(X_{1\rightharpoondown (i-1)},l,X_{(i+1)\rightharpoondown n})\mid X_{1\rightharpoondown (i-1)}]\\&\leq \sup _{x_{u}\in {\mathcal {X}}_{i},x_{l}\in {\mathcal {X}}_{i}}\mathbb {E} [c_{i}\mid X_{1\rightharpoondown (i-1)}]\\[6pt]&\leq c_{i}\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f4575c944d2aa6f26072f96a149dac22fa66cf81)
![{\displaystyle {\text{P}}(f(X_{1},\ldots ,X_{n})-\mathbb {E} [f(X_{1},\ldots ,X_{n})]\geq \varepsilon )=\operatorname {P} (Z_{n}-Z_{0}\geq \varepsilon )\leq \exp \left(-{\frac {2\varepsilon ^{2}}{\sum _{i=1}^{n}c_{i}^{2}}}\right).}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4a5a67a03307a7983380121343d55e057618ac43)
