Dudleyの積分評価

同義語:Dudleyの不等式ダドリーの不等式Dudleyのエントロピー積分評価Dudley's inequalityDudley's integral inequalityDudley's entropy integral bound

概要

Dudleyの積分評価(Dudley's entropy integral bound)とは、擬距離空間 $(T,d)$ を添字とする確率過程で、増分 $X_t-X_s$ が尺度 $d(s,t)$ の劣 Gauss の裾をもち平均が $0$ のものについて、上限の期待値を被覆数 $N(T,d,\varepsilon)$ で $E\sup_tX_t\le C\int_0^\infty\sqrt{\log N(T,d,\varepsilon)}\,d\varepsilon$ と抑える不等式である。粗い網から細かい網へ点を順に近似する連鎖の方法で証明され、定数は $C=12$ にとれる。近い 2 点の増分も同じ積分で一様に抑えられ、積分が有限なら過程は連続な修正をもつ。中心化 Gauss 過程では Sudakov の下界と対になり、Rademacher 複雑度や経験過程の評価に使われる。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: Gauss過程, 全有界, Hoeffdingの不等式

Dudleyの積分評価(Dudley's entropy integral bound)は、添字の集合 $T$ の上の確率過程 $(X_t)_{t\in T}$ の上限の期待値を、$T$ の被覆数で上から抑える不等式である。増分 $X_t-X_s$ が距離 $d(s,t)$ を尺度とする劣 Gauss の裾をもち、平均が $0$ なら
$$ E\sup_{t\in T}X_t\le C\int_0^\infty\sqrt{\log N(T,d,\varepsilon)}\,d\varepsilon $$
が成り立つ。ここで $N(T,d,\varepsilon)$ は $T$ を半径 $\varepsilon$ の球で覆うのに要る最小の個数で、$C$ は過程にも $T$ にもよらない定数である(この記事の形では $C=12$ でよい)。
有限個の確率変数の最大値は、個数の対数の平方根の程度でしか大きくならない。$T$ が無限集合でも、$T$ を粗い網から細かい網へと順に近似し、各段の増分の最大値を足し合わせれば(連鎖、chaining)、各段で「網の点の個数の対数の平方根 × その段の尺度」の分だけ払えば済む。尺度について足すと上の積分になる。中心化 Gauss過程 では、下からの評価(Sudakov の下界、Slepianの補題)と対になり、上限の大きさを $T$ の幾何で測る基本の道具である。経験過程・Rademacher複雑度 の評価や、道の連続性の判定に使われる。

定義

$T$ を空でない集合、$d$ を $T$ の上の擬距離($d(s,t)=0$ で $s\ne t$ となってもよい距離)とし、$(X_t)_{t\in T}$ を同じ確率空間の上の実数値の確率変数の族とする。

劣 Gauss の増分

$(X_t)_{t\in T}$ が $d$ について 劣 Gauss の増分 をもつとは、すべての $s,t\in T$ と $\lambda\in\mathbb R$ について
$$ E\bigl[e^{\lambda(X_t-X_s)}\bigr]\le e^{\lambda^2d(s,t)^2/2} $$
が成り立つことをいう。

これは、各増分 $X_t-X_s$ が分散の目安 $d(s,t)^2$ の劣 Gauss(集中不等式 の定義「劣 Gauss 性」)で平均 $0$ であることと同じである。実際、$Z$ が $E e^{\lambda Z}\le e^{\lambda^2\sigma^2/2}$ を満たせば、Jensen の不等式で $\lambda EZ\le\lambda^2\sigma^2/2$ がすべての $\lambda$ で成り立つので $EZ=0$ である。よって $E X_t$ は $t$ によらない。さらに $\cosh x-1\ge x^2/2$ から $\frac{\lambda^2}2EZ^2\le E\cosh(\lambda Z)-1\le e^{\lambda^2\sigma^2/2}-1$ で、$\lambda\to0$ として
$$ E(X_t-X_s)^2\le d(s,t)^2\qquad(1) $$
を得る。

劣 Gauss の増分をもつ過程
  1. 中心化 Gauss 過程:$(X_t)$ が平均 $0$ の Gauss過程 なら、$d(s,t):=\bigl(E(X_t-X_s)^2\bigr)^{1/2}$(標準擬距離)について等号で成り立つ。$X_t-X_s$ が $N(0,d(s,t)^2)$ に従うからである。
  2. Rademacher 過程:$\sigma_1,\dots,\sigma_m$ を $\pm1$ を確率 $\frac12$ ずつとる独立な確率変数とし、$A\subset\mathbb R^m$ と $a\in A$ について $X_a:=\sum_i\sigma_ia_i$ とおく。$d$ を Euclid 距離 $\lvert a-b\rvert$ とすると、独立性と $\cosh x\le e^{x^2/2}$(両辺の Taylor 展開の係数を比べると $(2k)!\ge2^kk!$ による)から
    $$ E e^{\lambda(X_a-X_b)}=\prod_{i=1}^m\cosh\bigl(\lambda(a_i-b_i)\bigr)\le e^{\lambda^2\lvert a-b\rvert^2/2} $$
    である。
被覆数とエントロピー積分

$\varepsilon>0$ について、$T$ の点 $t_1,\dots,t_N$ で、どの $t\in T$ もある $t_i$ との距離が $\varepsilon$ 以下になるものがとれる最小の $N$ を 被覆数 $N(T,d,\varepsilon)$ という(とれなければ $+\infty$)。$\log N(T,d,\varepsilon)$ を 計量エントロピー といい、
$$ J(T,d):=\int_0^\infty\sqrt{\log N(T,d,\varepsilon)}\,d\varepsilon\in[0,\infty] $$
を Dudley のエントロピー積分 という。

$N(T,d,\varepsilon)$ は $\varepsilon$ について単調減少なので、積分は意味をもつ。$D:=\operatorname{diam}T=\sup_{s,t}d(s,t)$ とすると、$\varepsilon\ge D$ では 1 点で覆えるので被積分関数は $0$ である。$J(T,d)< \infty$ なら、すべての $\varepsilon>0$ で $N(T,d,\varepsilon)< \infty$($T$ は 全有界)で、$D< \infty$ である($D=\infty$ なら $N\ge2$ がすべての $\varepsilon$ で成り立ち、積分は発散する)。
$T$ が非可算のとき $\sup_tX_t$ は可測とは限らない。この記事では
$$ E\sup_{t\in T}X_t:=\sup\Bigl\{E\max_{t\in F}X_t:\ F\subset T\text{ は有限集合}\Bigr\} $$
と約束する。$T$ が可算なら、有限集合を増やしていけば単調収束定理によって通常の期待値と一致する。

主定理

まず、有限個の劣 Gauss 変数の最大値を抑える。

有限個の最大値

$Y_1,\dots,Y_N$($N\ge1$)が、すべての $\lambda\in\mathbb R$ と $i$ で $E e^{\lambda Y_i}\le e^{\lambda^2\sigma^2/2}$ を満たすとする(独立でなくてよい)。このとき
$$ E\max_{1\le i\le N}Y_i\le\sigma\sqrt{2\log N} $$
である。

指数関数で最大値を和に置き換える

各 $Y_i$ は積率母関数が有限なので可積分で、$\max_iY_i$ も可積分である。$\lambda>0$ とすると、Jensen の不等式と $e^{\lambda\max_iY_i}\le\sum_ie^{\lambda Y_i}$ から
$$ e^{\lambda E\max_iY_i}\le E e^{\lambda\max_iY_i}\le\sum_{i=1}^NE e^{\lambda Y_i}\le Ne^{\lambda^2\sigma^2/2} $$
で、$E\max_iY_i\le\frac{\log N}\lambda+\frac{\lambda\sigma^2}2$ である。$\sigma>0$ かつ $N\ge2$ なら $\lambda=\sqrt{2\log N}/\sigma$ とおいて結論を得る。$\sigma=0$ または $N=1$ なら、右辺の $\lambda>0$ についての下限は $0$ で、結論の右辺も $0$ である。$\square$

Dudley の積分評価

$(T,d)$ を擬距離空間、$(X_t)_{t\in T}$ を $d$ について劣 Gauss の増分をもつ過程とし、$D:=\operatorname{diam}T$ とする。このとき、どの $t_0\in T$ についても
$$ E\sup_{t\in T}\,(X_t-X_{t_0})\le12\int_0^{D/2}\sqrt{\log N(T,d,\varepsilon)}\,d\varepsilon $$
である。とくに、$E X_t=0$($t\in T$)なら
$$ E\sup_{t\in T}X_t\le12\int_0^{D/2}\sqrt{\log N(T,d,\varepsilon)}\,d\varepsilon\le12\,J(T,d),\qquad E\sup_{s,t\in T}\lvert X_t-X_s\rvert\le24\,J(T,d) $$
である。

2 進の尺度の網で連鎖を作る

右辺が有限で $D>0$ の場合を示せばよい($D=0$ なら (1) から $X_t=X_{t_0}$ がほとんど確実に成り立つ)。このとき $D< \infty$ で、すべての $\varepsilon>0$ で $N(T,d,\varepsilon)< \infty$ である。
段 1(網と連鎖)。 $t_0\in F$ となる有限集合 $F\subset T$ を固定する($F$ に $t_0$ を足すと最大値は減らないので、これで足りる)。$k\ge0$ について $\varepsilon_k:=D2^{-k}$、$N_k:=N(T,d,\varepsilon_k)$ とおく。$T_0:=\{t_0\}$ とし(どの点も $t_0$ から $D=\varepsilon_0$ 以内にある)、$k\ge1$ では $T$ の $N_k$ 個の点からなる集合 $T_k$ で、どの $t\in T$ も $T_k$ のある点から $\varepsilon_k$ 以内にあるものをとる。各 $t\in F$ と $k\ge0$ について、$d(t,\pi_k(t))\le\varepsilon_k$ を満たす $\pi_k(t)\in T_k$ を 1 つ選ぶ($\pi_0(t)=t_0$)。$K\ge1$ について、和を順に打ち消すと
$$ X_t-X_{t_0}=\sum_{k=1}^K\bigl(X_{\pi_k(t)}-X_{\pi_{k-1}(t)}\bigr)+\bigl(X_t-X_{\pi_K(t)}\bigr) $$
である。和の最大値は最大値の和以下なので
$$ \max_{t\in F}(X_t-X_{t_0})\le\sum_{k=1}^K\max_{t\in F}\bigl(X_{\pi_k(t)}-X_{\pi_{k-1}(t)}\bigr)+\max_{t\in F}\bigl(X_t-X_{\pi_K(t)}\bigr).\qquad(2) $$
段 2(各段の増分)。 $d(\pi_k(t),\pi_{k-1}(t))\le d(\pi_k(t),t)+d(t,\pi_{k-1}(t))\le\varepsilon_k+\varepsilon_{k-1}=3\varepsilon_k$ である。よって (2) の第 $k$ 項は、組 $(u,v)\in T_k\times T_{k-1}$ で $d(u,v)\le3\varepsilon_k$ を満たすものすべてにわたる $X_u-X_v$ の最大値以下である。組の個数は $N_kN_{k-1}\le N_k^2$ 以下で(被覆数は $\varepsilon$ について減少)、各 $X_u-X_v$ は分散の目安 $(3\varepsilon_k)^2$ の劣 Gauss の条件を満たす。lem-dud-max により、第 $k$ 項の期待値は
$$ 3\varepsilon_k\sqrt{2\log N_k^2}=6\,\varepsilon_k\sqrt{\log N_k} $$
以下である。(2) の最後の項は $\lvert F\rvert$ 個の変数 $X_t-X_{\pi_K(t)}$ の最大値で、lem-dud-max により期待値は $\varepsilon_K\sqrt{2\log\lvert F\rvert}$ 以下である。
段 3(和を積分に直す)。 (2) の期待値をとり $K\to\infty$ とすると、$\varepsilon_K\to0$ なので
$$ E\max_{t\in F}(X_t-X_{t_0})\le6\sum_{k\ge1}\varepsilon_k\sqrt{\log N_k} $$
である。$\varepsilon\in(\varepsilon_{k+1},\varepsilon_k]$ では $N(T,d,\varepsilon)\ge N_k$ であり、区間の長さは $\varepsilon_k/2$ なので
$$ \varepsilon_k\sqrt{\log N_k}\le2\int_{\varepsilon_{k+1}}^{\varepsilon_k}\sqrt{\log N(T,d,\varepsilon)}\,d\varepsilon $$
である。$k\ge1$ について足すと、右辺の区間は $(0,\varepsilon_1]=(0,D/2]$ を覆うので、$E\max_{t\in F}(X_t-X_{t_0})\le12\int_0^{D/2}\sqrt{\log N(T,d,\varepsilon)}\,d\varepsilon$ を得る。$F$ について上限をとれば最初の不等式である。
段 4(系)。 $E X_{t_0}=0$ なら $E\max_{t\in F}X_t=E\max_{t\in F}(X_t-X_{t_0})$ なので第 2 の不等式が従う。$-X$ も同じ条件を満たすので、$\max_{s,t\in F}\lvert X_t-X_s\rvert=\max_t(X_t-X_{t_0})+\max_s(X_{t_0}-X_s)$ の期待値は $2\cdot12J(T,d)$ 以下である。$\square$

定数と文献の形

定数 $12$ は証明を簡単にするためのもので、最良ではない。Ver18 Theorem 8.1.3・8.1.4(p. 190)は、増分の条件を $\psi_2$ ノルム $\|X_t-X_s\|_{\psi_2}\le Kd(s,t)$ で述べ、絶対定数 $C$ で $E\sup_tX_t\le CK\int_0^\infty\sqrt{\log N(T,d,\varepsilon)}\,d\varepsilon$ とする。証明(pp. 191–193)は同じ 2 進の連鎖である。上限の積分を $\operatorname{diam}T$ で切れることは同書 Remark 8.1.9(p. 194)にある。

最初の不等式に平均 $0$ の仮定は要らないが、$E\sup_tX_t$ の評価には要る(反例の節)。

増分の一様な評価と道の連続性

連鎖を、尺度 $\delta$ から始めると、近い 2 点の増分を一様に抑えられる。

増分の一様な評価

thm-dud-main の仮定のもとで、$0< \delta\le D$ について
$$ E\sup_{s,t\in T,\ d(s,t)\le\delta}\lvert X_s-X_t\rvert\le24\int_0^\delta\sqrt{\log N(T,d,\varepsilon)}\,d\varepsilon+11\,\delta $$
である(左辺は有限部分集合の上の最大値の期待値の上限と解釈する)。

尺度 $\delta$ の網から両側に連鎖を伸ばす
証明を開く

$\varepsilon_k:=\delta2^{-k}$($k\ge0$)、$N_k:=N(T,d,\varepsilon_k)$ とし、$T_k$ と $\pi_k$ を prf-dud-main と同じく(ただし $k=0$ でも $N_0$ 個の点の網として)とる。有限集合 $F$ の点 $s,t$ で $d(s,t)\le\delta$ なら $\lvert X_s-X_t\rvert\le\lvert X_s-X_{\pi_0(s)}\rvert+\lvert X_t-X_{\pi_0(t)}\rvert+\lvert X_{\pi_0(s)}-X_{\pi_0(t)}\rvert$ で、$d(\pi_0(s),\pi_0(t))\le3\delta$ である。$\lvert Y\rvert$ の最大値は $\pm Y$ の $2$ 倍の個数の変数の最大値なので、lem-dud-max から第 3 項の最大値の期待値は $3\delta\sqrt{2\log(2N_0^2)}$ 以下である。第 1・2 項は prf-dud-main と同じ連鎖で、それぞれの最大値の期待値は $\sum_{k\ge1}3\varepsilon_k\sqrt{2\log(2N_k^2)}$ 以下である(最後の項は $K\to\infty$ で消える)。$\sqrt{2\log(2N^2)}\le\sqrt{2\log2}+2\sqrt{\log N}$ と $\sum_{k\ge1}\varepsilon_k=\delta$ から、全体は $9\sqrt{2\log2}\,\delta+12\sum_{k\ge0}\varepsilon_k\sqrt{\log N_k}$ 以下で、$9\sqrt{2\log2}< 10.6$ である。prf-dud-main の段 3 と同じく $\varepsilon_k\sqrt{\log N_k}\le2\int_{\varepsilon_{k+1}}^{\varepsilon_k}\sqrt{\log N(T,d,\varepsilon)}\,d\varepsilon$ を $k\ge0$ について足せばよい。$\square$

連続な修正の存在

$(X_t)_{t\in T}$ が $d$ について劣 Gauss の増分をもち、$J(T,d)< \infty$ とする。このとき $X$ の 修正 $\widetilde X$(各 $t$ で $P(\widetilde X_t=X_t)=1$)で、すべての道 $t\mapsto\widetilde X_t$ が $(T,d)$ の上で一様連続かつ有界なものがある。とくに中心化 Gauss 過程は、標準擬距離のエントロピー積分が有限なら連続な修正をもつ。

可算な稠密集合の上の連続性の率を使う
証明を開く

$T$ は全有界なので可分で、可算な稠密部分集合 $T'$ がある。$\omega(\delta):=\sup\{\lvert X_s-X_t\rvert:s,t\in T',\,d(s,t)\le\delta\}$ は有限集合の上の最大値の増大列の極限なので可測で、単調収束定理と thm-dud-modulus により $E\omega(\delta)\le24\int_0^\delta\sqrt{\log N}\,d\varepsilon+11\delta$ である。$\omega$ は $\delta$ について増加なので極限 $\omega(0+)$ があり、$E\omega(0+)\le E\omega(\delta)\to0$($\delta\to0$、積分の絶対連続性)から $\omega(0+)=0$ がほとんど確実に成り立つ。その事象 $\Omega_0$ の上では $X$ は $T'$ の上で一様連続なので、$\widetilde X_t:=\lim_{s\to t,\,s\in T'}X_s$ が定まり(Cauchy 列になる)、$T$ の上で一様連続である。全有界な集合の上の一様連続関数は有界である。$\Omega_0$ の外では $\widetilde X:=0$ とする。修正であること:$T'\ni s_n\to t$ をとると (1) から $E(X_{s_n}-X_t)^2\le d(s_n,t)^2\to0$ で $X_{s_n}\to X_t$(確率収束)であり、一方 $X_{s_n}\to\widetilde X_t$(ほとんど確実)なので、$\widetilde X_t=X_t$ がほとんど確実に成り立つ。$\square$

