確率過程の sup 評価 ―― 行列ノルムを例として

はじめに

$M = (M_{i, j})$ を $n \times m$ サイズの実数値ランダム行列とし，各要素は $\sigma^2$ -subgaussian な分布に独立に従うとする．このとき， $M$ の ( $\mathbb{R}$ の 2-ノルムから誘導された) 作用素ノルム，すなわち
$\displaystyle{ \| M \| = \sup_{\| v\|, \| w \| \le 1} \langle v, Mw \rangle }$
の期待値を上から評価する問題を考える．この問題は，適切な定式化によって，Lipschitz な確率過程において $\sup$ を求めることに帰着する．この記事では，Lipschitz 過程における上界評価の具体的な手法を紹介し， $\|M\|$ の上界を求めることを目指す．

なお，この記事の大部分は，van Handel [1] を輪読した際のゼミ資料から抜粋して，(発表時に頂いたコメントを反映しつつ) 記述を全体的に簡略化したものである．

添字集合が有限な過程

$\{ X_t \}_{t \in T}$ という確率過程を考える． $T$ は添字集合 (例えば，時刻や位置の集合) である．いま，期待値 $\mathbb{E} \left[ \sup_{t \in T} X_t \right]$ を評価したい．標語的には，この上界は「確率過程の連続性」と「添字集合の複雑性」によって決まる．

もっとも単純なケースとして， $T$ が有限集合であって， $X_t$ が任意の $t$ で $\sigma^2$ -subgaussian となる状況を考える．このとき，どこかで見たような式による評価が得られる．

Lem. 1
$\{ X_t \}_{t \in T}$ を確率過程とする． $|T| < \infty$ であり，任意の $t \in T, \lambda \ge 0$ で $\log \mathbb{E} [ \exp (\lambda X_t) ] \le \sigma^2 \lambda^2 / 2$ が成り立つと仮定する．このとき，
$\displaystyle{ \mathbb{E} \left[ \sup_{t \in T} X_t \right] \le \sqrt{ 2\sigma^2 \log |T| } }$
が成り立つ．

pf.
$\psi (\lambda) = \sigma^2 \lambda^2 / 2$ とする．Jensen の不等式により，任意の $\lambda \ge 0$ について，
$\displaystyle{ \mathbb{E} \left[ \sup_{t \in T} X_t \right] \le \frac{1}{\lambda} \log \mathbb{E} [e^{\lambda \sup_{t \in T} X_t} ] \le \frac{1}{\lambda} \log \sum_{t \in T} \mathbb{E} [e^{\lambda X_t} ] \le \frac{\log |T| + \psi(\lambda)}{\lambda} }$
が成り立つ．ここで，右辺で $\lambda$ について $\inf$ を取ることで不等式を tight にしたいが，相加平均・相乗平均の不等式から， $\sqrt{ 2\sigma^2 \log |T|}$ が最適な評価である (かつ，実際にこの評価を達成できる) ことが分かる．(証明終)

Rmk.
この補題は， $X_t$ が subgaussian でなくても，モーメント母関数の対数が有界 ( $\psi (\lambda)$ によって抑えられる) な場合に一般化できる．その場合は， $\psi (\lambda)$ の Legendre 変換を用いた不等式評価が得られる．

Lipschitz 過程と covering number

$T$ が無限集合の場合，上述したような評価は使えない (自明な不等式しか与えない)．そこで， $T$ を有限集合 $N$ によって近似することを考える．もし，確率過程 $X_t$ が添字について「連続」であれば，適切に $N$ を構成することで，近似誤差をある程度小さくできる．この観察を定式化するため，「連続」な過程のもっとも強い形である Lipschitz 過程を導入する．

Def. 2
確率過程 $\{ X_t \}_{t \in T}$ が距離 $d : T\times T \to \mathbb{R}_{\ge 0}$ について Lipschitz であるとは，確率変数 $C$ が存在して，任意の $t, s \in T$ に対して
$\displaystyle{ |X_t - X_s| \le C d(t, s) }$
が成り立つことである．

