Submodular Minimax Optimization: Finding Effective Sets
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.
Code (0)
등록된 구현이 없습니다.
Tasks
dialog state trackingPrompt EngineeringQuestion AnsweringSimilar Papers 제목 키워드 기반
Minimax Optimization: The Case of Convex-Submodular
Minimax optimization has been central in addressing various applications in machine learning, game theory, and control theory. Prior literature has thus far mainly focused on studying such problems in the continuous doma…
Minimax Curriculum Learning: Machine Teaching with Desirable Difficulties and Scheduled Diversity
We introduce and study minimax curriculum learning (MCL), a new method for adaptively selecting a sequence of training subsets for a succession of stages in machine learning. The subsets are encouraged to be small and di…
ClusteringDiversitySubmodlib: A Submodular Optimization Library
Submodular functions are a special class of set functions which naturally model the notion of representativeness, diversity, coverage etc. and have been shown to be computationally very efficient. A lot of past work has …
Data SummarizationDiversityLearning Interpretable Decision Rule Sets: A Submodular Optimization Approach
Rule sets are highly interpretable logical models in which the predicates for decision are expressed in disjunctive normal form (DNF, OR-of-ANDs), or, equivalently, the overall model comprises an unordered collection of …
Gradient Descent Ascent for Minimax Problems on Riemannian Manifolds
In the paper, we study a class of useful minimax problems on Riemanian manifolds and propose a class of effective Riemanian gradient-based methods to solve these minimax problems. Specifically, we propose an effective Ri…