Robustness in Multi-Objective Submodular Optimization: a Quantile Approach

Cedric Malherbe, Kevin Scaman
Proceedings of the 39th International Conference on Machine Learning, PMLR 162:14871-14886, 2022.

Abstract

The optimization of multi-objective submodular systems appears in a wide variety of applications. However, there are currently very few techniques which are able to provide a robust allocation to such systems. In this work, we propose to design and analyse novel algorithms for the robust allocation of submodular systems through lens of quantile maximization. We start by observing that identifying an exact solution for this problem is computationally intractable. To tackle this issue, we propose a proxy for the quantile function using a softmax formulation, and show that this proxy is well suited to submodular optimization. Based on this relaxation, we propose a novel and simple algorithm called SOFTSAT. Theoretical properties are provided for this algorithm as well as novel approximation guarantees. Finally, we provide numerical experiments showing the efficiency of our algorithm with regards to state-of-the-art methods in a test bed of real-world applications, and show that SOFTSAT is particularly robust and well-suited to online scenarios.

Cite this Paper

BibTeX
@InProceedings{pmlr-v162-malherbe22a, title = {Robustness in Multi-Objective Submodular Optimization: a Quantile Approach}, author = {Malherbe, Cedric and Scaman, Kevin}, booktitle = {Proceedings of the 39th International Conference on Machine Learning}, pages = {14871--14886}, year = {2022}, editor = {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan}, volume = {162}, series = {Proceedings of Machine Learning Research}, month = {17--23 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v162/malherbe22a/malherbe22a.pdf}, url = {https://proceedings.mlr.press/v162/malherbe22a.html}, abstract = {The optimization of multi-objective submodular systems appears in a wide variety of applications. However, there are currently very few techniques which are able to provide a robust allocation to such systems. In this work, we propose to design and analyse novel algorithms for the robust allocation of submodular systems through lens of quantile maximization. We start by observing that identifying an exact solution for this problem is computationally intractable. To tackle this issue, we propose a proxy for the quantile function using a softmax formulation, and show that this proxy is well suited to submodular optimization. Based on this relaxation, we propose a novel and simple algorithm called SOFTSAT. Theoretical properties are provided for this algorithm as well as novel approximation guarantees. Finally, we provide numerical experiments showing the efficiency of our algorithm with regards to state-of-the-art methods in a test bed of real-world applications, and show that SOFTSAT is particularly robust and well-suited to online scenarios.} }
Endnote
%0 Conference Paper %T Robustness in Multi-Objective Submodular Optimization: a Quantile Approach %A Cedric Malherbe %A Kevin Scaman %B Proceedings of the 39th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2022 %E Kamalika Chaudhuri %E Stefanie Jegelka %E Le Song %E Csaba Szepesvari %E Gang Niu %E Sivan Sabato %F pmlr-v162-malherbe22a %I PMLR %P 14871--14886 %U https://proceedings.mlr.press/v162/malherbe22a.html %V 162 %X The optimization of multi-objective submodular systems appears in a wide variety of applications. However, there are currently very few techniques which are able to provide a robust allocation to such systems. In this work, we propose to design and analyse novel algorithms for the robust allocation of submodular systems through lens of quantile maximization. We start by observing that identifying an exact solution for this problem is computationally intractable. To tackle this issue, we propose a proxy for the quantile function using a softmax formulation, and show that this proxy is well suited to submodular optimization. Based on this relaxation, we propose a novel and simple algorithm called SOFTSAT. Theoretical properties are provided for this algorithm as well as novel approximation guarantees. Finally, we provide numerical experiments showing the efficiency of our algorithm with regards to state-of-the-art methods in a test bed of real-world applications, and show that SOFTSAT is particularly robust and well-suited to online scenarios.
APA
Malherbe, C. & Scaman, K.. (2022). Robustness in Multi-Objective Submodular Optimization: a Quantile Approach. Proceedings of the 39th International Conference on Machine Learning, in Proceedings of Machine Learning Research 162:14871-14886 Available from https://proceedings.mlr.press/v162/malherbe22a.html.

Related Material