Optimal Model Selection for Conformalized Robust Optimization¶
作者: Yajie Bao, Yang Hu, Haojie Ren, Peng Zhao, Changliang Zou
来源: Journal of the American Statistical Association
主题: 因果推断
相关性: 6/10
机构绿灯: Fudan University(US News 前 50,免分进入精读)
链接: 期刊页 · arXiv
一、领域脉络与小综述¶
这个方向是什么¶
本文研究的核心问题是:在"上下文鲁棒优化"(Contextual Robust Optimization, CRO)框架下,如何从一组预训练的不确定性量化模型(即不同的非一致性评分函数)中选择最优模型,以在保证鲁棒性约束的同时最小化下游决策风险。这是一个典型的"预测-决策"(predict-then-optimize)流水线问题,但加入了两个关键要素:(i) 使用 conformal prediction 构造的预测集来驱动鲁棒决策;(ii) 模型选择本身会破坏 conformal 预测的有效性(因为选择过程引入了对数据的依赖)。该方向处于不确定性量化、分布自由推断与决策科学三个领域的交叉点,属于方法论的"最后一公里"问题——即预测不确定性如何转化为高质量决策。
发展脉络¶
- 奠基工作:conformal prediction 的有限样本边际覆盖保证(Vovk et al., 2005)为后续所有工作提供了理论基础。这一保证的核心是交换性假设,即校准数据和测试数据可交换。在此基础上,Lei et al. (2018) 将 conformal prediction 与回归问题结合,建立了渐近条件覆盖与边际覆盖的桥梁。
- 主要进展:将 conformal prediction 引入决策问题是一个自然延伸。Johnstone and Cox (2022) 首次将 conformal 预测集用于鲁棒优化,提出了 CRO 的基本框架。随后,Sun et al. (2023) 系统研究了不同评分函数(box、ellipsoid)下 CRO 问题的可解性。在模型选择方面,Yang and Kuchibhotla (2025) 和 Liang et al. (2024) 分别提出了 EFCP/VFCP 和 ModSel-CP 方法,但这些方法的目标是选择使预测集宽度最小的模型,而非使下游决策风险最小的模型。作者明确指出(见 Section 5.1 和 Appendix G.5),宽度最小化与决策风险最小化并不等价——一个更窄的预测集可能对应更差的决策。
- 当前 frontier:本文的位置在于填补"模型选择"与"决策风险"之间的空白。作者提出的 CROMS 框架将模型选择直接嵌入 CRO 的决策风险最小化目标中,而非传统的预测集宽度。此外,本文还处理了有限样本下模型选择带来的覆盖偏差问题,通过全 conformal 技术(F-CROMS)和 Jackknife+ 技术(J-CROMS)恢复有限样本保证。
子线索聚类¶
- Conformal prediction 的模型选择:Yang and Kuchibhotla (2025)、Liang et al. (2024) 以及本文的 CROMS 框架。这条线索关注"选哪个模型"的问题,但目标函数不同(宽度 vs. 决策风险)。
- 端到端(End-to-End)训练:Yeh et al. (2024) 和 Chenreddy and Delage (2024) 提出直接训练预测集以最小化决策风险,但缺乏有限样本保证。本文的 E-CROMS 与之对比,指出端到端方法因样本分裂而损失效率。
- 鲁棒优化的预测集构造:Chenreddy et al. (2022)、Patel et al. (2024) 研究如何构造预测集以服务于鲁棒决策,但未涉及模型选择。
核心问题¶
- 如何定义"最优模型":在 CRO 中,最优模型应最小化期望决策风险,而非预测集宽度。这是一个目标函数的重新定义问题。
- 如何保证模型选择后的覆盖有效性:当模型选择依赖于数据时,交换性被破坏,标准 conformal 保证失效。需要新的技术恢复有限样本保证。
- 如何在保证鲁棒性的同时实现决策最优性:鲁棒性(worst-case)与最优性(average-case)之间存在张力,需要权衡。
⚠️ 作者的 framing¶
作者将缺口 frame 为:现有 conformal 模型选择方法(Yang & Kuchibhotla, Liang et al.)以预测集宽度为准则,但"宽度最小化并不直接关联下游决策风险"(作者在 Section 1.1 和 Appendix G.5 中反复强调这一点)。作者将本文定位为"首个将模型选择与决策风险统一在 CRO 框架下的工作"。竞争路线(端到端训练)被作者淡化为"缺乏有限样本保证"(见 Section 2.3 对 Yeh et al. 的讨论)。值得注意的是,作者没有提及 sensitivity analysis 或 partial identification 等因果推断中的鲁棒决策方法,这可能是一个值得研究者去查的空白。
张力¶
未见明显对立引用。但存在一个潜在张力:作者声称"模型选择应基于决策风险",但 CRO 本身是 worst-case 优化,而模型选择是 average-case 优化(期望决策风险)。这两者的目标函数不一致,作者在 Theorem 2.2 中通过渐近论证弥合了这一差距,但有限样本下的行为可能更复杂。
二、最核心、最简单的例子 / 数学问题¶
第一步:符号、模型、可观测数据¶
- 符号:
- \( X \in \mathcal{X} \subseteq \mathbb{R}^d \):协变量(可观测)
- \( Y \in \mathcal{Y} \):标签(可观测,训练/校准阶段)
- \( Z \in \mathcal{Z} \):决策变量(决策者的选择)
- \( \phi(y, z) \):损失函数,衡量决策 \( z \) 在真实标签 \( y \) 下的代价
- \( S_\lambda(x, y) \):非一致性评分函数,由预训练模型 \( \lambda \in \Lambda \) 定义
- \( U_\lambda(x) = \{ c : S_\lambda(x, c) \le \hat{q}_\lambda \} \):conformal 预测集
- \( \hat{q}_\lambda \):校准数据上的经验分位数
- \( z_\lambda(x) = \arg\min_{z \in \mathcal{Z}} \max_{c \in U_\lambda(x)} \phi(c, z) \):CRO 决策
- \( \alpha \):名义误差水平(如 0.1)
- \( n \):校准样本量
-
\( \Lambda \):候选模型索引集(有限或连续)
-
模型:数据生成机制为 \( (X_i, Y_i) \overset{i.i.d.}{\sim} P \),其中 \( P \) 是任意联合分布(无参数假设)。每个候选模型 \( \lambda \) 定义一个评分函数 \( S_\lambda \),该函数可以是任何预训练模型的输出(如神经网络 softmax、回归残差等)。关键假设:评分函数 \( S_\lambda \) 是固定的(预训练),不随校准数据变化。
-
可观测数据:校准集 \( \{(X_i, Y_i)\}_{i=1}^n \)(用于构造 conformal 预测集和进行模型选择),测试点 \( X_{n+1} \)(协变量可观测,标签 \( Y_{n+1} \) 未知)。
第二步:最小内核¶
问题:假设我们有两个候选模型 \( \lambda_1, \lambda_2 \),每个模型定义一个评分函数 \( S_{\lambda_1}, S_{\lambda_2} \)。我们只有 \( n \) 个校准样本。如何选择模型,使得最终决策 \( \hat{z}(X_{n+1}) \) 的期望损失 \( \mathbb{E}[\phi(Y_{n+1}, \hat{z}(X_{n+1}))] \) 尽可能小,同时保证鲁棒性 \( P\{\phi(Y_{n+1}, \hat{z}(X_{n+1})) \le \max_{c \in U_{\hat{\lambda}}(X_{n+1})} \phi(c, \hat{z}(X_{n+1}))\} \ge 1-\alpha \)?
最简例子:\( \mathcal{Y} = \{1, 2\} \)(二分类),\( \mathcal{Z} = \{1, 2\} \)(两个决策),损失矩阵 \( \phi(y, z) = \mathbb{1}\{y \ne z\} \)(0-1损失)。两个候选模型: - \( \lambda_1 \):评分函数 \( S_{\lambda_1}(x, y) = 1 - \hat{f}_1(y|x) \),其中 \( \hat{f}_1 \) 是逻辑回归 - \( \lambda_2 \):评分函数 \( S_{\lambda_2}(x, y) = 1 - \hat{f}_2(y|x) \),其中 \( \hat{f}_2 \) 是随机森林
核心困难:如果直接用校准数据选择使经验决策风险最小的模型,即 \( \hat{\lambda} = \arg\min_{\lambda} \frac{1}{n} \sum_{i=1}^n \phi(Y_i, z_\lambda(X_i)) \),那么选择过程引入了对校准数据的依赖。这破坏了 conformal 预测的交换性假设——因为预测集 \( U_{\hat{\lambda}}(X_{n+1}) \) 的构造依赖于 \( \hat{\lambda} \),而 \( \hat{\lambda} \) 又依赖于校准数据。结果是,标准 conformal 保证 \( P\{Y_{n+1} \in U_{\hat{\lambda}}(X_{n+1})\} \ge 1-\alpha \) 不再成立。
本文的核心思想:将模型选择视为一个"对称化"问题。E-CROMS 直接使用经验决策风险进行选择,但承认这会产生 \( O(\sqrt{\log|\Lambda|/n}) \) 的覆盖偏差(Theorem 2.1)。F-CROMS 通过全 conformal 技术(将测试点 \( X_{n+1} \) 与每个假设标签 \( y \) 一起加入校准集,重新计算分位数)恢复有限样本保证,但代价是计算复杂度。J-CROMS 通过 Jackknife+ 技术(留一法)在计算效率和覆盖保证之间取得平衡。
为什么这个例子能说明问题:在二分类 0-1 损失下,CRO 问题退化为"选择使最坏情况损失最小的决策",而模型选择的目标是"选择使期望损失最小的模型"。这两者的差异在有限样本下会产生可量化的偏差——这正是 Theorem 2.1 和 Theorem 2.2 所刻画的。
三、这篇论文做了什么¶
三句话¶
- 研究问题:在 CRO 框架下,如何从候选模型集合中选择最优模型,使得最终决策在满足 \( 1-\alpha \) 鲁棒性约束的同时,渐近最小化期望决策风险。
- 核心方法:提出 CROMS 框架,包含三个算法——E-CROMS(高效但仅渐近有效)、F-CROMS(全 conformal,有限样本有效但计算昂贵)、J-CROMS(Jackknife+,有限样本有效且计算可行),并进一步扩展至个性化模型选择(CROiMS)。
- 主要结论:E-CROMS 的覆盖偏差为 \( O(\sqrt{\log|\Lambda|/n}) \)(Theorem 2.1),决策风险上界为 \( O(\sqrt{\log|\Lambda|/n} + R_n(\mathcal{F}) + R_n(\mathcal{G})) \)(Theorem 2.2);F-CROMS 和 J-CROMS 分别实现 \( 1-\alpha \) 和 \( 1-2\alpha \) 的有限样本覆盖保证(Theorem 3.1, 3.5);CROiMS 在温和非参数假设下实现渐近条件覆盖与决策最优性(Theorem 4.1)。
关键设定与假设¶
- 设定:数据 \( (X_i, Y_i) \) i.i.d. 来自任意分布 \( P \)。候选模型集合 \( \{S_\lambda : \lambda \in \Lambda\} \) 预训练且固定。损失函数 \( \phi(y, z) \) 有界(\( |\phi| \le B \)),且对 \( z \) 满足 Lipschitz 条件(Assumption 3)。
- 假设:
- Assumption 1:评分函数 \( S_\lambda(X, Y) \) 的分布函数 \( F_\lambda \) 在分位数附近有密度下界 \( \mu > 0 \)。这保证了分位数估计的收敛速度。
- Assumption 2:损失函数有界(\( B < \infty \)),用于集中不等式。
- Assumption 3:CRO 决策 \( z_\lambda(x; q) \) 对阈值 \( q \) 是 Lipschitz 连续的(常数 \( L \))。这保证了阈值估计误差可以转化为决策损失误差。
- Assumption 4(CROiMS):协变量密度下界 \( \rho \),条件分布 \( F_\lambda(\cdot|x) \) 的 Lipschitz 性,以及核函数的正则性。这些是局部常数估计的标准条件。
- Assumption 5(CROiMS):条件决策风险 \( \mathbb{E}[\phi(Y, z_\lambda(X; q))|X=x] \) 关于 \( x \) 是 Lipschitz 连续的。
- Assumption C.1/C.2(网格近似):决策损失对预测集边界的 Lipschitz 性,以及网格近似误差的控制。
- 最小风险间隙条件(Theorem 3.2):\( \beta_n \ge O(\sqrt{\log|\Lambda|/n}) \),即最优模型与次优模型之间的决策风险差必须足够大,才能保证模型选择的一致性。
主要结果¶
- Theorem 2.1(E-CROMS 覆盖):\( P\{Y_{n+1} \in \hat{U}_{\text{E-CROMS}}(X_{n+1})\} \ge 1-\alpha - 2R_n(\mathcal{F}) \),其中 \( R_n(\mathcal{F}) \) 是函数类 \( \mathcal{F} = \{\mathbb{1}\{S_\lambda(x,y) > q\}\} \) 的 Rademacher 复杂度。对于有限 \( |\Lambda| \),\( R_n(\mathcal{F}) = O(\sqrt{\log|\Lambda|/n}) \)。直觉:模型选择引入了对校准数据的依赖,导致覆盖偏差正比于候选模型集合的复杂度。
- Theorem 2.2(E-CROMS 决策风险):\( \mathbb{E}[\phi(Y_{n+1}, \hat{z}_{\text{E-CROMS}}(X_{n+1}))] \le v^*_\Lambda + O(\sqrt{\log|\Lambda|/n} + R_n(\mathcal{F}) + R_n(\mathcal{G})) \),其中 \( v^*_\Lambda \) 是最优模型的期望决策风险。直觉:决策风险的上界由三部分组成——模型选择的泛化误差、分位数估计误差、以及 CRO 问题的 Lipschitz 常数。
- Theorem 3.1(F-CROMS 覆盖):\( P\{Y_{n+1} \in \hat{U}_{\text{F-CROMS}}(X_{n+1})\} \ge 1-\alpha \),无任何分布假设。证明路线:通过全 conformal 技术,将测试点 \( X_{n+1} \) 与每个假设标签 \( y \) 一起加入校准集,重新计算分位数。由于模型选择过程对增广数据集是对称的,交换性得以恢复。
- Theorem 3.5(J-CROMS 覆盖):\( P\{Y_{n+1} \in \hat{U}_{\text{J-CROMS}}(X_{n+1})\} \ge 1-2\alpha \)。证明路线:基于 Jackknife+ 的留一法,利用留一预测残差的交换性。
- Theorem 4.1(CROiMS):在 Assumption 4-5 下,CROiMS 实现 \( 1-\alpha - O(\sqrt{\log|\Lambda|/(n h_n^d)}) \) 的渐近条件覆盖,以及 \( v^*_\Lambda(X_{n+1}) + O(h_n + \sqrt{\log|\Lambda|/(n h_n^d)}) \) 的渐近条件决策风险。证明路线:结合局部常数估计(核方法)与全 conformal 技术。
证明路线与技术技巧¶
- 整体路线:论文的证明框架分为三步——(i) 建立模型选择的泛化界(通过 Rademacher 复杂度或 VC 维);(ii) 建立分位数估计的一致性(通过密度下界假设);(iii) 将分位数误差转化为决策风险误差(通过 Lipschitz 假设)。
- 关键技巧:
- 对称化:E-CROMS 的覆盖偏差分析使用了标准的对称化技巧,将经验过程的上确界转化为 Rademacher 复杂度。
- 全 conformal:F-CROMS 的关键在于将模型选择过程视为一个"算法",该算法对增广数据集是对称的。通过将测试点与每个假设标签一起加入校准集,恢复了交换性。
- Jackknife+:J-CROMS 利用留一法的预测残差,构造了类似 Jackknife+ 的预测集。其覆盖保证依赖于留一残差的交换性,而非模型选择的对称性。
- 网格近似:对于连续标签空间,F-CROMS 需要搜索整个标签空间。作者提出网格近似,将标签空间离散化,并证明了网格误差可以控制在 \( O(\epsilon_{\text{grid}}) \) 内(Theorem 3.4)。
- 加权 Rademacher 复杂度:CROiMS 的证明使用了加权 Rademacher 复杂度,其中权重由核函数决定。这允许在局部邻域内控制函数类的复杂度。
真实例子¶
- 合成数据:分类任务(\( |\mathcal{Y}| = 5 \)),候选模型为不同惩罚参数 \( \lambda \) 的评分函数。结果显示 E-CROMS 和 F-CROMS 在决策损失上显著优于基线(Naive-CP、E2E),且 F-CROMS 在有限样本下保持覆盖。
- 回归任务:\( Y \subset \mathbb{R}^2 \),候选模型为不同特征子集的 box 评分函数。J-CROMS 在计算效率和决策性能之间取得最佳平衡。
- COVID-19 影像诊断:真实数据,4 个候选模型(不同训练数据分布),CROiMS 在保持条件覆盖的同时,将平均决策损失降低约 20%。
- 皮肤镜诊断:HAM10000 数据集,CROiMS 在年龄分组上实现约 41% 的决策损失降低。
🔎 结论是否比证明窄¶
- E-CROMS 的覆盖保证:Theorem 2.1 给出的是边际覆盖下界 \( 1-\alpha - 2R_n(\mathcal{F}) \),但作者在 Section 2.3 中承认,对于连续标签空间,E-CROMS 的覆盖偏差可能无法通过简单的分位数调整来消除。这比 Theorem 2.1 的陈述要窄。
- F-CROMS 的决策最优性:Theorem 3.2 需要最小风险间隙条件 \( \beta_n \ge O(\sqrt{\log|\Lambda|/n}) \)。如果候选模型之间的性能差异很小(例如,两个模型在有限样本下几乎等价),则 F-CROMS 可能无法选择最优模型。作者在 Appendix C.2 中讨论了这一条件,但未给出放松该条件的方法。
- CROiMS 的渐近性:Theorem 4.1 的收敛速度依赖于带宽 \( h_n \) 的选择。作者在 Section 4 中建议 \( h_n \asymp n^{-1/(d+2)} \),但未讨论自适应带宽选择或数据驱动的最优带宽。
- 计算复杂度:F-CROMS 需要搜索整个标签空间,对于连续标签空间,其计算复杂度为 \( O(|\mathcal{Y}| \cdot n) \)(分类)或 \( O((n h_n^d)^{-1}) \)(回归,网格近似)。作者在 Section 3.1 中提出了加速方法,但未给出严格的计算复杂度分析。
四、开放问题¶
-
有限样本下的最优带宽选择:Theorem 4.1 的收敛速度依赖于带宽 \( h_n \),但作者仅给出了理论最优阶 \( h_n \asymp n^{-1/(d+2)} \),未讨论如何在实际中数据驱动地选择带宽。扎根于 Theorem 4.1 的陈述和 Section 4 的讨论。
-
放松最小风险间隙条件:Theorem 3.2 要求候选模型之间的决策风险差至少为 \( O(\sqrt{\log|\Lambda|/n}) \)。当候选模型高度相似时(例如,同一模型的不同正则化参数),该条件可能不满足。扎根于 Theorem 3.2 的假设和 Appendix C.2 的讨论。
-
覆盖与鲁棒性之间的最优权衡:作者在 Appendix A 中分析了覆盖与鲁棒性之间的差距 \( \Delta(U) \),并指出可以通过调整预测集的置信水平来精确控制鲁棒性。但这一调整依赖于数据分布(如 Gaussian 假设),在分布未知时如何实现有限样本控制仍是一个开放问题。扎根于 Appendix A 的 Proposition A.1 和 Section 7 的讨论。
-
连续模型空间的高效搜索:当 \( \Lambda \) 是连续空间时,E-CROMS 的 ERM 问题(公式 5)通常非凸。作者在 Section 7 中建议使用隐式微分技术,但未给出收敛性保证。扎根于 Section 7 的 future work 讨论。
-
个性化模型选择的泛化界:CROiMS 的 Theorem 4.1 给出了渐近结果,但未提供非渐近的有限样本界。扎根于 Theorem 4.1 的陈述和 Section 4 的讨论。
提醒:要确认上述开放问题是否是真 gap,建议去读以下近期文献的 intro(约 5 篇):(1) Yang & Kuchibhotla (2025) 的模型选择与 conformal 预测;(2) Liang et al. (2025) 的 ModSel-CP;(3) Kiyani et al. (2025) 的决策理论 conformal 预测;(4) Gibbs & Candès (2021) 的 adaptive conformal;(5) Barber et al. (2023) 的 distribution-free 推断。如果这些文献的 intro 都指向同一个未解决问题,那大概率是真 gap;如果互相打架,则可能是机会。
Maintained by 陈星宇 · Homepage · Source on GitHub