Poincaré不等式 - ややプログラム紀行

<a href="https://laurenceguy.bandcamp.com/track/on-your-side-single-3">On Your Side (Single) Laurence Guy</a>

気がつけばもう今年も終わりだ
今年は何もしてないわけではない(と思う)のでその点は自分を褒めたいけど、振り返って反省点を挙げるならとにかく活動時間の短さだと思う
周りの博士課程の人たちが毎日朝から夕方まで社会人のように研究してて、(自分もそんなに研究したら毎月論文書けるわ！)なんて思ったりしてたけど、流石にそろそろ態度を改めた方がいい気がしてきた😰
何となく研究に充てる時間を増やせばそれに反比例して効率が下がりそうで甘えていたけど、多分今の活動時間を2倍にしても何も効率は変わらない
というか現状が0*(効率)=0でやばい

最近電車に乗っている間などにMarkov過程とそれにまつわる不等式まわりの本↓を読んでたので、それについて軽くまとめようと思う
link.springer.com
毎回軽くと言いつつ少し長文になってる気がするので、今回は本当に適当&フォーマルにまとめる

Markov過程の詳しい定義は省略するとして、Markov過程 $X=(X_t)_{t \geq 0}$ に対応して次のような演算子が考えられる: 各時刻 $t$ と適当な実数値関数 $f$ に対して

$\displaystyle P_t f(x) := \mathbb{E}\left[f(X_t) \mid X_0 = x \right]$

こうして定義される演算子の族 $P = (P_t)_{t \geq 0}$ は任意の $t,s \geq 0$ に対して $P_t \circ P_s = P_{t+s}$ を満たす、すなわち半群になっているのでMarkov semigroupと呼ばれる
引数の $f$ はそれなりに広いクラスを取れるので、Markov過程の挙動をMarkov semigroup $P=(P_t)_{t \geq 0}$ を通して考えることができる

Markov過程といえばMarkov性、すなわち時刻 $t$ での変化がそれ以前の時刻 $s < t$ での状態に依存しないという性質を持つので、Markov semigroupの時刻 $t$ での瞬間的な変化、すなわち微分に注目したくなる
そこで次のような演算子、infinitesimal generatorが考えられる

$\displaystyle L: f \mapsto \partial_t P_t f|_{t = 0}$

Markov semigroupの線形性より $\frac{1}{s}\left[P_{t+s} - P_t\right] = P_t\left(\frac{1}{s}[P_s - 1]\right) = \left(\frac{1}{s}[P_s-1]\right)P_t$ 、 $s\to 0$ とすれば $\partial_t P_t|_t = P_tL = LP_t$ が成り立つので、逆にinfinitesimal generator $L$ からMarkov semigroup $P$ を構成する、ということも考えられる

例えば有名なMarkov過程としてOrnstein-Uhlenbeck過程を考えてみると、これは確率微分方程式

$\displaystyle dX_t = \sqrt{2}dW_t - X_t dt$

に従う( $(W_t)_{t \geq 0}$ はWiener過程)確率過程 $X=(X_t)_{t \geq 0}$ として定義されるが、これのMarkov semigroupは

$\displaystyle P_t f(x) = \mathbb{E}\left[ f\left(e^{-t}x + \sqrt{1-e^{-2t}}G \right) \right]$

( $G$ は標準正規分布に従う確率変数)、またinfinitesimal generatorは

$\displaystyle L_{\mathrm{OU}}: f \mapsto \partial_t P_t f|_{t = 0} = f'' - xf'$

となることが示せる

実は、 $L_{\mathrm{OU}}$ の固有ベクトルはHermite多項式によって与えられることが知られている:

$\displaystyle e^{sx - s^2/2} = \sum_{k \in \mathbb{N}} \frac{s^k}{\sqrt{k!}}H_k(x)$

によって定まる多項式 $H_0(x) = 1,\ H_1(x) = x,\ H_2(x) = \frac{1}{\sqrt{2}}(x^2-1),\dots$ は

$\displaystyle -L_{\mathrm{OU}}H_k = k H_k$

を満たす

さらに $(H_k)_{k \in \mathbb{N}}$ は $\mathbb{L}^2(\mu)$ ( $\mu$ は標準正規分布)の正規直交基底なので、関数 $f$ は

$\displaystyle f = \sum_{k \in \mathbb{N}} a_k H_k$

と表すことができ、

$\displaystyle -L_{\mathrm{OU}}f = \sum_{k \in \mathbb{N}} ka_k H_k$

と書ける

そもそもinfinitesimal generator $L_{\mathrm{OU}}$ はMarkov semigroup $P_t$ の時間微分 $L_{\mathrm{OU}}f = \partial_t P_t f$ だったことを思い出すと、 $P_tf = \sum_{k \in \mathbb{N}} e^{-kt} a_k H_k$ という関係式が得られる

以上のことから、 $t\to\infty$ で $P_t f \to a_0 H_0 = a_0$ に $\mathbb{L}^2(\mu)$ 収束することがわかるが、これはMarkov過程が $t\to\infty$ で平衡状態に収束している様子の現れと言える
より厳密に $\mathbb{L}^2(\mu)$ 収束の様子を調べると、

