无悔贝叶斯优化与有限库输入扭曲核

# 有限库输入扭曲核的无遗憾贝叶斯优化
来源：https://arxiv.org/html/2609.02993

## 有限库输入扭曲核的无遗憾贝叶斯优化
致谢：实验代码已开源：
https://github.com/edvin-ketabati/bogp-paper-experiments

###### 摘要
高斯过程贝叶斯优化（GP-BO）擅长处理昂贵函数的黑箱优化，例如超参数优化（HPO）和多智能体系统（MAS）设计。部分方法，特别是高斯过程置信上界（GP-UCB），已存在收敛速率保证，但要求使用固定的核函数。关键在于，核函数决定了输入相似度如何影响目标值的相似性。当原始坐标与这种几何关系匹配度不佳时（如对数尺度的超参数或局部峰值），输入扭曲能显著提升采样效率；然而已知的GP-UCB证明需要固定的核函数。我们提出**有限库输入扭曲贝叶斯优化（FLIWBO）**，该方法通过任何依赖历史记录的规则，从有限个平滑输入映射库中选择扭曲函数。它通过适应输入几何加速学习，同时在温和假设下保持高概率收敛保证，并带有显式的 \(N_{\varepsilon}\) 库大小代价项。受控诊断实验表明，有限库扭曲能修复预设的几何失配问题，并识别FLIWBO的失效情形。在四个重复基准测试中——扭曲合成目标函数、一个置信栅栏陷阱和时尚MNIST超参数优化——FLIWBO-UCB在几何误设情况下优于原始坐标GP-UCB，逃脱了甚至能击败预言机扭曲期望改进（EI）的陷阱，并恢复了大部分手动对数缩放带来的收益，同时在已测试的具有匹配遗憾保证的方法中领先。一个20维多智能体系统设计研究进一步展示了在昂贵噪声评估下的可行性。实验代码已开源：
https://github.com/edvin-ketabati/bogp-paper-experiments。
联系邮箱：[email protected], [email protected]
AI Sweden，瑞典哥德堡

## 1 引言
许多科学和技术的进步依赖于只能评估有限数量候选设计或配置的优化问题。在许多此类问题中，性能只有通过运行昂贵的实验、模拟或训练过程才能显现，几乎没有穷举搜索的余地。贝叶斯优化（BO）非常适合这种黑箱环境，因为它使用概率代理模型来引导评估流向有前景或信息量大的输入。然而，当评估成本高昂时，仅仅经验表现良好是不够的：我们还希望数学上保证探索的成本不会无限累积。高斯过程置信上界（GP-UCB）是一种开创性的方法，它在预测性能和不确定性之间进行权衡；在温和假设下，它具有亚线性累积遗憾，因此其相对于最优解的平均损失随时间推移而消失（Srinivas等人，2010；Chowdhury和Gopalan，2017）。这些保证要求使用固定的核函数，该核函数编码了输入接近度如何影响目标值相似性。不幸的是，用于描述问题的坐标通常与目标函数的变化方式匹配不佳。例如，在超参数优化（HPO）中，学习率通常按对数尺度处理，而其他参数则保持线性尺度。图1（见原文链接）提供了一个一维说明：原始坐标几何可能隐藏重要的变化，输入扭曲可以将其暴露出来，从而使优化将查询集中在关键区域。因此，输入扭曲可以加速GP-BO（Snoek等人，2014），但理想情况下不应牺牲理论保证。
（图表说明）
图1：所有面板使用相同的P1一维目标函数和BO预算，如第4节所述。
*(a) 问题：* 在原始坐标中使用标准固定核Matérn GP，将相等的x距离视为具有相同信息量；它将查询分散在平坦背景区域，并过度平滑了狭窄的峰值。
*(b) 直观修复：* 所选的单调Beta累积分布函数（CDF）扭曲 \(z = w(x)\) 扩展了峰值的邻域，因此相同的基核能看到一个宽广、平滑的特征并产生更好的拟合。
*(c) 结果：* 将该后验映射回原始x空间得到一个尖锐、定位良好的拟合；扭曲改变的是输入几何，而非目标函数本身。
*(d) 我们的贡献：* FLIWBO从优化数据中学习输入几何，而非要求用户指定预言机扭曲。从浅到深，所选扭曲（Beta CDF）向一种扩展狭窄高值区域的表示自适应，表明随着观测的积累，算法能自行识别合适的扭曲。
在(a)-(c)中，蓝色曲线是目标函数，圆点是查询点，红色虚线是GP均值，带状区域是 \(\mu \pm 2\sigma\)；在(d)中，菱形标记最大值点，颜色表示FLIWBO迭代轮次。
从观测数据中学习这样的扭曲使得核函数依赖于历史记录，这阻碍了标准GP-UCB证明。现有的关于未知平稳超参数、误设和有限模型选择的理论并未涵盖这种数据自适应的非线性几何形式（Wang和de Freitas, 2014；Berkenkamp等人, 2019；Bogunovic和Krause, 2021；Cutkosky等人, 2021；Liu和Singh, 2023）。我们提出三个贡献来调和这种紧张关系。

