Submodular Optimization for Diverse Subset Selection

206 concepts127 papers2 proposals

In many machine learning tasks, the goal is to select a small subset of items from a massive pool—whether they are search results, training samples, or reasoning steps. A naive approach might simply pick the "best" individual items. However, as Streeter et al. argue, this fails to account for redundancy: the total value of a list is rarely just the sum of its parts. If the top three search results all provide the same information, the second and third results add almost no value to the user.

To solve this, researchers have turned to submodular optimization, a mathematical framework that formalizes the intuitive principle of diminishing returns. By modeling selection as a submodular problem, we can naturally incentivize diversity and coverage without needing complex, manual heuristics.

The Law of Diminishing Returns

At the heart of this research direction is the submodular set function. A function $f$ is submodular if, for any two sets $A \subseteq B$ and an item $x$, the marginal gain of adding $x$ to the smaller set is at least as large as the marginal gain of adding it to the larger set:

$$f(A \cup \{x\}) - f(A) \geq f(B \cup \{x\}) - f(B)$$

This property mathematically captures the "law of diminishing returns." As El-Arini et al. explain, this ensures that as more items are selected, the utility of adding a similar item decreases. This eliminates the need for explicit redundancy penalties; the math itself makes redundant items less attractive to the selection algorithm.

Modeling Diversity as Coverage

How do we actually build a submodular function that "prefers" diversity? Two common strategies emerge across the literature:

  1. Coverage Functions: These functions reward the selection of items that "cover" new ground. For example, in document summarization, Lin et al. and Nenkova et al. use submodular functions to ensure a summary covers a broad spectrum of viewpoints rather than clustering around a single dominant theme. Similarly, Sun et al. use coverage to select diverse object proposals in computer vision.
  2. Concave Transformations: Another powerful technique involves partitioning items into clusters and applying a concave reward function (like a square root) to the number of items chosen from each cluster. As Lin et al. and the authors of SWAP demonstrate, because the marginal gain of a concave function decreases as its input grows, the system naturally prioritizes the first item from an unrepresented cluster over the tenth item from a cluster that is already well-represented.

This approach is highly flexible. It has been used to select diverse synthetic styles for domain generalization (Kang et al.), identify unique visual attributes for zero-shot learning (CVPR 2017), and even discover disentangled "knobs" for image editing in GANs (Simsar et al.).

The Efficiency of Greedy Selection

One of the most compelling reasons to use submodular functions is that they are remarkably easy to optimize. While finding the absolute best subset is often NP-hard, a simple greedy algorithm—which repeatedly picks the item with the highest marginal gain—is guaranteed to be near-optimal.

Krause et al. proved that for many submodular problems, this greedy strategy is nearly as effective as the best possible batch policy. This theoretical guarantee, often reaching the $1 - 1/e$ (approx. 63%) "golden barrier" of the optimal solution, provides a rigorous foundation for applications ranging from active learning to phrase table pruning in machine translation (Suzuki et al.).

A Universal Tool for Modern AI

As AI models grow more complex, the need for diverse selection has expanded into new frontiers:

  • Reinforcement Learning: Fang et al. use submodular facility location functions to sample a diverse set of "failed" trajectories, preventing agents from overfitting to redundant experiences.
  • Large Language Models: In complex reasoning tasks, Zhao et al. use submodular optimization to select a diverse set of "next steps," ensuring the model explores distinct logical paths rather than getting stuck in a repetitive loop.
  • Data Condensation: To speed up training on massive graphs, Liang et al. use submodular functions to select a condensed set of nodes that captures the full structural and semantic diversity of the original data.

By treating diversity not as a vague heuristic but as a formal optimization objective, this research direction provides a robust, scalable way to manage the "noise" of big data and the complexity of modern generative models. As Vanchinathan et al. note, increasing diversity often results in a negligible loss of total utility, suggesting that in the quest for the best information, variety is not just a luxury—it is a mathematical necessity.

Key Foundational Work

Turning down the noise in the blogosphere (2009) — contributed 2 concept elements to this direction.
Online Learning of Assignments that Maximize Submodular Functions (2009) — contributed 2 concept elements to this direction.
Online Learning of Assignments (2009) — contributed 2 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 133 papers
  2. Version 1 · 2026-10-04 · 143 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_submodular_diversity_optimization_82b44010,
  title = {submodular diversity optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/submodular-diversity-optimization/rdr_82b44010991f490ba8b374d9fbc91410},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_submodular_diversity_optimization_82b44010_v2,
  title = {submodular diversity optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/submodular-diversity-optimization/rdr_82b44010991f490ba8b374d9fbc91410/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake