跳转至

Recertifying decisions via e-closure: uniform improvements of conformal risk control and randomized e-BH

作者: Tian Bai, Aaditya Ramdas
主题: 数理统计 / 假设检验
相关性: 6/10
链接: https://arxiv.org/abs/2610.35821


一、领域脉络与小综述

这个方向是什么

本文所处的子方向是基于 e-value 的决策与推断理论,其根本目标是:在保证某种期望风险(如 FDR、期望损失)受控的前提下,构造尽可能"不保守"的统计决策程序。该方向的成熟度较高——e-value 作为 p-value 的替代或补充,已在假设检验、多重比较、置信区间、风险控制等多个场景中建立了系统的理论框架(Vovk & Wang 2021; Ramdas & Wang 2025),但"如何系统性地利用程序未用完的风险预算"这一问题,在本文之前缺乏统一的处理框架。

发展脉络

  • 奠基工作:e-value 的概念与基本性质由 Vovk 和 Wang (2021) 系统化,其核心是"期望至多为一的非负统计量",这使其天然适合处理依赖性与事后(post hoc)推断。同期,Wang 和 Ramdas (2022) 提出了 e-BH 过程,将 e-value 引入多重比较,证明其在任意依赖结构下控制 FDR,这是本文的直接起点。
  • 主要进展:e-closure 原理由 Xu 等人 (2026b) 提出,它给出了"一个拒绝集能被 e-value 族认证"的充要条件,将 e-BH 等程序统一为 e-closure 的特例。与此同时,Grünwald (2023, 2024) 发展了 e-posterior 框架,将 e-value 与贝叶斯决策联系起来;Andrews 和 Chen (2025) 则研究了"带证书的决策"问题。在风险控制一侧,Angelopoulos 等人 (2024) 提出 conformal risk control (CRC),将 conformal prediction 从覆盖率推广到一般单调损失;Yeh 等人 (2025) 进一步引入依赖 λ 的损失上界(envelope),得到更紧的 CRC 变体。
  • 当前 frontier:两条线正在交汇——一条是 e-value 框架下的多重比较与事后推断(Xu et al. 2026b; Ramdas 2026; Sun & Wang 2026),另一条是 conformal 框架下的风险控制(Angelopoulos 2026; Tibshirani et al. 2026)。本文的贡献正是在这两条线的交汇处:将 e-closure 原理推广到一般决策问题,并以此统一和改进 CRC 与随机化 e-BH。
  • 本文的位置:本文提出 recertification 范式,作为 e-closure 的"反向"应用——不是从 e-value 族出发构造认证集,而是从已有有效程序出发,计算其未用完的风险预算,再通过放大 e-value 来构造更不保守的决策。这一位置使其成为 e-closure 原理的构造性补充,而非仅仅是一个新的特例。

子线索聚类

  1. e-value 与多重比较:Wang & Ramdas (2022) 的 e-BH、Xu 等人 (2026b) 的 e-closure、Xu & Ramdas (2023) 的随机化 e-BH、Ignatiadis 等人 (2024) 的最小自适应 e-BH、Ramdas (2026) 的 anchoring、Sun & Wang (2026) 的完备类与可容许性。这条线关注"如何在任意依赖下控制 FDR,并尽可能提高功效"。
  2. conformal 预测与风险控制:Angelopoulos 等人 (2024) 的 CRC、Bates 等人 (2021) 的 RCPS 与 LTT、Yeh 等人 (2025) 的 envelope CRC、Angelopoulos (2026) 的非单调损失扩展、Tibshirani 等人 (2026) 的 universality 结果。这条线关注"如何在分布自由(distribution-free)下控制期望损失"。
  3. 决策论与事后推断:Grünwald (2023, 2024) 的 e-posterior、Andrews & Chen (2025) 的 certified decisions、Koning (2023, 2026) 的 e-value 与群不变性。这条线关注"e-value 如何支撑事后选择的决策"。

