Random Hypervolume Scalarizations for Provable Multi-Objective Black Box Optimization

Abstract

Single-objective black box optimization (also known as zeroth-order optimization) is the process of minimizing a scalar objective $f(x)$, given evaluations at adaptively chosen inputs $x$. In this paper, we consider multi-objective optimization, where $f(x)$ outputs a vector of possibly competing objectives and the goal is to converge to the Pareto frontier. Quantitatively, we wish to maximize the standard hypervolume indicator metric, which measures the dominated hypervolume of the entire set of chosen inputs. In this paper, we introduce a novel scalarization function, which we term the hypervolume scalarization, and show that drawing random scalarizations from an appropriately chosen distribution can be used to efficiently approximate the hypervolume indicator metric. We utilize this connection to show that Bayesian optimization with our scalarization via common acquisition functions, such as Thompson Sampling or Upper Confidence Bound, provably converges to the whole Pareto frontier by deriving tight hypervolume regret bounds on the order of $\tilde{O}(\sqrt{T})$. Furthermore, we highlight the general utility of our scalarization framework by showing that any provably convergent single-objective optimization process can be effortlessly converted to a multi-objective optimization process with provable convergence guarantees.

ICML 2020

References in corpus (11)

• Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networks
• Theoretically Principled Trade-off between Robustness and Accuracy
• Predictive Entropy Search for Multi-objective Bayesian Optimization
• On the relation between accuracy and fairness in binary classification
• A Modern Take on the Bias-Variance Tradeoff in Neural Networks
• Pareto Multi-Task Learning
• A Flexible Framework for Multi-Objective Bayesian Optimization using Random Scalarizations
• Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization
• Multi-objective Contextual Bandit Problem with Similarity Information
• Multi-Objective Generalized Linear Bandits
• Combinatorial Multi-Objective Multi-Armed Bandit Problem

Cited by in corpus (5)

• Parallel Bayesian Optimization of Multiple Noisy Objectives with Expected Hypervolume Improvement
• Multi-objective Asynchronous Successive Halving
• The Fairness-Accuracy Pareto Front
• Multi-Objective Learning to Predict Pareto Fronts Using Hypervolume Maximization
• A multi-objective perspective on jointly tuning hardware and hyperparameters