楠岡 成雄「Rademacher 複雑度と正則化」
§7 例

　ここでは $\rho : \mathbb {R}\rightarrow \mathbb {R}$ は連続関数で、条件 (R-1), (R-2) を満たし、 $$|\rho (t)| \leq 1, \ \ \ \ \ t\in \mathbb {R}$$ となると仮定する。

　さらに、$\gamma _0 > 0,$ $C_0\in (0, \infty )$ が存在して $$\int _E\exp \left(\gamma _0h_i(x)^2\right)\nu (dx) \leq C_0, \ \ \ \ \ i = 1, \ldots , I_0,$$ かつ $\exp (\gamma _0) \leq C_0$ と仮定する。

　今、$f : E \rightarrow \mathbb {R}$ は可測関数とし、$F : E\times \mathbb {A}\rightarrow \mathbb {R}$ を $$F(x ; \vec {a}) = \left(f(x) - g^{(m)}_1(x ; \vec {a})\right)^2, \ \ \ \ \ x\in E$$ で定める。

　例えば $$\phi _0(\vec {a}) = \max _{k = 0, \ldots , m}(q_k(\vec {a}) + 1)$$ とおき $$\tilde {\mathcal {F}}_r = \left\{g^{(m)}_1(\cdot ; \vec {a})\ ; \ \phi _0(\vec {a})\leq r\right\}$$ とおくと、 $$\mathcal {R}_n(\tilde {\mathcal {F}}_r ; \nu ) \leq \frac{2^{m+1}C_1}{n^{1/2}}(r-1)r^m, \ \ \ \ \ r\geq 1$$ となり、さらに $$\sup \left\{ |g(x)|\ ; \ x\in E, \ \ g\in \tilde {\mathcal {F}}_r \right\} \leq r - 1, \ \ \ \ \ r\geq 1$$ となる。

場合 1. $f : E\rightarrow \mathbb {R}$ は有界と仮定する。

　今、$\mathcal {F}_r = \{F(x ; \vec {a})\ ; \ \phi _0(\vec {a})\leq r\}$ とおく。$g\in \tilde {\mathcal {F}}_r$ ならば $(f(x) - g(x))^2 = (f(x) - ((-r)\vee g(x))\wedge r)^2$ となる。

　$\rho _r(t, x) = (f(x) - ((-r)\vee t)\wedge r)^2$ とおくと $$\begin{align*} \left|\frac{\partial }{\partial t}\rho _r(t, x)\right| &\leq 2|f(x) - ((-r)\vee t)\wedge r|\\ &\leq 2(||f||_\infty + r), \ \ \ \ \ t\in \mathbb {R}, \ r\geq 1 \end{align*}$$ であるので、命題 3.4 より $$\begin{align*} \mathcal {R}_n(\mathcal {F}_r ; \nu ) &\leq 2(||f||_\infty + r)\mathcal {R}_n(\tilde {\mathcal {F}}_r ; \nu )\\ &\leq \frac{2^{m+2}C_1}{n^{1/2}}(||f||_\infty + r)r^{m+1} \end{align*}$$ であり、 $$\sup \left\{ |g(x)|\ ; \ x\in E, \ \ g\in \mathcal {F}_r \right\} \leq (||f||_\infty + r)^2$$ となる。

