Assouad 引理 | Codeboy's Blog

形式陈述

Assouad 方法把极小极大风险下界组织成笛卡尔超立方，再以相邻顶点观测分布的全变差距离衡量每一坐标的不可辨识性。

设 $d\ge1$ ，参数索引为

\omega=(\omega_1,\ldots,\omega_d)\in\{-1,+1\}^d,

每个顶点对应观测分布 $P_\omega$ 和目标对象 $\theta_\omega$ 。构造应满足：若两个顶点在多个坐标不同，目标损失至少按 Hamming 距离累积。具体地，固定 $a>0$ ，假设每个允许的估计量 $\widehat\theta$ 都能诱导可测坐标猜测 $\widehat\omega$ ，并且对所有 $\omega$ 及所有可能的输出，有

L(\theta_\omega,\widehat\theta) \ge a\sum_{j=1}^d \mathbf{1}_{\{\widehat\omega_j\ne\omega_j\}}

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

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

一种标准陈述

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

\sup_{\omega} \mathbb E_\omega L(\theta_\omega,\widehat\theta) \ge \frac{ad}{2} \left( 1-\max_{\omega,j} \operatorname{TV}(P_\omega,P_{\omega^{(j)}}) \right).

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

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

对 $m\ge1$ 个 IID 样本，分布替换为 $P_\omega^{\otimes m}$ 。可再用采用自然对数 KL 散度的 Pinsker 不等式

\operatorname{TV}(P,Q) \le\sqrt{\frac12\mathrm{KL}(P\|Q)}

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

证明

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

\mathbb E L(\theta_\Omega,\widehat\theta) \ge a\sum_{j=1}^d \Pr(\widehat\Omega_j\ne\Omega_j).

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

\overline P_{j,+} =2^{-(d-1)}\sum_{\omega:\omega_j=+1}P_\omega, \qquad \overline P_{j,-} =2^{-(d-1)}\sum_{\omega:\omega_j=-1}P_\omega.

估计 $\Omega_j$ 至少和区分这两个等先验分布一样难。二点检验的最小错误和公式给

\Pr(\widehat\Omega_j\ne\Omega_j) \ge\frac12 \bigl(1-\operatorname{TV}(\overline P_{j,+},\overline P_{j,-})\bigr).

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

直觉

一次二点检验只能暴露一个困难方向；超立方让每个坐标都携带一份局部二选一不确定性，并要求损失能够把坐标错误相加。只要每条边仍难区分，维度因子就会从这些局部错误的总和中出现。

例子与边界

Bernoulli 坐标例子

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

Y\mid J=j\sim\operatorname{Bernoulli}\!\left( \frac12+\omega_j\alpha \right).

观测包含坐标编号 $J$ 与结果 $Y$ ，目标可以是恢复 $d$ 个符号，也可以是估计向量 $p_\omega=(1/2+\omega_j\alpha)_{j=1}^d$ 。翻转第 $j$ 位时，只有样本恰好选择坐标 $J=j$ 才能看见两个世界的差异；这一事件每次只以概率 $1/d$ 发生。因此，维度越高，单个坐标获得的有效观测越少。

当 $\alpha\to0$ 时，相邻顶点之间的单样本 KL 为

\frac1d\operatorname{kl}\!\left(\frac12+\alpha\,\middle\|\,\frac12-\alpha\right) =\frac{(8+O(\alpha^2))\alpha^2}{d}.

取

\alpha=\frac18\min\{1,\sqrt{d/m}\}.

二元 KL 不超过 $16\alpha^2$ ，所以相邻顶点的 $m$ 样本 KL 至多为 $16m\alpha^2/d\le1/4$ ，TV 小于 $1/2$ 。对符号的 Hamming 损失， $a=1$ ，上式给最坏期望错误数至少 $d/4$ 。

若改用概率向量的平均平方损失 $L=d^{-1}\sum_j(\widehat p_j-p_{\omega,j})^2$ ，在 $1/2$ 处把每个估计坐标解码为正负号。每个错误坐标至少损失 $\alpha^2/d$ ，因而

\inf_{\widehat p}\sup_\omega E_\omega\frac1d\sum_{j=1}^d(\widehat p_j-p_{\omega,j})^2 \ge\frac{\alpha^2}{4} =\frac1{256}\min\{1,d/m\}.

损失是否除以 $d$ 会改变显示出的维数因子；必须先固定这一归一化，才有可比较的风险速率。

单个全参数二点构造只能展示一个方向的困难。超立方的作用不是简单增加候选数量，而是让 $d$ 个局部二选一问题与可加损失逐坐标对齐。

与 Fano 方法的区别

Fano 方法构造许多整体分离的候选，用索引熵与平均互信息控制“猜中整个候选”的概率。Assouad 不要求一次识别完整顶点，而把可加损失拆成逐坐标错误；它特别适合 $L_1$ 、Hamming、积分平方误差等能由局部块相加的损失。

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

边界与构造检查

好构造必须同时满足两个相反要求：目标在相邻坐标翻转后产生足够损失，观测分布却仍足够接近。若 $a$ 选得很大但 TV 也接近 $1$ ，下界乘积会归零；若两个分布完全相同，结论取决于目标的定义：对允许不可识别参数标签的模型，这正能证明不可消除的估计误差；若目标已规定为分布的单值泛函 $\theta=\psi(P)$ ，却给同一分布指定不同目标值，才是构造不合法。

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

推论与应用

密度估计、回归函数估计和稀疏向量恢复中的可加损失常适合 Assouad：每个局部 bump 或坐标贡献一份难度。若候选主要靠整体分离而非坐标可加，则 Fano packing 往往更自然。

实际下界还需把单样本 KL 或 Hellinger 距离提升到乘积分布，并选择扰动幅度平衡损失分离与统计可辨性。引理提供骨架，参数选择与模型合法性检查决定最终速率。

参考资料

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, Springer, 2009, minimax lower-bound chapter.

形式陈述 ​

一种标准陈述 ​

证明 ​

Bernoulli 坐标例子 ​

与 Fano 方法的区别 ​

边界与构造检查 ​

反向链接

形式陈述

一种标准陈述

证明

Bernoulli 坐标例子

与 Fano 方法的区别

边界与构造检查