Hölder関数クラスのノンパラメトリック推定におけるminimax下界
Published:
Kernel法などの線形推定器がminimax最適性を達成できる場合の例. このページでは, 最初のステップとしてminimax下界を示す.
問題設定
以下のモデルからのi.i.dサンプル ${(X_i, Y_i)}_{i=1}^n$ が与えられる.
\[Y_i = f(X_i) + \xi_i,\ \xi_i \sim \mathcal{N}(0, \sigma^2)\]ただし, $f: \mathbb{R}^d \mapsto \mathbb{R}$ は $\beta$ 階微分可能かつ, $X_i \in \mathbb{R}^D$ はD次元の入力であり, 決定的である.
定理を示すために確認すべきことは, $\xi$ のルベーグ測度に対するガウス確率密度 $p_{\xi}$ に対して, 以下を満たす $p_*,\ v_0$ が存在する.
\[\forall |v| \leq v_0,\ \int p_{\xi}(u) \log \frac{p_{\xi}(u)}{p_{\xi}(u+v)} \mathrm{~d}u \leq p_*v^2\]定理
任意のestimator $\hat{f}_n$ に対して, 以下の不等式を満たす $n$ に依存しない定数 $c$ が存在する.
\[\inf_{\hat{f}_n} \sup_{f \in C^{\lfloor \beta \rfloor, \beta}} \mathbb{E}_f\left[ \| \hat{f} - f \|_{L^2(P_X)} \right] \geq c n^{-\frac{\beta}{2\beta + D}}\]ただし, $C^{k, \beta}$ は階数 $k$ の $\beta$ -Hölder空間である. 推定量 $\hat{f}$ も $f$ から生成されるデータに基づいて作られるので, $f$ に依存することに注意.
本定理は, Hölderクラスに入っている真の関数の, 有限サンプルによる近似レートの限界オーダーを示している. 逆に, これと同じレートで近似可能な手法があれば, 理論上最適な手法と言える. (ミニマックス最適)
証明
マルコフ不等式より, 任意の定数 $a>0$ に対して,
\[\mathbb{E}_f\left[ \| \hat{f} - f \|_2 \right] \geq a P_f(\| \hat{f} - f \|_2 \geq a)\]仮説空間を有限点の集合で近似する. 今後は, 以下の不等式の右辺をさらに下から評価する.
\[\inf_{\hat{f}_n} \sup_{f \in C^{\lfloor \beta \rfloor, \beta}} P_f \left(\| \hat{f}_n - f \|_2 \geq a \right) \geq \inf_{\hat{f}_n} \sup_{f \in \{ f_1, f_2,\dots, f_M \}} P_f \left(\| \hat{f}_n - f \|_2 \geq a \right)\]仮説空間のHölder空間 $C^{\lfloor \beta \rfloor, \beta}$ を以下のように構成する.
\[\mathcal{E} = \left\{ f(x) = \sum_{k=1}^m w_k \varphi_k(x),\ w_k \in \{ 0, 1\} \right\} \subseteq C^{\lfloor \beta \rfloor, \beta},\ \varphi_k(x) = Lh_n^{\beta}K\left( \frac{x-x_k}{h_n}\right), \\ m = \lceil c_0 n^{\frac{1}{2 \beta +D}} \rceil,\ h_n = \frac{1}{m},\ x_k = \frac{k-1/2}{m} \mathbf{1}\]ただし, 関数 $K\colon \mathbb{R}^D \mapsto [0, \infty)$ は以下を満たす.
\[K \in C^{\lfloor \beta \rfloor, \beta},\ K(u) > 0 \iff u \in \left(-\frac{1}{2}, \frac{1}{2} \right)^D\]この時, 任意の仮説 $f_w, f_{w’}\in \mathcal{E}$ 間の距離は, 以下のように評価できる.
\[\begin{aligned} \| f_w - f_{w'} \|_2 &= \left[ \int (f_w(x) - f_{w'}(x))^2 \mathrm{~d}x \right]^{\frac{1}{2}} \\ &= \left[ \sum_{k=1}^m (w_k - w'_k)^2 \int \phi_k^2(x) \mathrm{~d}x \right]^{\frac{1}{2}} \\ &= Lh^{\beta}\left[ \sum_{k=1}^m (w_k - w'_k)^2 \int K^2\left(\frac{x - x_k}{h}\right) \mathrm{~d}x \right]^{\frac{1}{2}} \\ &= Lh^{\beta + \frac{D}{2}} \left[ \int K^2(u) \mathrm{~d}u\right]^{\frac{1}{2}}\left[ \sum_{k=1}^m (w_k - w'_k)^2\right]^{\frac{1}{2}} \end{aligned}\]Gilbert–Varshamov boundとHoeffdingの不等式より, $m$ に対して, 以下を満たしかつ $M \geq 2^{m/8}$ を満たす $M$ が存在する.
\[\sum_{i=1}^m \left( w_i - w'_i \right)^2 \geq \frac{m}{8}\]上の条件を満たすように仮説空間を構成すると, 任意の仮説のペア $f_w, f_{w’} \in \{ f_1, \dots, f_M \}$ に対して以下が満たされる.
\[\| f_w - f_{w'} \|_2 \geq Lh_n^{\beta + \frac{D}{2}} \|K\|_2 \sqrt{\frac{m}{8}} \geq \frac{L}{4} \|K\|_2(2c_0)^{-\beta} n^{-\frac{\beta}{2 \beta + D}} =: 2a\]半径aのM個の球で関数空間$\mathcal{E}$を埋めているイメージ. データ数nが大きくなるにしたがって, Mを大きく取り, 一方でaは小さく取る必要がある. このトレードオフの良いバランスが存在すると言っている. また, aが小さくなることは近似精度が高くなることを意味する.
$| f_w - f_{w’} |_2 \geq 2a$ の時, $\Psi \colon \mathcal{X} \mapsto {0, 1, \dots, M }$ を用いて, 式(5)の右辺は以下のように書ける.
\[\inf_{\hat{f}_n} \sup_{f \in \{ f_1, f_2,\dots, f_M \}} P_f \left(\| \hat{f}_n - f \|_2 \geq a \right) \geq \inf_{\Psi} \sup_{1 \leq j \leq M} P_{f_j}(\Psi \neq j)\]$\inf$ は真の関数からの距離が近いものを探す問題から, 真の $f_j$ を当てる問題になっている. 不等号になるのは, $\Psi^* \neq j \Rightarrow | \hat{f}_n - f_j|^2 \geq a$ だが, 逆は成立しないため. $| \hat{f}_n - f_j|^2 \geq a$ でも必ずしも $\hat{f}_n$ にもっと近い $f_k$ があるかは不明である.
Fano’s lemmaより, 以下が成立する.
\[P_{f_j}(\Psi \neq j) \geq 1 - \frac{I + \log 2}{\log M} \geq 1 - \alpha - \frac{\log 2}{\log M} =: b\]2つ目の不等号は, $c_0$ をうまく取ることで, $0 < \alpha < 1$ に対して, $I=\frac{1}{M} \sum_{m=1}^M \operatorname{KL}(f_m, f_0) \leq \alpha \log M$ となることを使った. ([1] p.106参照.)
最終的に以下のlower boundが求まる.
\[\inf_{\hat{f}_n} \sup_{f \in C^{\lfloor \beta \rfloor, \beta}} \mathbb{E}_f\left[ \| \hat{f} - f \|_{L^2(P_X)} \right] \geq \tilde{a}b n^{-\frac{\beta}{2 \beta + D}},\ \tilde{a} = \frac{L}{2} \|K\|_2(2c_0)^{-\beta}\]備考
上の証明は, Fano’s lemmaを用いた証明で, 他にもいくつか証明方法がある. [1]の2.7章参照
[1] Sampson, Paul D., and Peter Guttorp. “Nonparametric estimation of nonstationary spatial covariance structure.” Journal of the American Statistical Association 87.417 (1992): 108-119.