　よって、命題 5.1 より確率 $1 - 2\exp (-a^2)/(1-\exp (-a^2)/2)$ で $$\begin{align*} \left|\hat {F}_n(\vec {a}) - F_0(\vec {a})\right| &\leq \frac{a}{n^{1/2}}(\phi _0(\vec {a}) + ||f||_\infty + 1)^2(\phi _0(\vec {a}) + 1)^{1/2}\\ &\ \ \ \ + \frac{2^{m+3}C_1}{n^{1/2}}(\phi _0(\vec {a}) + ||f||_\infty + 1)(\phi _0(\vec {a}) + 1)^{m+1}. \end{align*}$$ ただし $$\hat {F}_n(\vec {a}) = \frac{1}{n}\sum ^n_{k=1}F(X_k, \vec {a}), \ \ \ \ \ F_0(\vec {a}) = \int _EF(x, \vec {a})\nu (dx)$$ である。今、$\phi : \mathbb {A}\rightarrow [0, \infty ),$ $\lambda > 0$ を定めて $$\begin{align*} \theta _0 &= \mathrm {argmin}_{\vec {a}\in \mathbb {A}}F_0(\vec {a}) , \\ \hat {\theta }_\lambda &= \mathrm {argmin}_{\vec {a}\in \mathbb {A}}(\hat {F}_n(\vec {a}) + \lambda \phi (\vec {a})) \end{align*}$$ とおくと、 $$\begin{align*} &F_0(\hat {\theta }_\lambda ) - F_0(\theta _0)\\ &= (\hat {F}_n(\hat {\theta }_\lambda ) + \lambda \phi (\hat {\theta }_\lambda )) - (\hat {F}_n(\theta _0) + \lambda \phi (\theta _0))\\ & \ \ \ \ \ - (\hat {F}_n(\hat {\theta }_\lambda ) - F_0(\hat {\theta }_\lambda )) - \lambda \phi (\hat {\theta }_\lambda )\\ & \ \ \ \ \ + (\hat {F}_n(\theta _0) - F_0(\theta _0)) + \lambda \phi (\theta _0)\\ &\leq \frac{a}{n^{1/2}}(\phi _0(\hat {\theta }_\lambda ) + ||f||_\infty + 1)^2(\phi _0(\hat {\theta }_\lambda ) + 1)^{1/2}\\ & \ \ \ \ \ + \frac{2^{m+3}C_1}{n^{1/2}}(\phi _0(\hat {\theta }_\lambda ) + ||f||_\infty + 1)(\phi _0(\hat {\theta }_\lambda ) + 1)^{m+1}\\ & \ \ \ \ \ - \lambda \phi (\hat {\theta }_\lambda ) + (\hat {F}_n(\theta _0) - F_0(\theta _0)) + \lambda \phi (\theta _0) \end{align*}$$ となる。

　例えば、 $$\phi (\theta ) = (\phi _0(\theta ) + 1)^{m+2}, \ \ \ \ \ \theta \in \mathbb {A}$$ とおくと、 $$\begin{align*} &F_0(\hat {\theta }_\lambda ) - F_0(\theta _0)\\ &\leq \frac{a}{n^{1/2}}(||f||_\infty + 1)^2(\phi _0(\hat {\theta }_\lambda ) + 1)^{5/2}\\ & \ \ \ \ \ + \frac{2^{m+3}C_1}{n^{1/2}}(||f||_\infty + 1)(\phi _0(\hat {\theta }_\lambda ) + 1)^{m+2}\\ & \ \ \ \ \ - \lambda (\phi _0(\hat {\theta }_\lambda ) + 1)^{m+2} + (\hat {F}_n(\theta _0) - F_0(\theta _0)) + \lambda \phi (\theta _0) \end{align*}$$ となり、 $$\frac{a}{n^{1/2}}(||f||_\infty + 1)^2 + \frac{2^{m+3}C_1}{n^{1/2}}(||f||_\infty + 1) \leq \lambda$$ であれば $$F_0(\hat {\theta }_\lambda ) - F_0(\theta _0) \leq (\hat {F}_n(\theta _0) - F_0(\theta _0)) + \lambda \phi (\theta _0)$$ となる。

場合 2. $f$ が有界でない場合

　$b > 0$ に対して $A_b = \{x\in E\ ; \ |f(x)|\leq b\}$ とおく。$\tilde {\Omega }_{b, n} = \cap ^n_{k=1}\{X_k\in A_b\}$ とおくと、$P(\tilde {\Omega }_{b, n}) \geq 1 - n(1 - \nu (A_b))$ となる。 $$F_b(x ; \vec {a}) = (1_{A_b}(x)f(x) - g^{(m)}_1(x ; \vec {a}))^2$$ とおき、 $$\begin{align*} F_{b, 0}(\vec {a}) &= \int _EF_b(x, \vec {a})\nu (dx), \\ \hat {F}_{b, n}(\vec {a}) &= \frac{1}{n}\sum ^n_{k=1}F_b(X_k, \vec {a}) \end{align*}$$ とおく。

