Bayesian Optimization is critically vulnerable to extreme outliers. Existing provably robust methods typically assume a bounded cumulative corruption budget, which makes them defenseless against even a single corruption of sufficient magnitude. To address this, we introduce a new adversary whose budget is only bounded in the frequency of corruptions, not in their magnitude. We then derive RCGP-UCB, an algorithm coupling the famous upper confidence bound (UCB) approach with a Robust Conjugate Gaussian Process (RCGP). We present stable and adaptive versions of RCGP-UCB, and prove that they achieve sublinear regret in the presence of up to $O(T^{1/2})$ and $O(T^{1/3})$ corruptions with possibly infinite magnitude. This robustness comes at near zero cost: without outliers, RCGP-UCB's regret bounds match those of the standard GP-UCB algorithm.

翻译：贝叶斯优化对极端异常值极为敏感。现有的可证明鲁棒的方法通常假设累积扰动预算有界，这使得它们即使面对单个足够大幅度的扰动也缺乏防御能力。为解决这一问题，我们引入了一种新的对抗模型，其预算仅在扰动频率上有界，而在幅度上无界。随后，我们推导出RCGP-UCB算法，该算法将著名的上置信界（UCB）方法与鲁棒共轭高斯过程（RCGP）相结合。我们提出了RCGP-UCB的稳定版本和自适应版本，并证明在存在多达$O(T^{1/2})$和$O(T^{1/3})$个可能无限幅度的扰动时，它们能够实现次线性遗憾。这种鲁棒性几乎不带来额外成本：在没有异常值的情况下，RCGP-UCB的遗憾界与标准GP-UCB算法保持一致。