Many critical challenges in modern machine learning boil down to a deceptively simple question: How do we choose the best subset of items from a massive pool?
Whether you are selecting a handful of representative images to train a data-efficient model, picking the most informative examples to prime a large language model prompt, or assembling a diverse team of neural networks for an ensemble, you face a combinatorial explosion. If you have a dataset of size $N$ and want to find the optimal subset of size $k$, an exhaustive search requires evaluating $\binom{N}{k}$ combinations—a task that quickly becomes computationally impossible.
Because finding the absolute best subset is typically NP-hard, we must rely on approximations. Remarkably, for a broad and vital class of objective functions, a simple greedy hill-climbing strategy—where you iteratively pick the single next-best item—is guaranteed to find a solution that is remarkably close to the global optimum.
To understand why this simple strategy works so well, we have to look at the mathematical property of submodularity.
The Intuition of Diminishing Returns
Submodularity is the discrete analogue of concavity. It formalizes the common real-world phenomenon of diminishing returns: adding an item to a small set provides a greater marginal benefit than adding that same item to a larger set.
Mathematically, let $f$ be a set function that maps a subset of items to a real number representing its utility or quality. The function $f$ is submodular if, for any two sets $A$ and $B$ where $A \subseteq B$, and for any new item $x \notin B$:
$$f(A \cup \{x\}) - f(A) \ge f(B \cup \{x\}) - f(B)$$
Imagine you are building a summary of a dataset to explain a model's behavior, as explored by Been Kim and Oluwasanmi O Koyejo in Examples are not enough, learn to criticize! Criticism for Interpretability. If your current summary ($A$) is empty or very small, adding a new prototypical data point $x$ introduces a massive amount of novel information. However, if your summary ($B$) already contains hundreds of examples covering most of the dataset's variations, adding that same data point $x$ yields very little new insight. The marginal utility of $x$ has diminished.
Why the Greedy Strategy Works: The $1 - 1/e$ Bound
The classic greedy algorithm starts with an empty set $S_0 = \emptyset$. At each step $i$, it scans all remaining items and selects the item $e_i$ that maximizes the immediate marginal gain:
$$e_i = \arg\max_{e} \left[ f(S_{i-1} \cup \{e\}) - f(S_{i-1}) \right]$$
It repeats this until it has collected $k$ items.
Why does this short-sighted, myopic strategy guarantee a high-quality global solution? In a foundational piece of discrete optimization, David Kempe and Éva Tardos demonstrated in Maximizing the spread of influence through a social network that for monotone submodular functions, the greedy algorithm is guaranteed to capture at least $(1 - 1/e) \approx 63.2\%$ of the optimal subset's total value.
To build intuition for why this bound holds, let $S^*$ be the true, globally optimal subset of size $k$ that we wish we could find. At any step $i$, our current greedy subset is $S_{i-1}$. If we were to add all $k$ elements of the optimal set $S^*$ to our current set, the total value could at most grow to the optimal value $f(S^*)$. Therefore, the total remaining value left on the table is at most $f(S^*) - f(S_{i-1})$.
By the property of submodularity, the combined marginal contributions of the $k$ elements in $S^*$ must be at least as large as this total remaining value:
$$\sum_{e \in S^*} \left[ f(S_{i-1} \cup \{e\}) - f(S_{i-1}) \right] \ge f(S^*) - f(S_{i-1})$$
If $k$ different elements together contribute at least $f(S^*) - f(S_{i-1})$, then by the pigeonhole principle, at least one single element in $S^*$ must contribute at least the average share:
$$\max_{e} \left[ f(S_{i-1} \cup \{e\}) - f(S_{i-1}) \right] \ge \frac{1}{k} \left[ f(S^*) - f(S_{i-1}) \right]$$
Because our greedy algorithm explicitly searches for and picks the element with the absolute maximum marginal gain, its choice at step $i$ is guaranteed to do at least this well:
$$f(S_i) - f(S_{i-1}) \ge \frac{1}{k} \left[ f(S^*) - f(S_{i-1}) \right]$$
If we track the "error" or distance to the optimum, $R_i = f(S^*) - f(S_i)$, this inequality implies that each greedy step shrinks the remaining error by a factor of at least $(1 - 1/k)$:
$$R_i \le \left(1 - \frac{1}{k}\right) R_{i-1}$$
Unrolling this recurrence over $k$ steps starting from an empty set ($R_0 = f(S^*)$), we find:
$$R_k \le \left(1 - \frac{1}{k}\right)^k f(S^*)$$
Using the standard calculus identity $(1 - 1/k)^k \le 1/e$, the remaining error after $k$ steps is bounded by $\frac{1}{e} f(S^*)$. Converting this back into the value achieved by our greedy set:
$$f(S_k) \ge \left(1 - \frac{1}{e}\right) f(S^*)$$
This elegant guarantee turns an otherwise intractable combinatorial search into a fast, predictable, and highly effective tool.
Applications Across Modern Machine Learning
Researchers leverage this mathematical guarantee across a wide variety of domains to solve complex subset selection problems.
Data Pruning and Coresets
As deep learning datasets grow into the terabytes, training models becomes incredibly expensive. Researchers use submodular optimization to extract a "coreset"—a small, highly representative subset of data that yields the same performance as the full dataset.
For instance, Baharan Mirzasoleiman et al. showed that matching the gradient of a full dataset can be framed as a submodular facility location problem, allowing a greedy algorithm to drastically accelerate training. Similarly, Siddharth Joshi et al. applied double-greedy submodular maximization to scale contrastive language-image pretraining (CLIP) to millions of samples with strict quality guarantees. In semi-supervised learning, Krishnateja Killamsetty et al. utilized approximate submodularity to select clean, informative subsets from noisy, unlabeled data pools.
Prompt Engineering and In-Context Learning
Large language models are highly sensitive to the few-shot demonstrations included in their prompts. Finding the ideal combination of examples is an NP-hard problem.
To address this, Shuaimin Li et al. framed example mining for data visualization as a submodular function maximization, using a greedy search to assemble diverse and informative prompt contexts. In a similar vein, Soumya Suvra Ghosal et al. proved that information-theoretic exemplar selection exhibits approximate submodularity, justifying a highly efficient greedy retrieval mechanism that scales gracefully to massive demonstration pools.
Diversity and Coverage in Retrieval
When answering ambiguous questions or generating creative content, a system must provide a diverse set of outputs rather than variations of the same answer.
Poojitha Nandigam et al. utilized greedy inference over Determinantal Point Processes (DPPs) to retrieve diverse, multi-answer passages for open-domain question answering. In text generation, Vinayak Puranik et al. optimized a submodular objective function via a greedy hill-climbing algorithm to balance diversity and fidelity when generating questions from web articles.
Conclusion
The power of submodular greedy optimization lies in its ability to bridge the gap between theoretical rigor and practical scalability. By recognizing the property of diminishing returns within an objective function, we can confidently replace exhaustive combinatorial searches with simple, iterative choices—secure in the mathematical certainty that our fast approximation will land remarkably close to the global optimum.