Gauss過程 の定理「Gauss 過程の連続な修正」は、$[0,1]^n$ の上で増分の 2 乗平均が $\lvert t-s\rvert^\alpha$ の定数倍以下という条件から Kolmogorovの連続性定理 を通して連続性を導く。cor-dud-continuity は添字の集合を一般の擬距離空間にしたもので、$[0,1]^n$ でその条件が成り立てば $N(T,d,\varepsilon)\le C\varepsilon^{-2n/\alpha}$ で $J< \infty$ となる。

例

Brown 運動の上限

$T=[0,1]$、$X_t=B_t$(Brown運動)とする。標準擬距離は $d(s,t)=\lvert s-t\rvert^{1/2}$ で、$d$ の半径 $\varepsilon$ の球は長さ $2\varepsilon^2$ の区間なので、$\varepsilon\le1/\sqrt2$ で $N(T,d,\varepsilon)=\lceil1/(2\varepsilon^2)\rceil$、$D=1$ である。thm-dud-main から
$$ E\sup_{0\le t\le1}B_t\le12\int_0^{1/2}\sqrt{\log\lceil1/(2\varepsilon^2)\rceil}\,d\varepsilon\approx9.53 $$
を得る。実際の値は、反射原理(Brown運動) により $\sup_{t\le1}B_t$ が $\lvert B_1\rvert$ と同じ分布に従うので $\sqrt{2/\pi}\approx0.798$ である。定数は粗いが、評価は分布の詳しい性質を使わない。
thm-dud-modulus を $\delta=\sqrt h$($0< h< 1/2$)で使うと、$\lceil1/(2\varepsilon^2)\rceil\le\varepsilon^{-2}$($\varepsilon\le1/\sqrt2$)と $\int_0^\delta\sqrt{\log(1/\varepsilon)}\,d\varepsilon\le\delta\sqrt{\log(1/\delta)}+\frac{\delta}{2\sqrt{\log(1/\delta)}}$($\delta< 1$、$\varepsilon\sqrt{\log(1/\varepsilon)}$ の微分による)から
$$ E\sup_{\lvert s-t\rvert\le h}\lvert B_s-B_t\rvert\le C\sqrt{h\log(1/h)}\qquad(0< h\le h_0) $$
となる($C,h_0$ は絶対定数)。

