Packing–Fano 学习下界

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

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

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

观察联合高斯样本理路多元正态分布Multivariate normal distribution · Multivariate Gaussian distribution · Jointly Gaussian vector以所有线性组合都正态刻画联合高斯向量，并由特征函数连接线性构造、退化支撑、全维密度与条件分布。 $X_1,\dots ,X_m\sim \mathcal{N}(\theta ,I_d)$，以平方欧氏误差估计 $\theta$。当 $d$ 足够大时，由Gilbert–Varshamov 界的二元有限码构造理路Gilbert–Varshamov 界Gilbert–Varshamov bound · GV bound由极大码的覆盖性质证明具有给定最小距离的大码存在，并导出渐近可达率下界。，可在 $\{-1,+1{\}}^d$ 中选出 $M\ge e^{cd}$ 个向量，任意两者 Hamming 距离至少 $d/8$。令 ${\theta }_v=av$，则候选间

故可取 $s^2\asymp a^{2}d$。另一方面，由正定协方差 $I_d$ 的联合密度及 ${\mathbb{E}}_{{\theta }_v}X={\theta }_v$，单样本高斯 KL 为

因此，$m$ 个样本的互信息至多 $O(m{a}^{2}d)$。取参考均值 ${\theta }_0=0$，再选择 $a^2$ 为足够小的常数倍 $1/m$，便使 $I(V;X)\le (\log M)/4$；$d$ 足够大也保证 $\log 2/\log M\le 1/4$。Fano 因而给出至少 $1/2$ 的解码错误率，最终

对剩余有界的小维数，固定其他坐标，在首坐标放置 $\pm 1/(4\sqrt{m})$，用两点检验下界理路两点检验下界Le Cam's two-point method · two-point lower bound把两个目标相隔但观测分布接近的参数点化为二元检验，从而证明估计下界。得到常数倍 $1/m$；调整统一常数便仍有 $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 引理理路Assouad 引理Assouad's lemma · Assouad lemma · 超立方下界把超立方参数族上的可加估计误差分解为逐坐标二点检验，并以相邻分布的重叠给出 minimax 下界。把可加损失拆成各坐标二元错误，区别于这里猜中整个候选的全局解码；若只有两个自然候选，两点检验下界理路两点检验下界Le Cam's two-point method · two-point lower bound把两个目标相隔但观测分布接近的参数点化为二元检验，从而证明估计下界。更直接。

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

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