Adaptive Conformal Inference through the Lens of Blackwell Approachability

技术摘要：通过 Blackwell 可接近性视角审视自适应符合推理

问题陈述
由 Gibbs 和 Candès (2021) 提出的自适应符合推理 (Adaptive Conformal Inference, ACI) 旨在解决标准符合推理的局限性，后者依赖于在序列或时间依赖场景（如时间序列预测）中经常被破坏的可交换性假设。ACI 旨在顺序构建预测集，使得经验覆盖率收敛到期望的 $1-\alpha$ 水平，适用于任意数据序列。虽然现有的 ACI 策略保证了有效性（经验覆盖率 $\geq 1-\alpha$），但通常缺乏对效率（平均预测区间长度）的同时理论保证。在对抗性设置中，如果没有额外的假设，是不可能实现非平凡效率保证的；而在可交换性设置中，现有方法往往产生次优的区间长度。核心挑战在于设计一种统一的策略，既能确保针对任意序列的有效性，又能使效率适应底层数据的随机程度。

方法论
作者将 ACI 重新表述为一个具有向量值收益的重复双人有限博弈。

1. 博弈公式化：
   • 学习者动作： 选择一个误覆盖水平 $a_t \in A$，其中 $A$ 是由校准集的序统计量导出的有限网格。这决定了预测集 $C_{1-a_t}(x_t)$。
   • 对手动作： 选择一个结果 $y_t$，该结果被映射到一个离散动作 $b_t \in B$，代表包含 $y_t$ 的“最紧凑”的符合集。
   • 收益向量： 学习者接收一个收益向量 $m(a_t, b_t) = (1_{b_t \leq a_t}, L(C_{1-a_t}))$，编码了误覆盖指示器（有效性）和区间长度（效率）。
2. 可接近性框架：
   • 目标是将平均收益向量 $m_T$ 引导向一个目标集 $C_{\alpha, Q} \subseteq [0, \alpha] \times [0, 2L]$。
   • 该目标集取决于对手博弈上的约束 $Q \subseteq \Delta(B)$。$Q$ 代表对手动作在渐近意义上遵循的分布集合。
   • 机会主义可接近性 (Opportunistic Approachability)： 作者采用了 Blackwell 可接近性 理论及其由 Bernstein 等人 (2014) 提出的扩展，即机会主义可接近性。该框架允许学习者在对手的博弈被限制在特定集合 $Q$ 内时，趋向一个更小、更高效的目标集，而无需学习者预先知道 $Q$。
3. 算法 (BO-ACI)：
   • 提出的策略——Blackwell 机会主义自适应符合推理 (BO-ACI)——利用了一个辅助的校准预报器 $F$。
   • 在每一轮中，$F$ 预测对手下一个动作 $b_t$ 的分布。
   • 学习者确定性地选择动作 $a_t$，旨在最小化预期长度，同时针对预测分布满足有效性约束（通过响应函数 $p^*$ 实现）。

核心贡献

1. 博弈论重构： 本文建立了一种全新的 ACI 公式化方法，将其视为具有向量值收益的重复有限博弈，明确地将有效性和效率与多目标可接近性问题联系起来。
2. 统一策略 (BO-ACI)： 作者引入了一种基于机会主义可接近性的策略，该策略保证了对于任何数据序列（随机或对抗性）的有效性，同时提供了能够适应数据未知随机性的效率保证。
3. “多种世界之最”的保证： 该策略实现了统一的保证集：
   • 可交换设置： 恢复了最优效率保证 $L(C_{1-\alpha})$，在理想条件下匹配标准符合预测的性能。
   • 对抗设置： 保证有效性，但接受平凡的效率界限（区间长度为 $2L$），这与完全对抗设置下的不可行性结果一致。
   • 中间设置： 为诸如单分布偏移或“近似可交换”数据（例如具有弱依赖关系的时间序列）等场景提供有意义的效率保证。

结果

• 理论收敛性： 定理 19 证明，在 BO-ACI 策略下，对于任何限制对手博弈的凸集 $Q$，平均收益向量 $m_T$ 几乎处处收敛到目标集 $C_{\alpha, Q}$。
• 特定场景：
  • 可交换数据： 如果对手被限制在均匀分布 $q_{unif}$ 下，平均区间长度收敛至 $L(C_{1-\alpha})$。
  • 单分布偏移： 如果测试分数遵循与校准分布 $S$ 不同的分布 $V$，则策略收敛至长度 $L(C_{1-a_{S,V}})$，其中 $a_{S,V}$ 是针对偏移分布的最优误覆盖水平。
  • $\epsilon$-可交换/时间序列： 对于与可交换性偏差较小（通过全变差或 Kolmogorov 距离衡量）的数据，该策略实现的长度接近最优可交换长度，并随着偏差的增加而优雅地退化。
  • 对抗性： 在缺乏限制（$Q = \Delta(B)$）的情况下，该策略确保有效性，但无法保证优于平凡界限的效率，这证实了获得非平凡效率所需的 $Q$-限制的必要性。
• $\epsilon$-校准： 结果被扩展到使用 $\epsilon$-校准预报器的策略（定理 34），提供了依赖于 $\epsilon$ 的收敛界限。

意义与主张
本文声称提供了一个用于自适应符合推理的统一理论框架，解决了有效性与效率之间的张力。通过利用 Blackwell 可接近性，作者证明了设计一种单一算法是可能的，该算法可以：

1. 无论数据生成机制如何，均保证有效性。
2. 自动适应数据的“随机程度”以最大化效率。
3. 在极端情况（可交换和对抗性）下恢复已知的最优结果，同时在中间且更现实的场景（如时间序列预测）中提供新的、有意义的保证，而此前的方法在这些场景中缺乏理论支撑。

作者将这项工作定位为一种“多种世界之最”的解决方案，避免了根据假设的数据分布来调整超参数的需求，因为该策略在利用 $Q$-限制的同时，本身对特定的 $Q$-限制是“无意识”的。该工作还强调了完全对抗设置的局限性，强化了效率保证需要某些数据结构性假设的观点。