收敛速度的下界

在第一章中,我们分别研究了

核密度估计中的单点误差 $C n^{-2\beta/2\beta+1}$

核密度估计中的 $L_2$ 误差 $C n^{-2\beta/2\beta+1}$

局部多项式估计的单点误差 $C n^{-2\beta/2\beta+1}$

局部多项式估计的 $L_2$ 误差 $C n^{-2\beta/2\beta+1}$

局部多项式估计的 $L_\infty$ 误差 $C(\log n/n)^{-2\beta/2\beta+1}$

投影估计的 $L_2$误差 $Q(\beta,L)$ $$\mathrm{MISE}\leq C n^{-2\beta/2\beta+1}$$

可以看到他们都有一个形式极为相近的收敛速度(除了可能有 $\log n$ 的差别)。那么一个自然的想法就是,我们是否达到了最优的收敛速度?能否继续改进。事实上可以证明,上面给出了收敛速度已经达到了最优,而本章就是在研究如何论证这一命题。

求下界的框架:Minimax rate

我们的设定如下

首先我们有一个非参的函数空间 $\Theta$ ,我们所要估计的函数落在这个空间内,比如之前提到的 $\Sigma(\beta, L)$ (Holder 空间) 或 $W(\beta, L)$ (Sobolev 空间)

一族概率测度 $\{P_\theta,\theta\in\Theta\}$。在概率密度模型中,$P_\theta$ 是样本 $\boldsymbol{X}=(X_1,\ldots,X_n)$ 上的概率测度,其中每个样本 $X_i$ 的概率密度为 $\theta$

一个 $\Theta$ 上的距离度量 $d:\Theta\times\Theta\rightarrow[0,+\infty)$,满足非负性 $d(\theta,\theta’)\ge 0$, 同一性 $d(\theta,\theta’)=0\Leftrightarrow \theta=\theta’$, 对称性 $d(\theta,\theta’)=d(\theta’,\theta)$ 和三角不等式 $d(\theta,\theta’)+d(\theta’,\theta’’)\ge d(\theta,\theta’’)$

而我们估计参数的方法即为 $\widehat{\theta}_n:X^n\rightarrow \Theta$

为了度量这个估计的好坏,我们考察参数空间中最坏的情况,定义出最大风险为

$$r(\widehat{\theta}_n)\overset{\Delta}{=}\sup\limits_{\theta\in\Theta}\mathbb{E}_\theta[d^2(\widehat{\theta},\theta)]$$

之前的章节中我们证明的就是对于我们构造的那些估计中,有 $r(\widehat{\theta}_n)\leq C\psi_n^2$

而接下来的章节就是寻找当 $n$ 充分大时,所有估计方法中风险的下界(也就是考察最好的估计方法,不能比这个再好了)

$$\forall\widehat{\theta}_n:\qquad r(\widehat{\theta}_n)\ge c\psi_n^2$$

为此,我们定义 minimax risk 为

$$\mathcal{R}_n^\ast\overset{\Delta}{=}\inf\limits_{\widehat{\theta}} r(\widehat{\theta}_n)=\inf\limits_{\hat{\theta}}\sup\limits_{\theta\in\Theta}\mathbb{E}_\theta[d^2(\widehat{\theta},\theta)]$$

之前建立上界的时候意味着存在常数 $C<\infty$,使得对于一个收敛于零的序列 $\psi_n$

$$\underset{n\rightarrow\infty}{\lim\sup}\ \psi_n^{-2}\mathcal{R}_n^\ast\leq C$$

而对应的下界说明存在常数 $c>0$,对于同样的序列 $\psi_n$,有

$$\underset{n\rightarrow\infty}{\lim\inf}\ \psi_n^{-2}\mathcal{R}_n^\ast\ge c$$

而如果某个估计 $\theta_n^\ast$ 满足下式,我们就称他为渐进最优的

$$\lim\limits_{n\rightarrow\infty}\frac{r(\theta_n^\ast)}{\mathcal{R}_n^\ast}=1$$

