In machine learning and natural language processing, we often operate under the assumption that more data equals better performance. However, as datasets scale into millions or billions of samples, we quickly encounter the law of diminishing returns. Adding more data points does not scale performance linearly; instead, it introduces redundancy, increases computational costs, and dilutes high-quality signals.
To solve this, we need to select a representative subset of data. But traditional methods fail because they evaluate data points in isolation. For instance, an uncertainty-based active learning strategy might select 1,000 highly uncertain images that happen to be nearly identical copies of each other. As Soumi Das et al. argue in Finding High-Value Training Data Subset through Differentiable Convex Programming, effective data selection requires subset-aware valuation—a framework that judges a data point's utility based on what has already been chosen.
Submodular optimization provides the mathematical foundation for this subset-aware valuation, formalizing the concept of diminishing returns into a rigorous framework.
The Mathematics of Diminishing Returns
Consider a ground set of all available data points $V$. A set function $f: 2^V \to \mathbb{R}$ maps any subset of data to a real number representing its utility or information coverage.
The function $f$ is submodular if, for any two subsets $A$ and $B$ where $A \subseteq B$, and for any new element $x \notin B$:
$$f(A \cup \{x\}) - f(A) \ge f(B \cup \{x\}) - f(B)$$
In plain English: the marginal gain of adding $x$ to a smaller set $A$ is greater than or equal to the marginal gain of adding it to a larger, more comprehensive set $B$. If the system already contains a wealth of information (set $B$), a new piece of data $x$ is less valuable than if the system knew very little (set $A$).
Why It Works: The Greedy Guarantee
Finding the absolute best subset of size $k$ from a massive pool is an NP-hard combinatorial problem. However, submodularity unlocks a powerful algorithmic shortcut. As highlighted by Hui Lin et al. in Multi-document Summarization via Budgeted Maximization of Submodular Functions, a simple greedy algorithm provides a near-optimal solution.
The greedy algorithm starts with an empty set and iteratively adds the single element $x$ that maximizes the current marginal gain $f(A \cup \{x\}) - f(A)$. Because of the submodular property, this straightforward approach is mathematically guaranteed to achieve a solution within $(1 - 1/e) \approx 63.2\%$ of the global optimum.
Open-source toolkits like apricot, introduced by Jacob M. Schreiber et al. in apricot: Submodular selection for data summarization in Python, leverage these algorithmic speedups to make submodular selection practical for massive, real-world datasets.
Balancing Coverage and Diversity
Submodular functions naturally balance representing the entire dataset (coverage) while avoiding duplicates (diversity).
Consider a classic submodular function family: Facility Location. This function models the distance from every unselected data point to its nearest representative in the selected subset. Maximizing a Facility Location function forces the greedy algorithm to pick "anchors" that are centrally located within clusters of data. Once a cluster has an anchor, adding another point from the same cluster yields almost zero marginal gain, naturally pushing the algorithm to explore unrepresented regions of the data space.
As Akshat Gautam et al. demonstrate in INSITE: labelling medical images using submodular functions and semi-supervised data programming, using functions like Facility Location and Log Determinant allows experts to label a tiny, highly diverse fraction of a dataset (e.g., 10–30 images) while maintaining high downstream accuracy across thousands of unlabelled images.
Targeted Selection via Submodular Mutual Information
Standard submodular functions evaluate a dataset in a vacuum. But what if you have a specific target domain, or want to actively mine for rare edge cases?
This is where Submodular Mutual Information (SMI) comes in. SMI functions measure the information shared between an unlabelled subset and a specific query or target set.
- Active Learning for Rare Slices: In Talisman: Targeted Active Learning for Object Detection with Rare Classes and Slices Using Submodular Mutual Information, Suraj Nandkishor Kothawade et al. use SMI to discover rare visual concepts (like a bicycle at night). Once one example is found, the submodular property ensures the system prioritizes different variations of that rare slice rather than flooding the training set with redundant copies.
- Distribution Shift: Similarly, Athresh Karanam et al. introduce ORIENT in ORIENT: Submodular Mutual Information Measures for Data Subset Selection under Distribution Shift, using SMI to select source data that is both internally diverse and highly relevant to a shifted target domain.
From Document Summarization to Large Language Models
The core mechanics of submodular selection have proven remarkably versatile, evolving across decades of AI research:
- Text and Speech Summarization: Early applications focused on extractive text summarization (Ani Nenkova et al. in Automatic Summarization; Lu Wang et al. in Query-Focused Opinion Summarization for User-Generated Content). Kai Wei et al. then adapted these exact techniques to acoustic data in Using Document Summarization Techniques for Speech Data Subset Selection, treating speech utterances like sentences to optimize training budgets.
- Instruction Tuning and LLMs: Today, the framework is critical for pruning massive instruction-tuning datasets. In SMART: Submodular Data Mixture Strategy for Instruction Tuning, H. S. V. N. S. Kowndinya Renduchintala shows that mathematically pruning instruction mixtures consistently outperforms manual heuristics. Furthermore, Yicheng Chen et al. demonstrate in MIG: Automatic Data Selection for Instruction Tuning by Maximizing Information Gain in Semantic Space that maximizing information gain over a semantic graph allows models to achieve full-dataset performance using just 5% of the data.
By formalizing the intuitive concept of diminishing returns into a rigorous mathematical framework, submodular optimization transforms data selection from an ad-hoc guessing game into a predictable, highly efficient optimization pipeline.
Key Foundational Work
Automatic Summarization (2011) — contributed 1 concept elements to this direction.
Multi-document Summarization via Budgeted Maximization of Submodular Functions (2010) — contributed 1 concept elements to this direction.