两点测试的框架

给定问题后，我们构造出两个函数 \(\theta_0,\theta_1\)，然后检验

  • \(\theta_0,\theta_1\in\Theta\)
  • \(d(\theta_0,\theta_1)\ge 2s\)
  • \(KL(P_{\theta_0},P_{\theta_1})\leq\alpha\)

这样，我们就可以根据下面的推导得到 minimax risk 的阶是与 \(s\) 相同

\[\inf_{\widehat{\theta}}\sup_{\theta\in\Theta} E[d(\theta,\widehat{\theta})]\ge s\cdot p_{err,1}\]

\[p_{err,1}=\inf_\psi\max_{j=0,1} P_j(\psi\neq j)\ge\max\{\frac{1}{4}e^{-\alpha}, \frac{1-\sqrt{\alpha/2}}{2}\}\]

这里只是先将两点测试的框架拍出来——只要我们能给出 \(p_{err,1}\) 的一个良好的下届，我们就能给出 minimax rate 的一个下界。而且它的阶和 \(d(\theta_0,\theta_1)\) 是相同的，这也提示了我们如何选择良好的 \(\theta\)。

\(p_{err,1}\) 的下界

下面的记号中，\(p_i(x)​\) 表示第 \(i​\) 个分布的 p.d.f.，\(\mathbb{P}_i(I)=\int_I p_i(x)\,\mathrm{d}x​\) 表示区间 \(I​\) 上（或满足某一条件）的概率值。

可以看到在这样的测试框架中 \(p_{err,1}\) 的下界发挥着很重要的作用。我们先对他做一个估计。记 \(\mathbb{P}_1[\psi\neq 0]=p\)，则 \(\mathbb{P}_1[\psi\neq 1]=1-p\)。下考察 \(\mathbb{P}_0[\psi\neq 0]\)

\[\begin{align}\mathbb{P}_0[\psi\neq 0]&=\int \boldsymbol{1}[\psi\neq 0]p_0(x)\,\mathrm{d}x\\&=\int \boldsymbol{1}[\psi\neq 0] \frac{p_0(x)}{p_1(x)}p_1(x)\,\mathrm{d}x\\&\ge\int \tau \boldsymbol{1}[\psi\neq 0\cap \frac{p_0(x)}{p_1(x)}\ge\tau] p_1(x)\,\mathrm{d}x\\&\ge\tau\Bigg(\mathbb{P}_1[\psi\neq 0]-\mathbb{P}_1\bigg[\frac{p_0(x)}{p_1(x)}\leq\tau\bigg]\Bigg)\\&\overset{\Delta}{=}\tau(p-\alpha)\end{align}​\]

\[p_{err,1}=\inf\limits_\psi\max\limits_{j=0,1}\mathbb{P}_j[\psi\neq j]\ge\min\limits_{0\le p\leq 1}\{\tau(p-\alpha), 1-p)\}=\frac{\tau(1-\alpha)}{1+\tau}\]

注意此时 \(\tau​\) 是任取的，故可以得到

\[p_{err,1}\ge\sup\limits_{\tau}\frac{\tau(1-\alpha)}{1+\tau}=\sup\limits_\tau\left\{\frac{\tau}{1+\tau}\cdot\mathbb{P}_1\left[\frac{p_0(x)}{p_1(x)}\ge\tau\right]\right\}\]

一个失败的例子

我们先看一个失败的例子来加深我们操作这个框架的方法。

考虑模型 \(Y_i=f(i/n)+\varepsilon_i\)

设 \(f\in\Sigma(\beta,L),\beta=1\)，我们知道\[\mathbb{E}\lVert\widehat{f}_n-f\rVert_\infty\leq C(\log n/n)^{-1/3}\]

如果我们选取 \[\theta_0=f_0(x)\equiv 0,\quad \theta_1=f_1(x)=\sin(2\pi n x)/2\pi n\]

那么 \(f_0(i/n)=f_1(i/n)\)，则可以导出 \(p_0(x)=p_1(x)\)，所以

\[p_{err,1}=\sup\limits_\tau\{\frac{\tau}{1+\tau}\cdot\boldsymbol{1}[\tau\leq 1]\}=\frac{1}{2}\]

考虑无穷范数得 \[\lVert\theta_0-\theta_1\rVert_\infty=1/(2\pi n)=2s​\]

故 \(s=1/(4\pi n)\)，则 \(\inf\limits_{\widehat{\theta}_n}\sup\limits_{\theta\in\Theta} \mathbb{E}[d(\widehat{\theta}_n,\theta)]\ge s\cdot p_{err,1}=\frac{1}{8n\pi}\)

得 \(\psi_n​\) 和 \(1/n​\) 同阶，因此我们得到收敛速度的下界是 \(1/n​\)，这远远小于我们预期的 \((\log n/n)^{1/3}​\)，这主要是因为我们的 \(\theta_0,\theta_1​\) 选得不够好。但这也是因为我们求 \(p_{err,1}​\) 的下届的时候过于松散，没有充分发挥出选取 \(\theta_0,\theta_1​\) 的威力。因此我们需要一个更精细的 \(p_{err,1}​\) 的下界。

更加精细的构造

