Submodular Minimax Optimization: Finding Effective Sets

Loay Raed Mualem, Ethan R Elenberg, Moran Feldman, Amin Karbasi
Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, PMLR 238:1081-1089, 2024.

Abstract

Despite the rich existing literature about minimax optimization in continuous settings, only very partial results of this kind have been obtained for combinatorial settings. In this paper, we fill this gap by providing a characterization of submodular minimax optimization, the problem of finding a set (for either the min or the max player) that is effective against every possible response. We show when and under what conditions we can find such sets. We also demonstrate how minimax submodular optimization provides robust solutions for downstream machine learning applications such as (i) prompt engineering in large language models, (ii) identifying robust waiting locations for ride-sharing, (iii) kernelization of the difficulty of instances of the last setting, and (iv) finding adversarial images. Our experiments show that our proposed algorithms consistently outperform other baselines.

Cite this Paper

BibTeX
@InProceedings{pmlr-v238-raed-mualem24a, title = {Submodular Minimax Optimization: Finding Effective Sets}, author = {Raed Mualem, Loay and R Elenberg, Ethan and Feldman, Moran and Karbasi, Amin}, booktitle = {Proceedings of The 27th International Conference on Artificial Intelligence and Statistics}, pages = {1081--1089}, year = {2024}, editor = {Dasgupta, Sanjoy and Mandt, Stephan and Li, Yingzhen}, volume = {238}, series = {Proceedings of Machine Learning Research}, month = {02--04 May}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v238/raed-mualem24a/raed-mualem24a.pdf}, url = {https://proceedings.mlr.press/v238/raed-mualem24a.html}, abstract = {Despite the rich existing literature about minimax optimization in continuous settings, only very partial results of this kind have been obtained for combinatorial settings. In this paper, we fill this gap by providing a characterization of submodular minimax optimization, the problem of finding a set (for either the min or the max player) that is effective against every possible response. We show when and under what conditions we can find such sets. We also demonstrate how minimax submodular optimization provides robust solutions for downstream machine learning applications such as (i) prompt engineering in large language models, (ii) identifying robust waiting locations for ride-sharing, (iii) kernelization of the difficulty of instances of the last setting, and (iv) finding adversarial images. Our experiments show that our proposed algorithms consistently outperform other baselines.} }
Endnote
%0 Conference Paper %T Submodular Minimax Optimization: Finding Effective Sets %A Loay Raed Mualem %A Ethan R Elenberg %A Moran Feldman %A Amin Karbasi %B Proceedings of The 27th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2024 %E Sanjoy Dasgupta %E Stephan Mandt %E Yingzhen Li %F pmlr-v238-raed-mualem24a %I PMLR %P 1081--1089 %U https://proceedings.mlr.press/v238/raed-mualem24a.html %V 238 %X Despite the rich existing literature about minimax optimization in continuous settings, only very partial results of this kind have been obtained for combinatorial settings. In this paper, we fill this gap by providing a characterization of submodular minimax optimization, the problem of finding a set (for either the min or the max player) that is effective against every possible response. We show when and under what conditions we can find such sets. We also demonstrate how minimax submodular optimization provides robust solutions for downstream machine learning applications such as (i) prompt engineering in large language models, (ii) identifying robust waiting locations for ride-sharing, (iii) kernelization of the difficulty of instances of the last setting, and (iv) finding adversarial images. Our experiments show that our proposed algorithms consistently outperform other baselines.
APA
Raed Mualem, L., R Elenberg, E., Feldman, M. & Karbasi, A.. (2024). Submodular Minimax Optimization: Finding Effective Sets. Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 238:1081-1089 Available from https://proceedings.mlr.press/v238/raed-mualem24a.html.

Related Material