一个更一般性的框架是定义最大风险为

$$r_w(\widehat{\theta}_n)\overset{\Delta}{=}\sup\limits_{\theta\in\Theta}\mathbb{E}_\theta[w(\psi_n^{-1}\cdot d^2(\widehat{\theta},\theta))]$$

其中 $w:[0,\infty)\rightarrow[0,\infty),\ w\nearrow,\ w(0)=0,w\not\equiv 0$ 称为 loss 函数,此时下界可以如下给出

$$\underset{n\to\infty}{\lim\inf}\ \inf\limits_{\hat{\theta}_n}\ \sup\limits_{\theta\in\Theta}\mathbb{E}_\theta[w(\psi_n^{-1}d(\hat{\theta}_n,\theta))]\ge c>0$$

常见的 $w$ 可以选为 $w(u)=u^p,p>0$ 或 $w(u)=\boldsymbol{1}[u\ge A],A>0$

三步走

为了得到一个下界,一个典型的方法使用了三次放缩

放缩至概率

取 $w(u)=\boldsymbol{1}[u\ge A]$

根据 Markov 不等式,我们有

$$\mathbb{E}_\theta[w(\psi_n^{-1}d(\hat{\theta}_n,\theta))]\ge w(A)\cdot\mathbb{P}_\theta[\psi_{n}^{-1}d(\hat{\theta}_n,\theta)\ge A]=w(A)\cdot\mathbb{P}_\theta[d(\hat{\theta}_n,\theta)\ge s]$$

其中 $s=s_n=A\psi_n$

放缩至有限空间

取 $\Theta$ 中的一个有限子集 $\{\theta_0,\ldots,\theta_M\}$,我们有

$$\inf\limits_{\hat{\theta}_n}\sup\limits_{\theta\in \Theta}\mathbb{P}_\theta[d(\hat{\theta}_n,\theta)\ge s]\ge \inf\limits_{\hat{\theta}_n}\sup\limits_{\theta\in \{\theta_1,\ldots,\theta_m\}}\mathbb{P}_\theta[d(\hat{\theta}_n,\theta)\ge s]$$

构造 $2s-$ 可分子集

取合适的 $\theta_0,\ldots,\theta_m$ 使得 $d(\theta_i,\theta_j)\ge 2s,\ i\neq j$

定义 $\psi^\ast : X^n\rightarrow\{0,1,\ldots,M\} =\arg\min\limits_{0\leq i\leq M} d(\hat{\theta}_n,\theta_i)$

那么有 $$\mathbb{P}_{\theta_j}[d(\hat{\theta}_n,\theta)\ge s]\ge\mathbb{P}_{\theta_j}[\psi^\ast\neq j],\ j=0,1,\ldots,M$$

为方便,以后记 $\mathbb{P}_{\theta_j}\overset{\Delta}{=}\mathbb{P}_j$, $p_{err, M}\overset{\Delta}{=}\inf\limits_\psi\max\limits_{0\le j\le M} \mathbb{P}_j(\psi\neq j)$

至此,如果我们能证明 $p_{err,M}\ge c’$ 其中 $c’$ 为一个常数,则

$$\underset{n\to\infty}{\lim\inf}\ \inf\limits_{\hat{\theta}_n}\ \sup\limits_{\theta\in\Theta}\mathbb{E}_\theta[w(\psi_n^{-1}d(\hat{\theta}_n,\theta))]\ge w(A)c’>0​$$

总结

至此,我们得到了一个有效的检验框架:我们会构造一系列 $\theta_i$,然后验证下面几个条件

  • $\theta_i$ 落在我们讨论的空间里
  • $\theta_i$ 是 $2s$ 可分的
  • 我们找到 $p_{err,M}$ 的一个常数下界

这样,我们就得到了一个收敛速度的下界,它和 $s$ 是同阶的。
在接下来的两章里,我们将会分别考虑两点测试和多点测试,并看如何构造 $\theta_i$,并利用他们的性质刻画出 $p_{err,M}$ 的一个下界。