Multi-objective optimisation via the R2 utilities
2305.11774
0
0
๐ฃ๏ธ
Abstract
The goal of multi-objective optimisation is to identify a collection of points which describe the best possible trade-offs between the multiple objectives. In order to solve this vector-valued optimisation problem, practitioners often appeal to the use of scalarisation functions in order to transform the multi-objective problem into a collection of single-objective problems. This set of scalarised problems can then be solved using traditional single-objective optimisation techniques. In this work, we formalise this convention into a general mathematical framework. We show how this strategy effectively recasts the original multi-objective optimisation problem into a single-objective optimisation problem defined over sets. An appropriate class of objective functions for this new problem are the R2 utilities, which are utility functions that are defined as a weighted integral over the scalarised optimisation problems. As part of our work, we show that these utilities are monotone and submodular set functions which can be optimised effectively using greedy optimisation algorithms. We then analyse the performance of these greedy algorithms both theoretically and empirically. Our analysis largely focusses on Bayesian optimisation, which is a popular probabilistic framework for black-box optimisation.
Create account to get full access
Overview
- The paper discusses a mathematical framework for solving multi-objective optimization problems using scalarization functions.
- It shows how this strategy effectively transforms the original multi-objective problem into a single-objective optimization problem defined over sets.
- The paper analyzes the properties of a specific class of objective functions called R2 utilities, which are well-suited for this approach.
- It also explores the performance of greedy optimization algorithms for solving these set-based optimization problems, with a focus on Bayesian optimization.
Plain English Explanation
When dealing with optimization problems that have multiple objectives (e.g., minimizing cost while maximizing performance), it can be challenging to find the best set of trade-offs between these different goals. The authors of this paper propose a mathematical framework that can help solve these multi-objective optimization problems.
The key idea is to transform the original multi-objective problem into a single-objective problem by using "scalarization functions." These functions combine the multiple objectives into a single value that can be optimized using standard optimization techniques. The authors show that this approach effectively reframes the problem as a single-objective optimization problem over sets of solutions, rather than individual points.
The paper then focuses on a specific class of scalarization functions called "R2 utilities." These are utility functions that are defined as a weighted average of the scalarized optimization problems. The authors prove that these R2 utilities have some useful mathematical properties, such as being "monotone" and "submodular," which means they can be optimized efficiently using greedy algorithms.
The paper also analyzes the performance of these greedy algorithms, particularly in the context of Bayesian optimization, which is a popular framework for optimizing "black-box" functions (functions with unknown or complex internal structure). The authors provide both theoretical and empirical insights into the effectiveness of this approach.
Technical Explanation
The paper formalizes the common practice of using scalarization functions to transform a multi-objective optimization problem into a collection of single-objective problems. This strategy effectively recasts the original problem as a single-objective optimization problem defined over sets of solutions, rather than individual points.
The authors show that an appropriate class of objective functions for this set-based optimization problem are the R2 utilities. These utilities are defined as a weighted integral over the scalarized optimization problems and have the useful mathematical properties of being monotone and submodular. This means they can be optimized effectively using greedy optimization algorithms.
The paper analyzes the performance of these greedy algorithms, both theoretically and empirically. A particular focus is on Bayesian optimization, a popular probabilistic framework for black-box optimization. The authors provide insights into the convergence rates and approximation guarantees of the greedy algorithms in this context.
Critical Analysis
The paper provides a solid mathematical foundation for using scalarization functions to solve multi-objective optimization problems. The analysis of the R2 utilities and their optimization via greedy algorithms is thorough and technically sound.
However, the paper does not delve into the practical implications or limitations of this approach. For example, the choice of scalarization function and the weighting of the different objectives can have a significant impact on the resulting trade-offs, but this is not discussed in depth.
Additionally, the paper focuses primarily on Bayesian optimization, but there are other techniques for multi-objective optimization, such as reinforcement learning or bilevel optimization, that could potentially be combined with the proposed framework. Exploring the interactions between this approach and other multi-objective optimization methods could be a fruitful area for further research.
Conclusion
This paper presents a comprehensive mathematical framework for solving multi-objective optimization problems using scalarization functions and R2 utilities. The authors demonstrate the favorable theoretical and empirical properties of this approach, particularly in the context of Bayesian optimization.
While the technical details are complex, the core idea of transforming a multi-objective problem into a single-objective one defined over sets of solutions is an important contribution to the field of multi-objective optimization. This framework could potentially be enhanced through the use of machine learning techniques and applied to a wide range of real-world optimization problems with competing objectives.
This summary was produced with help from an AI and may contain inaccuracies - check out the links to read the original source documents!
Related Papers
Scalarisation-based risk concepts for robust multi-objective optimisation
Ben Tu, Nikolas Kantas, Robert M. Lee, Behrang Shafei
0
0
Robust optimisation is a well-established framework for optimising functions in the presence of uncertainty. The inherent goal of this problem is to identify a collection of inputs whose outputs are both desirable for the decision maker, whilst also being robust to the underlying uncertainties in the problem. In this work, we study the multi-objective extension of this problem from a computational standpoint. We identify that the majority of all robust multi-objective algorithms rely on two key operations: robustification and scalarisation. Robustification refers to the strategy that is used to marginalise over the uncertainty in the problem. Whilst scalarisation refers to the procedure that is used to encode the relative importance of each objective. As these operations are not necessarily commutative, the order that they are performed in has an impact on the resulting solutions that are identified and the final decisions that are made. This work aims to give an exposition on the philosophical differences between these two operations and highlight when one should opt for one ordering over the other. As part of our analysis, we showcase how many existing risk concepts can be easily integrated into the specification and solution of a robust multi-objective optimisation problem. Besides this, we also demonstrate how one can principally define the notion of a robust Pareto front and a robust performance metric based on our robustify and scalarise methodology. To illustrate the efficacy of these new ideas, we present two insightful numerical case studies which are based on real-world data sets.
5/17/2024
UCB-driven Utility Function Search for Multi-objective Reinforcement Learning
Yucheng Shi, Alexandros Agapitos, David Lynch, Giorgio Cruciata, Cengis Hasan, Hao Wang, Yayu Yao, Aleksandar Milenovic
0
0
In Multi-objective Reinforcement Learning (MORL) agents are tasked with optimising decision-making behaviours that trade-off between multiple, possibly conflicting, objectives. MORL based on decomposition is a family of solution methods that employ a number of utility functions to decompose the multi-objective problem into individual single-objective problems solved simultaneously in order to approximate a Pareto front of policies. We focus on the case of linear utility functions parameterised by weight vectors w. We introduce a method based on Upper Confidence Bound to efficiently search for the most promising weight vectors during different stages of the learning process, with the aim of maximising the hypervolume of the resulting Pareto front. The proposed method is shown to outperform various MORL baselines on Mujoco benchmark problems across different random seeds. The code is online at: https://github.com/SYCAMORE-1/ucb-MOPPO.
5/17/2024
๐ ๏ธ
Multi-Objective Hyperparameter Optimization in Machine Learning -- An Overview
Florian Karl, Tobias Pielok, Julia Moosbauer, Florian Pfisterer, Stefan Coors, Martin Binder, Lennart Schneider, Janek Thomas, Jakob Richter, Michel Lang, Eduardo C. Garrido-Merch'an, Juergen Branke, Bernd Bischl
0
0
Hyperparameter optimization constitutes a large part of typical modern machine learning workflows. This arises from the fact that machine learning methods and corresponding preprocessing steps often only yield optimal performance when hyperparameters are properly tuned. But in many applications, we are not only interested in optimizing ML pipelines solely for predictive accuracy; additional metrics or constraints must be considered when determining an optimal configuration, resulting in a multi-objective optimization problem. This is often neglected in practice, due to a lack of knowledge and readily available software implementations for multi-objective hyperparameter optimization. In this work, we introduce the reader to the basics of multi-objective hyperparameter optimization and motivate its usefulness in applied ML. Furthermore, we provide an extensive survey of existing optimization strategies, both from the domain of evolutionary algorithms and Bayesian optimization. We illustrate the utility of MOO in several specific ML applications, considering objectives such as operating conditions, prediction time, sparseness, fairness, interpretability and robustness.
6/7/2024
๐
Multi-Objective Recommendation via Multivariate Policy Learning
Olivier Jeunen, Jatin Mandav, Ivan Potapov, Nakul Agarwal, Sourabh Vaid, Wenzhe Shi, Aleksei Ustimenko
0
0
Real-world recommender systems often need to balance multiple objectives when deciding which recommendations to present to users. These include behavioural signals (e.g. clicks, shares, dwell time), as well as broader objectives (e.g. diversity, fairness). Scalarisation methods are commonly used to handle this balancing task, where a weighted average of per-objective reward signals determines the final score used for ranking. Naturally, how these weights are computed exactly, is key to success for any online platform. We frame this as a decision-making task, where the scalarisation weights are actions taken to maximise an overall North Star reward (e.g. long-term user retention or growth). We extend existing policy learning methods to the continuous multivariate action domain, proposing to maximise a pessimistic lower bound on the North Star reward that the learnt policy will yield. Typical lower bounds based on normal approximations suffer from insufficient coverage, and we propose an efficient and effective policy-dependent correction for this. We provide guidance to design stochastic data collection policies, as well as highly sensitive reward signals. Empirical observations from simulations, offline and online experiments highlight the efficacy of our deployed approach.
5/6/2024