Robust Bayesian Optimisation with Unbounded Corruptions
This addresses a critical robustness issue in Bayesian Optimization for applications where outliers can be arbitrarily large, offering a provable solution with minimal performance loss.
The paper tackles the vulnerability of Bayesian Optimization to extreme outliers by introducing a new adversary with unbounded corruption magnitude, and presents RCGP-UCB algorithms that achieve sublinear regret with up to O(T^{1/2}) and O(T^{1/3}) corruptions while matching standard GP-UCB regret bounds without outliers.
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.