Assouad 引理 | Codeboy's Blog

形式陈述

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

设参数索引为

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

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

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

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

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

一种标准陈述

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

\sup_{\omega} \mathbb E_\omega L(\widehat\theta,\theta_\omega) \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$ 个 IID 样本，分布替换为 $P_\omega^{\otimes m}$ 。可再用 Pinsker

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

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

证明

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

\mathbb E L(\widehat\theta,\theta_\Omega) \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).

目标是估计 $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}.

对 $m$ 个 IID 样本，KL 按乘积可加，因而总量再乘 $m$ 。在 $m\gtrsim d$ 的区间，取足够小常数倍的 $\alpha\asymp\sqrt{d/m}$ ，便能让相邻世界保持难分。覆盖全部参数区间时，可写成

\alpha\asymp\min\{1,\sqrt{d/m}\},

并把常数限制在 $1/4$ 以内，以保证 Bernoulli 参数仍落在合法范围。每个坐标由此贡献一份不可消除的错误，Assouad 求和产生维度相关风险下界。

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

与 Fano 方法的区别

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

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

边界与构造检查

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

超立方参数不需要是真实参数空间的笛卡尔坐标，但每个 $\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 方法的区别

边界与构造检查