Неравенство Мак-Диармида
Концепция вероятности и информатики

В теории вероятностей и теоретической информатике неравенство Мак-Диармида (названное в честь Колина Мак-Диармида [1] ) представляет собой неравенство концентрации , которое ограничивает отклонение между выборочным значением и ожидаемым значением определенных функций, когда они оцениваются на независимых случайных величинах . Неравенство Мак-Диармида применяется к функциям, которые удовлетворяют свойству ограниченной разности , что означает, что замена одного аргумента функции, оставляя все остальные аргументы неизменными, не может вызвать слишком большого изменения значения функции.

Заявление

Функция удовлетворяет свойству ограниченных разностей , если подстановка значения th-й координаты изменяет значение не более чем на . Более формально, если существуют константы такие, что для всех , и всех , ф : Х 1 × Х 2 × ⋯ × Х н → Р {\displaystyle f:{\mathcal {X}}_{1}\times {\mathcal {X}}_{2}\times \cdots \times {\mathcal {X}}_{n}\rightarrow \mathbb {R} } я {\displaystyle я} х я {\displaystyle x_{i}} ф {\displaystyle f} с я {\displaystyle c_{i}} с 1 , с 2 , … , с н {\displaystyle c_{1},c_{2},\точки ,c_{n}} я ∈ [ н ] {\displaystyle я\в [н]} х 1 ∈ Х 1 , х 2 ∈ Х 2 , … , х н ∈ Х н {\displaystyle x_{1}\in {\mathcal {X}}_{1},\,x_{2}\in {\mathcal {X}}_{2},\,\ldots ,\,x_{n}\in {\mathcal {X}}_{n}}

Как дела х я ′ ∈ Х я | ф ( х 1 , … , х я − 1 , х я , х я + 1 , … , х н ) − ф ( х 1 , … , х я − 1 , х я ′ , х я + 1 , … , х н ) | ≤ с я . {\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]  —  Пусть удовлетворяет свойству ограниченных разностей с границами . ф : Х 1 × Х 2 × ⋯ × Х н → Р {\displaystyle f:{\mathcal {X}}_{1}\times {\mathcal {X}}_{2}\times \cdots \times {\mathcal {X}}_{n}\rightarrow \mathbb {R} } с 1 , с 2 , … , с н {\displaystyle c_{1},c_{2},\точки ,c_{n}}

Рассмотрим независимые случайные величины, где для всех . Тогда для любого , Х 1 , Х 2 , … , Х н {\displaystyle X_{1},X_{2},\точки ,X_{n}} Х я ∈ Х я {\displaystyle X_{i}\in {\mathcal {X}}_{i}} я {\displaystyle я} ε > 0 {\displaystyle \varepsilon >0}

П ( ф ( Х 1 , Х 2 , … , Х н ) − Э [ ф ( Х 1 , Х 2 , … , Х н ) ] ≥ ε ) ≤ эксп ⁡ ( − 2 ε 2 ∑ я = 1 н с я 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),}
П ( ф ( Х 1 , Х 2 , … , Х н ) − Э [ ф ( Х 1 , Х 2 , … , Х н ) ] ≤ − ε ) ≤ эксп ⁡ ( − 2 ε 2 ∑ я = 1 н с я 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 ∑ i = 1 n c i 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 ) ∑ i = 1 n c i 2 + 2 3 ε max i c i ) . {\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 ′ ) | ≤ ∑ i : x i ≠ x i ′ c i . {\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 i ∈ X i {\displaystyle X_{i}\in {\mathcal {X}}_{i}} 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 max ( 0 , ε − p ∑ i = 1 n c i ) 2 ∑ i = 1 n c i 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 max ( 0 , ε − p ∑ i = 1 n c i ) 2 ∑ i = 1 n c i 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} 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}}

Неравенство Мак-Диармида (субгауссовская норма) [7] [8]  —  Пусть будет функцией. Рассмотрим независимые случайные величины , где для всех . 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} } X = ( X 1 , X 2 , … , X n ) {\displaystyle X=(X_{1},X_{2},\dots ,X_{n})} X i ∈ X i {\displaystyle X_{i}\in {\mathcal {X}}_{i}} i {\displaystyle i}

Пусть относится к й центрированной условной версии . Пусть обозначает субгауссовскую норму случайной величины. f k ( X ) {\displaystyle f_{k}(X)} k {\displaystyle k} f {\displaystyle f} ‖ ⋅ ‖ ψ 2 {\displaystyle \|\cdot \|_{\psi _{2}}}