単位球と Gauss 幅

$T=\{t\in\mathbb R^n:\lvert t\rvert\le1\}$、$g$ を $n$ 次元の標準正規ベクトル、$X_t:=\langle g,t\rangle$ とすると、標準擬距離は Euclid 距離である。$T$ の点で互いの距離が $\varepsilon$ を超える極大な集合は $T$ を半径 $\varepsilon$ で覆い、その点を中心とする半径 $\varepsilon/2$ の球は互いに交わらず半径 $1+\varepsilon/2$ の球に含まれるので、体積を比べて $N(T,\lvert\cdot\rvert,\varepsilon)\le(1+2/\varepsilon)^n$ である。$D=2$ なので
$$ E\sup_{\lvert t\rvert\le1}\langle g,t\rangle\le12\sqrt n\int_0^1\sqrt{\log(1+2/\varepsilon)}\,d\varepsilon\approx16.2\sqrt n $$
である。左辺は $E\lvert g\rvert$ で、$E\lvert g\rvert^2=n$、$E\lvert g\rvert^4=n^2+2n\le3n^2$ と Hölder の不等式 $E\lvert g\rvert^2\le(E\lvert g\rvert)^{2/3}(E\lvert g\rvert^4)^{1/3}$ から $\sqrt{n/3}\le E\lvert g\rvert\le\sqrt n$ なので、$\sqrt n$ の程度は正しい。

