  Bayesian Optimization (BO) is a successful methodology to tune the
hyperparameters of machine learning algorithms. The user defines a metric of
interest, such as the validation error, and BO finds the optimal
hyperparameters that minimize it. However, the metric improvements on the
validation set may not translate to the test set, especially on small datasets.
In other words, BO can overfit. While cross-validation mitigates this, it comes
with high computational cost. In this paper, we carry out the first systematic
investigation of overfitting in BO and demonstrate that this is a serious yet
often overlooked concern in practice. We propose the first problem-adaptive and
interpretable criterion to early stop BO, reducing overfitting while mitigating
the cost of cross-validation. Experimental results on real-world hyperparameter
optimization tasks show that our approach can substantially reduce compute time
with little to no loss of test accuracy,demonstrating a clear practical
advantage over existing techniques.
