Submodular Minimax Optimization: Finding Effective Sets
Loay Mualem Ethan R. Elenberg Moran Feldman Amin Karbasi
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) efficient
prompt engineering for question answering, (ii) prompt engineering for dialog
state tracking, (iii) identifying robust waiting locations for ride-sharing,
(iv) ride-share difficulty kernelization, and (v) finding adversarial images.
Our experiments demonstrate that our proposed algorithms consistently
outperform other baselines.