Cost-aware Stopping for Bayesian Optimization

技术摘要：面向贝叶斯优化的成本感知停止策略

问题陈述
在自动化机器学习、科学发现以及其他贝叶斯优化（BO）应用中，从业者面临着一个挑战：即如何决定何时终止昂贵黑盒函数的评估。虽然现有的停止规则已经存在，但它们往往无法以原则性的方式处理变化的评估成本。

• 启发式规则（例如固定迭代次数或在最佳值保持不变时停止）缺乏理论保证，且可能导致过早停止或产生不必要的评估。
• 基于遗憾（Regret-based）的规则（例如 UCB-LCB、知识梯度 KG）在最小化简单遗憾方面具有理论基础，但通常是为统一成本设置设计的。它们并未明确考虑评估成本，在成本较高时，往往会导致过高的累积成本和高额的“成本调整后遗憾”（cost-adjusted regret）。
• 成本感知采集函数（例如潘多拉魔盒吉廷斯指数 PBGI 和单位成本对数期望改进量 LogEIPC）已被开发用于优化解决方案质量与成本之间的权衡，但其与自适应停止规则的集成尚未得到系统的研究。

核心目标是设计一种停止规则，以优化期望成本调整后简单遗憾，其定义为简单遗憾（当前找到的最佳解与全局最优解之间的差异）与数据收集的累积成本之和。

方法论
作者提出了一种源自**潘多拉魔盒（Pandora's Box）**决策框架的新颖且具有原则性的成本感知停止规则。该方法建立了两种最先进的成本感知采集函数之间的理论联系：

1. 潘多拉魔盒吉廷斯指数 (PBGI)： 源自潘多拉魔盒问题的动态规划解，并针对相关贝叶斯优化进行了适配。
2. 单位成本对数期望改进量 (LogEIPC)： 一种对贝叶斯最优策略的一步近似。

所提出的停止规则被称为 PBGI/LogEIPC 停止规则，其定义为：当没有任何未观测点能提供值得其评估成本的预期改进时，优化应当停止。数学表达式为，当满足以下条件时，在时间 $\tau$ 停止：
$$\min_{x \in X \setminus \{x_1, \dots, x_\tau\}} \alpha_{PBGI}^\tau(x) \geq y^*_{1:\tau}$$
或者等价于：
$$\max_{x \in X \setminus \{x_1, \dots, x_\tau\}} \alpha_{LogEIPC}^\tau(x) \leq 0$$
其中 $y^*_{1:\tau}$ 是迄今为止观测到的最佳值。

关键实现细节包括：

• 后验更新时机： 该规则利用在当前迭代后验更新之后计算出的采集函数值（前瞻性），作者认为这更好地反映了“公平价值”（fair value）的直觉，并且相比于后瞻性方法具有经验上的增益。
• 处理未知成本： 当成本未知时，将其建模为随机过程（例如在对数成本上的高斯过程），并使用期望成本 $E[c(x)]$ 进行停止条件判定。
• 稳定性控制： 为了防止由模型波动或采集函数优化不完善（尤其是在高维情况下）引起的伪停止，作者强制执行了一个稳定期，并对停止信号应用了移动平均平滑处理。

主要贡献

1. 一种新型成本感知停止规则： 本文提出了一种源自潘多拉魔盒理论的自适应停止规则，该规则自然地扩展到了期望改进设计原则。它提供了一个适用于经典及成本感知型贝叶斯优化的统一框架。
2. 理论保证： 作者证明了当与 PBGI 或 LogEIPC 采集函数配对时，所提出的停止规则满足期望成本调整后简单遗憾的理论上界。具体而言，该策略被保证其表现不会差于“立即停止”基准（即在第一次评估后立即停止）。这是针对贝叶斯优化中任何自适应停止规则提供的首个此类理论保证。
3. 经验验证： 研究通过合成任务以及经验基准测试（用于超参数优化的 LCBench 和用于神经架构搜索的 NATS-Bench）进行了系统性评估。

结果

• 合成任务： 在 1D 和 8D 贝叶斯遗憾设置下（采用统一、线性及周期性成本函数），与相应采集函数配对的 PBGI/LogEIPC 停止规则始终能匹配或超越其他组合（包括 UCB-LCB、LogEIPC-med 和 PRB）。在处理高成本场景时，该规则表现尤为稳健。
• 经验基准：
  • 在 LCBench（35 个数据集）上，与 PBGI 或 LogEIPC 配对的规则在约 75% 的任务中排名在前 3 位。
  • 在 NATS-Bench 上，该规则表现出竞争力，接近事后最优性能。
  • 该规则能够可靠地在迭代上限（200 次迭代）之前停止，而基准遗憾类规则（如 SRGap-med 和 UCB-LCB）经常无法实现早期停止，从而产生了过高的成本。
  • 作者指出，在特定小型数据集上的表现欠佳，可能是由于基准测试固有的验证/测试不匹配导致的，而非停止规则本身的问题。

意义与主张
本文旨在解决贝叶斯优化中一个关键但研究不足的实际问题：即成本感知的停止时机判定。

• 理论进展： 该工作弥合了成本感知采集函数与自适应停止之间的鸿沟，首次提供了形式化保证，证明自适应策略产生的成本调整后遗憾不会差于立即停止。
• 实际效用： 所提出的规则通过直接从评估成本中推导阈值，消除了对启发式停止阈值（例如固定常数或基于中位数的阈值）进行人工调优的需求。
• 鲁棒性： 该框架在不同的成本结构和模型误设情况下均展示了鲁棒性，为昂贵优化任务中的启发式停止准则提供了一个有原则性的替代方案。

作者总结道，尽管这些被视为未来的研究方向而非当前的贡献，但其框架可以扩展到涉及噪声、多保真度或批量评估的情景，以及其他的目标函数形式。