Asymptotic Performance of Time-Varying Bayesian Optimization
This framework optimizes expensive, noisy functions that change over time using Time-Varying Bayesian Optimization (TVBO). The study analyzes how the performance, measured by cumulative regret, depends entirely on the temporal kernel's spectral density. It finds that for broadband or band-limited kernels, sublinear regret is impossible (regret scales linearly with iterations), while for almost-periodic or low-rank kernels, algorithms can achieve asymptotic no-regret behavior.