Assouad 引理

超立方构造 ​

设参数索引为

$$\omega =({\omega }_1,\dots ,{\omega }_d)\in \{-1,+1{\}}^d,$$

每个顶点对应观测分布 $P_{\omega }$ 和目标对象 ${\theta }_{\omega }$。构造应满足：若两个顶点在多个坐标不同，目标损失至少按 Hamming 距离累积。具体地，假设某个估计量 $\hat{\theta }$ 可诱导坐标猜测 $\hat{\omega }$，且

$$L(\hat{\theta },{\theta }_{\omega })\ge a\sum _{j=1}^d{\mathbf{1}}_{\{{\hat{\omega }}_j\ne {\omega }_j\}}$$

，其中 $a>0$ 是每个坐标错误的损失尺度。

Assouad 方法把估计 $d$ 位的总困难拆成 $d$ 个问题：在其他坐标未知并平均掉后，能否判断第 $j$ 位是 $+1$ 还是 $-1$？如果相邻顶点的观测分布很接近，每一位都有不可消除的错误概率，求和便给维度因子。

一种标准陈述 ​

记 ${\omega }^{(j)}$ 为翻转 $\omega$ 第 $j$ 位得到的相邻顶点。对任意估计量，以上面的损失嵌入为前提，有

$$\underset{\omega }{sup}{\mathbb{E}}_{\omega }L(\hat{\theta },{\theta }_{\omega })\ge \frac{ad}{2}(1-\underset{\omega ,j}{max}\mathrm{TV}(P_{\omega },P_{{\omega }^{(j)}})).$$

不同版本会用对所有边的平均 TV、Hellinger affinity，或把 $a$ 的定义吸收一个 $1/2$，导致常数变化。结构始终是

$$\text{每坐标损失}\times \text{坐标数}\times \text{相邻世界不可分辨度}.$$

对 $m$ 个 IID 样本，分布替换为 $P_{\omega }^{\otimes m}$。可再用 Pinsker

$$\mathrm{TV}(P,Q)\le \sqrt{\frac{1}{2}\mathrm{KL}(P\Vert Q)}$$

及乘积 KL 的可加性控制相邻可辨性。

证明 ​

先在均匀随机 $\mathrm{\Omega }\sim \mathrm{Unif}(\{-1,+1{\}}^d)$ 下取 Bayes 平均风险。由损失嵌入，

$$\mathbb{E}L(\hat{\theta },{\theta }_{\mathrm{\Omega }})\ge a\sum _{j=1}^d\text{Pr}({\hat{\mathrm{\Omega }}}_j\ne {\mathrm{\Omega }}_j).$$

固定坐标 $j$，把其余 $d-1$ 位平均掉，得到两个混合分布：

$${\bar{P}}_{j,+}=2^{-(d-1)}\sum _{\omega :{\omega }_j=+1}{P}_{\omega },{\bar{P}}_{j,-}=2^{-(d-1)}\sum _{\omega :{\omega }_j=-1}{P}_{\omega }.$$

估计 ${\mathrm{\Omega }}_j$ 至少和区分这两个等先验分布一样难。二点检验公式给

$$\text{Pr}({\hat{\mathrm{\Omega }}}_j\ne {\mathrm{\Omega }}_j)\ge \frac{1}{2}(1-\mathrm{TV}({\bar{P}}_{j,+},{\bar{P}}_{j,-})).$$

由 TV 的凸性，将 $+$ 侧每个顶点与翻转第 $j$ 位的 $-$ 侧顶点配对，可用相邻边 TV 的平均控制两个混合分布距离。对 $j$ 求和得到平均风险下界，而 minimax 上确界至少不小于该 Bayes 平均值。

Bernoulli 坐标例子 ​

设每个样本先均匀选择坐标 $J\in [d]$，并固定 $0<\alpha \le 1/4$，再观察

$$Y\mid J=j\sim \mathrm{Bernoulli}(\frac{1}{2}+{\omega }_j\alpha ).$$

目标是估计 $d$ 个符号。翻转一位只改变落在该坐标的观测，而每个样本命中它的概率为 $1/d$。当 $\alpha \to 0$ 时，相邻单样本 KL 为

$$\frac{1}{d}\mathrm{kl}(\frac{1}{2}+\alpha \Vert \frac{1}{2}-\alpha )=\frac{(8+O({\alpha }^2)){\alpha }^2}{d},$$

故 $m$ 个样本后为同一数量的 $m$ 倍。在 $m\gtrsim d$ 的区间选择足够小常数倍的 $\alpha \asymp \sqrt{d/m}$，可使相邻世界仍难区分；全参数区间可统一写成 $\alpha \asymp min\{1,\sqrt{d/m}\}$，并把常数取得不超过 $1/4$。Assouad 求和由此产生维度相关风险下界。

这个例子展示了为何不能只做一次全参数二点检验：单个二点构造只提供一个方向的困难，超立方让 $d$ 个局部不确定方向的损失相加。

与 Fano 方法的区别 ​

Fano 方法公理库Packing–Fano 学习下界Packing-Fano method · Fano method for minimax lower bounds将参数空间离散成大量两两分离却统计上难以区分的候选，再由 Fano 不等式导出维数敏感的极小极大下界。构造许多整体分离的候选，用索引熵与平均互信息控制“猜中整个候选”的概率。Assouad 不要求一次识别完整顶点，而把可加损失拆成逐坐标错误；它特别适合 $L_1$、Hamming、积分平方误差等能由局部块相加的损失。

两者都可能从 packing 开始，也都可用 KL 控制信息，但证明组织不同。把 Fano 的 $\log M$ 机械换成 $d$ 会漏掉 Assouad 必需的相邻边结构和损失嵌入。

边界与构造检查 ​

好构造必须同时满足两个相反要求：目标在相邻坐标翻转后产生足够损失，观测分布却仍足够接近。若 $a$ 选得很大但 TV 也接近 $1$，下界乘积会归零；若分布完全相同却目标差异违反可识别模型，构造可能根本不合法。

超立方参数不需要是真实参数空间的笛卡尔坐标，但每个 ${\theta }_{\omega }$ 必须属于原模型类。对函数估计，常用不相交局部 bump 承担各坐标；要检查光滑度、非负性、积分为一等全局约束在所有顶点上都成立。

参考资料

• Patrice Assouad, “Deux remarques sur l’estimation,” Comptes Rendus de l’Académie des Sciences, 1983.
• Bin Yu, “Assouad, Fano, and Le Cam,” in Festschrift for Lucien Le Cam, 1997.
• Alexandre Tsybakov, Introduction to Nonparametric Estimation, minimax lower-bound chapter.