[论文] 通过贝叶斯竞赛实现帕累托最优随时算法

Source: arXiv - 2603.08493v1

概述

论文介绍了 PolarBear，一个用于在事先不知道可用运行时间的情况下比较和选择优化算法的新框架。通过将“随时性能”（即解的质量随时间的演变）视为帕累托优化问题，作者能够对算法进行排序，而无需特定问题的界限或手动检查图形。其结果是一个统计上可靠、自动生成的算法集合，在任何可能的运行时间下都能支配其他算法。

关键贡献

• 基于Pareto的随时比较: 将算法支配性形式化，覆盖所有时间点，而不仅限于单一预算或聚合标量。
• 仅基于排名的推断: 仅使用解质量的相对排名（不使用绝对目标值），消除归一化或已知最优解的需求。
• 时序Plackett‑Luce模型: 将经典的Plackett‑Luce排名模型扩展至处理时间索引数据，提供成对支配的后验概率。
• 贝叶斯竞赛程序（PolarBear）: 自适应抽样，在算法被确信支配后即予以淘汰，大幅降低评估成本。
• 可直接决策的输出: 返回后验校准的Pareto集合，可直接嵌入下游选择工具，支持任意时间预算偏好和风险容忍度。

方法论

1. 数据收集： 在一组问题实例上运行每个候选算法，记录它在一系列时间检查点（例如每秒）达到的最佳目标值。
2. 转换为排名： 在每个检查点，按每个实例的当前最佳值对算法进行排序，并分配排名（1 = 最佳，2 = 次佳，…）。此步骤消除对实际数值的依赖。
3. 时序 Plackett‑Luce 模型： 将排名序列视为由每个算法的潜在“技能”参数（随时间演化）生成的观测。贝叶斯推断在每个检查点产生这些技能的后验分布。
4. 贝叶斯竞赛： 利用后验，计算算法 A 在 所有 未来检查点上支配算法 B 的概率。如果该概率超过用户定义的置信阈值，则将 B 从竞赛中淘汰。该过程迭代进行，将计算预算集中在仍存活的竞争者上。
5. Pareto 集合提取： 当竞赛停止（要么除少数算法外全部被淘汰，要么预算耗尽）时，剩余的算法构成 anytime Pareto 集合——集合中的任何算法在整个时间范围内都不被支配。

结果与发现

• 效率: 在基准套件（例如 SAT、TSP、连续优化）中，PolarBear 在仅评估约 30% 的总运行时间后，就消除了多达 70% 的候选算法，节省了大量计算资源。
• 鲁棒性: 由于使用了排名，该方法即使在实例之间目标尺度差异极大或最优值未知的情况下也能保持一致的表现。
• 决策质量: 当在不同时间预算偏好下模拟下游选择时，PolarBear 产生的帕累托集合的选择与最优（oracle）选择的差距在 2% 以内，较传统的基于标量的基准（例如 AUC、曲线下面积）提升了 10–15%。
• 校准: 支配关系的后验概率校准良好（Brier 分数 < 0.05），让开发者有信心设定激进的淘汰阈值而不会冒过早丢弃的风险。

实际意义

• 自动化算法组合： DevOps 流水线可以集成 PolarBear，构建一个能够自动适应可用计算时间的求解器组合，在任何时刻提供最佳可能的解。
• 超参数调优服务： 基于云的优化 API 可以利用 Pareto 集合向终端用户展示“时间预算”滑块，内部将请求映射到合适的算法，无需额外的基准测试。
• 资源感知调度： 在作业运行时间不可预测的异构集群中，调度器可以查询后验分布，选择在剩余实际时间下最小化期望后悔的算法。
• 风险感知决策： 贝叶斯后验使得风险敏感的策略成为可能（例如，“选择在 10 秒后至少有 95 % 的概率在最佳可能解的 5 % 以内的算法”）。
• 降低基准测试成本： 企业可以在少量实例上评估数十个候选求解器，仍然获得可靠的随时可用的 Pareto 前沿，从而减少昂贵的大规模基准测试。

限制与未来工作

• 对非常大算法池的可扩展性: 虽然贝叶斯竞赛降低了运行时间，但推断步骤仍然随活跃算法数量呈二次增长；稀疏近似或层次建模可能有所帮助。
• 单调改进的假设: 该方法假设解的质量随时间永不下降，这在大多数确定性优化器中成立，但在随机或频繁重启的策略中可能被违反。
• 时间粒度: 选择检查点间隔是一个权衡；网格过粗可能错过短期优势转变，而网格过细会增加数据量。自适应检查点是一个有前景的方向。
• 向多目标问题的扩展: 当前的公式只处理单一目标；将排序模型扩展到处理向量化目标（例如成本与延迟）将扩大适用范围。

PolarBear 提供了一种原则性、对开发者友好的方式来回答“当我只剩 X 秒时应该运行哪个优化器？”的问题——将传统上手动、基于图表的过程转变为自动化、具统计依据的决策引擎。

作者

• Jonathan Wurth
• Helena Stegherr
• Neele Kemper
• Michael Heider
• Jörg Hähner

论文信息

• arXiv ID: 2603.08493v1
• 分类: cs.NE, cs.LG
• 出版日期: 2026年3月9日
• PDF: 下载 PDF