Тогда для любого , ε > 0 {\displaystyle \varepsilon >0}

P ( f ( X 1 , … , X n ) − m ≥ ε ) ≤ exp ⁡ ( − ε 2 32 e ‖ ∑ k ∈ [ n ] ‖ f k ( X ) ‖ ψ 2 2 ‖ ∞ ) . {\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).}

Неравенство Мак-Диармида (субэкспоненциальная норма) [8]  —  Пусть — функция. Рассмотрим независимые случайные величины , где для всех . 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} } X = ( X 1 , X 2 , … , X n ) {\displaystyle X=(X_{1},X_{2},\dots ,X_{n})} X i ∈ X i {\displaystyle X_{i}\in {\mathcal {X}}_{i}} i {\displaystyle i}

Пусть относится к й центрированной условной версии . Пусть обозначает субэкспоненциальную норму случайной величины. f k ( X ) {\displaystyle f_{k}(X)} k {\displaystyle k} f {\displaystyle f} ‖ ⋅ ‖ ψ 1 {\displaystyle \|\cdot \|_{\psi _{1}}}

Тогда для любого , ε > 0 {\displaystyle \varepsilon >0}

P ( f ( X 1 , … , X n ) − m ≥ ε ) ≤ exp ⁡ ( − ε 2 4 e 2 ‖ ∑ k ∈ [ n ] ‖ f k ( X ) ‖ ψ 1 2 ‖ ∞ + 2 ε e max k ∈ [ n ] ‖ ‖ f k ( X ) ‖ ψ 1 ‖ ∞ ) . {\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).}

Формы Беннета и Бернстайна

Уточнения неравенства Мак-Диармида в стиле неравенства Беннета и неравенства Бернштейна стали возможны благодаря определению члена дисперсии для каждого аргумента функции. Пусть

B := max k ∈ [ n ] sup 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 := sup 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 i ∈ X i {\displaystyle X_{i}\in {\mathcal {X}}_{i}} 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 log ⁡ ( 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).}

Неравенство Мак-Диармида (форма Бернштейна) [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}} 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 2 ( σ ~ 2 + B ε 3 ) ) . {\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).}

Доказательство

Следующее доказательство неравенства Мак-Диармида [2] строит мартингал Дуба, отслеживающий условное ожидаемое значение функции по мере того, как все больше и больше ее аргументов отбираются и обуславливаются, а затем применяет неравенство концентрации мартингала ( неравенство Азумы ). Существует также альтернативный аргумент, избегающий использования мартингалов, использующий преимущество независимости аргументов функции для предоставления аргумента, подобного границе Чернова . [4]

Для лучшей читаемости введем сокращенную запись: будем обозначать для любых и целых чисел , так что, например, z i ⇁ j {\displaystyle z_{i\rightharpoondown j}} z i , … , z j {\displaystyle z_{i},\dots ,z_{j}} z ∈ X n {\displaystyle z\in {\mathcal {X}}^{n}} 1 ≤ i ≤ j ≤ n {\displaystyle 1\leq i\leq j\leq n}

f ( X 1 ⇁ ( i − 1 ) , y , x ( i + 1 ) ⇁ n ) := f ( X 1 , … , X i − 1 , y , x i + 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 ≤ … ≤ ∑ i = 1 n c i , {\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 i } {\displaystyle \{Z_{i}\}} Z i {\displaystyle Z_{i}} X 1 , … , X i {\displaystyle X_{1},\ldots ,X_{i}}

Z i := E [ f ( X 1 ⇁ n ) ∣ X 1 ⇁ i ] {\displaystyle Z_{i}:=\mathbb {E} [f(X_{1\rightharpoondown n})\mid X_{1\rightharpoondown i}]}

для всех и , так что . 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})}

Теперь определим случайные величины для каждого i {\displaystyle i}

