Fano 不等式与 Le Cam 方法

统计学的下界证明有一个几乎统一的套路：先把估计问题换成一个检验问题，再证明这个检验问题很难。

设 $X_1,\dots,X_n\sim N(\theta,1)$ ，要估计 $\theta$ 。样本均值给出风险 $1/n$ 。这个 $1/n$ 是不是最优的？也就是说，是否存在某个估计量，能让最坏情况下的风险比 $1/n$ 更小？Le Cam 的两点方法给出的回答是：不存在。它的论证只用了两个候选参数 $\theta_0=0$ 与 $\theta_1=\Delta$ ——如果连这两个点都分不清，那就更不可能把 $\theta$ 估准。

本文介绍这套语言里最常用的三个工具：Le Cam 的两点方法、Fano 不等式，以及 Assouad 的超立方体引理。三者的共同点是：先选一个有限的「困难子问题」，把估计下界转化为检验下界，再用总变差、KL 散度或互信息来度量「有多难分」。

一、极小极大：下界在说什么

一个估计量 $\hat\theta$ 的优劣，通常用它的风险衡量：在真实参数为 $\theta$ 时， $\hat\theta$ 的平均损失。但真实参数是未知的，所以我们不能只关心某一个 $\theta$ 下的风险。极小极大（minimax）的立场是：先让大自然挑一个最不利的 $\theta$ ，再让统计学家挑估计量，看统计学家能保证什么。

用博弈的话说，极小极大风险是

\inf_{\hat\theta}\sup_{\theta\in\Theta}\ \mathbb E_{P_\theta}\bigl[\ell(\theta,\hat\theta)\bigr].

这个量回答的是：在所有可能的参数中，最坏情况下的风险最小能压到多少。 一个上界对应一个具体的估计量；一个下界则对应一句否定：无论你多聪明，都不可能比这个数更好。

下界为什么难？因为你要同时对所有估计量说话。逐一检查是不可能的。所以下界证明总是走同一条路：把参数空间缩小到一个有限的、精心挑选的子集，使得在这个子集上「区分参数」本身就已经很难；如果区分都做不到，估计就更做不到。

这就是「归约到检验」。接下来的三种方法，区别只在于子集有多大、用什么距离度量「难分」。

二、决策论框架

2.1 模型、损失与风险

设 $\{P_\theta:\theta\in\Theta\}$ 是样本空间 $\mathcal X$ 上的一族分布，参数空间 $\Theta$ 可以是任意集合。我们观测 $n$ 个独立同分布的样本

X^n=(X_1,\dots,X_n)\sim P_\theta^{\otimes n},

一个估计量是任意可测映射 $\hat\theta:\mathcal X^n\to\Theta$ 。损失函数 $\ell:\Theta\times\Theta\to[0,\infty)$ 度量估计值 $\hat\theta$ 与真值 $\theta$ 的差距，常用的有：

平方损失 $\ell(\theta,\hat\theta)=\lVert\theta-\hat\theta\rVert_2^2$ ；
绝对损失 $\ell(\theta,\hat\theta)=\lVert\theta-\hat\theta\rVert_1$ ；
$0$ - $1$ 损失 $\ell(\theta,\hat\theta)=\mathbf 1[\theta\neq\hat\theta]$ 。

估计量 $\hat\theta$ 在 $\theta$ 处的风险是

R_\theta(\hat\theta)=\mathbb E_{P_\theta^{\otimes n}}\bigl[\ell(\theta,\hat\theta(X^n))\bigr].

注意这里的期望是对数据取的， $\theta$ 固定。极小极大风险则再对 $\theta$ 取最坏情况：

\mathfrak M_n(\Theta,\ell)=\inf_{\hat\theta}\sup_{\theta\in\Theta}R_\theta(\hat\theta).

2.2 一个先验视角

极小极大风险有一个贝叶斯下界。对任意 $\Theta$ 上的先验 $\pi$ ，记贝叶斯风险为

\mathfrak B_n(\pi)=\inf_{\hat\theta}\int R_\theta(\hat\theta)\,\pi(d\theta).

由于「积分 ≤ 最大值」，

\mathfrak B_n(\pi)\le \mathfrak M_n(\Theta,\ell).

所以，任何一个先验下的贝叶斯风险，都是极小极大风险的下界。这个观察非常有用：下界证明往往先选一个先验（通常是有限集上的均匀分布），再算贝叶斯风险。Le Cam 与 Fano 本质上都是在做这件事，只是把贝叶斯风险进一步转化成了检验误差。

