凸解析のツールの一つとして凸共役という概念があります. $I\subseteq \mathbb{R}$上で定義された実関数$f$の凸共役とは
\[
f^*(a) = \sup_{x\in I}\{ax - f(x)\}
\]
で定義されます. 通常は$I=\mathbb{R}$や$I=(0,\infty)$を考えます. ここでは凸解析の理論には踏み込まず, この概念が確率集中不等式の文脈でどのように登場するかを説明します.
確率集中不等式とは, 実確率変数$X$がある点 (通常は期待値$\mathbb{E} X$) から離れる確率がどれくらい小さくなるかを評価する不等式です. (本記事では基本的に確率変数は全て期待値や分散が存在するものを考えます). 次の不等式を使います:
本記事の目標は$\Pr[X \ge \mathbb{E} X + a]$を上から抑えることです. 簡単な式変形により, 任意の$\lambda>0$に対し
\begin{align*}
\Pr[X \ge \mathbb{E} X + a] &= \Pr\left[ \mathrm{e}^{\lambda (X - \mathbb{E} X)} \ge \mathrm{e}^{\lambda a}\right] \\
&\le \mathrm{e}^{-\lambda a} \cdot \mathbb{E} \mathrm{e}^{\lambda ( X - \mathbb{E} X) }
\end{align*}
を得ます (一つ目の不等式では$\lambda>0$を利用し, 二つ目の不等式でマルコフの不等式を用いた). ここで, $\lambda>0$に対し$\psi_X(\lambda):=\log\mathbb{E}\mathrm{e}^{\lambda (X - \mathbb{E} X)}$とおくと,
\begin{align*}
\log \Pr[X \ge \mathbb{E} X + a ] \le - (\lambda a - \psi_X(\lambda)).
\end{align*}
この不等号は任意の$\lambda > 0$で成り立つので, 最適な$\lambda>0$を選ぶと
\begin{align*}
\log \Pr[X \ge \mathbb{E} X + a ] \le - \sup_{\lambda > 0}\{\lambda a - \psi_X(\lambda)\}
\end{align*}
となり, 右辺はまさに凸共役 $\psi_X^*(a)$になっています. 従って以下を得ます:
以上より, 凸共役$\psi_X^*(a)$の下界が得られればそこから集中不等式を導出できます. なお, $\lambda \le 0$に対しても$\psi_X(\lambda)$を定義することは可能でそこからlower tailを得ることができます. また, $\psi_X$は凸関数であることが知られており (ヘルダーの不等式を用いると示せる), 凸共役の性質より凸共役を2回とると元に戻ります.
独立な確率変数$X_1,\dots,X_n$に対して$X=X_1+\dots+X_n$と表せたとします. このとき
\[
\mathbb{E}\mathrm{e}^{\lambda X} = \prod_{i=1}^n \mathbb{E}\mathrm{e}^{\lambda X_i}
\]
となることから$\psi_X(\lambda) = \sum_{i=1}^n \psi_{X_i}(\lambda)$を得ます.
例1. 劣ガウシアン性を持つ確率変数
パラメータ$v>0$に対し, $X$が$v$-sub-gaussianであるとは, 任意の$\lambda\in \mathbb{R}$に対して$\psi_X(\lambda) \le \frac{v\lambda^2}{2}$であることをいう.
簡単に言うと劣ガウシアン性は$\psi_X(\lambda) = O(\lambda^2)$となるような確率変数のクラスです. ちなみに$\psi_X(\lambda) = \log\frac{1}{1-\lambda/a}$の形になっているという性質を劣指数性と呼びます.
さて, 簡単な平方完成から
\begin{align*}
\psi_X^*(a) &= \sup_{\lambda > 0}\{a\lambda - \psi_X(\lambda)\} \\
&\ge \sup_{\lambda > 0}\left\{ a \lambda - \frac{v\lambda^2}{2} \right\} \\
&\ge \frac{a^2}{2v}
\end{align*}
を得ます (最後の等号では$\lambda = \frac{a}{v}$を代入).
例2. ポアソン分布
平均$v$のポアソン分布に従う確率変数$X\sim\mathrm{Po}(v)$を考えます. すなわち, 任意の非負整数$k$に対し
\begin{align*}
\Pr[ X = k ] = \mathrm{e}^{- v} \frac{v^k}{k!}
\end{align*}
です. このとき, $\psi_X(\lambda) = v(\mathrm{e}^{\lambda} - \lambda - 1)$であり, $\lambda = \log\left( 1+\frac{a}{v} \right)$を代入すると次の凸共役を得ます:
\begin{align*}
\psi_X^*(a) = v h\left(\frac{a}{v}\right).
\end{align*}
ただし$h(x) = (1+x)\log(1+x) - x$.
上記のバウンドはBennetの不等式でよく見る形の関数になっています. 有名な不等式として
\[
h(x) \ge \frac{x^2}{1+x/3}
\]
というものがあります (この形で表現される集中不等式としてBernsteinの不等式と呼ばれる非常に有名なものがあります).
例3. ベルヌーイ試行
$X$を成功確率$p$のベルヌーイ試行とします. すなわち, $X\in\{0,1\}$であり
\begin{align*}
\Pr[X = b] = \begin{cases}
1 & \text{with probability }p,\\
0 & \text{with probability }1-p.
\end{cases}
\end{align*}
導出過程は省略(自分で手計算すると簡単に確認できる)しますが,
\begin{align*}
\psi_X(\lambda) = \lambda p + \log(p\mathrm{e}^\lambda + 1 - p)
\end{align*}
となり, $\lambda = \log\frac{(1-p)(p+a)}{p(1-p+a)}$を代入すると凸共役$\psi^*_X(a)$が得られ,
\begin{align*}
\psi_X^*(a) = (p+a)\log\frac{p+a}{p} + (1-p-a)\log\frac{1-p-a}{1-p}
\end{align*}
となります. この式の右辺はベルヌーイ試行のKLダイバージェンスと等しいです. $\mathrm{Ber}(p)$と$\mathrm{Ber}(q)$のKLダイバージェンスを$\mathrm{KL}(p||q)$と書くと, この値は
\[
\mathrm{KL}(\mathrm{Ber}(p) || \mathrm{Ber}(q)) = p\log\frac{p}{q} + (1-p)\log\frac{1-p}{1-q}
\]
で定義され, これを用いると$\psi_X^*(a) = \mathrm{KL}(p+a||p)$と書くことができます. このことから以下のChernoff bound (の特殊ケース)を得ます:
$X\sim\mathrm{Bin}(n,p)$のとき, $\Pr[X\ge np + n a] \le \mathrm{e}^{-n\mathrm{KL}(p+a||p)}$.
ここにPinskerの不等式$\mathrm{KL}(p||q)\ge 2(p-q)^2$を代入するとHoeffding boundになります.
0 件のコメント:
コメントを投稿