参考概率测度的度量一节，我们可以得到下列更精细的构造

  • 如果 \(\mathrm{TV}({p}_1,{p}_0)\leq\alpha <1​\), 则 \(p_{err,1}\ge\frac{1-\alpha}{2}​\)
  • 如果 \(\mathcal{H}^2(p_1,p_0)\leq\alpha <2​\), 则 \(p_{err,1}\ge\frac{1-\sqrt{\alpha(1-\alpha/4)}}{2}​\)
  • 如果 \(KL(p_1,p_0)\leq\alpha <1​\), 则 \(p_{err,1}\ge\max\{\frac{1}{4}e^{-\alpha},\frac{1-\sqrt{\alpha/2}}{2}\}​\)

通常使用 \(KL​\) 散度的形式来进行约束能够得到不错的效果，当然这还是取决于你设计的 \(\mathbb{P}​\) 的样式。下面给出一个成功的例子

一个成功的例子

考察非参数回归中单点 \(x_0\) 的误差的minimax risk，我们要证明其下界为 \(O(n^{-\beta/(2\beta+1)})\)

先回顾我们的问题

  • \(Y_i=f(X_i)+\varepsilon_i, i=1,2,\ldots,n\)，其中 \(f:[0,1]\to\mathbb{R}\)
  • \(\varepsilon_i\) 独立同分布于 \(p_\varepsilon(\cdot)\)，且 \(\exists p_\ast>0,v_0>0,\int p_\varepsilon(u)\log\frac{p_\varepsilon(u)}{p_\varepsilon(u+v)}\,\mathrm{d}u\leq p_\ast v^2\text{ for all }\lvert v\rvert\leq v_0\)。可以验证，\(\mathcal{N}(0,\sigma^2)\) 是满足这一条件的。下面的证明中使用了正态的 KL 散度来简化计算，更一般的情形下，直接用该式子进行放缩即能得到 \(KL\leq p_\ast\sum_{i=1}^{n}\theta_1(x_i)^2\) 然后殊途同归。
  • \(X_i\in[0,1]\) 且是 determinstic 的，且满足提到的假设 LP2，即存在实数 \(a_0>0\) 使得对任意区间 \(A\subseteq [0,1]\) 和所有的 \(n\geq 1\) ，均有 \(\sum\limits_{i=1}^{n}\boldsymbol{1}[X_i\in A]\leq a_0\max\{n\cdot\mathrm{Leb}(A), 1\}\)

我们的目标是给出 \((\Theta,d)\) 上的 minimax risk，其中函数空间为 \(\Theta=\Sigma(\beta,L),\beta>0,L>0\) ，距离度量 \(d(f,g)=\lvert f(x_0)-g(x_0)\rvert\)

为此，我们取，取 \(K_0(u)=e^{-\frac{1}{1-u^2}}\boldsymbol{1}(\lvert u\rvert\leq 1), K(u)=K_0(2u)\)，这是为了让其支撑集的长度(或者说宽度)为 \(1\)，方便后面的构造.

随后我们取 \(\theta_0(x)\equiv 0,\theta_1(x)=Lh^\beta K\left(\frac{x-x_0}{h}\right)\) ，不难验证其在 \(\Sigma(\beta,L)\) 中

且我们有 \(d(\theta_0,\theta_1)=Lh^\beta K_\max\ge 2s\) ，而我们希望 \(s=O(n^{-\beta/(2\beta+1)})\)

由此我们知我们的 \(h\) 应选取为 \(n^{-1/(2\beta+1)}\)

而 \(p_{\theta_0}=\prod_{j=1}^{n}\frac{1}{\sqrt{2\pi}}\exp\left\{-\frac{y_j^2}{2}\right\}\), \(p_{\theta_1}=\prod_{j=1}^{n}\frac{1}{\sqrt{2\pi}}\exp\left\{-\frac{(y_j-\theta_1(x_j))^2}{2}\right\}\)

由 KL 散度性质有对于标准正态分布 \(\varphi(x)​\)，有 \(KL(\varphi(x),\varphi(x+t))=t^2/2​\)

\[\begin{align}KL(p_{\theta_0}, p_{\theta_1})&=\sum_{j=1}^{n}KL(p_{\theta_0,j},p_{\theta_1,j})\\&=\frac{1}{2}\sum_{j=1}^{n}\theta_1^2(x_j)\\&=\frac{1}{2}L^2 h^{2\beta}\sum_{j=1}^{n}K^2\left(\frac{x_j-x_0}{h}\right)\\&\leq \frac{1}{2}L^2 h^{2\beta}K_\max^2\sum_{j=1}^{n}\boldsymbol{1}[\lvert x_j-x_0\rvert\leq h/2]\end{align}\]

由于 \(nh\ge 1​\)，加上假设(2) 有 \(\sum_{j=1}^{n}\boldsymbol{1}[\lvert x_j-x_0\rvert\leq h/2]\leq\max\{nh, 1\}=nh​\)

且 \(nh^{2\beta+1}=1\) 故 \(KL(p_{\theta_0}, p_{\theta_1})\leq \frac{1}{2}L^2h^{2\beta+1} n K_\max^2=\frac{1}{2}c'L^2K_\max^2<\infty\)

所以有

\[P_{err,1}\ge c\Rightarrow \inf_{\widehat{\theta}}\sup_{\theta\in\Theta} E[d(\theta,\widehat{\theta})]\ge s\cdot P_{err,1}=c\frac{Lh^\beta K_\max}{2}=c'n^{-\beta/(2\beta+1)}\]

于是我们得到了结论，在上述假设下，\(\forall x_0\in[0,1]\) ，单点误差的 minimax risk 为 \(O(n^{-\beta/(2\beta+1)})\)