Hypercontractive不等式

ステートメント

関数$f\colon{-1,1}^n \to \mathbb{R}$と実数$\rho \in [-1,1]$に対し，
$$
T_\rho f(x)=\mathbb{E}{y∼N\rho(x)}[f(y)]
$$
と定義する．
ここで$y∼N_\rho(x)$とは，各$i \in {1,\ldots,n}$について独立に
$$
y_i = \begin{cases}
x_i & \text{確率 } \frac{1+\rho}{2}\
-x_i & \text{確率 } \frac{1-\rho}{2} \
\end{cases}
$$
と選ぶことを指す．

このとき関数$f: {-1,1}^n \to \mathbb{R}$と，$0 \leq \rho \leq \sqrt{\frac{p-1}{q-1}}$なる実数$1 \leq p \leq q \leq \infty$に対して，
$$
|T_\rho f|_q \leq |f|_p
$$
が成り立つ．

出典

R. O'Donnell. Analysis of Boolean Functions (2014).

ステートメント

$X$をパラメータ$v$のポアソン分布とする，$Y=X-v$の生成母関数の対数$\psi_{Y}(\lambda) := \mathbb{E} e^{\lambda (Y)}$は

$$
\psi_{Y} (\lambda) = v\phi(\lambda),
$$
ここで，$\phi(u) := e^u-u-1$である．さらに，$\psi_Y$のCramer変換，$\psi_Y^{\ast}(t) := \sup_{\lambda>0} e^{\psi_Y (\lambda) -\lambda t}$ は

$$
\psi_Y^{\ast}(t) = vh\left(\frac{t}{v}\right)
$$
である，ここで$h(u) := (1+u)\log (1+u) - u (u>0)$である．

コメント

• Bennetの不等式（#5）の証明にこの事実を使える

出典

Boucheron et al. Concentration inequalities: A Nonasymptotic Theory of Independence (2013)

概要

$X$を確率変数とする，任意の$t>0$に対して
$$
\mathbb{P} \{|X - \mathbb{E}| \geq t\} \leq \frac{\mathrm{Var}(X)}{t^2}
$$
が成り立つ．

証明の概要

Markovの不等式（#1）から証明可能

出典

Boucheron et al. Concentration inequalities: A Nonasymptotic Theory of Independence (2013)

確率分布間距離の比較についてのエントリが複数あるため (Le Camの不等式，Pinskerの不等式)，距離尺度の定義の一覧と，それらの強弱関係をまとめたページがあると良いかもと思いました．

距離尺度の例

• Total variation distance
• Hellinger distance
• Wasserstein distance
• Kullback--Leibler divergence
• chi^2-divergence
• Renyi divergence
• Levy metric, Prokhorov metric
• Ky Fan metric

強弱関係の例

• Le Camの不等式
• Pinskerの不等式
• Wasserstein距離とKLの比較
• Weighted Pinsker (Villani 2009, Theorem 22.10)
• どの位相の距離付けになっているか

Gibbs and Su (2002) Figure 1が有益

参考文献

• Tsybakov. Introduction to Nonparametric Estimation. (2009) Section 2.4.1
• Villani. Optimal Transport: Old and New. (2009)
• Gibbs and Su. On choosing and bounding probability metrics. (2002)
• A summary on “On choosing and bounding probability metrics” AIP松井さんのスライド

ステートメント

$X$を確率変数とする，任意の$t>0$と$\lambda \in \mathbb{R}$に対して
$$
\mathbb{P}\{ |X - \mathbb{E}X| \geq t\} \leq e^{\psi_{X}(\lambda)-\lambda t}.
$$
ここで，$\psi_{X}$は$X$の生成母関数の対数，$\psi_{X}(\lambda):=\log \mathbb{E}\left[e^{\lambda X} \right]$．

証明の概要

Markovの不等式（#1）から証明できる

コメント

この不等式により，期待値周りの確率集中は生成母関数の対数$\psi_X$を評価することに帰着される

出典

Boucheron et al. Concentration inequalities: A Nonasymptotic Theory of Independence (2013)

ステートメント

$X_1, \ldots, X_N$を独立な確率変数であり，$\mathbb{E}X_i^2 < \infty$かつ，ある$b > 0$が存在して$X_i < b$ a.s. であると仮定する．$S := \sum_{i=1}^{N} X_i$とすると，任意の$\lambda > 0$に対して，