Sudakov の下界との比較

中心化 Gauss 過程では、被覆数による下からの評価がある。

Sudakov の下界(主張)

絶対定数 $c>0$ があって、平均 $0$ の Gauss 過程 $(X_t)_{t\in T}$ と標準擬距離 $d$、$\varepsilon>0$ について $E\sup_{t\in T}X_t\ge c\,\varepsilon\sqrt{\log N(T,d,\varepsilon)}$ である。

主張の所在

これは Ver18 Theorem 7.4.1(p. 171)で、証明の筋は Slepianの補題 の定理「Sudakov の下界」の注意にある。この記事では証明しない。

thm-dud-main と並べると
$$ c\sup_{\varepsilon>0}\varepsilon\sqrt{\log N(T,d,\varepsilon)}\le E\sup_{t\in T}X_t\le12\int_0^\infty\sqrt{\log N(T,d,\varepsilon)}\,d\varepsilon $$
で、左辺は曲線 $\varepsilon\mapsto\sqrt{\log N}$ の下の最大の長方形、右辺は曲線の下の面積である。両者の差は一般には埋まらず、エントロピー積分が有限であることは上限が有限であるための必要条件ではない。

積分は発散するが上限は有限

$g_1,g_2,\dots$ を独立な標準正規変数とし、$T=\{1,2,\dots\}$、$X_k:=g_k/\sqrt{1+\log k}$ とする。$E\sup_kX_k\le2.12$ だが $J(T,d)=\infty$ である。

