TL;DR
This paper introduces qPOTS, a novel Bayesian optimization (BO) approach for efficiently finding optimal solutions in complex, multi-objective problems where evaluating objectives is costly. By leveraging Thompson Sampling (TS) to directly target Pareto optimality and employing evolutionary algorithms on GP posteriors, qPOTS achieves superior sample efficiency and handles constraints and batch acquisitions more effectively than existing methods.
What Problem Does This Paper Address?
Many real-world optimization problems involve simultaneously optimizing multiple objectives (e.g., maximizing performance while minimizing cost). These objectives are often "expensive oracles," meaning each evaluation is time-consuming or resource-intensive. Traditional evolutionary algorithms (EAs) can find good solutions but require a vast number of evaluations, making them impractical. Bayesian Optimization (BO) offers a sample-efficient alternative by building probabilistic models (Gaussian Processes or GPs) of the objectives and intelligently selecting the next points to evaluate. However, standard BO for multi-objective problems (MOBO) faces challenges: the "inner optimization" of acquisition functions is often computationally expensive, non-convex, and difficult to solve, especially when acquiring multiple points simultaneously (batch optimization). This difficulty hinders MOBO's sample efficiency. Furthermore, handling constraints in MOBO is also a significant challenge.
Methods
The core innovation of qPOTS lies in its adaptation of Thompson Sampling (TS) for multi-objective Bayesian optimization. Instead of traditional acquisition functions that require solving a difficult inner optimization problem, qPOTS directly samples from the posterior distribution of the objectives. Specifically:
- Pareto Optimal Thompson Sampling: qPOTS selects candidate points based on their probability of being Pareto optimal, rather than simply being "optimal" in a single objective sense. This is achieved by sampling from the posterior GPs and then finding the Pareto optimal set of these sampled paths.
- Cheap Inner Optimization: The "inner optimization" to find the Pareto optimal set of sampled paths is performed using evolutionary algorithms (like NSGA-II) on the sampled GP posteriors. This is significantly cheaper than optimizing complex acquisition functions.
- Batch Acquisition: qPOTS naturally extends to batch acquisition by selecting multiple points from the computed Pareto set of the sampled GP paths. To ensure diversity and balance exploration/exploitation, these points are chosen using a maximin distance criterion to previously observed points.
- Constraint Handling: The method seamlessly incorporates constraints by fitting additional GPs for each constraint and filtering the sampled Pareto sets based on feasibility. This requires no structural changes to the core algorithm.
- Nyström Approximation: For high-dimensional problems, qPOTS utilizes the Nyström approximation to efficiently compute the GP posterior covariance matrix, improving scalability.
Datasets
The paper evaluates qPOTS on a variety of synthetic and real-world benchmarks:
Synthetic Experiments: * Branin-Currin * ZDT3 (known for disjoint Pareto frontiers) * DTLZ3 * DTLZ7 * OSY (a constrained problem with 6 constraints)
Real-World Experiments: * Penicillin production (d=7, K=3) * Vehicle Safety problem (d=5, K=3) * Car side-impact problem (d=5, K=3, with 10 constraints)
The paper does not introduce new benchmarks.
Key Insights and Ideas
- Thompson Sampling for Pareto Optimality is Powerful: Directly sampling from the posterior and identifying Pareto optimal sets within these samples is a more principled and efficient way to guide exploration than optimizing complex, hand-crafted acquisition functions.
- Bridging EA and BO: qPOTS effectively combines the accuracy of evolutionary approaches (for the inner optimization on posteriors) with the sample efficiency of Bayesian Optimization.
- Natural Exploration-Exploitation Balance: The TS approach, combined with the maximin distance criterion for batch selection, inherently balances exploring uncertain regions with exploiting promising ones.
- Seamless Constraint Handling: The ability to incorporate constraints by simply adding more GPs and filtering is a significant advantage over methods that struggle with or do not support constraints.
- Batch Efficiency: The computational cost of batch acquisition in qPOTS is comparable to sequential acquisition, a major improvement over many existing batch MOBO methods.
Key Results
- Superior Sample Efficiency: qPOTS consistently outperforms state-of-the-art methods (TSEMO, PESMO, MESMO, qNEHVI, qPAREGO, Sobol) in terms of hypervolume achieved for a given number of evaluations across various synthetic and real-world problems.
- Effective Constraint Handling: qPOTS successfully handles constrained problems where other methods (like TSEMO, PESMO, MESMO, qNEHVI) struggle or fail due to memory issues or lack of support.
- Scalability: The Nyström approximation allows qPOTS to scale to higher dimensions without significant loss of accuracy.
- Batch Performance: The benefit of qPOTS is particularly pronounced in batch acquisition settings, where it maintains efficiency while competitors become more expensive.
- Theoretical Guarantees: The paper provides theoretical guarantees showing that qPOTS's posterior GP objectives converge to the true objectives and the predicted Pareto frontier converges to the true Pareto frontier with high probability.
Limitations and Future Work
- Assumption of Exact Inner Optimization: The theoretical proofs rely on the assumption that the inner multiobjective optimization problem (finding the Pareto set of sampled GP paths) is solved exactly. The authors argue this is reasonable in practice by increasing EA parameters (population size, generations), which is demonstrated empirically.
- Choice of Nyström Subset: The paper mentions that the choice of the subset for the Nyström approximation is an open research question, though they use the subset of nondominated points from the current observations.
- Future Work:
- Marrying qPOTS with nonstationary GPs (like deep GPs) and input warping for problems with non-stationary output spaces.
- Exploring the use of multitask GPs to exploit correlations between objectives and constraints.
- The authors anticipate that qPOTS would require minimal structural changes to accommodate these extensions.
Summary updated