2025-11-15T00:58:11.500809

Regret Analysis for Randomized Gaussian Process Upper Confidence Bound

Takeno, Inatsu, Karasuyama

Gaussian process upper confidence bound (GP-UCB) is a theoretically established algorithm for Bayesian optimization (BO), where we assume the objective function $f$ follows a GP. One notable drawback of GP-UCB is that the theoretical confidence parameter $Î²$ increases along with the iterations and is too large. To alleviate this drawback, this paper analyzes the randomized variant of GP-UCB called improved randomized GP-UCB (IRGP-UCB), which uses the confidence parameter generated from the shifted exponential distribution. We analyze the expected regret and conditional expected regret, where the expectation and the probability are taken respectively with $f$ and noise and with the randomness of the BO algorithm. In both regret analyses, IRGP-UCB achieves a sub-linear regret upper bound without increasing the confidence parameter if the input domain is finite. Furthermore, we show that randomization plays a key role in avoiding an increase in confidence parameter by showing that GP-UCB using a constant confidence parameter can incur linearly growing expected cumulative regret. Finally, we show numerical experiments using synthetic and benchmark functions and real-world emulators.

academic

Regret Analysis for Randomized Gaussian Process Upper Confidence Bound

基本信息

论文ID: 2409.00979
标题: Regret Analysis for Randomized Gaussian Process Upper Confidence Bound
作者: Shion Takeno (Nagoya University, RIKEN AIP), Yu Inatsu (Nagoya Institute of Technology), Masayuki Karasuyama (Nagoya Institute of Technology)
分类: cs.LG, stat.ML
发表时间: 2024年9月 (arXiv v3: 2025年7月16日)
论文链接: https://arxiv.org/abs/2409.00979v3

摘要

本文研究贝叶斯优化中GP-UCB算法的理论改进。经典GP-UCB的主要缺陷是理论置信参数β随迭代次数增长（βt ∝ log t），导致实际应用中过度探索。作者提出改进的随机化GP-UCB (IRGP-UCB)，使用移位指数分布生成置信参数。在有限输入域情况下，IRGP-UCB实现了亚线性遗憾上界且无需增加置信参数。通过证明使用常数置信参数的GP-UCB会产生线性遗憾，作者论证了随机化的必要性。实验验证了方法的实用有效性。

研究背景与动机

核心问题

贝叶斯优化(BO)旨在用尽可能少的函数评估次数优化昂贵的黑箱函数。GP-UCB是理论保证最强的BO算法之一，但存在严重的理论-实践鸿沟：

置信参数过大问题：理论分析要求βt = Θ(log t)，在实际应用中导致：
- 置信区间过宽
- 算法过度探索
- 收敛速度慢
现有方法的局限：
- Berk et al. (2020)提出的RGP-UCB使用Gamma分布随机化，但其分析存在技术问题
- 即使修正后，仍需βt随时间增长
- 频率学派方法(如Chowdhury & Gopalan 2017)与贝叶斯设定的假设不同

研究重要性

理论意义：填补贝叶斯设定下无需增长置信参数的理论空白
实践价值：解决GP-UCB在材料科学、自动机器学习、药物设计等领域应用中的过度探索问题
方法论贡献：证明随机化在避免置信参数增长中的关键作用

核心贡献

期望遗憾界（定理4.1-4.2）：
- 有限域：BCRT ≤ √(C₁C₂TγT)，其中C₂ = 2 + 2log(|X|/2)为常数
- 连续域：BCRT ≤ π²/6 + √(C₁TγT(2 + sT))，sT = O(d log T)
条件期望遗憾界（定理4.3-4.4）：
- 对算法随机性条件化，对问题随机性取期望
- 以高概率1-δ保持相同收敛速率
- 更公平地与确定性算法比较
高概率遗憾界（定理4.5，推论4.1）：
- 证明随机化不损害高概率保证
- 虽然Eζt需增长，但仍可获得O(√(TγT log(T|X|/δ)))界
常数置信参数的下界（定理4.6）：
- 构造反例：在简单的两点域上，使用常数β的GP-UCB产生Ω(T)线性遗憾
- 证明随机化对避免参数增长的必要性
实验验证：
- 合成函数、基准函数和真实材料数据集
- IRGP-UCB性能优于GP-UCB、RGP-UCB和其他主流方法

方法详解

任务定义

标准贝叶斯优化设定：