確かめを開く

上限:$u\ge2$ で $P(\sup_kX_k>u)\le\sum_kP\bigl(g_k>u\sqrt{1+\log k}\bigr)\le e^{-u^2/2}\sum_kk^{-u^2/2}\le\frac{\pi^2}6e^{-u^2/2}$(正規分布の裾 $P(g>x)\le e^{-x^2/2}$、$x\ge0$)。よって $E\sup_kX_k^+\le2+\frac{\pi^2}6\int_2^\infty e^{-u^2/2}du\le2+\frac{\pi^2}6\cdot\frac{e^{-2}}2< 2.12$($\int_2^\infty e^{-u^2/2}du\le\int_2^\infty\frac u2e^{-u^2/2}du$)。

積分:$j\ne k\le m$ なら $d(j,k)^2=\frac1{1+\log j}+\frac1{1+\log k}\ge\frac2{1+\log m}$ なので、半径 $\varepsilon< 1/\sqrt{2(1+\log m)}$ の球は $1,\dots,m$ のうち 1 つしか含まず、$N(T,d,\varepsilon)\ge m$ である。$0< \varepsilon\le1/4$ について $m:=\lceil e^{1/(2\varepsilon^2)-1}\rceil-1$ とおくと条件を満たし、$x=1/(2\varepsilon^2)\ge8$ で $e^{x-1}-1\ge e^{x/2}$ なので $\log N(T,d,\varepsilon)\ge\frac1{4\varepsilon^2}$ である。よって被積分関数は $\frac1{2\varepsilon}$ 以上で、$J(T,d)=\infty$ である。

