Generic Chaining (3)

前提

Generic chainingのタイトさを個人的に理解するためのノートの3つめ。

実は、とてもわかりやすい資料[1]を発見したため、あまり自分でリライトする意味がなくなりつつある。でも一応自分の言葉でまとめておく。

$X_t$は平均0の$d$-sub-Gaussian processとする。つまり、増分がsub-Gaussianであるような確率過程とする：
$$
\Pr(| X_s - X_t| \geq u) \leq 2 \exp \left( - \frac{u^2}{2d(s,t)^2}\right).
\tag{1}
$$
下つきの添字がスペース上の都合で書きにくいときは$X_t = X(t)$とも書く。

特に、$X_t$がガウス過程のときは、距離$d$として、$X_t$から定まる内在的な距離
$$
d(s, t) = \sqrt{\mathbb{E}(X_t - X_t)^2}
$$
を用いればよい。

平均0なので、$t_0 \in T$を固定すれば
$$
\mathbb{E}\sup_t X(t) = \mathbb{E}\sup_t (X(t) - X(t_0))
$$
が成り立つ。左辺に興味がある場合も、右辺を考えた方が今は都合がよい。$Y = \sup_t (X(t) - X(t_0))$は非負なので、
$$
\mathbb{E} Y = \int_0^\infty \Pr(Y \geq u) \dd u
$$
が成り立つ。

Generic chainingによる上界

連鎖 (chaining) というのは次のような考え方であった。$T$の代表点の集合$T_n$の増加列をつくり、$T_n$の要素数が増大するペースと、近時の第$n$階層と$(n+1)$階層の間の分散が減るペースをコントロールする。分散と要素数がコントロールされたsub-Gaussian変数の最大値（の期待値）をバウンドする不等式を用いて、$|X(\pi_n(t)) - X(\pi_{n+1}(t))|$の最大値をまとめ上げることによって、目的の$|X(t)-X(t_0)|$の最大値をバウンドする（前回参照）。

上の操作をもっとシステマティックに整理したのがgeneric chainingによる上界と言える。
改善の余地があるとしたら、直感的には次の二点な気がする：

  • もともとのchainingでは、$T_n$は$T$の$2^{-n}$-netになるようにとった。つまり、$T_n$の点はいわば等間隔に選んでいたが、冷静に考えると必ずしもそうである必要はない。$T$という空間の形状を考慮すると、最大に近い値をとりやすい領域とそうでない領域が発生している可能性がある。そういった$T$の偏りを考慮すると、実際に最大値をとりそうな領域の周辺で解像度を上げるべきかもしれない。
  • もとは階層ごとに最大不等式を使ってバウンドしていた。こうすると、階層ごとにチェーンをぶつ切りにして最大値を達成するような代表点の組をその都度選び直していることになるが、どうせならチェーンはつながったままにして、最大を考える作業は最後にまとめてやれば良い気がする。$\sum_n \sup_t$よりも$\sup_\t \sum_n$の方がおそらくましである（下の(4)式も参照）。

というわけで、generic chainingでは、$T_n$の点の間隔を可変にして、$\sup_t$という評価を行う作業は最後まで遅延する。

以下で考える$T_n$は、$T_0 = \{ t_0 \}$であって、$T_0 \subset T_1 \subset \cdots \subset T$となるような列とする。
ただし、間隔を可変にしたとはいえ、要素数が一気に増えすぎるとunion boundが無意味になるという（若干技術的な）事情があるので、
$$
|T_n|\leq 2^{2^n}
$$
となるようにする。イメージとしては、$|T_{n + 1}| \approx |T_n|^2$というペースで要素数を増やす[1]。
$\gamma_2(T,d)$を次のように定義する：
$$
\gamma_2(T, d) := \inf \sup_{t \in T} \sum_{n=0}^\infty 2^{n/2} d(t, T_n)
$$
ここで、infは上のような$T_n$の全体にわたってとる。$d(t, T_n) = \min_{s \in T_n} d(t, s)$とする。

定理
普遍的な定数$C > 0$が存在して、
$$
\mathbb{E}\sup_t X_t \leq C \gamma_2(T, d)
\tag{2}
$$
が成り立つ。

証明は省略するが、要は$T_n$を固定したときに
$$
\Pr( \sup_t (X(t) - X(t_0) > u \sum_{n=0}^\infty 2^{n/2} d(t, T_n)) \leq C \exp(-u^2)
$$
であることを言えばよいのであって、これはsub-Gaussian性(1)とunion boundから出てくる。

とはいえ、結局、”最適な” $T_n$の選び方をある程度特定してやらないことには(2)のタイト感はよくわからない。
一方で、前述のように$T_n$を等間隔にしたものがchainingであったから、chaining boundに相当するものは(2)から復元できる。

エントロピー数 $e_n(T)$を、
$$
e_n(T) := \inf_{T_n} \sup_t d(t, T_n)
\tag{3}
$$
と定義する。ただし、infは$|T_n| \leq 2^{2^n}$をみたすような有限集合全体にわたってとる。エントロピー数は、$\epsilon$-カバリングナンバーや$\epsilon$-パッキングナンバーの逆関数のようなもので、要素数を固定したときの$\epsilon$だと考えればよい。
(3)でinfを達成するような$T_n$を選ぶことによって、
$$
\gamma_2(T, d) \leq \sup_t \sum_{n=0}^\infty 2^{n/2} d(t, T_n) \leq \sum_{n=0}^\infty 2^{n/2} e_n(T)
\tag{4}
$$
がわかる。しかし、最右辺は、ある定数$C > 0$が存在して
$$
\sum_{n=0}^\infty 2^{n/2} e_n(T) \leq C \int_0^\infty \sqrt{\log N(T, d, \epsilon)} \dd \epsilon
$$
であることがわかるから[2]、chaining boundが (up-to-constantで) 復元する。

Generic chainingによる下界

$X_t$はガウス過程であるとする。この場合はとくに、generic chainingによる下からの評価も成立する。

定理 (Majorizing measure theorem)
$X_t$はガウス過程とし、$d$は$X_t$からきまる$T$上の擬距離とする。普遍的な定数$c > 0$が存在して、
$$
\mathbb{E}\sup_t X_t \geq c \gamma_2(T, d)
$$
が成り立つ。

少々どうでもいいんですが、なぜmajorizing “measure”という名前なのかというと、$\gamma_2$と本質的に同じものを代表点$T_n$ではなくて$T$上の測度を使って定式化することができ、そちらが先に出てきたという歴史的経緯によるものらしい。”Majorizing measures without measures”という（一体何を言ってるんだという感じのタイトルの）論文が存在するあたり、若干その雰囲気がうかがえる。

まとめ

このノートでは確率過程のsupについて次のことを書いた:

  • 有限個のsub-Gaussian変数の最大不等式 ($\sqrt{\log N}$)
  • sub-Gaussian processのchaining bound ($\int \sqrt{\log N(T, d, \epsilon)} \dd \epsilon$)
  • generic chaining bound (上界 & ガウス過程の下界)

他にもchaining boundがタイトでなくなる具体例とか、下界が成り立つ理由を書こうと思ったものの、力尽きたのでやめておく。[2]が専門書です。

参考文献

[1] J. R. Lee. Notes on Gaussian processes and majorizing measures (PDF)
[2] M. Talagrand. Upper and Lower bounds for Stochastic Processes, Springer, 2014.
[3] M. Talagrand. Majorizing Measures without Measures, The Annals of Probability, 29(1):411–417, 2001.