⚠️ 作者的 framing

作者将缺口 frame 成:"统计程序在控制期望损失时,往往留下未使用的风险预算,而现有理论缺乏系统性地利用这些预算的方法。" 他们声称 recertification 是"显然的下一步",因为它直接建立在 e-closure 原理之上,且对 CRC 和随机化 e-BH 都给出了统一的改进。作者淡化了以下竞争路线:(1) 直接优化 e-value 族(如条件校准,Lee & Ren 2024)而非从已有程序出发;(2) 通过贝叶斯或决策论框架(Grünwald 2024)选择最优决策,而非在固定风险约束下改进。这些路线在文中仅作为 related work 提及,未与 recertification 做系统比较。

张力

未见明显对立引用。但有一个值得注意的张力:Xu 等人 (2026b) 的 e-closure 强调"认证集的完备性"(所有有效程序都是 e-closure 的特例),而本文的 recertification 强调"从已有程序出发的构造性改进"。这两者并不矛盾,但若 e-closure 的完备性成立,则 recertification 的改进空间应已被 e-closure 覆盖——作者通过指出"e-closure 只保证存在性,不保证构造性"来化解这一张力,但这在文中只是隐含的,未明确讨论。


二、最核心、最简单的例子 / 数学问题

第一步:符号、模型、可观测数据

在展开论文技术细节之前,先建立统一的记号框架。本文的核心记号如下:

  • 数据与状态:
  • \(X\):观测数据,取值于空间 \(\mathcal{X}\)。
  • \(s \in \mathcal{S}\):未知状态(如多重比较中真实零假设的集合,或 conformal 中数据分布)。
  • \(\mathcal{P}_s\):状态 \(s\) 下数据 \(X\) 的分布类。
  • \(Z_1, \dots, Z_n, Z_{n+1}\):conformal 设定下的 \(n\) 个校准点加 1 个测试点,联合可交换。

  • 决策与损失:

  • \(a \in \mathcal{A}\):决策(行动),如 conformal 中的预测集或多重比较中的拒绝集。
  • \(L_t(s, a; x)\):第 \(t\) 类损失,\(t \in \mathcal{T}\),已知非负函数。
  • \(\alpha_t(s)\):第 \(t\) 类损失的风险预算(目标上界)。
  • 风险:\(R_t(s, A) = \mathbb{E}_{P}[L_t(s, A(X); X)]\),其中 \(A: \mathcal{X} \to \mathcal{A}\) 是决策规则。

  • e-value 与 e-collection:

  • \(E_{s,t}(X)\):针对状态-损失对 \((s,t)\) 的 e-value,满足 \(\mathbb{E}_P[E_{s,t}(X)] \le 1\) 对所有 \(P \in \mathcal{P}_s\)。
  • e-collection:一族 e-value \(\{E_{s,t}: s \in \mathcal{S}, t \in \mathcal{T}\}\)。
  • 认证集:给定 e-collection,认证集 \(\mathcal{C}_\alpha(E; x) = \{a : L_t(s,a;x) \le \alpha_t(s) E_{s,t}(x) \ \forall s,t\}\)。

  • 可观测与不可观测:

  • 可观测:校准数据 \(Z_1, \dots, Z_n\)、测试点的特征 \(X_{n+1}\)(在 CRC 中)、e-value 的观测值 \(E_{s,t}(X)\)。
  • 不可观测(潜在):测试点的标签 \(Y_{n+1}\)(CRC 中)、真实状态 \(s\)(多重比较中)、以及"假设的增广样本"中未观测到的部分。

第二步:最小内核

本文的核心数学问题可以归结为以下最小内核:

问题设定:假设我们有一个有效的决策规则 \(A\),即它满足风险约束 \(\mathbb{E}_P[L_t(s, A(X); X)] \le \alpha_t(s)\)。但该规则可能是保守的——在某些数据实现下,它选择的行动 \(A(x)\) 的损失远低于预算 \(\alpha_t(s)\),留下了未使用的风险预算。

