不依赖预算和最优值,用排名找最优算法组合
Pareto-Optimal Anytime Algorithms via Bayesian Racing
- 用时间维度上的帕累托排序替代数值比较
- 无需归一化或已知最优解,跨问题集可稳定聚合
- 支持任意时间偏好与风险偏好下的智能选型
优化算法选择需在多个问题实例上评估性能,但部署时的计算预算常未知。现有方法要么将随时性能压缩为单一数值,依赖人工看图,或结论随算法增减而变化;基于原始目标值的方法需归一化,依赖上下界或最优值,常不可得且破坏跨实例一致性。本文提出将随时算法比较建模为时间维度上的帕累托优化:若无其他算法在所有时间点均优于某算法,则其为非支配者。通过使用排名而非目标值,本方法无需边界、无需归一化,且能对任意实例分布实现一致聚合,无需已知最优解。我们提出PolarBear(基于贝叶斯竞速的帕累托最优随时算法),通过校准不确定性的自适应采样识别随时帕累托集。贝叶斯推断基于时序普拉克特-卢瑟模型,获得两两支配关系的后验信念,支持早期淘汰确定性被支配算法。输出的帕累托集与后验分布,可直接支撑下游在任意时间偏好与风险偏好下的算法选择,无需额外实验。
原文摘要 · Abstract (English)
Selecting an optimization algorithm requires comparing candidates across problem instances, but the computational budget for deployment is often unknown at benchmarking time. Current methods either collapse anytime performance into a scalar, require manual interpretation of plots, or produce conclusions that change when algorithms are added or removed. Moreover, methods based on raw objective values require normalization, which needs bounds or optima that are often unavailable and breaks coherent aggregation across instances. We propose a framework that formulates anytime algorithm comparison as Pareto optimization over time: an algorithm is non-dominated if no competitor beats it at every timepoint. By using rankings rather than objective values, our approach requires no bounds, no normalization, and aggregates coherently across arbitrary instance distributions without requiring known optima. We introduce PolarBear (Pareto-optimal anytime algorithms via Bayesian racing), a procedure that identifies the anytime Pareto set through adaptive sampling with calibrated uncertainty. Bayesian inference over a temporal Plackett-Luce ranking model provides posterior beliefs about pairwise dominance, enabling early elimination of confidently dominated algorithms. The output Pareto set together with the posterior supports downstream algorithm selection under arbitrary time preferences and risk profiles without additional experiments.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。