Time-Varying Bayesian Optimization Without a Metronome
This work addresses a key limitation in TVBO for optimizing time-varying functions, offering incremental improvements in algorithm design and performance.
The paper tackles the unrealistic assumption of constant observation frequency in Time-Varying Bayesian Optimization (TVBO) by deriving the first upper regret bound that accounts for changes in sampling frequency, leading to practical recommendations and showing that an algorithm (BOLT) outperforms state-of-the-art TVBO on synthetic and real-world problems.
Time-Varying Bayesian Optimization (TVBO) is the go-to framework for optimizing a time-varying, expensive, noisy black-box function $f$. However, most of the asymptotic guarantees offered by TVBO algorithms rely on the assumption that observations are acquired at a constant frequency. As the GP inference complexity scales with the cube of its dataset size, this assumption is unrealistic in the long run. In this paper, we relax this assumption and derive the first upper regret bound that explicitly accounts for changes in the observations sampling frequency. Based on this analysis, we formulate practical recommendations about dataset sizes and stale data policies of TVBO algorithms. We illustrate how an algorithm (BOLT) that follows these recommendations performs better than the state-of-the-art of TVBO through experiments on synthetic and real-world problems.