核心思想:将有效规则 \(A\) 的损失归一化为 e-value:

\[E_{s,t}(x) = \frac{L_t(s, A(x); x)}{\alpha_t(s)}.\]
由于 \(A\) 有效,\(\mathbb{E}_P[E_{s,t}(X)] \le 1\),所以这是一个合法的 e-collection。现在,recertification 的关键步骤是:计算这个 e-collection 在观测数据 \(x\) 下的"未使用预算",即
\[\Delta(x) = \alpha_t(s) - L_t(s, A(x); x) \ge 0.\]
然后,将这个未使用的预算重新分配给更不保守的行动。具体地,对于 CRC,recertification 将未使用的预算 \(\Delta(D \cup \{z\})\) 均分给 \(n+1\) 个 held-out 位置,从而允许选择比 \(A(D)\) 更小的 \(\lambda\)(更不保守的行动),同时保持风险约束。

为什么成立:关键在于 e-value 的期望性质。如果我们将每个 held-out 位置的损失上界从 \(L_t(s, A(x); x)\) 提高到 \(L_t(s, A(x); x) + \Delta/(n+1)\),那么新的 e-collection 的期望仍然至多为 1,因为 \(\Delta\) 是未使用的预算,其期望恰好补偿了损失的增加。因此,新的决策规则仍然有效。

最小例子(CRC 特例):设 \(n=1\),损失为 miscoverage \(\ell(z, \lambda) = \mathbf{1}\{y \notin C_\lambda(x)\}\),预算 \(\alpha = 0.1\)。假设校准点 \(z_1\) 在 \(\lambda = 0.5\) 时损失为 0(预测集覆盖了标签),测试点 \(z_2\) 的损失未知。CRC 选择最小的 \(\lambda\) 使得 \(\ell(z_1, \lambda) + 1 \le 2\alpha = 0.2\),即 \(\lambda\) 使得 \(\ell(z_1, \lambda) \le -0.8\),这不可能,所以 CRC 选择最保守的 \(\lambda^+\)。Recertification 计算未使用预算:\(\Delta = 2\alpha - \ell(z_1, \lambda^+) - \ell(z_2, \lambda^+) = 0.2 - 0 - 0 = 0.2\)(假设 \(\lambda^+\) 下两个点都覆盖)。然后允许 \(\lambda\) 减小到使得 \(\ell(z_1, \lambda) + \ell(z_2, \lambda) \le 0.2 + \Delta/2 = 0.3\),从而可能选择更小的 \(\lambda\),提高预测集的精确度。

这个内核的数学本质:recertification 是一种风险预算的再分配。它不改变总预算,而是通过 e-value 的期望性质,将未使用的预算从"不可能发生"的状态(如校准点损失为 0)转移到"可能发生"的状态(如测试点损失较大),从而在不破坏风险约束的前提下,允许更激进的决策。


三、这篇论文做了什么

三句话

  1. 研究了什么问题:如何系统地利用有效统计程序(如 CRC 和随机化 e-BH)在控制期望损失时留下的未使用风险预算,从而构造更不保守的决策。
  2. 核心工具/方法:提出了 recertification 范式,基于 e-value 的期望性质和 e-closure 原理,通过计算并重新分配未使用的风险预算来放大认证 e-value,进而扩大决策集。
  3. 主要结论:recertification 对 CRC 和随机化 e-BH 都给出了逐点(pointwise)不劣于原程序的改进;在 CRC 中,迭代 recertification 在凸损失下以几何速率收敛到可容许的控制器;在多重比较中,recertified 随机化 e-BH 在保持 FDR 控制的同时,期望拒绝数达到条件预算约束下的最大值。

关键设定与假设

