Asymptotic Performance of Time-Varying Bayesian Optimization

Anthony Bardou, Patrick Thiran

Abstract

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. Is it possible for the instantaneous regret of a TVBO algorithm to vanish asymptotically, and if so, when? We answer this question of great theoretical importance by providing algorithm-independent lower regret bounds and upper regret bounds for TVBO algorithms, from which we derive sufficient conditions for a TVBO algorithm to have the no-regret property. Our analysis covers all major classes of stationary kernel functions.

Introduction

Bayesian Optimization (BO) has become a standard tool for optimizing expensive, noisy black-box functions. However, many real-world scenarios—ranging from drone swarm coordination to dynamic network parameter tuning—involve objective functions that evolve over time. While Time-Varying BO (TVBO) algorithms have seen empirical success, their theoretical limits remained largely unexplored. The central question is whether a TVBO algorithm can ever "catch up" to a moving target, achieving what is known as the "no-regret" property, where instantaneous regret vanishes as time approaches infinity.

Categorizing Temporal Dynamics

To analyze this problem, we categorize temporal kernels ($k_T$)—which describe how the objective function changes over time—into four classes based on their spectral density:

  1. Broadband: Kernels like RBF or Matérn that utilize the entire frequency domain.
  2. Band-Limited: Kernels such as the Sinc kernel that operate within a specific frequency range.
  3. Almost-Periodic: Kernels modeling functions that repeat over time.
  4. Low-Rank: Kernels represented as finite sums of trigonometric functions.

Methods: Spectral Analysis of Covariance Operators

Our approach utilizes the spectral analysis of covariance operators to quantify the information gain available to an algorithm over time. By examining the eigenvalues of the kernel matrices, we can determine the fundamental limits of prediction.

Spectral decomposition of kernel matrices $K_S/n$, $K_T$, and $K$, illustrating the eigenvalue distributions used to derive regret bounds.

We also introduced an "oracle" model—an idealized algorithm with full visibility of the noiseless function at each step—to establish absolute lower bounds on performance.

The Spectral Support Rule

The key theoretical finding is the Spectral Support Rule: the possibility of achieving no-regret depends entirely on the support of the temporal kernel's spectral density.

  • If the support is a continuous interval (Broadband or Band-Limited), the algorithm is inherently limited to linear regret.
  • If the support is discrete (Almost-Periodic or Low-Rank), no-regret performance is achievable.

Surprisingly, even the "oracle" model fails to achieve sublinear regret for Broadband kernels, indicating that the limitation is a property of the temporal model's inherent uncertainty rather than algorithmic deficiency.

Key Results and Empirical Validation

The following table summarizes the regret bounds for each kernel class:

Temporal Kernel Class Cumulative Regret ($R_n$) No-Regret Possible?
Broadband (RBF, Matérn) $\Theta(n)$ (Linear) No
Band-Limited (Sinc) $\Theta(n)$ (Linear) No
Almost-Periodic (Periodic) $o(n)$ (Sublinear) Yes
Low-Rank (Sum of Cosines) $o(n)$ (Sublinear) Yes

Numerical experiments validate these findings by tracking the scaled mutual information $I(f_n, y_n)/n$. For kernels with discrete spectral support, this value vanishes as $n$ increases, allowing for convergence. For broadband and band-limited kernels, it remains bounded away from zero, signifying persistent uncertainty.

Scaled mutual information $I(f_n, y_n)/n$ across different temporal kernel classes. Note the convergence for periodic and low-rank kernels compared to RBF and Sinc.

Conclusion and Future Work

This work proves that for the most common kernels used in practice (RBF, Matérn), achieving zero instantaneous regret is theoretically impossible. Practitioners must choose between the flexibility of broadband kernels and the asymptotic convergence of periodic or low-rank models. Future research will explore hybrid kernels, non-fixed sampling frequencies, and more complex spatio-temporal structures.

Summary updated

Abstract

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. Is it possible for the instantaneous regret of a TVBO algorithm to vanish asymptotically, and if so, when? We answer this question of great theoretical importance by providing algorithm-independent lower regret bounds and upper regret bounds for TVBO algorithms, from which we derive sufficient conditions for a TVBO algorithm to have the no-regret property. Our analysis covers all major classes of stationary kernel functions.
BibTeX
@misc{bardou2025asymptotic,
  author = {Anthony Bardou and Patrick Thiran},
  title = {{Asymptotic Performance of Time-Varying Bayesian Optimization}},
  year = {2025},
  eprint = {2505.13012},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2505.13012},
}
Figure