# Time-Varying Bayesian Optimization Without a Metronome

arXiv: https://arxiv.org/abs/2501.18963 · HTML: https://mlsanity.com/paper/2501.18963/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 26 references that are in the map.
- First posted on arXiv 31 Jan 2025.

## Builds on (most cited first, 10 of 10)

- [Multi-Objective Bayesian Optimization over High-Dimensional Search Spaces](https://mlsanity.com/paper/2109.10964/) (2021)
- [Time-Varying Gaussian Process Bandit Optimization](https://mlsanity.com/paper/1601.06650/) (2016)
- [Weighted Gaussian Process Bandits for Non-stationary Environments](https://mlsanity.com/paper/2107.02371/) (2021)
- [Bayesian Optimization for Synthetic Gene Design](https://mlsanity.com/paper/1505.01627/) (2015)
- [No-Regret Algorithms for Time-Varying Bayesian Optimization](https://mlsanity.com/paper/2102.06296/) (2021)
- [Bayesian Multi-Scale Optimistic Optimization](https://mlsanity.com/paper/1402.7005/) (2014)
- [Bayesian Optimization for Dynamic Problems](https://mlsanity.com/paper/1803.03432/) (2018)
- [Relaxing the Additivity Constraints in Decentralized No-Regret High-Dimensional Bayesian Optimization](https://mlsanity.com/paper/2305.19838/) (2023)
- [Event-Triggered Time-Varying Bayesian Optimization](https://mlsanity.com/paper/2208.10790/) (2022)
- [This Too Shall Pass: Removing Stale Observations in Dynamic Bayesian Optimization](https://mlsanity.com/paper/2405.14540/) (2024)

## Built on by (most cited first, 1 of 1)

- [Sharper Regret Bounds for Time-Varying Gaussian Process Bandits with Constant Exploration](https://mlsanity.com/paper/2608.18863/) (2026)

## Abstract (arXiv)

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.