# Minimax Optimization: The Case of Convex-Submodular

arXiv: https://arxiv.org/abs/2111.01262 · HTML: https://mlsanity.com/paper/2111.01262/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 75 references that are in the map.
- First posted on arXiv 1 Nov 2021.

## Builds on (most cited first, 30 of 35)

- [Making AI Forget You: Data Deletion in Machine Learning](https://mlsanity.com/paper/1907.05012/) (2019)
- [Descent-to-Delete: Gradient-Based Methods for Machine Unlearning](https://mlsanity.com/paper/2007.02923/) (2020)
- [On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/1906.00331/) (2019)
- [Curriculum Learning: A Survey](https://mlsanity.com/paper/2101.10382/) (2021)
- [Melding the Data-Decisions Pipeline: Decision-Focused Learning for Combinatorial Optimization](https://mlsanity.com/paper/1809.05504/) (2018)
- [Training GANs with Optimism](https://mlsanity.com/paper/1711.00141/) (2017)
- [DeltaGrad: Rapid retraining of machine learning models](https://mlsanity.com/paper/2006.14755/) (2020)
- [Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methods](https://mlsanity.com/paper/1902.08297/) (2019)
- [A Unified Analysis of Extra-gradient and Optimistic Gradient Methods for Saddle Point Problems: Proximal Point Approach](https://mlsanity.com/paper/1901.08511/) (2019)
- [Near-Optimal Algorithms for Minimax Optimization](https://mlsanity.com/paper/2002.02417/) (2020)
- [Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization](https://mlsanity.com/paper/2011.00364/) (2020)
- [Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems](https://mlsanity.com/paper/1808.02901/) (2018)
- [Efficient Algorithms for Smooth Minimax Optimization](https://mlsanity.com/paper/1907.01543/) (2019)
- [Stochastic Conditional Gradient Methods: From Convex Minimization to Submodular Maximization](https://mlsanity.com/paper/1804.09554/) (2018)
- [Global Convergence and Variance-Reduced Optimization for a Class of Nonconvex-Nonconcave Minimax Problems](https://mlsanity.com/paper/2002.09621/) (2020)
- [Robust Optimization for Non-Convex Objectives](https://mlsanity.com/paper/1707.01047/) (2017)
- [Discrete Adversarial Attacks and Submodular Optimization with Applications to Text Classification](https://mlsanity.com/paper/1812.00151/) (2018)
- [A Minimax Approach to Supervised Learning](https://mlsanity.com/paper/1606.02206/) (2016)
- [Gradient Methods for Submodular Maximization](https://mlsanity.com/paper/1708.03949/) (2017)
- [Coresets for Robust Training of Neural Networks against Noisy Labels](https://mlsanity.com/paper/2011.07451/) (2020)
- [Differentiable Submodular Maximization](https://mlsanity.com/paper/1803.01785/) (2018)
- [Minimax Active Learning](https://mlsanity.com/paper/2012.10467/) (2020)
- [Robust Submodular Maximization: A Non-Uniform Partitioning Approach](https://mlsanity.com/paper/1706.04918/) (2017)
- [Data Summarization at Scale: A Two-Stage Submodular Approach](https://mlsanity.com/paper/1806.02815/) (2018)
- [Streaming Robust Submodular Maximization: A Partitioned Thresholding Approach](https://mlsanity.com/paper/1711.02598/) (2017)
- [Submodular + Concave](https://mlsanity.com/paper/2106.04769/) (2021)
- [Distributionally Robust Submodular Maximization](https://mlsanity.com/paper/1802.05249/) (2018)
- [Robust Monotone Submodular Function Maximization](https://mlsanity.com/paper/1507.06616/) (2015)
- [A Primal-Dual Algorithm with Line Search for General Convex-Concave Saddle Point Problems](https://mlsanity.com/paper/1803.01401/) (2018)
- [Online Continuous DR-Submodular Maximization with Long-Term Budget Constraints](https://mlsanity.com/paper/1907.00316/) (2019)

## Built on by (most cited first, 5 of 5)

- [Submodular Minimax Optimization: Finding Effective Sets](https://mlsanity.com/paper/2305.16903/) (2023)
- [Solving the Offline and Online Min-Max Problem of Non-smooth Submodular-Concave Functions: A Zeroth-Order Approach](https://mlsanity.com/paper/2601.21243/) (2026)
- [Score-Based Methods for Discrete Optimization in Deep Learning](https://mlsanity.com/paper/2310.09890/) (2023)
- [Learning to Sparsify Stochastic Linear Bandits](https://mlsanity.com/paper/2605.10151/) (2026)
- [Toward Trustworthy AI: Multi-Target Adversarial Attacks and Robust Defenses for Continuous Data Summarization](https://mlsanity.com/paper/2606.11804/) (2026)

## Abstract (arXiv)

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 domain, e.g., convex-concave minimax optimization is now understood to a significant extent. Nevertheless, minimax problems extend far beyond the continuous domain to mixed continuous-discrete domains or even fully discrete domains. In this paper, we study mixed continuous-discrete minimax problems where the minimization is over a continuous variable belonging to Euclidean space and the maximization is over subsets of a given ground set. We introduce the class of convex-submodular minimax problems, where the objective is convex with respect to the continuous variable and submodular with respect to the discrete variable. Even though such problems appear frequently in machine learning applications, little is known about how to address them from algorithmic and theoretical perspectives. For such problems, we first show that obtaining saddle points are hard up to any approximation, and thus introduce new notions of (near-) optimality. We then provide several algorithmic procedures for solving convex and monotone-submodular minimax problems and characterize their convergence rates, computational complexity, and quality of the final solution according to our notions of optimally. Our proposed algorithms are iterative and combine tools from both discrete and continuous optimization. Finally, we provide numerical experiments to showcase the effectiveness of our purposed methods.