2.3 归约到有限子问题

对任意有限子集 $\Theta_0=\{\theta_1,\dots,\theta_M\}\subseteq\Theta$ ，

\mathfrak M_n(\Theta,\ell)\ge \mathfrak M_n(\Theta_0,\ell).

所以我们只需要在一个有限问题上证明下界。有限问题可以看成一场 $M$ 元检验：自然以某个先验选出 $\theta_K$ ，统计学家看到数据后要猜出 $K$ 。如果连「猜出是哪一个」都做不到，那么「把 $\theta$ 估到很小的损失」当然也做不到。

把这句话写成不等式，就是 Le Cam 与 Fano 的工具。

三、Le Cam 两点方法

3.1 定理与证明

先看最简单的情形：只有两个候选参数。

定理 3.1（Le Cam 两点方法） 设 $\theta_0,\theta_1\in\Theta$ ， $\ell(\theta_0,\theta_1)\ge 2\delta$ ，且 $\ell$ 满足三角不等式。则对任意估计量 $\hat\theta$ ，
$\max_{i=0,1}\ \mathbb E_{P_i^{\otimes n}}\bigl[\ell(\theta_i,\hat\theta)\bigr] \ge \frac{\delta}{2}\Bigl(1-\bigl\lVert P_0^{\otimes n}-P_1^{\otimes n}\bigr\rVert_{\mathrm{TV}}\Bigr).$

证明只用一个测试。令

\psi=\mathbf 1\Bigl[\ell(\theta_0,\hat\theta)\ge\delta\Bigr].

在事件 $\{\psi=0\}$ 上， $\ell(\theta_0,\hat\theta)<\delta$ ，由三角不等式

\ell(\theta_1,\hat\theta)\ge \ell(\theta_0,\theta_1)-\ell(\theta_0,\hat\theta)>2\delta-\delta=\delta.

于是

\mathbb E_{P_0}\ell(\theta_0,\hat\theta)\ge \delta\,P_0(\psi=1), \qquad \mathbb E_{P_1}\ell(\theta_1,\hat\theta)\ge \delta\,P_1(\psi=0).

两式相加：

\mathbb E_{P_0}\ell(\theta_0,\hat\theta)+\mathbb E_{P_1}\ell(\theta_1,\hat\theta) \ge \\ \delta\bigl[1+P_0(\psi=1)-P_1(\psi=1)\bigr] \ge \\ \delta\bigl(1-\lVert P_0-P_1\rVert_{\mathrm{TV}}\bigr).

最后，最大值不小于平均值，得到 $\delta(1-\mathrm{TV})/2$ 。证毕。

如果取 $0$ - $1$ 损失、 $\delta=1/2$ ，就得到最常见的检验形式：

\inf_{\hat\theta}\max_{i=0,1}\ P_i^{\otimes n}\bigl(\hat\theta\neq\theta_i\bigr) \ge \frac12\Bigl(1-\bigl\lVert P_0^{\otimes n}-P_1^{\otimes n}\bigr\rVert_{\mathrm{TV}}\Bigr).

这个式子的意思是：两个分布的总变差越小，任何检验的错误率就越接近 $1/2$ 。 当 $P_0=P_1$ 时，错误率至少是 $1/2$ ，这当然——数据里根本没有信息。

定理 3.1 要求 $\ell$ 满足三角不等式，平方损失并不满足。对平方损失，有一个常数稍有不同的版本。设 $\Delta=\lVert\theta_0-\theta_1\rVert_2^2$ ，则

\max_{i=0,1}\mathbb E_{P_i^{\otimes n}}\lVert\theta_i-\hat\theta\rVert_2^2 \ge \frac{\Delta}{4}\bigl(1-\lVert P_0^{\otimes n}-P_1^{\otimes n}\rVert_{\mathrm{TV}}\bigr).

证明用贝叶斯视角。取均匀先验，平方损失下的贝叶斯估计是后验均值

\hat\theta_B(X^n)=\pi(X^n)\theta_0+(1-\pi(X^n))\theta_1, \\ \pi(X^n)=\Pr(\theta=\theta_0\mid X^n).

