# Random Hypervolume Scalarizations for Provable Multi-Objective Black Box Optimization

arXiv: https://arxiv.org/abs/2006.04655 · HTML: https://mlsanity.com/paper/2006.04655/

## Key facts

- Cited by 60 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Jun 2020.

## Built on by (most cited first, 30 of 60)

- [Parallel Bayesian Optimization of Multiple Noisy Objectives with Expected Hypervolume Improvement](https://mlsanity.com/paper/2105.08195/) (2021)
- [Multi-Objective GFlowNets](https://mlsanity.com/paper/2210.12765/) (2022)
- [Multi-Objective Bayesian Optimization over High-Dimensional Search Spaces](https://mlsanity.com/paper/2109.10964/) (2021)
- [Pareto Set Learning for Neural Multi-objective Combinatorial Optimization](https://mlsanity.com/paper/2203.15386/) (2022)
- [Pareto Set Learning for Expensive Multi-Objective Optimization](https://mlsanity.com/paper/2210.08495/) (2022)
- [Joint Entropy Search for Multi-objective Bayesian Optimization](https://mlsanity.com/paper/2210.02905/) (2022)
- [Pareto Invariant Risk Minimization: Towards Mitigating the Optimization Dilemma in Out-of-Distribution Generalization](https://mlsanity.com/paper/2206.07766/) (2022)
- [Bayesian Optimization over Discrete and Mixed Spaces via Probabilistic Reparameterization](https://mlsanity.com/paper/2210.10199/) (2022)
- [Multi-objective Asynchronous Successive Halving](https://mlsanity.com/paper/2106.12639/) (2021)
- [Pareto Set Learning for Multi-Objective Reinforcement Learning](https://mlsanity.com/paper/2501.06773/) (2025)
- [Gradient-Based Multi-Objective Deep Learning: Algorithms, Theories, Applications, and Beyond](https://mlsanity.com/paper/2501.10945/) (2025)
- [ParetoFlow: Guided Flows in Multi-Objective Optimization](https://mlsanity.com/paper/2412.03718/) (2024)
- [Multi-Objective Learning to Predict Pareto Fronts Using Hypervolume Maximization](https://mlsanity.com/paper/2102.04523/) (2021)
- [Fair and Green Hyperparameter Optimization via Multi-objective and Multiple Information Source Bayesian Optimization](https://mlsanity.com/paper/2205.08835/) (2022)
- [Mitigating Gradient Bias in Multi-objective Learning: A Provably Convergent Stochastic Approach](https://mlsanity.com/paper/2210.12624/) (2022)
- [The Vizier Gaussian Process Bandit Algorithm](https://mlsanity.com/paper/2408.11527/) (2024)
- [A multi-objective perspective on jointly tuning hardware and hyperparameters](https://mlsanity.com/paper/2106.05680/) (2021)
- [Optimizing Privacy, Utility and Efficiency in Constrained Multi-Objective Federated Learning](https://mlsanity.com/paper/2305.00312/) (2023)
- [qPOTS: Efficient batch multiobjective Bayesian optimization via Pareto optimal Thompson sampling](https://mlsanity.com/paper/2310.15788/) (2023)
- [Gradient Shaping for Multi-Constraint Safe Reinforcement Learning](https://mlsanity.com/paper/2312.15127/) (2023)
- [TurboTrain: Towards Efficient and Balanced Multi-Task Learning for Multi-Agent Perception and Prediction](https://mlsanity.com/paper/2508.04682/) (2025)
- [Optimal Scalarizations for Sublinear Hypervolume Regret](https://mlsanity.com/paper/2307.03288/) (2023)
- [Constrained Multi-objective Bayesian Optimization through Optimistic Constraints Estimation](https://mlsanity.com/paper/2411.03641/) (2024)
- [On Multi-objective Policy Optimization as a Tool for Reinforcement Learning: Case Studies in Offline RL and Finetuning](https://mlsanity.com/paper/2106.08199/) (2021)
- [Probably Approximately Correct Federated Learning](https://mlsanity.com/paper/2304.04641/) (2023)
- [Multi-Objective Population Based Training](https://mlsanity.com/paper/2306.01436/) (2023)
- [C-MORL: Multi-Objective Reinforcement Learning through Efficient Discovery of Pareto Front](https://mlsanity.com/paper/2410.02236/) (2024)
- [IMO3: Interactive Multi-Objective Off-Policy Optimization](https://mlsanity.com/paper/2201.09798/) (2022)
- [Probability Distribution of Hypervolume Improvement in Bi-objective Bayesian Optimization](https://mlsanity.com/paper/2205.05505/) (2022)
- [Multi-objective optimisation via the R2 utilities](https://mlsanity.com/paper/2305.11774/) (2023)

## Abstract (arXiv)

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 widetildeO(√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.