收敛速度的下界

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

核密度估计中的单点误差 \(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\)误差 $ C n^{-2/2+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_{\widehat{\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_{\widehat{\theta}_n}\ \sup\limits_{\theta\in\Theta}\mathbb{E}_\theta[w(\psi_n^{-1}d(\widehat{\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(\widehat{\theta}_n,\theta))]\ge w(A)\cdot\mathbb{P}_\theta[\psi_{n}^{-1}d(\widehat{\theta}_n,\theta)\ge A]=w(A)\cdot\mathbb{P}_\theta[d(\widehat{\theta}_n,\theta)\ge s]\]

其中 \(s=s_n=A\psi_n\)

放缩至有限空间

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

\[\inf\limits_{\widehat{\theta}_n}\sup\limits_{\theta\in \Theta}\mathbb{P}_\theta[d(\widehat{\theta}_n,\theta)\ge s]\ge \inf\limits_{\widehat{\theta}_n}\sup\limits_{\theta\in \{\theta_1,\ldots,\theta_m\}}\mathbb{P}_\theta[d(\widehat{\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(\widehat{\theta}_n,\theta_i)\)

那么有 \[\mathbb{P}_{\theta_j}[d(\widehat{\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_{\widehat{\theta}_n}\ \sup\limits_{\theta\in\Theta}\mathbb{E}_\theta[w(\psi_n^{-1}d(\widehat{\theta}_n,\theta))]\ge w(A)c'>0​\]

总结

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

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

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