高维统计理论 非参数回归模型的误差分析基础

之前两篇介绍了RKHS及其经典应用kernel ridge regression，这一篇讨论一般的非参数最小二乘模型的理论性质。

---

非参数回归的数据模型可以写成$y_i=f^{\ast }(x_i)+\sigma w_i$，其中$f^{\ast }$表示真实函数，$w_i$服从标准正态分布。假设内积函数空间$(\mathcal{F},\Vert \cdot \Vert )$为备选的非参数模型，$\{(x_i,y_i){\}}_{i=1}^n$为样本点，则非参数最小二乘估计为
$$\hat{f}=\underset{f\in \mathcal{F}}{\mathrm{argmin}}\frac{1}{n}\underset{最小二乘损失}{\underbrace{\sum _{i=1}^n[y_i-f(x_i){]}^2}}+\underset{正则项}{\underbrace{{\lambda }_n\Vert f\Vert }}$$

${\lambda }_n>0$为正则参数。

非参最小二乘及其误差

我们主要分析不含正则项的NLS。用$\mathcal{X}$表示$f^{\ast }$与$\mathcal{F}$中的函数的定义域，且$(\mathcal{X},\mathcal{B}(\mathcal{X}))$为可测空间。定义$${\mathbb{P}}_n=\frac{1}{n}\sum _{i=1}^n{\delta }_{x_i}$$

这是样本点的经验分布导出的测度，$(\mathcal{X},\mathcal{B}(\mathcal{X}),{\mathbb{P}}_n)$形成一个测度空间，基于这个测度空间定义 L 2 ( P n ) = { f : X → R ∣ ∫ f 2 d P n < ∞ } L^2(\mathbb P_n) = \{f:\mathcal X \to \mathbb R| \int f^2 d \mathbb P_n<\infty\} L2(Pn​)={f:X→R∣∫f2dPn​<∞}

这是一个Hilbert空间，假设$\mathcal{F}\subset L^2({\mathbb{P}}_n)$，则非参最小二乘估计的in-sample fitting error为
$${\Vert \hat{f}-f^{\ast }\Vert }_{{\mathbb{P}}_n}=\frac{1}{n}\sum _{i=1}^n[\hat{f}(x_i)-f^{\ast }(x_i){]}^2$$

其中${\Vert \cdot \Vert }_{{\mathbb{P}}_n}$是$L^2({\mathbb{P}}_n)$的内积。

计算误差上界的思路

仅作不严谨地推导以说明计算误差上界的思路，考虑到$\hat{f}$是最小二乘估计，
$$\frac{1}{2n}\sum _{i=1}^n(y_i-\hat{f}(x_i){)}^2\le \frac{1}{2n}\sum _{i=1}^n(y_i-f^{\ast }(x_i){)}^2$$

代入$y_i=f^{\ast }(x_i)+\sigma w_i$，
$$\begin{gathered} \frac{1}{2n}\sum _{i=1}^n(f^{\ast }(x_i)+\sigma w_i-\hat{f}(x_i){)}^2\le \frac{1}{2n}\sum _{i=1}^n(f^{\ast }(x_i)+\sigma w_i-f^{\ast }(x_i){)}^2 \\ \frac{1}{2n}\sum _{i=1}^n[(f^{\ast }(x_i)-\hat{f}(x_i){)}^2+2\sigma w_i(f^{\ast }(x_i)-\hat{f}(x_i))]\le 0 \\ \frac{1}{2n}\sum _{i=1}^n(\hat{f}(x_i)-f^{\ast }(x_i){)}^2\le \frac{\sigma }{n}\sum _{i=1}^n{w}_i(\hat{f}(x_i)-f^{\ast }(x_i)) \end{gathered}$$

不等式右边的结构是Gauss过程，指标为 { f ^ ( x i ) − f ∗ ( x i ) } \{\hat f(x_i)-f^*(x_i)\} {f^​(xi​)−f∗(xi​)}，其中$\hat{f}\in \mathcal{F}$，为了分析这个Gauss过程的性质，我们定义 F ∗ = { f − f ∗ : f ∈ F } \mathcal F^*=\{f-f^*:f \in \mathcal F\} F∗={f−f∗:f∈F}，这个集合是Gauss过程的指标集，$\hat{f}-f^{\ast }\in {\mathcal{F}}^{\ast }$。定义local Gaussian complexity，
$$\mathcal{G}(\delta ;{\mathcal{F}}^{\ast })=E\left[\underset{g\in {\mathcal{F}}^{\ast },{\Vert g\Vert }_n\le \delta }{\sup }\left|\frac{1}{n}\sum _{i=1}^n{w}_{i}g(x_i)\right|\right]$$