U i := sup x ∈ X i E [ f ( X 1 ⇁ ( i − 1 ) , x , X ( i + 1 ) ⇁ n ) ∣ X 1 ⇁ ( i − 1 ) , X i = x ] − [ f ( X 1 ⇁ ( i − 1 ) , X i ⇁ n ) ∣ X 1 ⇁ ( i − 1 ) ] , L i := inf x ∈ X i E [ f ( X 1 ⇁ ( i − 1 ) , x , X ( i + 1 ) ⇁ n ) ∣ X 1 ⇁ ( i − 1 ) , X i = x ] − [ f ( X 1 ⇁ ( i − 1 ) , X i ⇁ n ) ∣ X 1 ⇁ ( i − 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 i , … , X n {\displaystyle X_{i},\ldots ,X_{n}} X i = x {\displaystyle X_{i}=x}

U i = sup x ∈ X i E [ f ( X 1 ⇁ ( i − 1 ) , x , X ( i + 1 ) ⇁ n ) − f ( X 1 ⇁ ( i − 1 ) , X i ⇁ n ) ∣ X 1 ⇁ ( i − 1 ) ] , L i = inf x ∈ X i E [ f ( X 1 ⇁ ( i − 1 ) , x , X ( i + 1 ) ⇁ n ) − f ( X 1 ⇁ ( i − 1 ) , X i ⇁ n ) ∣ X 1 ⇁ ( i − 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 i ≤ Z i − Z i − 1 ≤ U i {\displaystyle L_{i}\leq Z_{i}-Z_{i-1}\leq U_{i}}

U i − L i = sup u ∈ X i , ℓ ∈ X i E [ f ( X 1 ⇁ ( i − 1 ) , u , X ( i + 1 ) ⇁ n ) ∣ X 1 ⇁ ( i − 1 ) ] − E [ f ( X 1 ⇁ ( i − 1 ) , ℓ , X ( i + 1 ) ⇁ n ) ∣ X 1 ⇁ ( i − 1 ) ] = sup u ∈ X i , ℓ ∈ X i E [ f ( X 1 ⇁ ( i − 1 ) , u , X ( i + 1 ) ⇁ n ) − f ( X 1 ⇁ ( i − 1 ) , l , X ( i + 1 ) ⇁ n ) ∣ X 1 ⇁ ( i − 1 ) ] ≤ sup x u ∈ X i , x l ∈ X i E [ c i ∣ X 1 ⇁ ( i − 1 ) ] ≤ c i {\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 i } {\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 ∑ i = 1 n c i 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 i } {\displaystyle \left\{-Z_{i}\right\}} ◻ {\displaystyle \square }

Смотрите также

Ссылки

  1. ^ McDiarmid, Colin (1989). «О методе ограниченных разностей». Surveys in Combinatorics, 1989: Invited Papers at the Twelfth British Combinatorics Conference : 148–188. doi :10.1017/CBO9781107359949.008. ISBN 978-0-521-37823-9.
  2. ^ ab Doob, JL (1940). "Свойства регулярности некоторых семейств случайных величин" (PDF) . Transactions of the American Mathematical Society . 47 (3): 455–486. doi : 10.2307/1989964 . JSTOR  1989964.
  3. ^ Chou, Chi-Ning; Love, Peter J.; Sandhu, Juspreet Singh; Shi, Jonathan (2022). «Ограничения локальных квантовых алгоритмов на Random Max-k-XOR и далее». 49-й Международный коллоквиум по автоматам, языкам и программированию (ICALP 2022) . 229 : 41:13. arXiv : 2108.06049 . doi : 10.4230/LIPIcs.ICALP.2022.41 . Получено 8 июля 2022 г.
  4. ^ abcd Ying, Yiming (2004). "Неравенства Мак-Диармида форм Бернштейна и Беннета" (PDF) . Городской университет Гонконга . Получено 10 июля 2022 г. .
  5. ^ Комбс, Ричард (2015). «Расширение неравенства Мак-Диармида». arXiv : 1511.05240 [cs.LG].
  6. ^ Wu, Xinxing; Zhang, Junping (апрель 2018 г.). «Неравенства концентрации, зависящие от распределения, для более узких границ обобщения». Science China Information Sciences . 61 (4): 048105:1–048105:3. arXiv : 1607.05506 . doi :10.1007/s11432-017-9225-2. S2CID  255199895 . Получено 10 июля 2022 г. .
  7. ^ Конторович, Арье (22 июня 2014 г.). «Концентрация в неограниченных метрических пространствах и алгоритмическая устойчивость». Труды 31-й Международной конференции по машинному обучению . 32 (2): 28–36. arXiv : 1309.1007 . Получено 10 июля 2022 г. .
  8. ^ ab Maurer, Andreas; Pontil, Pontil (2021). «Неравенства концентрации при субгауссовых и субэкспоненциальных условиях» (PDF) . Advances in Neural Information Processing Systems . 34 : 7588–7597 . Получено 10 июля 2022 г. .
Retrieved from "https://en.wikipedia.org/w/index.php?title=McDiarmid%27s_inequality&oldid=1237349424"