Неравенство Мак-Диармида

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

Заявление

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

$\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}.$

Неравенство МакДиармида - Позволять $f:{\mathcal {X}}_{1}\times {\mathcal {X}}_{2}\times \cdots \times {\mathcal {X}}_{n}\rightarrow \mathbb {R}$ удовлетворять свойству ограниченных различий с границами $c_{1},c_{2},\dots ,c_{n}$.

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

${\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),$

${\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),$

и как непосредственное следствие,

${\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).$

Расширения

Несбалансированные распределения

Более строгая граница может быть установлена, когда аргументы функции выбираются из несбалансированных распределений, так что повторная выборка одного аргумента редко приводит к значительному изменению значения функции.

Неравенство Макдермида (несбалансированное) - Позволять $f:{\mathcal {X}}^{n}\rightarrow \mathbb {R}$ удовлетворять свойству ограниченных различий с границами $c_{1},c_{2},\dots ,c_{n}$.

Рассмотрим независимые случайные величины $X_{1},X_{2},\ldots ,X_{n}\in {\mathcal {X}}$ взято из распределения, где есть определенное значение $\chi _{0}\in {\mathcal {X}}$ что происходит с вероятностью $1-p$. Тогда для любого $\varepsilon >0$,

${\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).$

Это можно использовать, например, для характеристики значения функции на графах при ее оценке на разреженных случайных графах и гиперграфах , поскольку в разреженном случайном графе вероятность отсутствия какого-либо конкретного ребра гораздо выше, чем его присутствия.

Различия ограничены с высокой вероятностью

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

Неравенство МакДиармида (различия ограничены с высокой вероятностью) - Позволять $f:{\mathcal {X}}_{1}\times {\mathcal {X}}_{2}\times \cdots \times {\mathcal {X}}_{n}\rightarrow \mathbb {R}$ быть функцией и ${\mathcal {Y}}\subseteq {\mathcal {X}}_{1}\times {\mathcal {X}}_{2}\times \cdots \times {\mathcal {X}}_{n}$ быть подмножеством своей области определения и пусть $c_{1},c_{2},\dots ,c_{n}\geq 0$ быть такими константами, что для всех пар $(x_{1},\ldots ,x_{n})\in {\mathcal {Y}}$ и $(x'_{1},\ldots ,x'_{n})\in {\mathcal {Y}}$,

$\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},\dots ,X_{n}$ где $X_{i}\in {\mathcal {X}}_{i}$ для всех $i$. Позволять $p=1-\mathrm {P} ((X_{1},\ldots ,X_{n})\in {\mathcal {Y}})$ и пусть $m=\mathbb {E} [f(X_{1},\ldots ,X_{n})\mid (X_{1},\ldots ,X_{n})\in {\mathcal {Y}}]$. Тогда для любого $\varepsilon >0$,

${\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),$

и как непосредственное следствие,

${\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).$

В некоторых сценариях, зависящих от распределения, существуют более строгие уточнения этого анализа. такие как те, которые возникают в теории обучения .

Субгауссовы и субэкспоненциальные нормы

Пусть $k$центрированная условная версия функции $f$ быть

$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)$ – случайная величина, зависящая от случайных значений $x_{1},\ldots ,x_{k-1},x_{k+1},\ldots ,x_{n}$.

Неравенство МакДиармида (субгауссова норма) - Позволять $f:{\mathcal {X}}_{1}\times {\mathcal {X}}_{2}\times \cdots \times {\mathcal {X}}_{n}\rightarrow \mathbb {R}$ быть функцией. Рассмотрим независимые случайные величины $X=(X_{1},X_{2},\dots ,X_{n})$ где $X_{i}\in {\mathcal {X}}_{i}$ для всех $i$.

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

Тогда для любого $\varepsilon >0$,

${\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).$

Неравенство МакДиармида (субэкспоненциальная норма) - Позволять $f:{\mathcal {X}}_{1}\times {\mathcal {X}}_{2}\times \cdots \times {\mathcal {X}}_{n}\rightarrow \mathbb {R}$ быть функцией. Рассмотрим независимые случайные величины $X=(X_{1},X_{2},\dots ,X_{n})$ где $X_{i}\in {\mathcal {X}}_{i}$ для всех $i$.

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

Тогда для любого $\varepsilon >0$,

${\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).$

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

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

${\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}}$

Неравенство Мак-Диармида (форма Беннета) - Позволять $f:{\mathcal {X}}^{n}\rightarrow \mathbb {R}$ удовлетворять свойству ограниченных различий с границами $c_{1},c_{2},\dots ,c_{n}$. Рассмотрим независимые случайные величины $X_{1},X_{2},\dots ,X_{n}$ где $X_{i}\in {\mathcal {X}}_{i}$ для всех $i$. Позволять $B$ и ${\tilde {\sigma }}^{2}$ быть определены, как в начале этого раздела.

Тогда для любого $\varepsilon >0$,

${\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).$

Неравенство Мак-Диармида (форма Бернштейна) - Позволять $f:{\mathcal {X}}^{n}\rightarrow \mathbb {R}$ удовлетворять свойству ограниченных различий с границами $c_{1},c_{2},\dots ,c_{n}$. Позволять $B$ и ${\tilde {\sigma }}^{2}$ быть определены, как в начале этого раздела.

Тогда для любого $\varepsilon >0$,

${\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).$

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

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

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

$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}',\ldots ,x_{n}'$. Тогда для любого $x_{1},x_{2},\ldots ,x_{n}$, по неравенству треугольника ,

${\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$ ограничен.

С $f$ ограничен, определим мартингал Дуба $\{Z_{i}\}$ (каждый $Z_{i}$ является случайной величиной, зависящей от случайных значений $X_{1},\ldots ,X_{i}$) как

$Z_{i}:=\mathbb {E} [f(X_{1\rightharpoondown n})\mid X_{1\rightharpoondown i}]$

для всех $i\geq 1$ и $Z_{0}:=\mathbb {E} [f(X_{1\rightharpoondown n})]$, так что $Z_{n}=f(X_{1\rightharpoondown n})$.

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

${\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},\ldots ,X_{n}$ независимы друг от друга, обусловлены $X_{i}=x$ не влияет на вероятности других переменных, поэтому они равны выражениям

${\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}\leq Z_{i}-Z_{i-1}\leq U_{i}$. Кроме того,

${\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}}$

Затем, применяя общую форму неравенства Азумы к $\left\{Z_{i}\right\}$, у нас есть

${\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).$

Односторонняя оценка в другом направлении получается применением неравенства Азумы к $\left\{-Z_{i}\right\}$ и двусторонняя оценка следует из оценки объединения . $\square$

См. также

• Каталог статей по теории вероятностей
• Неравенство концентрации
• Ожидаемое значение и дисперсия
• Глоссарий вероятности и статистики
• Список вероятностных тем
• Обозначение вероятности