输入：域X ⊂ ℝᵈ，黑箱函数f: X → ℝ
观测模型：yt = f(xt) + εt，εt ~ N(0, σ²)
假设：f ~ GP(0, k)，k为已知核函数
目标：最小化累积遗憾RT = ∑ᵗ₌₁ᵀf(x*) - f(xt)

IRGP-UCB算法架构

算法1：IRGP-UCB

输入：域X，参数{st}t≥1和λ，GP先验μ=0和k
初始化：D₀ = ∅
对于 t = 1, 2, ...:
    1. 拟合GP到Dt-1
    2. 生成随机置信参数：ζt ← st + Zt，其中Zt ~ Exp(λ)
    3. 选择输入：xt ← argmax[μt-1(x) + ζt^(1/2)σt-1(x)]
    4. 观测：yt = f(xt) + εt
    5. 更新数据集：Dt ← Dt-1 ∪ (xt, yt)

关键设计：

移位指数分布：ζt ~ ShiftedExp(st, λ)，PDF为p(ζ) = λexp(-λ(ζ-st))，ζ ≥ st
有限域参数：st = 2log(|X|/2)，λ = 1/2
连续域参数：st = 2d log(bdrt²(√log(ad) + √(π/2))) - 2log 2

技术创新点

1. 核心引理（引理4.2）

关键不等式：对任意给定Dt-1， $E_t[f(x^*)] \leq E_t\left[\max_{x \in X} \mu_{t-1}(x) + \zeta_t^{1/2}\sigma_{t-1}(x)\right]$

证明思路（创新性技术）：

从引理4.1（有限域高概率界）出发： $P_t(f(x) \leq \mu_{t-1}(x) + \beta_\delta^{1/2}\sigma_{t-1}(x), \forall x) \geq 1-\delta$ 其中βδ = 2log(|X|/(2δ))
使用CDF的逆函数： $F_t^{-1}(1-\delta) \leq \max_x \mu_{t-1}(x) + \beta_\delta^{1/2}\sigma_{t-1}(x)$
关键步骤：代入U ~ Uni(0,1)到δ，取期望： $E_U[F_t^{-1}(1-U)] \leq E_U\left[\max_x \mu_{t-1}(x) + \beta_U^{1/2}\sigma_{t-1}(x)\right]$
逆变换采样技巧：F_t^{-1}(U)与f(x*)同分布，而： $\beta_U = 2\log(|X|/2) - 2\log(U)$ 恰好服从移位指数分布（因为-2log(U) ~ Exp(1/2)）

创新意义：

直接界定Ef(x*)，避免传统方法的联合界
自然导出移位指数分布
无需t依赖的参数增长

2. 期望遗憾分析技术

分解策略： $\text{BCR}_T = \sum_{t=1}^T E[f(x^*) - f(x_t)]$ $= \sum_{t=1}^T E[f(x^*) - v_t(x_t)] + E[v_t(x_t) - f(x_t)]$

其中vt(x) = μt-1(x) + ζt^(1/2)σt-1(x)。

关键观察：

第一项≤0（由引理4.2和算法选择规则）
第二项使用Cauchy-Schwarz和MIG界定： $\sum_{t=1}^T E[\zeta_t^{1/2}\sigma_{t-1}(x_t)] \leq \sqrt{\sum E[\zeta_t]} \cdot \sqrt{C_1\gamma_T}$

有限域优势：Eζt = 2 + st为常数！

3. 条件期望遗憾分析（新贡献）

动机：期望遗憾对算法随机性平均，可能掩盖变异性。

技术挑战：需对{ζt}t≥1条件化，分析： $E_{f,\{\epsilon_t\}}[R_T | \{\zeta_t\}_{t\geq1}]$

创新技术：

鞅差分序列构造： $A_1 = \sum_{t=1}^T \{E_{D_{t-1},\zeta_t}[v_t(x_t)|\{\zeta_i\}_{i<t}] - E_{D_{t-1}}[v_t(x_t)|\{\zeta_i\}_{i\leq t}]\}$
条件次高斯性证明（命题B.3）：
- 定义h(a) = Emax_x{μ + √(s + ||a||²₂)σ}
- 证明h是1-Lipschitz函数
- 应用高斯集中不等式
Azuma不等式应用（引理B.1）：
- 验证鞅差分性质
- 验证条件次高斯性
- 得到A1的18T-次高斯界
卡方分布尾界（引理E.4）：
- 对A2 = ∑ζt^(1/2)σt-1(xt)应用
- 因为∑(ζt - st) ~ χ²(T)