将上述不等式取期望后可得，
$$\frac{1}{2}E{\Vert \hat{f}-f^{\ast }\Vert }_n^2\le \sigma \mathcal{G}(\delta ;{\mathcal{F}}^{\ast })$$

如果记${\delta }^2=E{\Vert \hat{f}-f^{\ast }\Vert }_n^2$，则
$$\frac{{\delta }^2}{2}\le \sigma \mathcal{G}(\delta ;{\mathcal{F}}^{\ast })$$

这个推导自然是不严谨的，但由此我们可以得出，要推导误差的上界，我们需要选择critical value ${\delta }_n\ge \delta$，并用$\mathcal{G}(\delta ;{\mathcal{F}}^{\ast })$的上界作为对误差上界的估计。

定理
假设${\mathcal{F}}^{\ast }$为star-shaped function class，假设${\delta }_n$满足$\frac{{\delta }^2}{2}\le \sigma \mathcal{G}(\delta ;{\mathcal{F}}^{\ast })$，$\forall t>{\delta }_n$，
$$P\left({\Vert \hat{f}-f^{\ast }\Vert }_n^2\ge 16t{\delta }_n\right)\le e^{-\frac{nt{\delta }_n}{2{\sigma }^2}}$$

评注 star-shaped function class指的是$\forall \alpha \in [0,1],\forall f\in {\mathcal{F}}^{\ast }$, $\alpha f\in {\mathcal{F}}^{\ast }$，如果这个条件不满足，那么我们可以构造${\mathcal{F}}^{\ast }$的star hull，
s t a r ( F ∗ ; 0 ) = { α g : α ∈ [ 0 , 1 ] , g ∈ F ∗ } star(\mathcal F^*;0)=\{\alpha g:\alpha \in [0,1],g \in \mathcal F^*\} star(F∗;0)={αg:α∈[0,1],g∈F∗}

然后将定理应用在这个star hull上。star-shaped条件的作用是保证满足$\frac{{\delta }^2}{2}\le \sigma \mathcal{G}(\delta ;{\mathcal{F}}^{\ast })$的critical value ${\delta }_n$存在。${\mathcal{F}}^{\ast }$为star-shaped function class，则函数$\delta \to \frac{\mathcal{G}(\delta ;{\mathcal{F}}^{\ast })}{\delta }$关于$\delta >0$为非增函数，证明如下：考虑$0<\delta \le t$，$\forall h\in {\mathcal{F}}^{\ast }$, ${\Vert h\Vert }_n\le t$，定义$\tilde{h}=\delta h/t$，则${\Vert \tilde{h}\Vert }_n\le \delta$且$\tilde{h}\in {\mathcal{F}}^{\ast }$，计算
$$\frac{1}{n}\frac{\delta }{t}\sum _{i=1}^n{w}_{i}h(x_i)=\frac{1}{n}\sum _{i=1}^n{w}_i\tilde{h}(x_i)\le \underset{{\Vert \tilde{h}\Vert }_n\le \delta ,\tilde{h}\in {\mathcal{F}}^{\ast }}{\sup }\frac{1}{n}\sum _{i=1}^n{w}_i\tilde{h}(x_i)$$

左右两边取期望可得，
$$E\frac{1}{nt}\sum _{i=1}^n{w}_{i}h(x_i)\le \frac{\mathcal{G}(\delta ;{\mathcal{F}}^{\ast })}{\delta }$$

取左边的上确界，
$$\frac{1}{t}E\underset{{\Vert h\Vert }_n\le t,h\in {\mathcal{F}}^{\ast }}{\sup }\frac{1}{n}\sum _{i=1}^n{w}_{i}h(x_i)=\frac{\mathcal{G}(t;{\mathcal{F}}^{\ast })}{t}\le \frac{\mathcal{G}(\delta ;{\mathcal{F}}^{\ast })}{\delta }$$

