📊 statistics

Taking the GP Out of the Loop

本文介绍了认知最近邻（ENN），这是一种轻量级代理模型，用于在贝叶斯优化中替代高斯过程，以实现拟合和采集的线性 $\mathcal{O}(N)$ 扩展，从而在多达 50,000 次观测的场景中将建议时间缩短一至两个数量级。

原作者： Mehul Bafna, Siddhant anand Jadhav, David Sweet

发布于 2026-05-06

📖 1 分钟阅读☕ 轻松阅读

原作者： Mehul Bafna, Siddhant anand Jadhav, David Sweet

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正在寻找制作蛋糕的最佳食谱，但你没有食谱书。你必须烘烤蛋糕、品尝它们，并从结果中学习。这就是**贝叶斯优化（BO）**所做的：它是一种智能搜索算法，通过测试不同选项并从结果中学习，来寻找“最佳”解决方案（就像完美的蛋糕一样）。

问题：“慢厨师”

过去，这些“烘烤”实验非常昂贵且缓慢（就像等待化学反应需要数天）。因此，该算法设计得非常谨慎，只烘烤少量蛋糕。它使用一种称为**高斯过程（GP）**的复杂数学工具，根据已烘烤的蛋糕来猜测下一个蛋糕的味道。

然而，GP 工具就像一位缓慢且思虑过度的厨师。每次你将一个新蛋糕加入历史记录时，厨师都必须从头重新计算整个历史，以更新其猜测。

如果你有 10 个蛋糕，速度很快。
如果你有 1,000 个蛋糕，则需要很长时间。
如果你有 50,000 个蛋糕（在现代快速计算机上很容易做到），厨师会被计算工作压得喘不过气，导致整个过程停滞不前。

论文将这种情况称为BOMO（具有大量观测值的贝叶斯优化）。旧方法根本无法跟上现代模拟的速度。

解决方案：“邻里守望”

作者 Mehul Bafna、Siddhant Anand Jadhav 和 David Sweet 提出了一种名为TuRBO-ENN的新方法。他们不使用缓慢且思虑过度的 GP 厨师，而是采用一种更简单、更快的方法，称为认知最近邻（ENN）。

将 ENN 想象成邻里守望或本地八卦网络：

工作原理：当你问“这个新蛋糕会是什么味道？”时，ENN 不会重新阅读 50,000 个蛋糕的整个历史。相反，它只查看K 个最近邻（你已经烘烤过的最相似的蛋糕）。
数学原理：它取这些少数邻居的平均味道，并猜测新味道。它还根据新蛋糕与这些邻居的距离来估计其不确定程度（不确定性）。
速度：因为它只查看一小部分邻居，所以无论你拥有 10 个蛋糕还是 50,000 个蛋糕，做出猜测所需的时间大致保持不变。它呈线性扩展，意味着即使面对海量数据，其速度也极快。

两种模式

论文表明，这种新方法适用于两种不同的场景：

嘈杂世界（现实生活）：有时，两次烘烤同一食谱会得到略有不同的结果（也许烤箱温度波动了）。在这种情况下，TuRBO-ENN 仍然会快速计算以确定数据中有多少“噪声”，然后使用一种称为UCB的简单公式选择下一个要烘烤的最佳蛋糕（该公式平衡了尝试新事物与坚持有效方法之间的关系）。
完美世界（模拟）：有时，计算机模拟是完美的，每次都会给出完全相同的结果。在这种情况下，TuRBO-ENN 甚至更快。它完全跳过了“猜测噪声”的步骤，只需对选项进行排序以找到最佳选项，从而节省更多时间。

结果

作者在各种问题（从虚拟宇宙飞船着陆到优化机器人运动）上测试了这种新方法，并将其与旧的“慢厨师”（使用 GP 的 TuRBO）进行了比较。

速度：TuRBO-ENN 做出决策的速度比旧方法快 10 到 100 倍。
质量：尽管速度快得多且更简单，但它找到的解决方案与缓慢复杂的旧方法一样好。
规模：它成功处理了多达50,000 次观测而不会减速，而旧方法则会崩溃，或者仅为了做出单个决策就需要数小时。

核心结论

这篇论文本质上指出：“我们找到了一种将繁重、缓慢的数学计算从循环中移除的方法。”通过将复杂的全局模型替换为简单的、局部的“查看你的邻居”方法，我们可以在不降低质量的情况下更快地优化事物。他们甚至将此工具作为免费软件包提供给他人使用。

技术摘要：将高斯过程移出循环

问题陈述

贝叶斯优化（BO）传统上用于黑盒问题，其中函数评估代价高昂，导致观测次数（ $N$ ）较少。然而，有一类日益增长的问题被称为多观测贝叶斯优化（BOMO），涉及快速且可并行化的评估（例如大规模模拟），其中 $N$ 可达数万。

在 BOMO 模式下，标准 BO 方法面临可扩展性瓶颈。传统方法依赖高斯过程（GP）作为代理模型。尽管现代实现已将采集时间复杂度从 $O(N^3)$ 降低至约 $O(N^2)$ ，但在每次迭代中拟合 GP 超参数的要求仍然构成巨大的计算负担。这一拟合过程通常涉及核矩阵的重构，其随 $N$ 的扩展性较差，阻碍了 BO 在海量观测计数问题上的应用。