CRC 部分: - 设定:观测空间 \(\mathcal{Z}\),损失 \(\ell(z, \lambda)\) 满足 (3.1):非负、有界 \(B\)、关于 \(\lambda\) 非增且右连续、\(\ell(z, \lambda^+) \le \alpha\)。校准数据 \(Z_1, \dots, Z_n\) 与测试点 \(Z_{n+1}\) 可交换。 - 假设:控制器是对称的(symmetric),即对校准数据的排列不变。这是 Lemma 3.1 成立的必要条件。 - 相比已有工作的变化:标准 CRC 用常数 \(B\) 作为测试损失的保守上界;envelope CRC 用更紧的 \(\lambda\)-依赖上界 \(U(\lambda)\);recertification 进一步利用每个增广样本的未使用预算,得到逐点更紧的上界。

随机化 e-BH 部分: - 设定:\(K\) 个 e-value \(E_1, \dots, E_K\),任意依赖。状态 \(T\) 为零假设集合。损失为 FDP。 - 假设:e-value 在零假设下期望至多为一。随机化 e-BH 使用一个公共的均匀随机变量 \(U\) 来决定拒绝阈值。 - 相比已有工作的变化:标准 e-BH 和 U-eBH 只使用每个 e-value 自身的预算;recertification 利用条件于 e-value 的未使用预算,即每个 e-value 超过其被拒绝所需阈值的部分,来扩大拒绝集。

主要结果

定理 3.2(CRC 的均匀改进):对任意有效对称控制器 \(A\),recertified 控制器 \(RA\) 满足: 1. \(RA \le A\) 逐点(即更不保守); 2. \(RA\) 在任意有限可交换分布下有效(风险 \(\le \alpha\))。

证明思路:利用 Lemma 3.1 的精确刻画,将有效性转化为对每个增广样本的总损失约束。Recertification 将未使用预算 \(\Delta_A(S)\) 均分给 \(n+1\) 个 held-out 位置,使得新控制器的总损失恰好等于预算,从而保持有效性。

定理 3.5(凸损失下的收敛性):若损失 \(\ell(z, \cdot)\) 凸,则迭代 recertification 从任何有效基线出发,以几何速率 \(\rho = n/(n+1)\) 收敛到一个点态可容许的控制器。证明的关键是 Lemma 3.2 的一步比较:\(RA \le \rho A + C/(n+1)\),其中 \(C\) 是任意有效控制器。

命题 4.1(RU-eBH):recertified U-eBH 满足: 1. FDR \(\le \alpha|T|/K \le \alpha\); 2. 对每个 \(e, U\),拒绝集包含 U-eBH 的拒绝集; 3. 在条件于 e-value 的预算约束下,期望拒绝数最大。

命题 4.2(RC-eBH):recertified closed e-BH 满足: 1. FDR \(\le \alpha\); 2. 拒绝集包含 RU-eBH 的拒绝集; 3. 在条件于 e-value 的预算约束下,期望拒绝数最大,且该最大值由闭式给出。

真实例子

CIFAR-100 分层分类: - 数据:CIFAR-100 测试集 10,000 张图像,冻结的 ResNet-18 特征。分层标签:100 个细类、20 个超类。 - 任务:给定测试图像 \(x\),输出一个标签集合(预测集),要求覆盖真实标签的期望损失 \(\le \alpha\)。损失为分层损失:预测超类错误损失 1,预测细类错误损失 0.5。 - 方法:校准集 \(n=50\),目标 \(\alpha=0.15\)。基线为 CRC 和 envelope CRC;recertification 从 envelope CRC 出发,迭代 500 轮。 - 结果:CRC 的平均风险为 14.21%,envelope CRC 为 14.21%(相同),recertified 为 14.95%,接近目标 15%。预测集大小从 10.77 降至 8.92,减少 17.2%。这表明 recertification 在保持风险控制的同时,显著提高了预测的精确度。

多重比较模拟: - 设定:\(K=100\) 个假设,其中 10、50 或 90 个为假。e-value 为似然比,任意依赖(等相关高斯)。 - 结果:RU-eHC 和 RC-eHC 在所有设定下都比 U-eHC 和 e-HC 更强大,且 RC-eHC 在大多数设定下最强大。FDR 始终低于目标。