结果（定理4.3）：以概率≥1-δ， $E_{f,\epsilon}[R_T|\{\zeta_t\}] \leq 6\sqrt{T\log(\pi²T²/3\delta)} + \sqrt{C_1\gamma_T(\cdots)}$

保持O(√(TγT log|X|))速率。

4. 常数参数下界构造

反例设计（定理4.6）：

域：X = {x⁽¹⁾, x⁽²⁾}
先验：f ~ N(0, Σ)，Σ = 1, ρ; ρ, 0.99
噪声：εt ~ N(0,1)

关键事件： $E_T = \{f(x^{(1)}) \geq \frac{2\max\{1,c\}}{1-\rho}+1, f(x^{(2)}) > f(x^{(1)})+1, \sum_{i=1}^t\epsilon_i/t \geq -1\}$

证明策略：

证明Pr(ET) > 0（引理D.1：几何级数求和）
在ET下，归纳证明xt = x⁽¹⁾对所有t成立：
- 后验均值差：μt(x⁽¹⁾) - μt(x⁽²⁾) ≥ (1-ρ)/2 · t·f(x⁽¹⁾) + ∑εi/t
- 利用ET条件得差值≥c = β^(1/2)
但x* = x⁽²⁾，故每步遗憾≥1

结论：BCRT = Ω(T)，证明常数参数不足。

实验设置

数据集

1. 合成函数

生成：f ~ GP(0, k)，k为RBF核，ℓ=0.1
维度：d=3
域：X = {0, 0.1, ..., 0.9}³，|X|=1000
噪声：σ²=10⁻⁴
试验：10个函数 × 10个初始数据集 = 100次

2. 基准函数

Holder table (d=2)
Cross in tray (d=2)
Ackley (d=4)
来源：https://www.sfu.ca/~ssurjano/optimization.html
初始数据：|D₀|=2d
试验：10次随机初始化

3. 真实材料数据（Liang et al. 2021）

Perovskite：卤化物钙钛矿环境稳定性，d=3，|X|=94
P3HT/CNT：碳纳米管聚合物导电性，d=5，|X|=178
AgNP：银纳米颗粒吸收光谱，d=5，|X|=164
初始数据：|D₀|=2

评价指标

简单遗憾（Simple Regret）： $r_{\text{simple}} = f(x^*) - \max_{t \leq T} f(x_t)$

衡量找到的最佳点与真实最优点的差距。

对比方法

GP-UCB Srinivas et al. 2010：βt = 0.2d log(2t)（启发式）
RGP-UCB Berk et al. 2020：ζt ~ Gamma(κt, θ=1)，κt = 0.2d log(2t)
Thompson Sampling (TS) Russo & Van Roy 2014
PIMS Takeno et al. 2024：基于样本路径最大值的概率改进
Expected Improvement (EI) Mockus et al. 1978
Max-value Entropy Search (MES) Wang & Jegelka 2017
Joint Entropy Search (JES) Hvarfner et al. 2022

实现细节

后验采样：TS、PIMS、MES、JES使用随机傅里叶特征
蒙特卡洛：MES和JES使用10个样本
超参数优化：
- 合成函数：固定为真实参数
- 基准函数：每5次迭代最大化边际似然
- 真实数据：每次迭代优化（避免不稳定）
IRGP-UCB参数：
- 合成函数：st = 2log(|X|/2)，λ=1/2（理论值）
- 连续域：s = d/2，λ=1/2（启发式）

实验结果

主要结果

1. 置信参数比较（图1）

观察（|X|=1000，T=150）：

GP-UCB：βt从~~10增长到~~60（对数增长）
RGP-UCB：Eζt同样从~~10增长到~~60，95%置信区间宽
IRGP-UCB：Eζt≈4恒定，95%置信区间2,8

结论：IRGP-UCB显著减少过度探索。

2. 合成函数（图2，d=3）

性能排序（T=200时）：

IRGP-UCB：遗憾~10⁻⁴（最佳）
EI、MES：~10⁻³
PIMS：~5×10⁻³
GP-UCB、RGP-UCB、TS、JES：~10⁻²（收敛慢）

统计显著性：IRGP-UCB在大部分迭代中误差棒不重叠。

3. 基准函数（图3）

Holder table (d=2)：

JES前40次最快，但停滞在10⁻¹
IRGP-UCB在60次时达到10⁻³，最终最佳

Cross in tray (d=2)：