Rmk.
確率過程が Lipschitz であるという仮定は強い．つねにこのような評価ができるとは限らないことに注意する必要がある．たとえば，Wiener 過程は一般に Lipschitz でない．

次に， $T$ を近似する有限集合 $N$ の構成について考える． $N$ は， $T$ の任意の点から離れすぎておらず，かつ集合としてできるだけ小さいものにしたい．この直観的な考え方に基づいて，net と covering number という概念が定義される．
Def. 3
$N$ が $(T, d)$ の $\epsilon$ -net であるとは，任意の $t \in T$ に対してある $\pi (t) \in N$ が存在して， $d (t, \pi (t)) \le \epsilon$ を満たすことである．また， $(T, d)$ の $\epsilon$ -netのうち最小のものの濃度を covering number と呼び， $N(T, d, \epsilon)$ と書く．すなわち，
$\displaystyle{ N(T, d, \epsilon) = \inf \{ |N| \mid Nは(T, d)の\epsilon{\text-}net \} .}$

以上で，「確率過程の連続性」と「添字集合の複雑性」をそれぞれ表す指標が定まった．すなわち，前者は確率過程の Lipschitz 定数であり，後者は $(T, d)$ の covering number である．

Lipschitz 過程の sup

これまで導入した定義を用いることで，各時刻で subgaussian であるような Lipschitz 過程で $\sup$ を評価することができる．

Lem. 4
$\{X_t\}_{t\in T}$ は Lipschitz 過程であり，Lipschitz 定数は $C$ であるとする．また，任意の $t \in T$ について $X_t$ は $\sigma^2$ -subgaussian であるとする．このとき，
$\displaystyle{ \mathbb{E} \left[ \sup_{t \in T} X_t \right] \le \inf_{\epsilon > 0} \left\{ \epsilon \mathbb{E} [C] + \sqrt{2\sigma^2 \log N(T, d, \epsilon)} \right\} }$
が成り立つ．

pf.
$\epsilon$ を任意の正数とし， $N$ を $(T, d)$ の $\epsilon$ -net とする．このとき，
$\displaystyle{ \sup_{t \in T} X_t \le \sup_{t \in T} \left\{X_t - X_{\pi (t)} \right\} + \sup_{t \in T} X_{\pi (t)} \le C \epsilon + \sup_{t \in N} X_t }$
である．ここで，最右辺第 2 項では， $N$ が有限集合だから，Lem. 1 が適用できる．不等式の両辺で期待値を取ると，
$\displaystyle{ \mathbb{E} \left[ \sup_{t \in T} X_t \right] \le \epsilon \mathbb{E} [C] + \sqrt{2\sigma^2 \log |N|}. }$
$\epsilon > 0$ と $N$ は任意だったから，それらについて右辺を最小化することで，
$\displaystyle{ \mathbb{E} \left[ \sup_{t \in T} X_t \right] \le \inf_{\epsilon > 0} \left\{ \epsilon \mathbb{E} [C] + \sqrt{2\sigma^2 \log N(T, d, \epsilon)} \right\} }$
を得る．(証明終)

Packing number

さて，具体的な評価を得るためには covering-number $N(T, d, \epsilon)$ を求める (少なくとも，抑える) ことが必要である．そのために，数理最適化における双対問題と類似した概念を covering number に対して導入する．
Def. 5
$N \subseteq T$ が $(T, d)$ の $\epsilon$ -packing であるとは，任意の相異なる $t, t' \in N$ について $d(t, t') > \epsilon$ が成り立つことである．また， $(T, d)$ の $\epsilon$ -packing のうち最大のものの濃度を packing number と呼び， $D(T, d, \epsilon)$ で書く．すなわち，
$\displaystyle{ D(T, d, \epsilon) = \sup \{ |D| \mid Dは(T, d)の\epsilon{\text {-packing}} \}. }$

