mlsanityData to 14 Oct 2026

Submodular Minimax Optimization: Finding Effective Sets

arXiv 2305.16903 ↗First posted 26 May 2023cs.LG cs.DM math.OCcited by 7

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 7 papers in the map (data through 14 Oct 2026). Builds on 42 of its 88 references that are in the map. First posted on arXiv 26 May 2023.

Builds on

42 of 88 references.

References · 42

  1. 2020Language Models are Few-Shot Learnerscited by 32,419
  2. 2022Training language models to follow instructions with human feedbackcited by 15,971
  3. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Modelscited by 12,459
  4. 2019Sentence-BERT: Sentence Embeddings using Siamese BERT-Networkscited by 9,170
  5. 2021Evaluating Large Language Models Trained on Codecited by 8,320
  6. 2016SQuAD: 100,000+ Questions for Machine Comprehension of Textcited by 4,148
  7. 2021Prefix-Tuning: Optimizing Continuous Prompts for Generationcited by 3,915
  8. 2021The Power of Scale for Parameter-Efficient Prompt Tuningcited by 3,795
  9. 2022Rethinking the Role of Demonstrations: What Makes In-Context Learning Work?cited by 1,434
  10. 2021Unsupervised Dense Information Retrieval with Contrastive Learningcited by 1,216
  11. 2022Large Language Models Are Human-Level Prompt Engineerscited by 1,045
  12. 2022Super-NaturalInstructions: Generalization via Declarative Instructions on 1600+ NLP Taskscited by 868
30 more
  1. 2018MultiWOZ -- A Large-Scale Multi-Domain Wizard-of-Oz Dataset for Task-Oriented Dialogue Modellingcited by 766
  2. 2023Hard Prompts Made Easy: Gradient-Based Discrete Optimization for Prompt Tuning and Discoverycited by 336
  3. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 270
  4. 2022Prompting GPT-3 To Be Reliablecited by 260
  5. 2020Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimizationcited by 96
  6. 2015A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimizationcited by 50
  7. 2022In-Context Learning for Few-Shot Dialogue State Trackingcited by 47
  8. 2014Near-Optimally Teaching the Crowd to Classifycited by 32
  9. 2019Adversarial Attack Generation Empowered by Min-Max Optimizationcited by 32
  10. 2022Minimax Regret Optimization for Robust Machine Learning under Distribution Shiftcited by 31
  11. 2022Data-Efficient Structured Pruning via Submodular Optimizationcited by 23
  12. 2017Scalable Greedy Feature Selection via Weak Submodularitycited by 19
  13. 2016Constrained Submodular Maximization via a Non-symmetric Techniquecited by 18
  14. 2017Robust Submodular Maximization: A Non-Uniform Partitioning Approachcited by 15
  15. 2018Data Summarization at Scale: A Two-Stage Submodular Approachcited by 14
  16. 2022Resolving the Approximability of Offline and Online Non-monotone DR-Submodular Maximization over General Convex Setscited by 14
  17. 2017Weakly Submodular Maximization Beyond Cardinality Constraints: Does Randomization Help Greedy?cited by 13
  18. 2017Streaming Robust Submodular Maximization: A Partitioned Thresholding Approachcited by 13
  19. 2018Distributionally Robust Submodular Maximizationcited by 12
  20. 2019Near-optimal Approximate Discrete and Continuous Submodular Function Minimizationcited by 11
  21. 2015Robust Monotone Submodular Function Maximizationcited by 10
  22. 2015Deterministic Algorithms for Submodular Maximization Problemscited by 10
  23. 2017Streaming Weak Submodularity: Interpreting Neural Networks on the Flycited by 9
  24. 2022Using Partial Monotonicity in Submodular Maximizationcited by 9
  25. 2016Constrained Submodular Maximization: Beyond 1/ecited by 7
  26. 2022On Maximizing Sums of Non-monotone Submodular and Linear Functionscited by 7
  27. 2017Structured Robust Submodular Maximization: Offline and Online Algorithmscited by 5
  28. 2021Minimax Optimization: The Case of Convex-Submodularcited by 5
  29. 2019A Unified Framework of Constrained Robust Submodular Optimization with Applicationscited by 3
  30. 2020Robust Submodular Minimization with Applications to Cooperative Modelingcited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 2; 2024: 2; 2025: 0; 2026: 3.

7 papers.

  1. 2023GistScore: Learning Better Representations for In-Context Example Selection with Gist Bottleneckscited by 6
  2. 2023ORBSLAM3-Enhanced Autonomous Toy Drones: Pioneering Indoor Explorationcited by 5
  3. 2024Practical 0.385-Approximation for Submodular Maximization Subject to a Cardinality Constraintcited by 3
  4. 2026Solving the Offline and Online Min-Max Problem of Non-smooth Submodular-Concave Functions: A Zeroth-Order Approachcited by 2
  5. 2024Bridging the Gap Between General and Down-Closed Convex Sets in Submodular Maximizationcited by 1
  6. 2026Supportive Token Revealing for Fast Diffusion Language Model Decodingcited by 1
  7. 2026Fine-Tuning Diffusion Language Models with Context Selection and Target Weightingcited by 0