方法论

作者提出了TuRBO-ENN，该方法在信任区域贝叶斯优化（TuRBO）框架中，用一种名为**认知最近邻（Epistemic Nearest Neighbors, ENN）**的轻量级替代方案取代了 GP 代理模型。

1. 认知最近邻（ENN）

ENN 是一种基于 K 近邻（KNN）的代理模型，旨在以线性扩展性估算函数值及不确定性（认知不确定性和偶然不确定性）。

代理模型构建：对于查询点 $x$ ，ENN 在观测集 $D$ 中识别出 $K$ 个最近邻。它将每个邻居视为函数值的一个独立估计。
不确定性量化：
- 偶然方差（ $\sigma_a^2$ ）：建模为基础噪声水平（ $s_0^2$ ）与特定观测的噪声尺度（ $s_m^2$ ）之和。
- 认知方差（ $\sigma_e^2$ ）：建模为查询点与邻居之间欧几里得距离平方的比例（ $c_e d^2(x, x_m)$ ）。
聚合：最终均值估计 $\mu(x)$ 和方差估计是使用 $K$ 个邻居的精度加权平均（逆方差加权）计算得出的。这避免了 GP 所需的 $O(N^2)$ 成对协方差计算。
复杂度：使用最大堆或 Faiss 库查找 $K$ 个最近邻，每次查询耗时为 $O(N \ln K)$ 。超参数（ $s_0, c_e$ ）的拟合通过留一交叉验证（LOOCV）伪似然上的 II 型最大似然估计（MLE）进行，并使用固定大小的子样本进行近似，以维持 $O(N)$ 的扩展性。

2. TuRBO-ENN 集成

该方法将 ENN 集成到 TuRBO 算法中，该算法利用信任区域来集中搜索努力。

含噪目标：对于含噪问题，该方法拟合 ENN 超参数并使用**置信度上界（UCB）**采集函数： $UCB(x) = \mu(x) + \sigma(x)$ 。
无噪目标：对于确定性问题，作者提出了一种免拟合变体。由于已知噪声为零时无需拟合超参数，该方法通过**非支配排序（NDS）**对 $(\mu(x), \sigma(x))$ 对进行选择。这完全消除了拟合步骤，进一步减少了提议时间。
伪贝叶斯优化（PBO）：作者验证了 TuRBO-ENN 满足伪贝叶斯优化的条件（Chen & Lam, 2025），从而确保了理论上的收敛保证。

主要贡献

ENN 代理模型：引入了一种轻量级 KNN 代理模型，能以 $O(N)$ 的拟合和查询时间估算函数值及不确定性，与 GP 的 $O(N^2)$ 或 $O(N^3)$ 扩展性形成对比。
TuRBO-ENN 算法：开发了一种 BO 方法，用 ENN 和 UCB（或无噪情况下的 NDS）取代了 TuRBO 中的 GP 和汤普森采样。
实证验证：证明在观测数高达 50,000 的问题上，TuRBO-ENN 将提议时间（拟合 + 采集）相比 TuRBO-GP 减少了 1 到 2 个数量级，且未牺牲解的质量。
理论保证：验证 TuRBO-ENN 符合 PBO 方法的资格，继承了收敛保证。
开源：发布了 ennbo Python 包。

实验结果

作者在五个模拟任务（LunarLander, Hopper, BipedalWalker, Push）和一个超参数优化任务（LASSO-DNA，维度范围为 12 到 180）上，将 TuRBO-ENN 与最先进的方法（TuRBO-GP, Optuna, SMAC, CMA-ES, DNGO, Vecchia GP）进行了基准测试。

扩展性：基于 GP 的方法（如 turbo-one, ucb）在提议时间上表现出约 $O(N^2)$ 的扩展性，而 TuRBO-ENN 呈线性扩展（ $O(N)$ ）。
加速比：TuRBO-ENN 相比 TuRBO-GP 实现了 8.5 倍到 151 倍 的加速，在观测计数（ $N$ ）较高以及超参数拟合被省略的冻结噪声（无噪）设置中，增益更为显著。
解的质量：在所有测试任务中，TuRBO-ENN 的优化性能（解的质量）与 TuRBO-GP 相当。
拟合任务：在纯回归任务（合成数据）中，ENN 的拟合速度比精确 GP、SVGP 和神经网络代理模型快数个数量级，同时保持了具有竞争力的测试集对数似然。

意义与主张

该论文认为，随着模拟能力的增长，贝叶斯优化的瓶颈已从函数评估成本转移到了优化算法本身的计算成本（提议时间）。通过将高斯过程移出循环，TuRBO-ENN 使 BO 能够扩展到拥有数万观测值的区域，而在这些区域传统方法在计算上是不可行的。

作者谦逊地声称，他们的方法为 BOMO 问题提供了一种实用且可扩展的替代方案，为确定性模拟提供“免拟合”选项，为含噪模拟提供线性扩展选项，同时保持了贝叶斯优化的理论收敛属性。他们指出，虽然他们通过 PBO 公理实现了收敛保证，但并未提供具体的遗憾界。建议的未来工作方向包括将 ENN 适配为近似最近邻算法以实现 $O(\ln N)$ 的扩展性，以及在距离度量中探索特定维度的加权。