Covering number と packing number の間には，ある種の双対定理が成り立つ．
Lem. 6
任意の $\epsilon > 0$ について，
$\displaystyle{ D(T, d, 2\epsilon) \le N(T, d, \epsilon) \le D(T, d, \epsilon). }$

pf.
$D$ を $2\epsilon$ -packing とし， $N$ を $\epsilon$ -netとする．定義から，任意の $t \in D$ について， $\pi (t) \in N$ を $d(t, \pi (t)) \le \epsilon$ となるように選べる． $t \neq t'$ ならば，
$\displaystyle{ 2\epsilon < d(t, t') \le d(t, \pi (t)) + d(\pi (t), \pi (t')) + d(\pi (t') , t') \le 2 \epsilon + d(\pi (t), \pi (t')) }$
だから， $d(\pi(t), \pi (t')) > 0$ である．すなわち $\pi : D \to N$ は単射で， $|D| \le |N|$ が従う．したがって， $D(T, d, 2\epsilon) \le N(T, d, \epsilon)$ である．

次に，右側の不等式を示すために， $D$ を $(T, d)$ の最大 $\epsilon$ -packing とする．このとき， $D$ は $\epsilon$ -net でもある．実際，ある $t \in T$ があって任意の $t' \in D$ に対して $d (t, t') > \epsilon$ とすると， $D \cup \{ t \}$ もまた $\epsilon$ -packing であり， $D$ の最大性に矛盾する．(証明終)

行列ノルムの評価

いよいよ，最初に言及した行列ノルムの評価をおこなう．繰り返すと， $M$ は各要素が独立かつ $\sigma^2$ -subgaussian であるようなランダム行列であり，
$\displaystyle{ \| M \| = \sup_{\| v\|, \| w \| \le 1} \langle v, Mw \rangle }$
の期待値 $\mathbb{E} [ \|M\| ]$ を評価したいのだった．

$B_2^n = \{ x \in \mathbb{R}^n \mid \| x \| \le 1 \}, \; T = B_2^n \times B_2^m$ とし，
$\displaystyle{ X_{v, w} = \langle v, Mw \rangle = \sum_{i = 1}^n \sum_{j = 1}^n v_i M_{ij} w_j }$
とすると，
$\displaystyle{ \| M \| = \sup_{(v, w) \in T} X_{v, w} }$
と書ける．そこで，作用素ノルムの評価は，添字集合 $T$ を持つ確率過程の $\sup$ を求める問題に帰着する．さらに，この過程は， $T$ に適切な距離を入れることで Lipschitz となる．そのことを示そう．

Azuma の不等式から，任意の $(v, w) \in T$ について， $X_{v, w}$ は $\sigma^2$ -subgaussian である．さらに，
$\displaystyle{ \begin{equation*} \begin{split} |X_{v, w} - X_{v', w'} | &= | \langle v, Mw \rangle - \langle v', M w' \rangle | \\ &= | \langle v - v', Mw \rangle + \langle v', M w - w' \rangle | \\ &\le | \langle v - v', Mw \rangle| + | \langle v', M w - w' \rangle | \\ &\le \|v - v' \| \| M \| \| w \| + \| v' \| \| M \| \| w - w' \| \\ &\le \| M\| (\| v - v' \| + \| w - w' \| ) \end{split} \end{equation*} }$
が成り立つ．したがって， $T$ 上の距離 $d$ を $d ( (v, w), (v', w') ) = \| v - v' \| + \| w - w' \|$ で定めると， $X_{v, w}$ は Lipschitz 過程となる．Lipschitz 定数は $\| M \|$ である．以上で，Lem. 4 を用いるための仮定が揃った．Lem. 4 の不等式に Lipschitz 定数を代入して整理すると，
$\displaystyle{ \mathbb{E} [ \| M \| ] \le \inf_{\epsilon > 0} \frac{\sigma \sqrt{2}}{1 - \epsilon} \sqrt{ \log N(T, d, \epsilon)} }$
を得る．

さらに， $T$ が Euclid 空間の単位球の直積であることを踏まえて，packing number との双対性を利用しつつ，covering number を求める．
Lem. 7
$B_2^n$ を， $n$ 次元 Euclid 空間の単位球とする． $0 < \epsilon < 1$ のとき，
$\displaystyle{ \left( \frac{1}{\epsilon} \right)^n \le N(B_2^n, \| \cdot \|, \epsilon) \le \left( \frac{3}{\epsilon} \right)^n .}$

pf.
図を描いて考えると，比較的明らかである．

図 1 は， $B_2^n$ を青い円で描き， $2\epsilon$ -packingの点を打ったものである．赤い円の面積の総和は，グレーの円 (半径 $1 + \epsilon$ ) の面積以下である．小さい円は互いに交わらないから， $\lambda$ を Lebesgue 測度として，
$\displaystyle{ |D| \lambda (B (0, \epsilon)) = \sum_{t \in D} \lambda ( B (t, \epsilon)) = \lambda \left( \bigcup_{t \in D} B(t, \epsilon) \right) \le \lambda (B(0, 1 + \epsilon)). }$
したがって，
$\displaystyle{ |D| \le \frac{\lambda(B(0, 1 + \epsilon))}{\lambda(B(0, \epsilon))} = \left( \frac{1 + \epsilon}{\epsilon} \right)^n = \left( 1 + \frac{1}{\epsilon} \right)^n \le \left( \frac{3}{2\epsilon} \right)^n. }$
あとは， $2\epsilon \mapsto \epsilon$ と取りかえた上で，Lem. 6 の双対性を用いれば， $\left( \frac{1}{\epsilon} \right)^n \le N(B_2^n, \| \cdot \|, \epsilon)$ を得る．

図 2 は， $\epsilon$ -net の点を打ったものである．小さい円の面積の総和は，青い円 (半径 $1$ ) の面積以上である．そこで，
$\displaystyle{ \lambda(B_2^n) \le \lambda \left( \bigcup_{t \in N} B(t, \epsilon) \right) \le \sum_{t \in N} \lambda (B(t, \epsilon)) .}$
から，
$\displaystyle{ |N| \ge \frac{\lambda(B_2^n)}{\lambda (B(0, \epsilon))} = \left( \frac{1}{\epsilon} \right)^n }$
を得る．(証明終)

この補題により，作用素ノルムの期待値の評価を得ることができる．まず， $N_1, N_2$ がそれぞれ $B_2^n, B_2^m$ の $\epsilon$ -net であるとき， $N_1 \times N_2$ は (先述した距離のもとで) $T = B_2^n \times B_2^m$ の $2\epsilon$ -net である．したがって，
$\displaystyle{ N(T, d, 2\epsilon) \le N(B_2^n, \| \cdot \|, \epsilon) N(B_2^m, \| \cdot \|, \epsilon) \le \left( \frac{3}{\epsilon} \right)^{n + m} }$
である．定数倍を無視することで，
$\displaystyle{ \mathbb{E} [ \| M \| ] \lesssim \sigma \sqrt{n + m} }$
を得る．これが所期の不等式評価である．行列ノルムのオーダーが $\sqrt{nm}$ ではなく $\sqrt{n + m}$ であることは非自明であり，興味深い．

Rmk.
上記は， $\sup$ の期待値評価の一つの手法ではあるが，確率過程の Lipschitz 性や $T$ のコンパクト性に強く依拠している．実際，covering number が多項式オーダーであることは，添字集合が Euclid 空間の構造を持つことに由来する幸運であると言える．

また，Lem. 4 の評価は，ある意味で悲観的すぎて loose である．Covering number が指数オーダーで増加するような問題設定では，そのために，Lem. 4 の不等式が tight にならないことがある (van Handel [1] を参照)．その場合，net argument を利用しない別の手法が必要となる．

参考文献

[1] R. van Handel (2016), Probability in High Dimension. APC 550 Lecture Notes (https://web.math.princeton.edu/~rvan/APC550.pdf).