Pareto Set Identification With Posterior Sampling

Cyrille Kone, Marc Jourdan, Emilie Kaufmann
Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, PMLR 258:1000-1008, 2025.

Abstract

The problem of identifying the best answer among a collection of items having real-valued distribution is well-understood. Despite its practical relevance for many applications, fewer works have studied its extension when multiple and potentially conflicting metrics are available to assess an item’s quality. Pareto set identification (PSI) aims to identify the set of answers whose means are not uniformly worse than another. This paper studies PSI in the transductive linear setting with potentially correlated objectives. Building on posterior sampling in both the stopping and the sampling rules, we propose the \hyperlink{PSIPS}{PSIPS} algorithm that deals simultaneously with structure and correlation without paying the computational cost of existing oracle-based algorithms. Both from a frequentist and Bayesian perspective, \hyperlink{PSIPS}{PSIPS} is asymptotically optimal. We demonstrate its good empirical performance in real-world and synthetic instances.

Cite this Paper

BibTeX
@InProceedings{pmlr-v258-kone25a, title = {Pareto Set Identification With Posterior Sampling}, author = {Kone, Cyrille and Jourdan, Marc and Kaufmann, Emilie}, booktitle = {Proceedings of The 28th International Conference on Artificial Intelligence and Statistics}, pages = {1000--1008}, year = {2025}, editor = {Li, Yingzhen and Mandt, Stephan and Agrawal, Shipra and Khan, Emtiyaz}, volume = {258}, series = {Proceedings of Machine Learning Research}, month = {03--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v258/main/assets/kone25a/kone25a.pdf}, url = {https://proceedings.mlr.press/v258/kone25a.html}, abstract = {The problem of identifying the best answer among a collection of items having real-valued distribution is well-understood. Despite its practical relevance for many applications, fewer works have studied its extension when multiple and potentially conflicting metrics are available to assess an item’s quality. Pareto set identification (PSI) aims to identify the set of answers whose means are not uniformly worse than another. This paper studies PSI in the transductive linear setting with potentially correlated objectives. Building on posterior sampling in both the stopping and the sampling rules, we propose the \hyperlink{PSIPS}{PSIPS} algorithm that deals simultaneously with structure and correlation without paying the computational cost of existing oracle-based algorithms. Both from a frequentist and Bayesian perspective, \hyperlink{PSIPS}{PSIPS} is asymptotically optimal. We demonstrate its good empirical performance in real-world and synthetic instances.} }
Endnote
%0 Conference Paper %T Pareto Set Identification With Posterior Sampling %A Cyrille Kone %A Marc Jourdan %A Emilie Kaufmann %B Proceedings of The 28th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2025 %E Yingzhen Li %E Stephan Mandt %E Shipra Agrawal %E Emtiyaz Khan %F pmlr-v258-kone25a %I PMLR %P 1000--1008 %U https://proceedings.mlr.press/v258/kone25a.html %V 258 %X The problem of identifying the best answer among a collection of items having real-valued distribution is well-understood. Despite its practical relevance for many applications, fewer works have studied its extension when multiple and potentially conflicting metrics are available to assess an item’s quality. Pareto set identification (PSI) aims to identify the set of answers whose means are not uniformly worse than another. This paper studies PSI in the transductive linear setting with potentially correlated objectives. Building on posterior sampling in both the stopping and the sampling rules, we propose the \hyperlink{PSIPS}{PSIPS} algorithm that deals simultaneously with structure and correlation without paying the computational cost of existing oracle-based algorithms. Both from a frequentist and Bayesian perspective, \hyperlink{PSIPS}{PSIPS} is asymptotically optimal. We demonstrate its good empirical performance in real-world and synthetic instances.
APA
Kone, C., Jourdan, M. & Kaufmann, E.. (2025). Pareto Set Identification With Posterior Sampling. Proceedings of The 28th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 258:1000-1008 Available from https://proceedings.mlr.press/v258/kone25a.html.

Related Material