Bayes Optimal Early Stopping Policies for Black-Box Optimization
  We derive an optimal policy for adaptively restarting a randomized algorithm,
based on observed features of the run-so-far, so as to minimize the expected
time required for the algorithm to successfully terminate. Given a suitable
Bayesian prior, this result can be used to select the optimal black-box
optimization algorithm from among a large family of algorithms that includes
random search, Successive Halving, and Hyperband. On CIFAR-10 and ImageNet
hyperparameter tuning problems, the proposed policies offer up to a factor of
13 improvement over random search in terms of expected time to reach a given
target accuracy, and up to a factor of 3 improvement over a baseline adaptive
policy that terminates a run whenever its accuracy is below-median.