上の 2 つの評価の差を埋めるのが Talagrand の汎連鎖(generic chaining)で、網を尺度ごとに固定せず点ごとに最適化した量 $\gamma_2(T,d)$ によって、中心化 Gauss 過程の上限の期待値が定数倍を除いて決まる(Ver18 §8.5–8.6、主張のみ)。

経験過程と Rademacher 複雑度への応用

$A\subset\mathbb R^m$ を有界な集合とし、Rademacher複雑度 の記事と同じく
$$ \operatorname{Rad}(A):=E\sup_{a\in A}\frac1m\sum_{i=1}^m\sigma_ia_i $$
とおく。$d_m(a,b):=\bigl(\frac1m\sum_i(a_i-b_i)^2\bigr)^{1/2}$(標本の上の $L^2$ 距離)とする。

Rademacher 複雑度のエントロピー積分による評価

$D_m$ を $A$ の $d_m$ についての直径とすると
$$ \operatorname{Rad}(A)\le\frac{12}{\sqrt m}\int_0^{D_m/2}\sqrt{\log N(A,d_m,\varepsilon)}\,d\varepsilon $$
である。

$Y_a:=m^{-1/2}\sum_i\sigma_ia_i$ とおくと、ex-dud-examples の 2 により $(Y_a)$ は距離 $m^{-1/2}\lvert a-b\rvert=d_m(a,b)$ について劣 Gauss の増分をもち、$EY_a=0$ である。$a\mapsto\sum_i\sigma_ia_i$ は連続なので、上限は $A$ の可算な稠密部分集合でとっても変わらず、有限部分集合の増大列についての単調収束定理により、この記事の約束の $E\sup$ と通常の期待値は一致する。$\operatorname{Rad}(A)=m^{-1/2}E\sup_aY_a$ に thm-dud-main の最初の不等式($E Y_{a_0}=0$)を当てる。$\square$

