Packing–Fano 学习下界

Packing–Fano 把连续估计问题压成多路通信：自然先从候选集合均匀挑一个隐藏索引，样本是经过统计信道后的消息，估计器则试图从消息恢复索引。候选在目标度量下必须相隔很远，才能把解码错误转成实质估计误差；诱导分布又必须足够接近，才能让样本难以传递索引。

候选数的对数是需要传输的信息量，互信息是样本实际提供的辨识能力。两者保持常数比例差距时，Fano 强迫常数解码错误；指数规模 packing 的 $\log M$ 因而能把高维方向数带入下界。

高斯均值估计的维数因子 ​

观察 $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$，则候选间

故可取 $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 给出常数解码错误率，最终

两点法只能提供一个方向上的困难；指数多个 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把两个目标相隔但观测分布接近的参数点化为二元检验，从而证明估计下界。更直接。

两点法捕捉一个困难方向，Packing–Fano 通过 $\log M$ 汇总许多方向，因此特别适合高维均值、回归、密度估计和函数估计的维数敏感下界。若候选具有逐坐标 product 结构，Assouad 方法可能保留更细的坐标损失。

构造候选时应同时列出三张账：最小参数距离决定风险尺度，packing 基数决定 $\log M$，KL 或互信息决定可辨识度。只证明“候选很多”或“分布很近”都不够；非平凡下界来自三项在同一参数选择下兼容。