**方法。** 我们提出有限库输入扭曲贝叶斯优化（FLIWBO）（Ketabati Augustinsson, 2026）。该方法维护一个有限的平滑输入扭曲库（等效于候选GP），它们共享一个观测历史，并允许任何（特别是依赖历史的）规则来选择每轮的活跃扭曲。所选扭曲决定了下一轮查询的采集函数，在线适应输入几何以加速学习。

**理论。** 据我们所知，FLIWBO是第一个为从自身历史中学习非线性输入变换的BO提供高概率亚线性累积遗憾保证的方法。在常见假设下（目标函数属于 \(H_{\text{RKHS}}\)（Srinivas等人, 2010），扭曲的均匀正则性（Snoek等人, 2014），以及标准Matérn型Sobolev-RKHS等价性（Kanagawa等人, 2018）），我们证明了RKHS和信息增益边界以及每个分支的同步GP-UCB置信度。该保证适用于任何历史依赖的选择器；库大小对数影响置信度，并通过 \(N_{\varepsilon}\) 影响遗憾因子。

**证据。** 受控诊断实验表明，有限库扭曲能修复预设的几何失配问题，并识别固定几何更优的失效情形。在四个重复基准测试中——扭曲合成目标函数、一个置信栅栏陷阱和时尚MNIST超参数优化——FLIWBO-UCB在几何误设情况下优于原始坐标GP-UCB，逃脱了甚至能击败预言机扭曲期望改进（EI）的陷阱，并恢复了大部分手动对数缩放带来的收益，同时在已测试的具有匹配频率学遗憾保证的方法中领先。一项协作可行性研究进一步将FLIWBO应用于一个具有昂贵噪声评估的20维多智能体系统设计问题，并将选定的设计与人类工程师的参考进行了比较。代码、配置和数据在补充代码与数据包中提供。

## 2 相关工作
我们兼容的有限扭曲核族在数据自适应非线性几何下提供了均匀正则性、共同的信息增益控制和同步的GP-UCB置信度。据我们所知，没有类似的累积遗憾分析。

##### 自适应下的有保证GP优化。
固定核GP-UCB通过频率置信和最大信息增益来限定累积遗憾（Srinivas等人, 2010；Chowdhury和Gopalan, 2017）。未知超参数保证规定了期望改进（EI）估计或扩展了平稳函数类（Wang和de Freitas, 2014；Berkenkamp等人, 2019）；两者均未适应非线性几何。误设GP优化通过近似目标为一个有界RKHS函数来付出代价（Bogunovic和Krause, 2021）；我们则假设库内可实现性，排除库外的误设。

##### 有限模型族。
模型选择方案消除与遗憾边界不一致的候选算法或先验（Cutkosky等人, 2021）；GP变体消除有限先验，有时使用超先验（Ziomek等人, 2025；Sandberg和Haghir Chehreghani, 2025）。RKHS类自适应以模型选择代价识别有效类，包括在未知核正则性下（Liu和Singh, 2023）。FLIWBO则利用相容性：一个基核的平滑映射将目标函数置于每个候选RKHS中，具有一致的范数和信息增益边界。因此，置信度先于任意历史依赖的选择；无需识别真实或最佳扭曲。

##### 学习输入几何。
除了长度尺度，度量和深度核模型学习更丰富的表示（Snoek等人, 2012；Titsias和Lázaro-Gredilla, 2010；Kiyohara和Kumagai, 2025）。Snoek等人（2014）最直接地推断连续坐标级的Beta-CDF扭曲。FLIWBO将其构建离散化并与GP-UCB结合，以库大小和计算为代价，换取在自适应选择下的同步频率置信和有限时间累积遗憾控制。