IRGP-UCB在50次时快速收敛到10⁻⁴
其他方法需>80次

Ackley (d=4)：

IRGP-UCB持续领先，125次后最小
TS和JES因维度诅咒表现差

4. 真实材料数据（图4）

Perovskite (d=3)：

IRGP-UCB 20次后最佳（遗憾~2×10⁴）
优于GP-UCB、TS约2倍

P3HT/CNT (d=5)：

EI 60次后最佳
但IRGP-UCB前20次收敛最快

AgNP (d=5)：

关键发现：IRGP-UCB在42次所有试验中找到最优点
启发式方法(EI/MES/JES)需≥60次

消融实验

隐式消融（通过对比）：

随机化必要性：GP-UCB vs IRGP-UCB
- 相同UCB框架，仅置信参数不同
- IRGP-UCB持续优于GP-UCB
分布选择：RGP-UCB (Gamma) vs IRGP-UCB (Shifted Exp)
- 两者都随机化，但IRGP-UCB更优
- 验证移位指数分布的优越性
理论vs启发式：
- 合成函数（理论参数）：IRGP-UCB表现最佳
- 连续域（启发式s=d/2）：仍然有效
- 表明理论指导的实用价值

案例分析

材料发现加速（AgNP数据集）：

传统方法(EI)：需60次实验找到最优纳米颗粒合成参数
IRGP-UCB：仅需42次，节省30%实验成本
在实验成本高昂的材料科学中具有重要价值

实验发现

过度探索的代价：GP-UCB、RGP-UCB、TS在后期表现差，证实βt过大的负面影响
维度敏感性：高维(d=4,5)时，基于样本路径最大值的方法(TS/JES)性能下降
理论-实践一致性：理论最优的IRGP-UCB在实践中也最优，罕见的理论-实践统一
鲁棒性：IRGP-UCB在不同类型函数（光滑合成、多峰基准、噪声真实数据）上均表现良好

结论与讨论

主要结论

理论突破：
- 有限域：首次实现无需增长置信参数的亚线性遗憾界
- 条件期望遗憾：高概率保持相同速率
- 下界：证明常数参数不足，随机化必要
方法贡献：
- 移位指数分布的自然导出（引理4.2）
- 鞅差分序列技术（条件期望分析）
- 反例构造（定理4.6）
实践验证：
- 合成、基准、真实数据上均优于基线
- 桥接理论-实践鸿沟

局限性

1. 连续域限制

定理4.2/4.4：sT = O(d log T)，仍需增长
原因：离散化|Xt| = O(t^(2d))，log|Xt|依赖t
开放问题：能否避免？

2. 高概率界的参数增长

定理4.5/推论4.1：Eζt = O(log(t|X|/δ))
虽然保持与GP-UCB相同速率，但未实现常数参数
未来方向：高概率+常数参数

3. log|X|依赖

定理4.1：O(√(TγT log|X|))
虽比O(√(TγT log(T|X|)))略好，但差异仅常数
在T < |X|的典型BO场景中改进有限

4. 实验启发式

连续域实验：s = d/2（非理论值）
虽然有效，但理论-实践仍有小差距

5. 假设限制

假设2.1：四次可微核（RBF、Matérn-ν）
正确模型假设（f确实来自GP）
已知核函数和噪声方差

未来方向

1. 理论扩展

连续域的常数参数界
高概率+常数参数的统一
放松正确模型假设

2. 算法扩展（第6节提及）

多目标BO (Paria et al. 2020)
多保真度BO (Kandasamy et al. 2016, Takeno et al. 2020)
并行BO (Contal et al. 2013)
高维BO (Kandasamy et al. 2015)
鲁棒BO (Bogunovic et al. 2018)
级联BO (Kusakawa et al. 2022)

3. 其他获取函数

随机化EI/MES/JES
类似LSE的成功（Inatsu et al. 2024b）

4. 实践改进

自适应参数选择
超参数不确定性处理
批量评估策略

深度评价

优点

1. 理论创新性（★★★★★）

引理4.2的优雅性：通过逆变换采样自然导出移位指数分布，避免传统方法的复杂联合界
多层次分析：期望遗憾→条件期望遗憾→高概率界，全面覆盖
下界证明：定理4.6填补必要性证明空白，逻辑完整

2. 技术深度（★★★★★）

鞅理论应用：条件期望分析使用Azuma不等式，技术难度高
Lipschitz函数集中：命题B.3证明条件次高斯性，细节严谨
反例构造：定理4.6的两点域设计简洁有力