関数の族 $\mathcal F$ と標本 $z_1,\dots,z_m$ では、$A=\{(f(z_1),\dots,f(z_m)):f\in\mathcal F\}$ とおけば経験 Rademacher 複雑度の評価になり、Rademacher複雑度 の定理「一様な偏差の上界」と組み合わせて、経験過程 の上限を被覆数で抑えられる。有限の $A$ についての Massart の補題(Rademacher複雑度 の命題「Massart の補題」)は $\operatorname{Rad}(A)\le\max_a\lvert a\rvert\sqrt{2\log\lvert A\rvert}/m$ を与えるが、prop-dud-rademacher は対数の分だけ良くなることがある。

しきい値の関数

$z_1< \cdots< z_m$ を実数、$\mathcal F=\{\mathbf 1_{(-\infty,c]}:c\in\mathbb R\}$ とする。$A$ は $v_j=(1,\dots,1,0,\dots,0)$($1$ が $j$ 個、$0\le j\le m$)の $m+1$ 点で、$d_m(v_i,v_j)=\sqrt{\lvert i-j\rvert/m}$、直径は $1$ である。Massart の補題は $\operatorname{Rad}(A)\le\sqrt{2\log(m+1)/m}$ を与える。
一方 $\varepsilon\ge1/\sqrt m$ で $q:=\lfloor m\varepsilon^2\rfloor\ge1$ とおくと、連続する $2q+1$ 個の添字の中央の点が残りを半径 $\varepsilon$ で覆うので $N(A,d_m,\varepsilon)\le\lceil(m+1)/(2q+1)\rceil\le3/\varepsilon^2$($2q+1>2m\varepsilon^2-1\ge m\varepsilon^2$ による)、$\varepsilon< 1/\sqrt m$ では $N\le m+1$ である。$D_m=1$ なので、prop-dud-rademacher の積分を 2 つの範囲に分けると
$$ \operatorname{Rad}(A)\le\frac{12}{\sqrt m}\Bigl(\sqrt{\frac{\log(m+1)}m}+\int_0^{1/2}\sqrt{\log(3/\varepsilon^2)}\,d\varepsilon\Bigr)\le\frac{12}{\sqrt m}\Bigl(\sqrt{\frac{\log(m+1)}m}+1.04\Bigr) $$
で、程度は $m^{-1/2}$ であり、Massart の補題の $\sqrt{\log m/m}$ より良い。実際の値は、$\sigma$ の部分和を $S_j$ とすると $\operatorname{Rad}(A)=E\max_{0\le j\le m}S_j/m$ で、$m=1000$ では $0.0247$ である(Massart の上界は $0.118$)。