　この時、$\omega \in \tilde {\Omega }_{b, n}$ ならば、 $$\hat {F}_n(\vec {a}) = \hat {F}_{b, n}(\vec {a})$$ であり、 $$\begin{align*} &|F_{b, 0}(\vec {a}) - F_0(\vec {a})|\\ &\leq \int _E\left|F_b(x, \vec {a}) - F(x, \vec {a})\right|\nu (dx)\\ &\leq 2\int _{E\setminus A_b}\left |f(x)g^{(m)}_1(x, \vec {a})\right |\nu (dx) + \int _{E\setminus A_b}f(x)^2\nu (dx)\\ &\leq 2\int _{E\setminus A_b}|f(x)|^2\nu (dx) + \sup _{x\in E}\left|g^{(m)}_1(x, \vec {a})\right|^2\nu (E\setminus A_b). \end{align*}$$

　$\mathcal {F}_{b, r} = \{F_b(x ; \vec {a})\ ; \ \phi _0(\vec {a})\leq r\}$ とおく。先と同様にして、命題 3.4 より $$\begin{align*} \mathcal {R}_n(\mathcal {F}_{b, r} ; \nu ) &\leq 2(b + r)\mathcal {R}_n(\tilde {\mathcal {F}}_r ; \nu )\\ &\leq \frac{2^{m+2}C_1}{n^{1/2}}(b + r)r^{m+1} \end{align*}$$ であり、 $$\sup \left\{|g(x)|\ ; \ x\in E, \ g\in \mathcal {F}_r\right\} \leq (b+r)^2$$ となる。

　よって、命題 5.1 より確率 $1 - 2\exp (-a^2)/(1-\exp (-a^2/2))$ で $$\begin{align*} |\hat {F}_{b, n}(\vec {a}) - F_{b, 0}(\vec {a})| &\leq \frac{a}{n^{1/2}}(\phi _0(\vec {a}) + b + 1)^2(\phi _0(\vec {a}) + 1)^{1/2}\\ &\ \ \ \ + \frac{2^{m+3}C_1}{n^{1/2}}(\phi _0(\vec {a}) + b + 1)(\phi _0(\vec {a}) + 1)^{m+1}. \end{align*}$$

　この時、$\omega \in \tilde{\Omega }_{b, n}$ であれば $$\begin{align*} \left| \hat {F}_n(\vec {a}) - F_0(\vec {a}) \right| &\leq \left| \hat {F}_{b, n}(\vec {a}) - F_{b, 0}(\vec {a}) \right| + 2\int _{E\setminus A_b}|f(x)|^2\nu (dx)\\ &\ \ \ \ \ + \phi _0(\vec {a})^2\nu (E\setminus A_b) \end{align*}$$ であるので、確率 $1 - 2\exp (-a^2)/(1-\exp (-a^2/2))$$-n\nu (E\setminus A_b)$ で $$\begin{align*} |\hat {F}_n(\vec {a}) - F_0(\vec {a})| &\leq \frac{a}{n^{1/2}}(\phi _0(\vec {a}) + b + 1)^2(\phi _0(\vec {a}) + 1)^{1/2}\\ &\ \ \ \ + \frac{2^{m+3}C_1}{n^{1/2}}(\phi _0(\vec {a}) + b + 1)(\phi _0(\vec {a}) + 1)^{m+1}\\ &\ \ \ \ \ + 2\int _{E\setminus A_b}|f(x)|^2\nu (dx) + \phi _0(\vec {a})^2\nu (E\setminus A_b) \end{align*}$$ となる。