3. 实验充分性（★★★★☆）

覆盖合成、基准、真实数据三类
对比7种主流方法
统计显著性报告（误差棒）
不足：缺少大规模高维实验（d>5）

4. 写作清晰度（★★★★★）

结构清晰：背景→方法→理论→实验
动机明确：每个定理前说明目的
证明可读：主定理正文给出思路，细节放附录
符号一致：Dt-1, μt-1等统一

5. 可复现性（★★★★☆）

算法伪代码完整（算法1）
参数设置明确
数据集公开（Liang et al. 2021）
不足：未提供代码链接

不足

1. 理论局限

连续域遗憾：定理4.2的O(√(TγT log T))仍有增长
高概率界：推论4.1的Eζt增长，未完全解决问题
log|X|项：改进仅常数级，实际影响小

2. 实验设计

维度限制：最高d=5，未测试高维性能
噪声水平：仅σ²=10⁻⁴，未探索高噪声鲁棒性
计算成本：未报告运行时间
消融不足：未单独测试λ和st的影响

3. 假设限制

模型正确性：假设f确实来自GP（实践中可能不满足）
已知超参数：假设k和σ²已知（实践中需估计）
有限域假设：主要结果（定理4.1/4.3）仅适用有限域

4. 与相关工作比较

未与TRUVAR对比：同样是UCB变体
未讨论计算复杂度：与TS/EI的计算成本比较
RGP-UCB对比不足：仅实验对比，未理论对比

5. 实践指导

参数选择：连续域的s=d/2缺乏理论支持
超参数优化：每次迭代优化成本高，未讨论替代方案
收敛诊断：未提供停止准则

影响力

1. 学术贡献（预期高）

理论意义：填补贝叶斯BO理论空白
方法论：引理4.2的逆变换技术可能启发其他工作
完整性：期望+条件期望+高概率+下界，分析全面

2. 实用价值（中等）

材料科学：AgNP实验节省30%成本
自动ML：减少超参数调优次数
限制：高维、高噪声场景需进一步验证

3. 后续工作（已有）

Inatsu et al. 2024b：随机化LSE
可能影响多目标、多保真度BO

4. 社区接受度（预期）

优势：顶级会议（ICML 2023会议版）
挑战：需代码开源提高采用率

适用场景

理想场景：

有限离散域：组合优化、材料组分设计
昂贵评估：物理实验、大规模仿真
低维问题：d ≤ 10
低噪声：σ²较小
GP适用：目标函数光滑

不适用场景：

高维连续域：d > 20（理论保证弱）
高噪声：σ²很大（置信区间宽）
非光滑函数：不满足假设2.1
大规模域：|X| > 10⁶（log|X|项影响）
实时应用：GP推理O(t³)成本

竞争方法选择：

简单问题：EI（无超参数）
高维：基于梯度的方法
大规模并行：批量BO
模型不确定性：集成方法

参考文献（关键文献）

Srinivas et al. (2010): "Gaussian process optimization in the bandit setting: No regret and experimental design" - GP-UCB原始论文
Russo & Van Roy (2014): "Learning to optimize via posterior sampling" - TS的贝叶斯分析
Berk et al. (2020): "Randomised Gaussian process upper confidence bound for Bayesian optimisation" - RGP-UCB
Kandasamy et al. (2018): "Parallelised Bayesian optimisation via Thompson sampling" - TS的MIG界
Takeno et al. (2023): 本文的会议版本（ICML 2023）
Liang et al. (2021): "Benchmarking the performance of Bayesian optimization across multiple experimental materials science domains" - 材料数据集

总结

本文在贝叶斯优化理论中取得重要突破，通过巧妙的逆变换采样技术（引理4.2）自然导出移位指数分布，在有限域实现了首个无需增长置信参数的亚线性遗憾界。多层次理论分析（期望、条件期望、高概率）和必要性证明（定理4.6）构成完整的理论体系。实验验证了理论-实践一致性，特别是在材料科学应用中展示了实用价值。

主要限制在于连续域仍需参数增长，高概率界未完全解决问题，以及实验维度较低。尽管如此，本文为GP-UCB研究开辟了新方向，其技术（逆变换采样、鞅分析）具有方法论价值，预期将影响BO及相关领域（如LSE）的后续研究。对于有限域、低维、昂贵评估的实际应用，IRGP-UCB是理论保证最强的选择之一。