其风险为 $\Delta\,\mathbb E[\pi(X^n)(1-\pi(X^n))]$ 。由 $\pi(1-\pi)\ge\frac12\min(\pi,1-\pi)$ 与均匀先验下贝叶斯检验误差的下界 $\mathbb E[\min(\pi,1-\pi)]\ge\frac12(1-\mathrm{TV})$ ，风险至少是 $\frac{\Delta}{4}(1-\mathrm{TV})$ 。极小极大风险不小于贝叶斯风险，得证。

3.2 从 TV 到 KL

总变差通常不好直接算，尤其对乘积分布。Pinsker 不等式把它换成 KL 散度：

\lVert P-Q\rVert_{\mathrm{TV}}\le\sqrt{\frac12 D_{\mathrm{KL}}(P\Vert Q)}.

而 KL 对乘积分布是可加的：

D_{\mathrm{KL}}\bigl(P_0^{\otimes n}\Vert P_1^{\otimes n}\bigr)=n\,D_{\mathrm{KL}}(P_0\Vert P_1).

代入定理 3.1：

\max_{i=0,1}\mathbb E_{P_i^{\otimes n}}\ell(\theta_i,\hat\theta) \ge \frac{\delta}{2}\left(1-\sqrt{\frac{n}{2}D_{\mathrm{KL}}(P_0\Vert P_1)}\right).

这个式子把下界拆成了两个因子：损失间隔 $\delta$ ，和信息量 $nD_{\mathrm{KL}}$ 。要让下界为正，必须 $\frac n2D_{\mathrm{KL}}<1$ ；换句话说，如果两个分布在这个样本量下已经能被可靠地区分，两点方法就给不出非平凡的下界了。

这也解释了为什么下界里的样本量总以「 $n\times$ 单样本信息」的形式出现：独立样本的信息是线性累加的。

3.3 一个例子：Bernoulli 均值

设 $X_i\sim\mathrm{Ber}(p)$ ， $p\in\{1/2,1/2+\Delta\}$ ，损失为平方损失。两个分布的单样本 KL 是

D_{\mathrm{KL}}\Bigl(\mathrm{Ber}\bigl(\tfrac12\bigr)\Big\Vert\mathrm{Ber}\bigl(\tfrac12+\Delta\bigr)\Bigr) \\ =-\frac12\log\bigl(1-4\Delta^2\bigr) \approx 2\Delta^2 \qquad(\Delta\to0).

由 Pinsker， $n$ 个样本的总变差至多 $\Delta\sqrt n$ 。取 $\Delta=1/(2\sqrt n)$ ，则 $\Delta\sqrt n=1/2$ ，平方损失的版本给出

\max_i\mathbb E\bigl[(p_i-\hat p)^2\bigr] \ge \frac{\Delta^2}{4}\left(1-\frac12\right) =\frac{1}{32n}.

所以 Bernoulli 均值的极小极大速率是 $1/n$ 。这个结论不稀奇，但推导方式值得记住：我们只用了两个点，就把「 $1/n$ 不可能被突破」这件事证明完了。

3.4 两点方法的局限

两点方法简单、常数清楚，但它只能看见一个方向。考虑 $d$ 维高斯均值：

X_1,\dots,X_n\sim N(\theta,\sigma^2 I_d),\qquad \theta\in\mathbb R^d.

如果只取 $\theta_0=0$ 、 $\theta_1=a e_1$ ，那么 KL 是 $n a^2/(2\sigma^2)$ ，Le Cam 给出的下界是 $a^2/4$ 的量级，取 $a\asymp\sigma/\sqrt n$ 后只有 $1/n$ 。但真实的极小极大风险是 $\sigma^2d/n$ ——差了整整一个 $d$ 。

原因很直接：两点方法只探测了一个坐标方向，而 $d$ 维问题的困难来自 $d$ 个方向同时存在的不确定性。要捕捉这一点，需要让假设集合随着 $d$ 指数增长。这就是 Fano 不等式和 Assouad 引理的用武之地。

四、Fano 不等式

4.1 信息论形式

定理 4.1（Fano 不等式） 设 $K$ 在 $\{1,\dots,M\}$ 上均匀分布， $X$ 的分布依赖于 $K$ ， $\hat K=\hat K(X)$ 是任意估计。记 $P_e=\Pr(\hat K\neq K)$ ，则
$P_e\ge 1-\frac{I(K;X)+\log 2}{\log M},$
其中 $I(K;X)$ 是互信息。

证明分两步。第一步是条件熵的界：

H(K\mid \hat K)\le h(P_e)+P_e\log(M-1)\le \log 2+P_e\log M,