　例えば、$\gamma _2 > 0$ が存在して $$C_2 = \int _E\exp \left(\gamma ^{-1}_2f(x)^2\right)\nu (dx) < \infty$$ であるのならば、$b = \log n + \tilde {a}$ ($\tilde {a} \geq 0$) とおけば $$\begin{align*} n\nu (E\setminus A_b) &\leq n\exp \left(-\gamma ^{-1}_2\left(\log + \tilde {a}\right)^2\right)C_2\\ &\leq C_2n\exp \left(-\gamma ^{-1}_2(\log n)^2\right)\exp \left(-\gamma ^{-1}_2\tilde {a}^2\right). \end{align*}$$ また、 $$\begin{align*} &\int _{E\setminus A_b}|f(x)|^2\nu (dx)\\ &\leq 2\gamma _2\int _{E\setminus A_b}\exp \left(\frac{1}{2\gamma _2}|f(x)|^2\right)\nu (dx)\\ &\leq 2\gamma _2\left(\int _E\exp \left(\frac{1}{\gamma _2}|f(x)|^2\right)\nu (dx)\right)^{1/2}\nu (E\setminus A_b)^{1/2}\\ &\leq 2\gamma _2C_2\exp \left(-\frac{1}{2\gamma _2}(\log n)^2\right)\exp \left(-\frac{1}{2\gamma _2}\tilde {a}^2\right). \end{align*}$$ よって、確率 $1 - 2\exp (-a^2)/(1-\exp (-a^2)/2)$$-C_2n\exp \left(-\gamma ^{-1}_2(\log n)^2\right)\exp \left(-\gamma ^{-1}_2\tilde {a}^2\right)$ で $$\begin{align*} &|\hat {F}_n(\vec {a}) - F_0(\vec {a})|\\ &\leq \frac{a}{n^{1/2}}(\phi _0(\vec {a}) + \log n + \tilde {a} + 1)^2(\phi _0(\vec {a}) + 1)^{1/2}\\ &\ \ \ \ \ + \frac{2^{m+3}C_1}{n^{1/2}}(\phi _0(\vec {a}) + \log n + \tilde {a} + 1)(\phi _0(\vec {a}) + 1)^{m+1}\\ &\ \ \ \ \ + 4\gamma _2C_2\exp \left(-\frac{1}{2\gamma _2}(\log n)^2\right)\exp \left(-\frac{1}{2\gamma _2}\tilde {a}^2\right)\\ &\ \ \ \ \ + \phi _0(\vec {a})^2C_2\exp \left(-\frac{1}{2\gamma _2}(\log n)^2\right)\exp \left(-\frac{1}{2\gamma _2}\tilde {a}^2\right) \end{align*}$$ となる。

※以下は編集者による加筆

場合 1. と同様に $\phi ,$ $\hat {\theta }_\lambda,$ $\theta _0$ を定めると、確率 $1 - 2\exp (-a^2)/(1-\exp (-a^2)/2)$$-C_2n\exp \left(-\gamma ^{-1}_2(\log n)^2\right)\exp \left(-\gamma ^{-1}_2\tilde {a}^2\right)$ で $$\begin{align*} &F_0(\hat {\theta }_\lambda ) - F_0(\theta _0)\\ &\leq \frac{a}{n^{1/2}}(\log n + \tilde {a} + 1)^2\left(\phi _0(\hat {\theta }_\lambda ) + 1\right)^{5/2}\\ &\ \ \ \ \ + \frac{2^{m+3}C_1}{n^{1/2}}(\log n + \tilde {a} + 1)\left (\phi _0(\hat {\theta }_\lambda ) + 1\right )^{m + 2}\\ &\ \ \ \ \ + C_2\left(4\gamma _2 + \phi (\hat {\theta }_\lambda )^2\right)\exp \left(-\frac{1}{2\gamma _2}(\log n)^2\right)\exp \left(-\frac{1}{2\gamma _2}\tilde {a}^2\right)\\ & \ \ \ \ \ - \lambda (\phi _0(\hat {\theta }_\lambda ) + 1)^{m+2} + (\hat {F}_n(\theta _0) - F_0(\theta _0)) + \lambda \phi (\theta _0) \end{align*}$$ となり、 $$\frac{a}{n^{1/2}}(\log n + \tilde {a} + 1)^2 + \frac{2^{m+3}C_1}{n^{1/2}}(\log n + \tilde {a} + 1) \leq \lambda$$ であれば $$\begin{align*} &F_0(\hat {\theta }_\lambda ) - F_0(\theta _0)\\ &\leq (\hat {F}_n(\theta _0) - F_0(\theta _0)) + \lambda \phi (\theta _0)\\ &\ \ \ \ \ + C_2\left(4\gamma _2 + \phi (\hat {\theta }_\lambda )^2\right)\exp \left(-\frac{1}{2\gamma _2}(\log n)^2\right)\exp \left(-\frac{1}{2\gamma _2}\tilde {a}^2\right) \end{align*}$$ となる。