同じ論法で、VC 次元 $V$ の 0–1 値の族では $L^2$ の被覆数が $(2/\varepsilon)^{CV}$ 以下であること(Ver18 Theorem 8.3.18、p. 208、Dudley による)から、期待値で $C\sqrt{V/m}$ の一様な偏差の評価が得られる(同 Theorem 8.3.23、p. 211)。VC次元 と Sauer–Shelahの補題 だけから得られる評価 $\sqrt{V\log m/m}$ の対数が取れる。

反例

外した仮定反例成り立たなくなる結論
平均 $0$(thm-dud-main の $E\sup_tX_t\le12J$)$T$ は 1 点、$X_t\equiv1$$E\sup_tX_t=1$ だが $J(T,d)=0$
劣 Gauss の増分(2 乗平均の評価 (1) だけを仮定する)$T=\{1,\dots,n\}$、$X_t$ は独立で $P(\lvert X\rvert>u)=u^{-3}$($u\ge1$)の対称な分布、$d(s,t):=\sqrt6$($s\ne t$)$E(X_s-X_t)^2=6=d(s,t)^2$ だが、$E\max_tX_t\ge0.63(n/2)^{1/3}-0.75$ は $n$ が大きいと主定理の右辺 $12\int_0^{D/2}\sqrt{\log N}\,d\varepsilon=6\sqrt6\sqrt{\log n}$ を超える
逆向きの主張(積分の有限性は上限の有限性に必要)ex-dud-gap$E\sup_kX_k\le2.12$ だが $J(T,d)=\infty$
反例の 2 行目の確かめ

$E X^2=1+\int_1^\infty2u\cdot u^{-3}du=3$ なので $E(X_s-X_t)^2=6$ である。$M:=\max_tX_t$、$u:=(n/2)^{1/3}$ とすると $P(M\ge u)=1-(1-\frac1{2u^3})^n=1-(1-\frac1n)^n\ge1-e^{-1}$ で $E M^+\ge(1-e^{-1})u$ である。また $M^-\le X_1^-$ で $E X_1^-=\frac12E\lvert X\rvert=\frac34$ なので、$EM\ge0.63(n/2)^{1/3}-0.75$ である。$n=10^9$ で左辺は約 $501$、$6\sqrt6\sqrt{\log n}$ は約 $66.9$ である。増分が劣 Gauss でないので thm-dud-main は当てはまらない。

歴史と出典

出典

上限の積分による評価は R. M. Dudley に遡る(Ver18 §8.8、p. 229)。Gauss 過程の連続性は Dud67 が扱った。連鎖の考え方は Kolmogorov の連続性定理の証明にすでに現れる(同)。

関連項目

参考文献

[1]
Roman Vershynin, High-Dimensional Probability: An Introduction with Applications in Data Science, Cambridge University Press, 2018, Theorem 7.4.1(p. 171)、Theorem 8.1.3・8.1.4(p. 190)とその証明(pp. 191–193)、Remark 8.1.9(p. 194)、§8.5–8.6、Theorem 8.3.18(p. 208)、Theorem 8.3.23(p. 211)、§8.8(p. 229)。番号・頁は著者公開の第 1 版による
[2]
R. M. Dudley, The sizes of compact subsets of Hilbert space and continuity of Gaussian processes, Journal of Functional Analysis 1 (1967), no. 3, pp. 290–330, 1967

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する