因此$\forall c>0$，$\exists \delta >0$使得$c\delta \ge \frac{\mathcal{G}(\delta ;{\mathcal{F}}^{\ast })}{\delta }$（左边关于$\delta$递增，右边关于$\delta$非增，所以一定存在交点）。

Critical Value的metric entropy条件

定义 B n ( δ , F ∗ ) = { g ∈ s t a r ( F ∗ ; 0 ) : ∥ g ∥ n ≤ δ } B_n(\delta,\mathcal F^*)=\{g \in star(\mathcal F^*;0):\left\| g\right\|_n \le \delta \} Bn​(δ,F∗)={g∈star(F∗;0):∥g∥n​≤δ}，用$N_n(t;B_n(\delta ,{\mathcal{F}}^{\ast }))$表示$B_n(\delta ,{\mathcal{F}}^{\ast })$在${\Vert \cdot \Vert }_n$下的t-covering number，即
N n ( t ; B n ( δ , F ∗ ) ) = min ⁡ N s . t .   ∃ { g 1 , ⋯   , g N } ⊂ B n ( δ , F ∗ ) , ∀ g ∈ B n ( δ , F ∗ ) ∃ i ∈ { 1 , ⋯   , N } , ∥ g − g i ∥ n ≤ δ N_n(t;B_n(\delta,\mathcal F^*))=\min N \\ s.t. \ \exists \{g_1,\cdots,g_N\}\subset B_n(\delta,\mathcal F^*),\forall g \in B_n(\delta,\mathcal F^*) \\ \exists i \in \{1,\cdots,N\}, \left\| g-g_i \right\|_n \le \delta Nn​(t;Bn​(δ,F∗))=minNs.t. ∃{g1​,⋯,gN​}⊂Bn​(δ,F∗),∀g∈Bn​(δ,F∗)∃i∈{1,⋯,N},∥g−gi​∥n​≤δ

定理 $\forall \delta \in (0,\sigma ]$，如果
$$\frac{16}{\sqrt{n}}{\int }_{\frac{{\delta }^2}{4\sigma }}^{\delta }\sqrt{\log N_n(t;B_n(\delta ,{\mathcal{F}}^{\ast }))}dt\le \frac{{\delta }^2}{4\sigma }$$

则$\delta$满足$\frac{{\delta }^2}{2}\le \sigma \mathcal{G}(\delta ;{\mathcal{F}}^{\ast })$。

Oracle Inequality

在实际应用中，真实函数$f^{\ast }$可能并不在$\mathcal{F}$中，所以误差包括估计误差与近似误差（用$\mathcal{F}$中的函数近似$f^{\ast }$），估计误差在前文中讨论过了，而近似误差比较好的定义方法是计算$f^{\ast }$与$\mathcal{F}$的距离，即${\inf }_{f\in \mathcal{F}}{\Vert f-f^{\ast }\Vert }_n$，这个定义本身就意味着一种理想情况，就是我们知道 { f ∗ ( x i ) } \{f^*(x_i)\} {f∗(xi​)}的取值，所以称计算${\inf }_{f\in \mathcal{F}}{\Vert f-f^{\ast }\Vert }_n$上界的不等式为Oracle inequality。

以下定理可以视为对误差上界的推广：定义 ∂ F = { f 1 − f 2 : f 1 , f 2 ∈ F } \partial \mathcal F=\{f_1-f_2:f_1,f_2 \in \mathcal F\} ∂F={f1​−f2​:f1​,f2​∈F}，假设${\delta }_n$满足$\frac{\mathcal{G}(\delta ;\partial \mathcal{F})}{\delta }\le \frac{\delta }{2\sigma }$，存在常数$(c_0,c_1,c_2)$使得$\forall t\ge {\delta }_n$，
$${\Vert \hat{f}-f^{\ast }\Vert }_n^2\le \underset{\gamma \in (0,1)}{\inf }\left[\frac{1+\gamma }{1-\gamma }{\Vert f-f^{\ast }\Vert }_n^2+\frac{c_0}{\gamma (1-\gamma )}t{\delta }_n\right],\forall f\in \mathcal{F}$$

成立的概率大于$1-c_1{e}^{-c_2\frac{nt{\delta }_n}{{\sigma }^2}}$。