## 3 FLIWBO方法与收敛性
我们考虑一个非空紧致搜索域 \(X \subseteq \mathcal{X} \triangleq [0,1]^D\) 和一个未知连续目标函数 \(f: X \to \mathbb{R}\)。在每轮 \(t\)，算法选择 \(x_t \in X\)，这是 \(\mathcal{D}_{t-1}\) 的函数，并观测到 \(y_t = f(x_t) + \epsilon_t\)，其中 \(\mathcal{D}_t \triangleq \{(x_s, y_s)\}_{s=1}^t\)，\(\mathcal{D}_0 \triangleq \emptyset\)。遵循Srinivas等人（2010）的假设，我们假设 \(\mathbb{E}[\epsilon_t \mid \mathcal{D}_{t-1}] = 0\) 且 \(\|\epsilon_t\| \leq \sigma\) 几乎必然。对于在 \(\mathcal{X}\) 上定义的基础核 \(k\)（后记为 \(k_0\)），我们假设 \(k(x,x) \leq 1\) 并记 \(K_{t-1} = [k(x_s, x_s')]_{s,s'}\) 为核矩阵。我们假设基础核是特征值快速衰减的Mercer核（例如，参数 \(\nu > D/2\) 的Matérn核）。

##### 主要定理（定理1，简化）。
设 \(\mathcal{W}\) 为 \(N_{\varepsilon}\) 个光滑输入扭曲的库。假设对于每个扭曲 \(w \in \mathcal{W}\)，拉回目标函数 \(f \circ w^{-1}\) 属于一个一致有界RKHS，其范数为 \(B_w \leq B\)，且扭曲的雅可比行列式满足 \(1/C \leq |\det \nabla w(x)| \leq C\)。设 \(\Gamma_T\) 为所有扭曲的最大累积信息增益。那么，对于任何 \(\delta > 0\)，存在常数 \(\beta_T\)（对数依赖于 \(\delta^{-1}\) 和 \(N_{\varepsilon}\)），使得任何从 \(\mathcal{W}\) 中选择扭曲序列 \(\{w_t\}\) 的FLIWBO-UCB算法，在概率至少为 \(1-\delta\) 时，满足累积简单遗憾 \(R_T = \sum_{t=1}^T \max_{x \in X} f(x) - f(x_t)\) 的边界：
\[ R_T = O\left(\sqrt{T \beta_T N_{\varepsilon} \Gamma_T}\right) \]
其中 \(\beta_T\) 通常为 \(O(\log(T N_{\varepsilon} / \delta))\) 量级。

##### 保证的代价。
库通过两种方式影响边界。通过联合界，它仅出现在 \(\beta_t\) 的 \(\log^3(t N_{\varepsilon} / \delta)\) 项中。通过分支方差累积，它在 \(N_{\varepsilon}\) 因子中显式贡献。还有计算代价：穷举选择对每个候选几何评估一个GP，但选择器可以延迟评估这些后验，因为每个分支都由共同历史定义。如果 \(\Theta_{\varepsilon}\) 是紧致 \(p\) 维参数集的 \(\varepsilon\)-网，则 \(N_{\varepsilon} \leq (C_{\Theta}/\varepsilon)^p\)，因此 \(\log N_{\varepsilon} = \mathcal{O}(p \log(1/\varepsilon))\)；这仅控制库大小，而非对离网或最佳连续扭曲的近似误差。FLIWBO将固定核GP-UCB扩展到一组有限的扭曲，并采用任何学习机制；它并不保证自适应总是有益的。

## 4 实验设计
我们使用三个证据层级：隔离扭曲机制的受控单次运行诊断；在更广泛任务上估计跨运行性能的重复比较；以及在动机应用中测试可行性的昂贵多智能体系统（MAS）案例研究。这些回答不同的问题，而非优化器优越性的可互换证据。所有FLIWBO实验从有限库中使用共享优化历史选择坐标级Beta-CDF扭曲；精确的构造、实现选择和配置在补充材料和代码中。

### 受控机制诊断
四个构造的问题隔离机制。P1测试分辨率向狭窄高值区域的重新分配（图1）；P2测试恢复预设的潜在几何（图2上排）；P3测试二维中的坐标特定扭曲学习（补充材料）；P4是固定核GP-UCB更优的平稳负对照（图2下排）。每对轨迹在固定核GP-UCB和FLIWBO-UCB之间共享初始化、噪声、核函数、采集规则和预算。P1、P2和P4使用5次初始加25次BO评估；P3使用5次加50次。补充材料给出了精确目标、设置和完整轨迹。

### 重复优化器比较
表1（见原文链接）给出了所有运行和评估次数。置信栅栏问题测试几何和采集是否共同逃离初始设计盲区；扭曲高斯混合和扭曲Hartmann6问题测试二维和六维中已知的潜在畸变；时尚MNIST超参数优化问题（Xiao等人, 2017）询问学习到的扭曲是否恢复通常由手动对数缩放提供的好处。已知函数比较包括固定GP-UCB、FLIWBO-UCB、连续扭曲GP-EI（Snoek等人, 2014），以及给定生成扭曲的预言机GP-UCB/EI；两个高维问题还包括FLIWBO-EI。超参数优化比较包括FLIWBO-UCB/EI、连续扭曲GP-EI，以及在线性和手动对数编码下的固定GP-UCB/EI。方法在每次运行内共享种子。我们报告平均最佳简单遗憾（simple regret）。