Bayesian Optimization With Censored Response Data
This addresses the problem of efficiently minimizing costly functions, such as algorithm runtimes, by adaptively censoring slow evaluations, which is incremental but impactful for domain-specific optimization tasks.
The paper tackles Bayesian optimization with partially right-censored response data, where some evaluations only provide lower bounds on function values, and demonstrates that this approach substantially improves state-of-the-art model-based algorithm configuration.
Bayesian optimization (BO) aims to minimize a given blackbox function using a model that is updated whenever new evidence about the function becomes available. Here, we address the problem of BO under partially right-censored response data, where in some evaluations we only obtain a lower bound on the function value. The ability to handle such response data allows us to adaptively censor costly function evaluations in minimization problems where the cost of a function evaluation corresponds to the function value. One important application giving rise to such censored data is the runtime-minimizing variant of the algorithm configuration problem: finding settings of a given parametric algorithm that minimize the runtime required for solving problem instances from a given distribution. We demonstrate that terminating slow algorithm runs prematurely and handling the resulting right-censored observations can substantially improve the state of the art in model-based algorithm configuration.