其中 $h(P_e)\le\log 2$ 是二元熵的最大值。第二步是数据处理不等式：

H(K\mid \hat K)\ge H(K\mid X)=H(K)-I(K;X)=\log M-I(K;X).

两式合并，整理即得。

这个不等式有一个很直观的读法：如果 $X$ 几乎不包含关于 $K$ 的信息（ $I\approx0$ ），那么任何猜测的错误率至少是 $1-\log 2/\log M$ ，当 $M$ 很大时接近 $1$ ，也就是接近「瞎猜」。 反过来，要让错误率小，互信息必须达到 $\log M$ 的量级——你需要至少 $\log M$ 奈特的信息才能区分 $M$ 个等可能的选择。

4.2 从检验到估计

把 Fano 用在极小极大下界上，需要一个把「损失」翻译成「猜错」的分离条件。

定理 4.2（Fano 方法，度量形式） 设 $d$ 是 $\Theta$ 上的度量， $\theta_1,\dots,\theta_M\in\Theta$ 满足
$d(\theta_i,\theta_j)\ge 2\delta\qquad(i\neq j).$
令 $K\sim\mathrm{Unif}\{1,\dots,M\}$ ， $X\sim P_{\theta_K}$ 。则对任意估计量 $\hat\theta$ ，
$\frac1M\sum_{i=1}^M\mathbb E_{P_i}\bigl[d(\theta_i,\hat\theta)\bigr] \ge \delta\left(1-\frac{I(K;X)+\log 2}{\log M}\right).$
特别地，若 $I(K;X)\le\beta$ ，则
$\max_i\mathbb E_{P_i}\bigl[d(\theta_i,\hat\theta)\bigr] \ge \delta\left(1-\frac{\beta+\log 2}{\log M}\right).$

证明的关键是一个解码论证。定义最近点解码

\hat K=\arg\min_{i}d(\hat\theta,\theta_i).

若 $d(\theta_K,\hat\theta)<\delta$ ，则对任意 $j\neq K$ ，

d(\hat\theta,\theta_j)\ge d(\theta_K,\theta_j)-d(\theta_K,\hat\theta)>2\delta-\delta=\delta>d(\theta_K,\hat\theta),

所以 $K$ 是唯一的最小值点， $\hat K=K$ 。因此

\{d(\theta_K,\hat\theta)<\delta\}\subseteq\{\hat K=K\},

从而 $P_e\le \Pr(d(\theta_K,\hat\theta)\ge\delta)$ 。于是

\mathbb E\bigl[d(\theta_K,\hat\theta)\bigr] \ge \delta\,\Pr\bigl(d\ge\delta\bigr) \ge \delta\,P_e \ge \delta\left(1-\frac{I+\log 2}{\log M}\right).

左边正是 $M$ 个风险的平均，平均不超过最大，定理得证。

对平方损失 $\ell=d^2$ ，同样的解码论证把 $d$ 换成 $\sqrt{\ell}$ 。若平方间隔为 $\Delta$ ，即 $d(\theta_i,\theta_j)\ge\sqrt{\Delta}$ ，则取 $\delta=\sqrt{\Delta}/2$ ，得到

\frac1M\sum_i\mathbb E\bigl[\ell(\theta_i,\hat\theta)\bigr] \ge \frac{\Delta}{4}\left(1-\frac{I(K;X)+\log 2}{\log M}\right).

这里用了 $\{d<\delta\}$ 蕴含解码正确，因此 $\mathbb E[d^2]\ge\delta^2\Pr(d\ge\delta)\ge\delta^2P_e$ 。平方损失的常数是 $\Delta/4$ ，与 Le Cam 的平方损失版本一致。本文后面的例子只关心速率，常数不影响结论。

剩下的任务是把互信息控制住。由定义，

I(K;X)=\frac1M\sum_{i=1}^M D_{\mathrm{KL}}\bigl(P_i\Vert \bar P\bigr), \qquad \bar P=\frac1M\sum_{i=1}^M P_i.

再用 KL 对第二个变量的凸性，

I(K;X)\le \frac1{M^2}\sum_{i,j=1}^M D_{\mathrm{KL}}(P_i\Vert P_j) \le \max_{i,j}D_{\mathrm{KL}}(P_i\Vert P_j).

如果每个 $P_i$ 都是 $n$ 个独立样本的分布，那么成对 KL 是单样本 KL 的 $n$ 倍。这样，Fano 下界就变成了「 $\log M$ 与 $n\times$ KL 的竞争」。

