Abstract
We propose practical extensions to Bayesian optimization for solving dynamic problems. We model dynamic objective functions using spatiotemporal Gaussian process priors which capture all the instances of the functions over time. Our extensions to Bayesian optimization use the information learnt from this model to guide the tracking of a temporally evolving minimum. By exploiting temporal correlations, the proposed method also determines when to make evaluations, how fast to make those evaluations, and it induces an appropriate budget of steps based on the available information. Lastly, we evaluate our technique on synthetic and real-world problems.
Introduction: The Challenge of Dynamic Landscapes
Standard Bayesian Optimization (BO) is a powerful framework for finding the global minimum of expensive, black-box functions. However, traditional BO typically assumes a static objective function. In many real-world scenarios—such as tracking environmental pollutants, optimizing financial portfolios, or monitoring sensor networks—the underlying function changes over time. These are known as Dynamic Optimization Problems (DOPs).
Applying static BO to DOPs presents a dilemma: one can either treat time as a fixed variable, leading to outdated solutions, or restart the optimization process periodically, which discards valuable historical data and is computationally inefficient. The challenge is to create a "memory" of the function's past behavior to predict its future state, allowing the optimizer to track the moving minimum efficiently without wasting expensive evaluations.
Methodology: Adaptive Bayesian Optimization (ABO)
The authors propose Adaptive Bayesian Optimization (ABO), which handles the time dimension through two primary innovations:
1. Spatiotemporal Gaussian Processes
Instead of a standard spatial GP, ABO uses a spatiotemporal prior $f(x, t) \sim \mathcal{N}(y | \mu, K)$. The kernel $K$ is typically separable, combining a spatial kernel with a temporal kernel. This allows the model to learn the "rhythm" of the environment through the learned temporal length-scale ($l_t$). If $l_t$ is large, the function is stable; if small, it is volatile.
2. Temporal Search Constraints and Timing
Unlike static BO, ABO restricts its search for the next sample point to a specific time window in the near future. The algorithm operates in two primary modes:
- ABO-f (Fixed): Evaluates the function at regular time intervals.
- ABO-t (Timed): Treats the next evaluation time as a variable to be optimized. It uses $l_t$ to decide the optimal moment to sample, effectively deciding how fast to make evaluations based on the environment's rate of change.
Experimental Evaluation
The researchers evaluated ABO against several baselines (including standard BO, Particle Swarm Optimization, and Time-Varying Bandits) using:
- Modified Standard Benchmarks: Classic functions like the 6-hump Camelback and Branin, modified so that one dimension evolves over time.
- Moving Peaks Benchmark (MPB): A standard for dynamic optimization where multiple peaks change height, width, and location abruptly.
- Intel Berkeley Temperature Dataset: A real-world dataset of temperature readings from 54 sensors. The goal was to track the location of the maximum temperature over time.
Key Results and Insights
- Superior Efficiency: ABO-t was particularly impressive, often achieving better tracking performance while using 16% to 76% fewer iterations than fixed-interval methods on several benchmarks.
- The Horizon of Predictability: ABO uses the insight that a GP can only reliably extrapolate about one length-scale into the future to set an upper bound on its search, preventing overconfident guesses about the distant future.
- Robustness to Abrupt Change: Even on the Moving Peaks Benchmark, ABO was able to capture dynamics and track optima more effectively than standard BO or bandit-based methods.
- Real-World Success: In the Intel temperature sensor task, ABO-f achieved the best mean offline performance, proving its utility for actual sensor network applications.
Limitations and Future Work
The authors note a "Nyquist-like" constraint: if the objective function changes faster than the time it takes to evaluate it, the algorithm will fail to learn the pattern. Additionally, training a GP at every step introduces computational overhead, making ABO most suitable for "expensive" objective functions. Future work may explore non-stationary kernels to handle environments where the rate of change itself fluctuates over time.
Reference: Nyikosa, F. M., Osborne, M. A., & Roberts, S. J. (2018). Bayesian Optimization for Dynamic Problems. arXiv:1803.03432v1 [stat.ML].
Summary updated