$\displaystyle \begin{align*} \left\|P_tf - \lim_{t \to \infty}P_t f\right\|_2^2 &= \left\|\sum_{k \in \mathbb{N}} e^{-kt} a_k H_k - a_0 \right\|_2^2 \\ &= \sum_{k \geq 1} e^{-2kt}a_k^2 \\ &\leq e^{-2t} \sum_{k \geq 1} a_k^2 \\ &= e^{-2t} \left\| f - a_0 \right\|_2^2 \end{align*}$

$\operatorname{Var}_{\mu}(f) = \left\| f - \int fd\mu \right\|_2^2$ と定義すれば $a_0 = \int fd\mu$ より左辺は $\operatorname{Var}_\mu(P_t f)$ 、右辺は $e^{-2t} \operatorname{Var}_\mu(f)$ と書けるので、上の式はMarkov semigroup $P_t$ が指数関数的に均衡に収束していることを表す不等式になっていることがわかり、「Ornstein-Uhlenbeck過程と正規分布 $\mu$ はPoincaré不等式を満たす」という

今までの議論はinfinitesimal generatorが $\mathbb{L}^2(\nu)$ 空間の正規直交基底 $v_0,v_1,v_2,\dots$ で固有分解できれば同様のことが言える
具体的には、 $v_0,v_1,v_2,\dots$ に対応する固有値を $\lambda_0 = 0 > \lambda_1 > \lambda_2 > \dots$ と書けば

$\displaystyle \begin{align*} \operatorname{Var}_\nu(P_t f) &= \sum_{k \geq 1} e^{-2\lambda_k t}a_k^2 \\ &\leq e^{-2\lambda_1)t} \sum_{k \geq 1} a_k^2 \\ &= e^{2(\lambda_0-\lambda_1)t} \operatorname{Var}_\nu(f) \end{align*}$

となり、その収束率 $e^{2(\lambda_0-\lambda_1)t}$ の形からspectral gap不等式とも呼ばれる
ちなみに $\lambda_0 = 0$ となるのは $L1d = \partial_t P_t 1 = 0$ が成り立つことによる

なお、一般的に「分布 $\nu$ がPoincaré不等式を満たす」といえばDirichlet form

$\displaystyle \mathcal{E}(f) := -\int fLfd\nu$

を用いて「適当なクラスの任意の関数 $f$ に対して $\operatorname{Var}_\nu (f) \leq C\mathcal{E}(f)$ ( $C$ は定数)」を指すことが多いが、これは「任意の $f \in \mathbb{L}^2(\nu)$ に対して $\operatorname{Var}_\nu (P_tf) \leq e^{-2t/C} \operatorname{Var}_\nu (f)$ 」と等価であることが示せる
$\operatorname{Var}_\nu (P_tf) \leq e^{-2t/C} \operatorname{Var}_\nu (f)$ からはテイラー展開 $P_t f = f + tLf + o(t)$ より

$\displaystyle \int \left(P_tf\right)^2d\nu = \int f^2 d\nu - 2t\mathcal{E}(f) + o(t)$

となり、右辺 $e^{-2t/C} = 1 - 2t/C + o(t)$ と見比べれば良い
逆に $\operatorname{Var}_\nu (f) \leq C\mathcal{E}(f)$ からは等式 $\frac{d}{dt}\operatorname{Var}_\nu(P_t f) = -2\mathcal{E}(P_t f)$ を利用することで $\operatorname{Var}_\nu (P_tf) \leq e^{-2t/C} \operatorname{Var}_\nu (f)$ が示される

いずれにせよMarkov過程における均衡への収束スピードを評価した式になっており、これは機械学習の分野でもMarkov Chain Monte Carloや確率的勾配降下法のLangevin dynamics的解釈などMarkov過程の収束スピードを知りたくなる場面は多いので、シンプルでありながら有用な不等式になっている

Ornstein-Uhlenbeck過程の場合をもう一度考えてみると、部分積分より

$\displaystyle \mathcal{E}(f) = -\int fLfd\mu = \int {f'}^2d\mu$

となるので $\operatorname{Var}_\mu (f) \leq \mathcal{E}(f) = \int {f'}^2d\mu$ が成り立つ

同様のことが $\mathbb{R}^n$ 上の正規分布に対しても言える

(Poincaré inequality for the Gaussian measure) $\mu$ を $\mathbb{R}^n$ 上の標準正規分布とするとき、任意の(適当な)関数 $f:\mathbb{R}^n \to \mathbb{R}$ に対して以下が成り立つ:
$\displaystyle \operatorname{Var}_\mu (f) \leq \int_{\mathbb{R}^n} |\nabla f|^2d\mu$

この式にはもはやOrnstein-Uhlenbeck過程が登場していないことに注目したい
このように、Markov過程の均衡への収束率を調べることによって、同時に定常分布についての不等式が得られることが度々ある(自分の興味はどちらかというとこっち)