4.3 广义 Fano 与局部版本

定理 4.2 常被称为广义 Fano 不等式。它的使用可以总结成一句口诀：

\boxed{\ \text{只要}\ \log M\ \gg\ n\cdot \max_{i,j}D_{\mathrm{KL}}(P_i\Vert P_j),\ \text{就有}\ \mathfrak M_n\gtrsim\delta.\ }

这里 $M$ 是「用 $\delta$ 分开的假设个数」，也就是损失空间里的打包数（packing number）。于是下界问题变成了一个几何问题：在参数空间里能放多少个半径为 $\delta$ 的小球，同时又让它们在 KL 意义下足够接近？

Yang 与 Barron 的版本直接用 $I(K;X)=\frac1M\sum_i D_{\mathrm{KL}}(P_i\Vert\bar P)$ ，而不是把它放缩成最大成对 KL。这在局部问题里更精确，常常能去掉多余的 $\log$ 因子。其思想是：不要要求所有假设两两都接近，只要它们整体上离它们的「重心」接近就够了。

Fano 还有一个局部版本：不要求 $\theta_i$ 覆盖整个参数空间，只要求它们落在一个半径 $r$ 的小球里。非参数速率 $n^{-2\beta/(2\beta+d)}$ 正是这样来的——局部的打包数随 $r$ 增长，而 KL 随 $r$ 增长，两者平衡给出最优的 $r$ 。

五、Assouad 引理

5.1 超立方体

Fano 处理的是「 $M$ 个任意假设」，Assouad 处理的是一种特殊但极有用的结构：超立方体。

定理 5.1（Assouad 引理，平方损失） 设 $\Theta=\{0,1\}^m$ ， $P_\theta$ 是观测分布，损失为平方欧氏距离。对每个坐标 $j$ ，令
$Q_{j,0}=\frac1{2^{m-1}}\sum_{\theta:\theta_j=0}P_\theta, \qquad Q_{j,1}=\frac1{2^{m-1}}\sum_{\theta:\theta_j=1}P_\theta.$
则
$\inf_{\hat\theta}\max_{\theta\in\Theta}\mathbb E_{P_\theta}\bigl[\lVert\hat\theta-\theta\rVert_2^2\bigr] \ge \frac m4\left(1-\max_j\lVert Q_{j,0}-Q_{j,1}\rVert_{\mathrm{TV}}\right).$

证明用贝叶斯视角。取 $\Theta$ 上的均匀先验。平方损失下的贝叶斯估计是后验均值 $\hat\theta_B(X)=\mathbb E[\theta\mid X]$ ，其贝叶斯风险为

\sum_{j=1}^m\mathbb E\bigl[\pi_j(X)(1-\pi_j(X))\bigr], \qquad \pi_j(X)=\Pr(\theta_j=1\mid X).

固定 $j$ 。边际后验 $\pi_j$ 正是 $Q_{j,0}$ 与 $Q_{j,1}$ 在均匀先验下的后验概率。对任意 $\pi\in[0,1]$ ，

\pi(1-\pi)\ge\frac12\min(\pi,1-\pi),

而均匀先验下的贝叶斯检验误差满足

\mathbb E\bigl[\min(\pi_j,1-\pi_j)\bigr] \ge \frac12\left(1-\lVert Q_{j,0}-Q_{j,1}\rVert_{\mathrm{TV}}\right),

这是定理 3.1 的检验形式。于是每个坐标贡献至少 $\frac14(1-\mathrm{TV}_j)$ ，求和得

\mathfrak B_n\ge\frac m4\left(1-\max_j\lVert Q_{j,0}-Q_{j,1}\rVert_{\mathrm{TV}}\right).

极小极大风险不小于贝叶斯风险，定理得证。

5.2 逐坐标下界

Assouad 的威力在于它把 $m$ 维问题拆成了 $m$ 个一维问题。只要每个坐标上的两个混合分布足够接近， $m$ 个坐标就会贡献 $m$ 倍的下界——这正是高维速率里 $d$ 的来源。

对 $\Theta=\{0,\varepsilon\}^m$ ，令 $\theta=\varepsilon\theta'$ ，其中 $\theta'\in\{0,1\}^m$ 。平方损失满足

\lVert\hat\theta-\theta\rVert_2^2 =\varepsilon^2\bigl\lVert\hat\theta/\varepsilon-\theta'\bigr\rVert_2^2,

