Multi-Step Budgeted Bayesian Optimization with Unknown Evaluation Costs

Bayesian optimization (BO) is a sample-efficient approach to optimizing costly-toevaluate black-box functions. Most BO methods ignore how evaluation costs may vary over the optimization domain. However, these costs can be highly heterogeneous and are often unknown in advance. This occurs in many practical settings, such as hyperparameter tuning of machine learning algorithms or physics-based simulation optimization. Moreover, those few existing methods that acknowledge cost heterogeneity do not naturally accommodate a budget constraint on the total evaluation cost.