Packing–Fano 学习下界

方法模板 ​

设参数空间 $(\mathrm{\Theta },\rho )$ 对应分布族 $\{P_{\theta }:\theta \in \mathrm{\Theta }\}$，观察 $m$ 个 IID 样本。要下界所有估计器的极小极大风险公理库极小极大风险Minimax risk在模型族最坏参数上评价算法风险，再在所有允许算法中寻找最优值。，先取一个 $2s$-packing

$${\mathrm{\Theta }}_0=\{{\theta }_1,\dots ,{\theta }_M\},\rho ({\theta }_j,{\theta }_k)\ge 2s(j\ne k).$$

令随机索引 $V$ 在 $[M]$ 上均匀，条件于 $V=j$ 时生成 $X\sim P_{{\theta }_j}^{\otimes m}$。任意估计器都诱导最近邻解码器

$$\hat{V}=\arg \underset{j}{min}\rho (\hat{\theta }(X),{\theta }_j).$$

若 $\rho (\hat{\theta },{\theta }_V)<s$，packing 的三角不等式保证 $V$ 是唯一最近候选。因此

$$\text{Pr}(\rho (\hat{\theta },{\theta }_V)\ge s)\ge \text{Pr}(\hat{V}\ne V).$$

Fano 不等式公理库Fano 不等式Fano's inequality用估计错误概率上界条件熵，从而把信息不足转化为推断下界。再给

$$\text{Pr}(\hat{V}\ne V)\ge 1-\frac{I(V;X)+\log 2}{\log M}.$$

只要候选数的 $\log M$ 很大，而样本携带的互信息远小于它，任何估计器就以常数概率犯至少 $s$ 的误差；于是平方损失的极小极大风险至少为常数倍 $s^2$。

如何上界互信息 ​

令混合分布 $\bar{P}=M^{-1}\sum _j{P}_{{\theta }_j}^{\otimes m}$，则

$$I(V;X)=\frac{1}{M}\sum _j\mathrm{KL}(P_{{\theta }_j}^{\otimes m}\Vert \bar{P}).$$

混合分布常不易直接计算。由 KL 的凸性，可选任意参考候选 $P_{{\theta }_0}$，得到

$$I(V;X)\le \frac{1}{M}\sum _j\mathrm{KL}(P_{{\theta }_j}^{\otimes m}\Vert P_{{\theta }_0}^{\otimes m})=\frac{m}{M}\sum _j\mathrm{KL}(P_{{\theta }_j}\Vert P_{{\theta }_0}).$$

最后一个等号是 IID 乘积分布的 KL 可加性。证明设计因此要同时满足两种相反要求：参数在 $\rho$ 下足够远，使 $s$ 大；诱导分布在 KL 下足够近，使 $I(V;X)$ 小。packing 大小本身并不保证下界非平凡。

具体例子：高斯均值估计的维数因子 ​

观察 $X_1,\dots ,X_m\sim \mathcal{N}(\theta ,I_d)$，以平方欧氏误差估计 $\theta$。由 Varshamov–Gilbert 构造，可在 $\{-1,+1{\}}^d$ 中选出 $M\ge e^{cd}$ 个向量，任意两者 Hamming 距离至少 $d/8$。令 ${\theta }_v=av$，则候选间

$$\Vert {\theta }_v-{\theta }_{v^{\prime }}{\Vert }_2^2\ge \frac{a^{2}d}{2},$$

故可取 $s^2\asymp a^{2}d$。另一方面，单样本高斯 KL 为 $\frac{1}{2}\Vert {\theta }_v-{\theta }_0{\Vert }_2^2=O(a^{2}d)$，$m$ 个样本的互信息至多 $O(m{a}^{2}d)$。选择 $a^2$ 为足够小的常数倍 $1/m$，便使 $I(V;X)\le c^{\prime }\log M$，Fano 给出常数解码错误率，最终

$$\underset{\hat{\theta }}{inf}\underset{\theta }{sup}{\mathbb{E}}_{\theta }\Vert \hat{\theta }-\theta {\Vert }_2^2\gtrsim \frac{d}{m}.$$

两点法只能提供一个方向上的困难；指数多个 packing 候选把 $d$ 个可区分方向压进 $\log M\asymp d$，这正是维数因子的来源。

Packing、covering 与边界 ​

$2s$-packing 要求候选两两分离；$s$-covering 要求每个参数靠近某个中心，方向相反。最大 packing 与最小 covering 可通过标准半径关系比较，但不能把一个 covering 网直接当成 Fano 所需的分离集合。

连续参数空间必须先离散化，否则没有有限均匀索引 $V$ 和 $\log M$。对数底数也须一致：若互信息用自然对数，Fano 中写 $\log 2$ 与 $\log M$；改用比特时全部换成底 $2$。若问题具有逐坐标超立方结构，Assouad 引理常比全局解码更精细；若只有两个自然候选，两点检验下界公理库两点检验下界Le Cam's two-point method · two-point lower bound把两个目标相隔但观测分布接近的参数点化为二元检验，从而证明估计下界。更直接。

参考资料

• Bin Yu, “Assouad, Fano, and Le Cam,” 1997.
• Alexandre Tsybakov, Introduction to Nonparametric Estimation.
• Thomas Cover and Joy Thomas, Elements of Information Theory, Fano inequality.