# Submodular Functions: from Discrete to Continous Domains

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

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Nov 2015.

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

- [SIMILAR: Submodular Information Measures Based Active Learning In Realistic Scenarios](https://mlsanity.com/paper/2107.00717/) (2021)
- [Submodularity In Machine Learning and Artificial Intelligence](https://mlsanity.com/paper/2202.00132/) (2022)
- [Q-Match: Iterative Shape Matching via Quantum Annealing](https://mlsanity.com/paper/2105.02878/) (2021)
- [TALISMAN: Targeted Active Learning for Object Detection with Rare Classes and Slices using Submodular Mutual Information](https://mlsanity.com/paper/2112.00166/) (2021)
- [Faster Unbalanced Optimal Transport: Translation invariant Sinkhorn and 1-D Frank-Wolfe](https://mlsanity.com/paper/2201.00730/) (2022)
- [Neural Set Function Extensions: Learning with Discrete Functions in High Dimensions](https://mlsanity.com/paper/2208.04055/) (2022)
- [A Unified Approach for Maximizing Continuous DR-submodular Functions](https://mlsanity.com/paper/2305.16671/) (2023)
- [Nearly Minimax Optimal Submodular Maximization with Bandit Feedback](https://mlsanity.com/paper/2310.18465/) (2023)
- [On the convex hull of convex quadratic optimization problems with indicators](https://mlsanity.com/paper/2201.00387/) (2022)
- [Online Submodular Maximization via Online Convex Optimization](https://mlsanity.com/paper/2309.04339/) (2023)
- [Adversarial Causal Bayesian Optimization](https://mlsanity.com/paper/2307.16625/) (2023)
- [Greedy Bayesian Posterior Approximation with Deep Ensembles](https://mlsanity.com/paper/2105.14275/) (2021)
- [PLATINUM: Semi-Supervised Model Agnostic Meta-Learning using Submodular Mutual Information](https://mlsanity.com/paper/2201.12928/) (2022)
- [Scalable Inference of Sparsely-changing Markov Random Fields with Strong Statistical Guarantees](https://mlsanity.com/paper/2102.03585/) (2021)
- [INGENIOUS: Using Informative Data Subsets for Efficient Pre-Training of Language Models](https://mlsanity.com/paper/2305.06677/) (2023)
- [A Convex Loss Function for Set Prediction with Optimal Trade-offs Between Size and Conditional Coverage](https://mlsanity.com/paper/2512.19142/) (2025)
- [Submodular Maximization via Taylor Series Approximation](https://mlsanity.com/paper/2101.07423/) (2021)
- [Joint Continuous and Discrete Model Selection via Submodularity](https://mlsanity.com/paper/2102.09029/) (2021)
- [Lifting the Convex Conjugate in Lagrangian Relaxations: A Tractable Approach for Continuous Markov Random Fields](https://mlsanity.com/paper/2107.06028/) (2021)
- [Randomized Algorithms for Monotone Submodular Function Maximization on the Integer Lattice](https://mlsanity.com/paper/2111.10175/) (2021)
- [Solution Path of Time-varying Markov Random Fields with Discrete Regularization](https://mlsanity.com/paper/2307.13750/) (2023)
- [Scalable Projection-Free Optimization](https://mlsanity.com/paper/2105.03527/) (2021)
- [Robust Sequence Networked Submodular Maximization](https://mlsanity.com/paper/2212.13725/) (2022)
- [Discrete and Continuous Difference of Submodular Minimization](https://mlsanity.com/paper/2506.07952/) (2025)
- [The Independence Prior of SAEs Fragments Visual Concepts](https://mlsanity.com/paper/2610.04112/) (2026)

## Abstract (arXiv)

Submodular set-functions have many applications in combinatorial optimization, as they can be minimized and approximately maximized in polynomial time. A key element in many of the algorithms and analyses is the possibility of extending the submodular set-function to a convex function, which opens up tools from convex optimization. Submodularity goes beyond set-functions and has naturally been considered for problems with multiple labels or for functions defined on continuous domains, where it corresponds essentially to cross second-derivatives being nonpositive. In this paper, we show that most results relating submodularity and convexity for set-functions can be extended to all submodular functions. In particular, (a) we naturally define a continuous extension in a set of probability measures, (b) show that the extension is convex if and only if the original function is submodular, (c) prove that the problem of minimizing a submodular function is equivalent to a typically non-smooth convex optimization problem, and (d) propose another convex optimization problem with better computational properties (e.g., a smooth dual problem). Most of these extensions from the set-function situation are obtained by drawing links with the theory of multi-marginal optimal transport, which provides also a new interpretation of existing results for set-functions. We then provide practical algorithms to minimize generic submodular functions on discrete domains, with associated convergence rates.