# Submodularity in Action: From Machine Learning to Signal Processing Applications

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Jun 2020.

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

- [SIMILAR: Submodular Information Measures Based Active Learning In Realistic Scenarios](https://mlsanity.com/paper/2107.00717/) (2021)
- [TALISMAN: Targeted Active Learning for Object Detection with Rare Classes and Slices using Submodular Mutual Information](https://mlsanity.com/paper/2112.00166/) (2021)
- [Submodular Reinforcement Learning](https://mlsanity.com/paper/2307.13372/) (2023)
- [Submodular + Concave](https://mlsanity.com/paper/2106.04769/) (2021)
- [PLATINUM: Semi-Supervised Model Agnostic Meta-Learning using Submodular Mutual Information](https://mlsanity.com/paper/2201.12928/) (2022)
- [The Power of Subsampling in Submodular Maximization](https://mlsanity.com/paper/2104.02772/) (2021)
- [Randomized Algorithms for Monotone Submodular Function Maximization on the Integer Lattice](https://mlsanity.com/paper/2111.10175/) (2021)
- [Deep Submodular Peripteral Networks](https://mlsanity.com/paper/2403.08199/) (2024)
- [Combinatorial optimization for low bit-width neural networks](https://mlsanity.com/paper/2206.02006/) (2022)
- [Revisiting Matching Pursuit: Beyond Approximate Submodularity](https://mlsanity.com/paper/2305.07782/) (2023)
- [GreedyML: A Parallel Algorithm for Maximizing Constrained Submodular Functions](https://mlsanity.com/paper/2403.10332/) (2024)
- [Incentivizing Time-Aware Fairness in Data Sharing](https://mlsanity.com/paper/2510.09240/) (2025)

## Abstract (arXiv)

Submodularity is a discrete domain functional property that can be interpreted as mimicking the role of the well-known convexity/concavity properties in the continuous domain. Submodular functions exhibit strong structure that lead to efficient optimization algorithms with provable near-optimality guarantees. These characteristics, namely, efficiency and provable performance bounds, are of particular interest for signal processing (SP) and machine learning (ML) practitioners as a variety of discrete optimization problems are encountered in a wide range of applications. Conventionally, two general approaches exist to solve discrete problems: (i) relaxation into the continuous domain to obtain an approximate solution, or (ii) development of a tailored algorithm that applies directly in the discrete domain. In both approaches, worst-case performance guarantees are often hard to establish. Furthermore, they are often complex, thus not practical for large-scale problems. In this paper, we show how certain scenarios lend themselves to exploiting submodularity so as to construct scalable solutions with provable worst-case performance guarantees. We introduce a variety of submodular-friendly applications, and elucidate the relation of submodularity to convexity and concavity which enables efficient optimization. With a mixture of theory and practice, we present different flavors of submodularity accompanying illustrative real-world case studies from modern SP and ML. In all cases, optimization algorithms are presented, along with hints on how optimality guarantees can be established.