  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.