🔎 结论是否比证明窄

是,存在明显的"证明窄于结论"之处:

  1. CRC 的收敛性:定理 3.5 的几何收敛速率 \(\rho = n/(n+1)\) 是在凸损失下证明的。但作者在摘要和引言中声称 recertification 对"一般单调损失"有效。对于非凸损失,文中只证明了单步改进(定理 3.2),没有证明迭代收敛。作者在 3.5 节提到"非凸损失下可用 sweep 方法达到可容许性"(命题 3.7),但该命题要求观测空间有限,且 sweep 的收敛性没有给出速率。

  2. RC-eHC 的最优性:命题 4.2 的最优性是在"条件于 e-value 的预算约束"下证明的,即给定 e-value 的观测值,在所有满足该预算约束的随机化规则中,RC-eHC 期望拒绝数最大。但作者没有证明 RC-eHC 在无条件意义下的最优性,即没有证明它在所有 FDR 控制规则中是最优的。事实上,作者在 4.4 节明确说"RC-eHC 不是 admissible 的"(附录 C.5),因为它可以被 anchoring 进一步改进。

  3. CRC 的 admissible 极限:定理 3.5 证明的收敛极限是点态可容许的,即不存在其他有效控制器在每个校准集上都严格更优。但作者没有证明这个极限是风险可容许的,即不存在其他有效控制器在期望风险上严格更优。点态可容许强于风险可容许,但作者没有讨论这个区别。

  4. 计算复杂度:recertification 的迭代需要计算每个增广样本的未使用预算,在连续观测空间上不可行。作者在 3.5 节讨论了有限类型情形的计算,但真实数据实验(CIFAR-100)使用的是有限类型近似,没有给出近似误差的界。


四、开放问题

  1. 非凸损失的收敛性:定理 3.5 的几何收敛依赖于凸性。对于非凸损失(如 miscoverage 的 step 函数),迭代 recertification 是否收敛?收敛到何处?sweep 方法(命题 3.7)的收敛速率如何?——扎根于定理 3.5 的凸性假设和命题 3.7 的有限空间假设。

  2. RC-eHC 的无条件最优性:RC-eHC 在条件预算约束下最优,但无条件意义下是否最优?是否存在其他 FDR 控制规则,其期望拒绝数超过 RC-eHC?——扎根于命题 4.2 的"条件于 e-value"的表述和附录 C.5 中"RC-eHC 不是 admissible"的说明。

  3. recertification 的通用性:作者声称 recertification 适用于"任何有效程序",但文中只给出了 CRC 和随机化 e-HC 两个例子。对于其他风险控制问题(如置信区间的期望宽度控制、bandit 中的 regret 控制),recertification 如何应用?——扎根于第 2 节的通用框架和第 5 节的讨论。

  4. 计算-统计权衡:recertification 的迭代成本随轮数线性增长,且每轮需要计算增广样本的未使用预算。是否存在更高效的近似算法?近似误差如何影响有效性保证?——扎根于 3.5 节的计算讨论和附录 B.7 的实现细节。

  5. e-value 的选择:recertification 的效果依赖于基线程序留下的未使用预算。不同的基线(CRC vs envelope CRC)会导致不同的 recertified 程序。是否存在最优的基线选择?——扎根于第 3 节中"从任何有效基线出发"的表述。


提示:若要确认上述开放问题是否为真 gap,建议去读以下近期文献的 introduction:(1) Xu et al. (2026b) 的 e-closure 后续工作;(2) Lee & Ren (2024) 的条件校准;(3) Sun & Wang (2026) 的完备类结果。若这些文献的 introduction 都指向同一问题,则大概率是共识性 gap;若互相矛盾,则可能是机会。


Maintained by 陈星宇 · Homepage · Source on GitHub

评论