mlsanityData to 14 Oct 2026

Asymptotic Performance of Time-Varying Bayesian Optimization

arXiv 2505.13012 ↗First posted 19 May 2025stat.ML cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

Time-Varying Bayesian Optimization (TVBO) is the go-to framework for optimizing a time-varying black-box objective function that may be noisy and expensive to evaluate, but its excellent empirical performance remains to be understood theoretically. Is it possible for the instantaneous regret of a TVBO algorithm to vanish asymptotically, and if so, when? We answer this question of great importance by providing upper bounds and algorithm-independent lower bounds for the cumulative regret of TVBO algorithms. In doing so, we provide important insights about the TVBO framework and derive sufficient conditions for a TVBO algorithm to have the no-regret property. To the best of our knowledge, our analysis is the first to cover all major classes of stationary kernel functions used in practice.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 15 of its 44 references that are in the map. First posted on arXiv 19 May 2025.

Builds on

15 of 44 references.

References · 15

  1. 2013Finite-Time Analysis of Kernelised Contextual Banditscited by 177
  2. 2013Non-stationary Stochastic Optimizationcited by 175
  3. 2020On Information Gain and Regret Bounds in Gaussian Process Banditscited by 158
  4. 2017Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimizationcited by 78
  5. 2016Time-Varying Gaussian Process Bandit Optimizationcited by 50
  6. 2021Weighted Gaussian Process Bandits for Non-stationary Environmentscited by 30
  7. 2023On the Sublinear Regret of GP-UCBcited by 26
  8. 2021No-Regret Algorithms for Time-Varying Bayesian Optimizationcited by 19
  9. 2022An Optimization-based Algorithm for Non-stationary Kernel Bandits without Prior Knowledgecited by 17
  10. 2018Bayesian Optimization for Dynamic Problemscited by 10
  11. 2023Relaxing the Additivity Constraints in Decentralized No-Regret High-Dimensional Bayesian Optimizationcited by 9
  12. 2019Band-Limited Gaussian Processes: The Sinc Kernelcited by 8
3 more
  1. 2024Near-Optimal Algorithm for Non-Stationary Kernelized Banditscited by 8
  2. 2022Event-Triggered Time-Varying Bayesian Optimizationcited by 7
  3. 2024This Too Shall Pass: Removing Stale Observations in Dynamic Bayesian Optimizationcited by 6

Built on by

Not cited yet.