所以定理 5.1 直接给出

\inf_{\hat\theta}\max_{\theta\in\{0,\varepsilon\}^m}\mathbb E\lVert\hat\theta-\theta\rVert_2^2 \ge \frac{\varepsilon^2m}{4}\left(1-\max_j\lVert Q_{j,0}-Q_{j,1}\rVert_{\mathrm{TV}}\right).

如果损失换成 Hamming 距离，同样的逐坐标论证给出常数 $1/2$ ：把后验均值换成阈值检验即可。

六、两个完整的例子

6.1 高斯均值： $\sigma^2d/n$

模型：

X_1,\dots,X_n\sim N(\theta,\sigma^2 I_d),\qquad \theta\in\mathbb R^d,

损失为 $\lVert\hat\theta-\theta\rVert_2^2$ 。

上界。 样本均值 $\bar X$ 的风险是

\mathbb E\lVert\bar X-\theta\rVert_2^2=\frac{\sigma^2d}{n}.

下界。 把参数限制到超立方体 $\Theta_0=\{0,\varepsilon\}^d$ 。对坐标 $j$ ，混合分布 $Q_{j,0}$ 与 $Q_{j,1}$ 只在这一维的均值上相差 $\varepsilon$ 。由 KL 的联合凸性，

D_{\mathrm{KL}}(Q_{j,0}\Vert Q_{j,1}) \le \frac{n\varepsilon^2}{2\sigma^2}.

Pinsker 给出

\lVert Q_{j,0}-Q_{j,1}\rVert_{\mathrm{TV}} \le \frac{\varepsilon\sqrt n}{2\sigma}.

取 $\varepsilon=\sigma/\sqrt n$ ，则 TV 至多 $1/2$ 。Assouad：

\max_{\theta\in\Theta_0}\mathbb E\lVert\hat\theta-\theta\rVert_2^2 \ge \frac{\varepsilon^2d}{4}\left(1-\frac12\right) =\frac{\sigma^2d}{8n}.

上下界只差常数 $8$ ，速率 $\sigma^2d/n$ 被夹住了。

这个例子也说明了 Fano 与 Assouad 的分工：Fano 需要构造一个 $\delta$ -分离的打包，Assouad 则直接利用乘积结构，把打包问题化成了逐坐标的 TV 计算。

6.2 非参数回归： $n^{-2\beta/(2\beta+d)}$

模型：

Y_i=f(X_i)+\xi_i,\qquad X_i\sim\mathrm{Unif}([0,1]^d),\qquad \xi_i\sim N(0,\sigma^2),

$f$ 属于 $\beta$ -Hölder 球 $\Sigma(\beta,L)$ ，损失为 $\lVert\hat f-f\rVert_{L^2}^2$ 。

上界。 核估计或局部多项式估计可以达到

n^{-\frac{2\beta}{2\beta+d}}

（见 Tsybakov 第 1 章）。下界用 Fano。

取 $h\in(0,1)$ ，把 $[0,1]^d$ 分成 $m=h^{-d}$ 个边长为 $h$ 的小方块。取一个光滑的鼓包函数 $\varphi$ ，支撑在单位方块内，令

\varphi_j(x)=\varphi\Bigl(\frac{x-x_j}{h}\Bigr),

其中 $x_j$ 是第 $j$ 个方块的中心。对任意子集 $S\subseteq\{1,\dots,m\}$ ，定义

f_S=a\sum_{j\in S}\varphi_j,\qquad a=c\,h^\beta.

当 $c$ 足够小时， $f_S\in\Sigma(\beta,L)$ ：鼓包的高度是 $h^\beta$ 、宽度是 $h$ ，所以 $\beta$ 阶导数的量级是 $h^\beta/h^\beta=1$ 。

