多点测试的框架

类似的，我们首先取合适的 \(\theta_0,\ldots,\theta_M\)，然后依次检验

  • \(\theta_i\in\Theta\)
  • \(d(\theta_i,\theta_j)\ge 2s,(i\neq j)\)
  • \(\dfrac{1}{M}\sum_{i=1}^{M}KL(\mathbb{P}_i,\mathbb{P}_0)\leq \alpha\log M，\alpha<1/8​\) 或 \(\dfrac{1}{M}\sum_{i=1}^{M}\chi^2(\mathbb{P}_i,\mathbb{P}_0)\leq\alpha M,0<\alpha<1/2​\)

并定义 \(\psi^\ast=\arg\limits_{i}\min d(\widehat{\theta_n},\theta_i)​\)

其推导过程和之前介绍的完全一致

\[\begin{align}\inf\limits_{\widehat{\theta}_n}\sup\limits_{\theta\in\Theta}\mathbb{E}_\theta[d(\widehat{\theta}_n,\theta)]&\ge\inf\limits_{\widehat{\theta}_n}\sup\limits_{\theta\in\Theta}s\cdot\mathbb{P}_\theta[d(\widehat{\theta}_n,\theta)\ge s]\\&\ge \inf\limits_{\widehat{\theta}_n}\max\limits_{\theta\in\{\theta_0,\ldots,\theta_M\}}s\cdot P_\theta[d(\widehat{\theta}_n,\theta)\ge s]\\&=\inf\limits_{\widehat{\theta}_n}\max\limits_{j\in\{0,\ldots,M\}}s\cdot \mathbb{P}_{j}[d(\widehat{\theta}_n,\theta_j)\ge s]\\&\ge \inf\limits_{\widehat{\theta}_n}\max\limits_{\theta\in\{\theta_0,\ldots,\theta_M\}}s\cdot\mathbb{P}_{j}(\psi^\ast\neq j)\\&\ge s\cdot p_{err,M}\end{align}\]

随后自然就是控制 \(p_{err,M}\) 的一个下界。下面的证明自然是给出第三条关于 \(KL\) 或者 \(\chi^2\) 的约束后，其下界大于 0。

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

完全仿照 两点测试 中的做法，我们很自然地将其推广到 \(M>1​\) 的形式，为

\[p_{err,M}\ge\sup\limits_{\tau>0}\frac{\tau M}{1+\tau M}\left[\frac{1}{M}\sum_{j=1}^{M}\mathbb{P}_j[\frac{P_0}{P_j}\ge\tau]\right]\]

其证明思路类似，证明思路类似，记 \(A_j=\left\{\frac{P_0}{P_j}\ge\tau\right\}\)，则有

