Optimistic Bayesian Optimization with Unknown Constraints

Though some research efforts have been dedicated to constrained Bayesian optimization (BO), there remains a notable absence of a principled approach with a theoretical performance guarantee in the decoupled setting. Such a setting involves independent evaluations of the objective function and constraints at different inputs, and is hence a relaxation of the commonly-studied coupled setting where functions must be evaluated together. As a result, the decoupled setting requires an adaptive selection between evaluating either the objective function or a constraint, in addition to selecting an input (in the coupled setting). This paper presents a novel constrained BO algorithm with a provable performance guarantee that can address the above relaxed setting. Specifically, it considers the fundamental trade-off between exploration and exploitation in constrained BO, and, interestingly, affords a noteworthy connection to active learning. The performance of our proposed algorithms is also empirically evaluated using several synthetic and real-world optimization problems. Beyond the black-box objective function, recent advancements in BO have focused on addressing the prevalent presence of black-box constraints. For example, there often exist prediction time constraints and class-wise performance constraints when tuning machine learning models (Hernández-Lobato et al., 2016; Takeno et al., 2022) . They are just as costly to evaluate as the objective function. Constrained BO has led to many BO extensions such as EIC (an EI-based method) (Gardner et al., 2014) , a knowledge gradient-based method (Chen et al., 2021), CMES-IBO (an MES-based method) (Takeno et al., 2022) , augmented Lagrangian approaches (Gramacy et al., 2016; Picheny et al., 2016) , and upper trust bound (UTB) (a GP-UCB-based method) (Priem et al., 2020) .