$$ \psi_S(\lambda) \leq \frac{v}{b^2} \phi (b\lambda) $$

が成立する．ここで，$\psi_S$は確率変数の生成母関数の対数，すなわち$\psi_S(\lambda) := \mathrm{\log} \mathbb{E}\left[ e^{\lambda S} \right]$，$v := \sum_{i=1}^N \mathbb{E}[X_i^2]$，$\phi(u)$は$Z$をパラメータ$1$のポアソン分布とした時，$Z-1$の生成母関数の対数，すなわち$\phi(u) := e^u-u-1$である．

さらに，任意の$t>0$に対して，

$$ \mathbb{P}\left(S \geq t\right) \leq \exp\left( -\frac{v}{b} h\left( \frac{bt}{v}\right) \right) $$

が成立する．ここで，$h(u) := (1+u)\log (1+u) - u (u>0)$である．

コメント

• Hoeffdingの不等式（#4）を使うには，確率変数$X_i$達の値域が両側が抑えられている必要があるが，Bennettの不等式は片側だけ抑えられていれば使える．そのかわり各確率変数の分散が有限でないといけない．
• 2つ目の不等式は1つ目の不等式とChernoff bound（#3）から導かれる．

出典

Boucheron et al. Concentration inequalities: A Nonasymptotic Theory of Independence (2013)

ステートメント

$X_1, \ldots, X_N$が独立な確率変数であり，$X_i$はalmost sureで実数軸上の区間$[a_i, b_i] (a_i \leq b_i)$ に値を取ると仮定する．$S = \sum_{i=1}^{N} X_i$とすると，任意の$t\geq 0$に対し，

$$ \mathbb{P} \{ S - \mathbb{E}S \geq t \} \leq \exp\left( - \frac{2 t^2}{\sum_{i=1}^N(b_i - a_i)^2} \right) $$

コメント

この定理と「sub Gaussian性の必要十分条件」から，有界で独立な確率変数達の和はsub Gaussianであることがわかる．

出典

Boucheron et al. Concentration inequalities: A Nonasymptotic Theory of Independence (2013)

ステートメント

$X$を非負の確率変数とする，任意の$t> 0$に対して

$$
\mathbb{P} (X \geq t) \leq \frac{\mathbb{E}\left[X\right]}{t}
$$
が成り立つ．

証明の概要

任意の$t\geq 0$に対して，

$$
X \geq t\mathbb{1}_{\{X\geq t\}}
$$
が成り立つので，期待値を取って，

$$ \mathbb{E}\left[X\right] \geq \mathbb{E}\left[t\mathbb{1}_{\{X\geq t\}} \right] = t \mathbb{P} (X\geq t). $$

両辺を$t$で割れば不等式が得られる．

コメント

• 集中不等式と呼ばれる類の一連の不等式の出発点となる．
• Markovの不等式からChebyshevの不等式やExponential版のChebyshevの不等式が示せる．
• 文献によっては，Chebyshevの不等式のことをMarkovの不等式と呼ぶこともある．

出典

Boucheron et al. Concentration inequalities: A Nonasymptotic Theory of Independence (2013)

@book{boucheron2013concentration,
  title={Concentration inequalities: A nonasymptotic theory of independence},
  author={Boucheron, St{\'e}phane and Lugosi, G{\'a}bor and Massart, Pascal},
  year={2013},
  publisher={Oxford university press}
}

ステートメント

$X_1, \ldots, X_N$を独立な確率変数であり，$\mathbb{E}X_i^2 < \infty$かつ，ある$b > 0$が存在して$X_i < b$ a.s. であると仮定する．$S = \sum_{i=1}^{N} X_i$とすると，任意の$t>0$に対して，

$$ \mathbb{P}\left(S \geq t\right) \leq \exp\left( -\frac{t^2}{2(v + \frac{bt}{3})} \right) $$

が成立する．ここで，$h(u) = (1+u)\log (1+u) - u (u>0)$である．

証明の概要

Bennettの不等式（#5）と不等式
$$
h(u) \geq \frac{u^2}{2(1 + \frac{u}{3})}
$$
から導かれる．

出典

Boucheron et al. Concentration inequalities: A Nonasymptotic Theory of Independence (2013)