Bayesian Optimization under Stochastic Delayed Feedback
Bayesian optimization (BO) is a widely-used sequential method for
zeroth-order optimization of complex and expensive-to-compute black-box
functions. The existing BO methods assume that the function evaluation
(feedback) is available to the learner immediately or after a fixed delay. Such
assumptions may not be practical in many real-life problems like online
recommendations, clinical trials, and hyperparameter tuning where feedback is
available after a random delay. To benefit from the experimental
parallelization in these problems, the learner needs to start new function
evaluations without waiting for delayed feedback. In this paper, we consider
the BO under stochastic delayed feedback problem. We propose algorithms with
sub-linear regret guarantees that efficiently address the dilemma of selecting
new function queries while waiting for randomly delayed feedback. Building on
our results, we also make novel contributions to batch BO and contextual
Gaussian process bandits. Experiments on synthetic and real-life datasets
verify the performance of our algorithms.