\[\begin{align} \mathbb{P} _ { 0 } [\psi \neq 0 ] & = \sum _ { j = 1 } ^ { M } \mathbb{P} _ { 0 } [\psi = j ]\\ & \geq \sum _ { j = 1 } ^ { M } \tau \mathbb{P} _ { j } \left[\{ \psi = j \} \cap A _ { j } \right] \\ & \geq \tau M \left( \frac { 1 } { M } \sum _ { j = 1 } ^ { M } \mathbb{P} _ { j } [ \psi = j ]\right) - \tau \sum _ { j = 1 } ^ { M } \mathbb{P} _ { j } [ A _ { j } ^ { c } ] \\ & \overset{\Delta}{=} \tau M \left( p' - \alpha \right) \end{align}​\]

其中 \(p'= \frac { 1 } { M } \sum _ { j = 1 } ^ { M } \mathbb{P} _ { j } [\psi = j ] , \quad \alpha = \frac { 1 } { M } \sum _ { j = 1 } ^ { M } \mathbb{P} _ { j } \left[\frac { p_0(x) } { p_j(x) } < \tau \right]\)

于是

\[\begin{align} \max _ { 0 \leq j \leq M } \mathbb{P} _ { j } [ \psi \neq j ] & = \max \left\{ \mathbb{P} _ { 0 } [ \psi \neq 0 ] , \max _ { 1 \leq j \leq M } \mathbb{P} _ { j } [ \psi \neq j ] \right\} \\ & \geq \max \left\{ \tau M \left( p'- \alpha \right) , \frac { 1 } { M } \sum _ { j = 1 } ^ { M } \mathbb{P} _ { j } [ \psi \neq j ]\right\} \\ & \geq \max \left\{ \tau M \left( p' - \alpha \right) , 1 - p' \right\} \\ & \geq \min _ { 0 \leq p \leq 1 } \max \{ \tau M ( p - \alpha ) , 1 - p \} \\ & = \frac { \tau M ( 1 - \alpha ) } { 1 + \tau M } \end{align}\]

至此都是 \(M=1\) 平凡的推广，现在我们利用散度来得到更精细的刻画

\(KL\) 散度

如果我们有 \(\dfrac{1}{M}\sum_{j=1}^{M}KL(\mathbb{P}_j,\mathbb{P}_0)\leq\alpha_\ast<\infty​\)，那么

\[\begin{align}p_{err,M}\ge\sup_{0<\tau<1}\left[\frac{\tau M}{1+\tau M}\left(1+\frac{\alpha_\ast + \sqrt{\alpha_\ast/2}}{\log\tau}\right)\right]\end{align}​\]

要证明这个，等价于证明

\[\begin{align}\frac { 1 } { M } \sum _ { j = 1 } ^ { M } \mathbb{P} _ { j } \left[ \frac { p_0(x) } { p_j(x) } \geq \tau \right]\ge 1-\alpha',\quad\alpha'\overset{\Delta}{=}-\frac{\alpha_\ast+\sqrt{\alpha_\ast/2}}{\log \tau}\end{align}\]

而这是因为

\[\begin{align}\mathbb{P}_j\left[\frac{p_0(x)}{p_j(x)}\ge \tau\right]&=\mathbb{P}_j\left[\frac{p_j(x)}{p_0(x)}\leq \frac{1}{\tau}\right]\\&=1-\mathbb{P}_j\left[\frac{p_j(x)}{p_0(x)}> \frac{1}{\tau}\right]\\&=1-\mathbb{P}_j\left[\log\frac{p_j(x)}{p_0(x)}>\log \frac{1}{\tau}\right]\\&\ge1-\frac{1}{\log (1/\tau)}\mathbb{E}_{p_j}\left(\log\frac{p_j(x)}{p_0(x)}\right)_+\\&\ge1-\frac{1}{\log(1/\tau)}[KL(\mathbb{P}_0,\mathbb{P}_j)+\sqrt{KL(\mathbb{P}_0,\mathbb{P}_j)/2}]\end{align}\]

其中第四行的不等号使用了 Markov 不等式，第五行的不等式是因为

\[KL(\mathbb{P}_j,\mathbb{P}_0)=\mathbb{E}_{p_j}\log\frac{p_j(x)}{p_0(x)}=\mathbb{E}_{p_j}\left(\log\frac{p_j}{p_0}\right)_+-\mathbb{E}_{p_j}\left(\log\frac{p_j}{p_0}\right)_-\]

而 \(log x\leq x-1​\) 所以有

\[\begin{align}\mathbb{E}_{p_j}\left(\log\frac{p_j}{p_0}\right)_-&=\int_{p_j(x)<p_0(x)}p_j(x)\log\frac{p_0(x)}{p_j(x)}\,\mathrm{d}x\\&\leq\int_{p_j(x)<p_0(x)}p_j(x)(\frac{p_0(x)}{p_j(x)}-1)\,\mathrm{d}x\\&\leq V(\mathbb{P}_j,\mathbb{P}_0)\leq\sqrt{KL(\mathbb{P}_j,\mathbb{P}_0)/2}\end{align}\]

同时 Jensen 不等式指出

\[\frac{1}{M}\sum_{j=1}^{M}\sqrt{KL(\mathbb{P}_0,\mathbb{P}_j)}\leq\sqrt{\frac{1}{M}\sum_{j=1}^{M}KL(\mathbb{P}_0,\mathbb{P}_j)}\leq\sqrt{\alpha_\ast}\]

所以我们有

\[\begin{align}\frac{1}{M}\sum_{j=1}^{M}\mathbb{P}_j\left[\frac{p_0}{p_j}\ge\tau\right]\ge1-\frac{\alpha_\ast+\sqrt{\alpha_\ast/2}}{\log(1/\tau)}\end{align}\]

因此，取 \(\tau=M^{-1/2}​\)，只要有 \(\dfrac{1}{M}\sum_{i=1}^{M}KL(\mathbb{P}_i,\mathbb{P}_0)\leq \alpha\log M，\alpha<1/8​\) 就有

\[p_{err,M}\ge\dfrac{\sqrt{M}}{1+\sqrt{M}}(1-2\alpha-\sqrt{\dfrac{2\alpha}{\log M}})\ge\dfrac{\sqrt{M}}{1+\sqrt{M}}(1-\dfrac{1}{4}-\dfrac{1}{2}\sqrt{\dfrac{1}{\log 2}})>0\]

\(\chi^2\)

如果我们有 \(\dfrac{1}{M}\sum_{j=1}^{M}\chi^2(\mathbb{P}_j,\mathbb{P}_0)\leq\alpha_\ast<\infty​\)，那么

\[p_{err,M}\ge\sup\limits_{0<\tau<1}\left[\dfrac{\tau M}{1+\tau M}\big(1-\tau(\alpha_\ast+1)\big)\right]\]

这个证明就相对直接许多了，只需注意到

\[\begin{align}\mathbb{P}_j\left[\dfrac{p_0(x)}{p_j(x)}\ge\tau\right]&=1-\mathbb{P}_j\left[\dfrac{p_j(x)}{p_0(x)}>\dfrac{1}{\tau}\right]\\&=1-\int \dfrac{p_j(x)}{p_0(x)}\cdot I\left[\dfrac{p_j(x)}{p_0(x)}>\dfrac{1}{\tau}\right]\cdot p_0(x)\,\mathrm{d}x\\&\ge1-\tau\int\left(\dfrac{p_j(x)}{p_0(x)}\right)^2p_0(x)\,\mathrm{d}x=1-\tau\big(\chi^2(\mathbb{P}_j,\mathbb{P}_0)+1\big)\end{align}\]

于是 \(\dfrac{1}{M}\sum_{j=1}^{M}\mathbb{P}_j\left[\dfrac{p_0(x)}{p_j(x)}\ge\tau\right]\ge1-\tau(\alpha_\ast+1)\), 即得到 \(p_{err,M}\) 的下界

因此，取 \(\tau=M^{-1}\)，只要 \(\dfrac{1}{M}\sum_{i=1}^{M}\chi^2(\mathbb{P}_i,\mathbb{P}_0)\leq\alpha M,0<\alpha<1/2\)，就有

\[p_{err,M}\ge\dfrac{1}{2}(1-\alpha-M^{-1})>0\]

至此，我们给出了多点测试的框架。下面以两个例子作为结束

一个成功的例子 \(L_{\infty}\) risk

我们考察非参数回归模型，使用 \(L_{\infty}\) risk, 即 \(d(f,g)=\sup\limits_{x\in[0,1]}\lvert f(x)-g(x)\rvert\) ，我们要证明当函数空间为 \(\Sigma(\beta,L)\) 时，收敛速度下界为 \((\log n/n)^{\beta/(2\beta+1)}\)

构造多点测试

取\(M=h^{-1},x_j=\frac{j-0.5}{M}\)，即将 \([0,1]\) 划分为 \(M\) 段。(读者可能注意到这样取是有问题的——至少也应该加个上取整吧？这里我们为方便先进行推导，后面再严格地限定 \(h\) 好补上这一瑕疵)

取 \(\theta_0(x)\equiv 0, \theta_j(x)=Lh^\beta K\left(\frac{x-x_j}{h}\right),(1\leq j\leq M)\)，不难发现 \(\theta_j(1\le j\le M)\) 彼此支撑集不相交，且 \(d(\theta_i,\theta_j)=\lVert \theta_i-\theta_j\rVert_\infty=Lh^\beta K_\max\)

选择合适的 \(h\)

根据我们的目标，我们需要 \(h\sim(\log n/n)^{1/2\beta+1}\)，故 \(h,M\) 的选取为 \[M=\left\lceil c_0\left(\dfrac{n}{\log n}\right)^{ \frac{1}{2\beta+1}}\right\rceil, h=M^{-1}\] 这里就使得 \(M\) 为整数了。\(c_0\)可以任意选取，但在后面我们会对其加以限制来达到证明的目的。

寻找 \(p_{err,M}\) 的下界

而 \(KL(\mathbb{P}_{\theta_j}, \mathbb{P}_{\theta_0})=\frac{1}{2}\sum_{k=1}^{n}\theta_j(x_k)^2​\)，则

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

虽然看似是一个二重的求和，但由于每个样本 \(x_k​\) 至多落入一个 \([x_j-h/2,x_j+h/2)​\) 中，故后面的求和至多仍为 \(n​\)，所以

\[\frac{1}{M}\sum_{j=1}^{M} KL(P_{\theta_j},P_{\theta_0})\leq\frac{1}{2}L^2h^{2\beta+1}K_\max^2 n\leq c\cdot c_0^{-(2\beta+1)}\cdot\log n \]

而 \(\log M\ge\log(c_0)+\frac{1}{2\beta+1}\log\frac{n}{\log n}\ge\frac{\log n}{2\beta+2}\), 因为我们可以将 \(c_0\) 取充分大，而\(-\log\log n\) 相比 \(\log n\) 当 \(n\) 充分大时总能被忽略，故该放缩成立。

所以总能做到 \[\frac{1}{M}\sum_{j=1}^{M} KL(P_{\theta_j},P_{\theta_0})\leq\alpha\log M<1/8\log M\]

另一个成功的例子—— \(L_2\) risk

我们依然考察非参数回归模型，但使用 \(L_2\) risk，即 \(d(f,g)=\lVert f-g\rVert_2=\sqrt{\int_0^1(f(x)-g(x))^2\,\mathrm{d}x}\) 。我们要证明当函数空间为 \(\Theta=\Sigma(\beta,L)\) 时，我们的收敛速度下界为 \(n^{-\beta/(2\beta+1)}\)

构造多点测试

首先类似地取 \(m=\lceil c_0n^{-\frac{1}{2\beta+1}}\rceil, h=m^{-1},x_k=\frac{k-1/2}{m},\varphi_k(x)=Lh^\beta K\left(\frac{x-x_k}{m}\right)\)

而 \(\varphi_k\in\Sigma(\beta,L/2)\)，是我们将会使用的一组基。

考虑二元向量的集合 \(\Omega=\{\omega=(\omega_1,\ldots,\omega_m),\omega_i\in\{0,1\}\}=\{0,1\}^m\)

而我们的测试 \(f\) 将会从 \(\mathcal{E}=\{f_\omega(x)=\sum_{k=1}^{m}w_k\varphi_k(x),\omega\in\Omega\}\) 选出。

首先可以得到

\[\begin{aligned} d \left( f _ { \omega } , f _ { \omega ^ { \prime } } \right) & = \left[ \int _ { 0 } ^ { 1 } \left( f _ { \omega } ( x ) - f _ { \omega ^ { \prime } } ( x ) \right) ^ { 2 } d x \right] ^ { 1 / 2 } \\ & = \left[ \sum _ { k = 1 } ^ { m } \left( \omega _ { k } - \omega _ { k } ^ { \prime } \right) ^ { 2 } \int _ {(k-1)/m }^{k/m} \varphi _ { k } ^ { 2 } ( x ) d x \right] ^ { 1 / 2 } \\ & = L h ^ { \beta + \frac { 1 } { 2 } } \| K \| _ { 2 } \left[ \sum _ { k = 1 } ^ { m } \left( \omega _ { k } - \omega _ { k } ^ { \prime } \right) ^ { 2 } \right] ^ { 1 / 2 } \\ & = L h ^ { \beta + \frac { 1 } { 2 } } \| K \| _ { 2 } \sqrt { \rho \left( \omega , \omega ^ { \prime } \right) } \end{aligned}\]

其中 \(\rho(\omega,\omega')\) 称为汉明距离，也就是两个二元向量中不相等的元素的个数。

我们首先证明，可以在 \(\Omega​\) 中找到不少于 \(M+1=2^{m/8}+1​\) 个点，彼此的汉明距离大于 \(m/8​\)。首先我们先找一个最少的点的集合 \(\omega_0,\ldots,\omega_M​\)，他们的 \(m/8​\) 邻域可以覆盖 \(\Omega​\)（可以考虑每次随机一个点，然后将其邻域内的点全部删除，直至不能找到更多的元素，并在此中选择一个最优的，即选出点最少的方案），即

\[\{0,1\}^m\subset\bigcup_{\omega_j}\{\omega\mid d(\omega,\omega_j)\leq m/8\}\]

则 \(2^m\leq (M+1)\sum_{j=0}^{\lfloor m/8\rfloor}\binom{m}{j}\)

然而 \(2^{-m}\sum_{j=0}^{\lfloor m/8\rfloor}\binom{m}{j}\mathbb{P}[\mathrm{Binom}(m,1/2)\leq\lfloor m/8\rfloor]\leq \exp\{-9m/32\}<2^{-m/4}​\)，该放缩由 Hoeffding Inequality 给出，其证明了对于独立的随机变量 \(a_i\leq Z_i\leq b_i​\) ，有不等关系 \[\mathbb{P}[\sum_{i=1}^{m}(Z_i-\mathbb{E}[Z_i])\ge t]\leq\exp(-2t^2/\sum_{i=1}^{m}(b_i-a_i)^2)​\]

所以 \(M+1\ge 2^{m/4}\ge 2^{m/8}+1,\ m\ge 8\)

所以我们可以选择出 \(M+1\) 个向量 \(\omega_0,\ldots,\omega_M\)，然后检验三个条件

  • \(f\in\Sigma(\beta,L)\)，这是因为 \(\varphi_k\in\Sigma(\beta,L/2)\)，彼此支撑集不交，且 \(\lvert w_i\rvert\leq 1\)
  • \(d(f_i,f_j)\ge 2s\) ，这是因为当 \(m\ge 8\) 时

\[\lVert f_j(x)-f_{k}(x)\rVert_2= Lh^{\beta+1/2}\lVert K\rVert_2\sqrt{\rho(\omega_j,\omega_k)}\ge Lh^{\beta+1/2}\lVert K\rVert_2\sqrt{m/16}=\frac{L}{4}\lVert K\rVert_2 m^{-\beta}\]

设 \(n\ge n_\ast=(7/c_0)^{2\beta+1}\)，则 \(m\ge 8\) 且 \(m^\beta\leq (1+1/7)^{\beta}c_0^{\beta}n^{\beta/(2\beta+1)}\leq (2c_0)^\beta n^{\beta/(2\beta+1)}\)

则 \(d(f_i,f_j)\ge 2s\)，其中 \(s=An^{-\beta/(2\beta+1)},A=\frac{L}{8}\lVert K\rVert_2(2c_0)^{-\beta}\)

  • \(\dfrac{1}{M}\sum_{i=1}^{M}KL(\mathbb{P}_i,\mathbb{P}_0)\leq \alpha\log M，\alpha<1/8\)

利用 两点测试 的成功例子中对于 \(KL\) 散度的放缩，我们有

\[\begin{align} KL\left(\mathbb{P}_{j}, \mathbb{P}_{0}\right) & \leq p_{*} \sum_{i=1}^{n} f_{j }^{2}\left(X_{i}\right) \leq p_{*} \sum_{k=1}^{m} \sum_{i : X_{i} \in \Delta_{k}} \varphi_{k}^{2}\left(X_{i}\right) \\ & \leq p_{*} L^{2} K_{\max }^{2} h_{}^{2 \beta} \sum_{k=1}^{m} \operatorname{Card}\left\{i : X_{i} \in \Delta_{k}\right\} \\ &=p_{*} L^{2} K_{\max }^{2} n h_{}^{2 \beta} \leq p_{*} L^{2} K_{\max }^{2} c_{0}^{-(2 \beta+1)} m \end{align}\]

而 \(M>2^{m/8}​\)，即 \(m<8\log M/\log 2​\)，于是我们可以选择 \(c_0=\left(\dfrac{8p_\ast L^2K_{\max}^2}{\alpha\log 2}\right)^{1/(2\beta+1)}​\) 使得 \(KL(\mathbb{P_j},\mathbb{P}_0)<\alpha\log M​\)