两个函数 $f_S,f_{S'}$ 的 $L^2$ 距离只取决于它们不同的那些鼓包。若 $|S\triangle S'|=k$ ，则

\lVert f_S-f_{S'}\rVert_{L^2}^2 =a^2h^d\,k\,\lVert\varphi\rVert_{L^2}^2 =c^2h^{2\beta+d}\,k\,\lVert\varphi\rVert_{L^2}^2.

现在取一个长度为 $m$ 、相对 Hamming 距离至少 $1/4$ 的二元码。这样的码有 $M=2^{c_0m}$ 个码字（ $c_0>0$ 是常数），任意两个码字至少在 $m/4$ 个位置不同。于是

\lVert f_S-f_{S'}\rVert_{L^2}^2 \ge c_1h^{2\beta},

即平方间隔 $\Delta=c_1h^{2\beta}$ 。

另一方面，两个回归分布的 KL 是

D_{\mathrm{KL}}\bigl(P_{f_S}^{\otimes n}\Vert P_{f_{S'}}^{\otimes n}\bigr) =\frac{n}{2\sigma^2}\lVert f_S-f_{S'}\rVert_{L^2}^2 \le \frac{n c_2 h^{2\beta}}{\sigma^2}.

Fano 要求 $\log M\gg n h^{2\beta}$ ，即

h^{-d}\gtrsim n h^{2\beta} \quad\Longleftrightarrow\quad h\lesssim n^{-\frac{1}{2\beta+d}}.

取 $h\asymp n^{-1/(2\beta+d)}$ ，下界就是

\mathfrak M_n\gtrsim h^{2\beta} \asymp n^{-\frac{2\beta}{2\beta+d}},

与上界同阶。证毕。

这个构造值得反复看：鼓包的宽度 $h$ 控制两件事——损失间隔（ $h^{2\beta}$ ）和 KL（ $n h^{2\beta}$ ），而鼓包的个数 $h^{-d}$ 控制假设的个数。 三者平衡，就得到非参数速率。维度 $d$ 出现在指数上，正是因为它决定了「同样宽度下能放多少个鼓包」。

6.3 一些经典速率

问题	参数类	极小极大速率
$d$ 维高斯均值	$\lVert\theta\rVert_2\le R$	$\sigma^2d/n$
非参数回归	$\beta$ -Hölder， $L$	$n^{-2\beta/(2\beta+d)}$
密度估计	$\beta$ -Hölder， $L$	$n^{-2\beta/(2\beta+d)}$
$s$ -稀疏均值	$\lVert\theta\rVert_0\le s\ll d$	$\dfrac{\sigma^2s}{n}\log\dfrac ds$
一维单调回归	单调、有界	$n^{-2/3}$

这张表里的每一个速率，都可以用本文的三种方法之一推出来。稀疏均值的下界通常用 Fano 加一个随机支撑的打包；单调回归则用 Le Cam 加一个局部的「台阶」构造。

七、三种方法的比较

方法	假设个数	距离	优势	局限
Le Cam	$2$	TV / KL	简单，常数清楚	只探测一个方向，高维问题会松
Fano	$M$	互信息 / KL	通用，适合高维与非参数	需要构造打包，常数较松
Assouad	$2^m$	逐坐标 TV	乘积结构下最锋利	只适用于超立方体结构

三者的关系可以这样理解：

Le Cam 是 Fano 的两点版本。 当只有两个假设时，Fano 退化为两点检验；Le Cam 用 TV 给出了更干净的常数。
Fano 是 Le Cam 的多假设推广。 它把「两个点分不清」推广为「 $M$ 个点平均分不清」。
Assouad 是 Fano 在乘积结构上的精细化。 它不直接对 $2^m$ 个假设做 Fano，而是逐坐标做 Le Cam，再把 $m$ 个下界加起来。

实际使用时，选择哪种方法取决于参数空间的结构：

一维、局部、两样本问题：Le Cam 通常足够，而且常数最干净。
高维、非参数、需要 $\log M$ 的地方：Fano 是标准工具。
乘积结构、 $\ell_2$ 或 $\ell_\infty$ 速率：Assouad 最方便。

结语

回到开头的问题：为什么 $1/n$ 不能再小？因为两个足够接近的分布，在 $n$ 个样本下仍然难以区分；而任何估计器都必须先区分它们。这个论证只需要两个点，所以叫两点方法。

但当困难来自许多方向时，两个点就不够了。Fano 把「两个点」换成「 $M$ 个点」，用互信息度量整体的不可区分性；Assouad 则把 $m$ 维问题拆成 $m$ 个一维问题，逐坐标地累加下界。

如果只记三句话：

下界证明的第一步永远是归约：把估计问题换成一个有限检验问题。
Le Cam 用两个点，Fano 用 $M$ 个点，Assouad 用 $2^m$ 个点；工具在变，思想都是「构造一个在损失上离得远、在信息上离得近的假设集合」。
信息论下界告诉你统计上不可能；它不告诉你计算上不可能。深度学习时代真正难的，往往是后一个问题。