Time-Varying Bayesian Optimization Without a Metronome

Time-Varying Bayesian Optimization (TVBO) is the go-to framework for optimizing time-varying, expensive, noisy black-box functions. However, most asymptotic guarantees for TVBO algorithms assume observations are acquired at a constant frequency. Since streaming GP inference scales quadratically with dataset size, this assumption is unrealistic in the long run. We relax it and derive the first upper regret bound that explicitly accounts for changes in observation sampling frequency. This analysis yields practical recommendations for dataset sizes and stale-data policies. Experiments on synthetic and real-world problems show that an algorithm (BOLT) following these recommendations outperforms state-of-the-art TVBO methods.