In diverse fields of science and engineering, one frequently faces the need to know the optimum of a black-box function that is expensive to evaluate. In materials science, in order to determine an optimal composition of alloys one has to repeat manual experiments that cost time and money. In machine learning model building, one has to tune a number of hyperparameters of a model but testing the performance of a model on big data via cross validation takes hours or even days. Thus, a framework is needed that provides a systematic means to minimize the number of queries needed to reach the optimal solution. Bayesian optimization (BO) [1-3] is a powerful methodology to seek an optimum of a black-box function without knowledge of its analytical properties, such as its gradient.

Submodular function maximization has numerous applications in machine learning and artificial intelligence. Many real applications require multiple submodular objective func-tions to be maximized, and which function is regarded as important by a user is not known in advance. In such cases, it is desirable to have a small family of representative solutions that would satisfy any user’s preference. A traditional approach for solving such a problem is to enumerate the Pareto optimal solutions. However, owing to the massive number of Pareto optimal solutions (possibly exponentially many), it is difficult for a user to select a solution. In this paper, we propose two efficient methods for finding a small family of representative solutions, based on the notion of regret ratio. The first method outputs a family of fixed size with a nontrivial regret ratio. The second method enables us to choose the size of the output family, and in the biobjective case, it has a provable trade-off between the size and the regret ratio. Using real and synthetic data, we empirically demonstrate that our methods achieve a small regret ratio.