凸共役と集中不等式

 凸解析のツールの一つとして凸共役という概念があります. $I\subseteq \mathbb{R}$上で定義された実関数$f$の凸共役とは
$$f^*(a) = \sup_{x\in I}\{ax - f(x)\}$$
で定義されます. 通常は$I=\mathbb{R}$や$I=(0,\infty)$を考えます. ここでは凸解析の理論には踏み込まず, この概念が確率集中不等式の文脈でどのように登場するかを説明します.

確率集中不等式とは, 実確率変数$X$がある点 (通常は期待値$\mathbb{E} X$) から離れる確率がどれくらい小さくなるかを評価する不等式です. (本記事では基本的に確率変数は全て期待値や分散が存在するものを考えます). 次の不等式を使います:

補題1 (マルコフの不等式).

$X$を非負確率変数と任意の正の数$z>0$に対し, $\Pr[X \ge z] \le \frac{\mathbb{E}X}{z}$.

本記事の目標は$\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)$になっています. 従って以下を得ます:

命題2.

確率変数$X$に対し, そのlogMGFを$\psi_X$とする. このとき, $\Pr[X\ge \mathbb{E} X + a] \le \mathrm{e}^{ - \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. 劣ガウシアン性を持つ確率変数

劣ガウシアン性とは裾分布が正規分布のそれ以下のオーダーで減衰していく性質を意味し, 確率集中不等式の文脈では非常に重要なクラスをなします.

定義3 (劣ガウシアン分布).
パラメータ$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 (の特殊ケース)を得ます:

定理4 (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になります.