Submodular Subset Selection for Machine Learning

This direction is merged into another direction: greedy approximation guarantees. Its last version stays readable and citable here.

Version 1 of 1420 papers494 conceptsfrozen 2026-10-04

In many machine learning tasks, we are faced with a daunting combinatorial challenge: selecting the "best" subset of items from a massive pool. Whether we are picking the most representative images to explain a model's behavior, the most informative examples to train a program synthesizer, or the most diverse set of search results, the number of possible combinations grows exponentially with the size of the pool. Finding the absolute best subset is typically NP-hard.

However, a wide range of these problems share a mathematical property called submodularity. This property, often described as the "law of diminishing returns," allows us to use simple greedy algorithms to find solutions that are provably close to the theoretical optimum.

The Intuition of Diminishing Returns

A set function $f$ is submodular if adding an element to a small set provides more (or equal) marginal benefit than adding that same element to a larger set. Formally, for sets $A \subseteq B$, the marginal gain $f(A \cup \{x\}) - f(A) \geq f(B \cup \{x\}) - f(B)$.

This property is intuitive in many contexts:

  • Summarization: Adding a sentence about "climate change" to a short summary adds a lot of new information. Adding it to a 50-page report on the same topic adds very little.
  • Coverage: In BenTo, Hongyu Zhao and colleagues reduce LLM benchmarks by treating task selection as a facility location problem. Once a specific type of logic task is "covered" by a representative, adding more similar tasks provides diminishing utility for evaluating the model.
  • Interpretability: When Ruoyu Chen identifies important regions in an image to explain a classification, the first few pixels chosen provide the most "confidence" boost; subsequent pixels often just reinforce what is already known.

Why Greedy Selection Works

Because of submodularity, we don't need to check every possible combination. A greedy algorithm—which simply picks the best available item at each step—is remarkably effective. For monotone submodular functions, this greedy approach is guaranteed to capture at least $(1 - 1/e) \approx 63\%$ of the optimal value.

This guarantee has transformed heuristic-based fields into principled ones. For example, Linxiao Yang and L. Sun frame learning interpretable decision rule sets as a submodular optimization problem, moving away from ad-hoc search toward algorithms with rigorous performance bounds. Similarly, in E-LDA, researchers replace traditional heuristic samplers for topic modeling with a combinatorial framework that provides a guaranteed approximation of the optimal posterior probability.

Applications Across the Pipeline

The power of submodular selection is its versatility across different stages of the machine learning lifecycle.

1. Data and Benchmark Pruning

In program synthesis, Yewen Pu and Armando Solar-Lezama show that selecting a small, representative subset of input-output examples can maximally prune the search space. Because the constraints exhibit submodularity, a greedy selection finds a near-optimal set of examples that represents the full search space with minimal computational overhead.

2. Model Interpretability

Explaining "black box" models often requires finding a small set of representative examples or rules. Stratis Tsirtsis and Manuel Gomez Rodriguez use submodular optimization to select optimal sets of counterfactual explanations that incentivize users to improve their features. In the domain of Graph Neural Networks, Mert Kosan and Sourav Medya use similar logic to maximize dataset coverage with a fixed number of representative counterfactuals.

3. Diversity and Information Retrieval

Standard ranking algorithms often return redundant results. Yisong Yue and Thorsten Joachims addressed this by predicting diverse subsets that maximize "word coverage." By treating diversity as a submodular objective, they ensure that each added document covers new subtopics, rather than repeating what the user has already seen.

Beyond Simple Submodularity

While the basic monotone submodular case is well-understood, recent work has pushed into more complex territory:

  • Non-monotone Functions: In BETA, Himabindu Lakkaraju and colleagues handle cases where adding an item might actually decrease the objective (e.g., adding a rule that makes an explanation too long to read). They use approximate local search to maintain guarantees even without monotonicity.
  • Weak Submodularity: Piyushi Manupriya and Pratik Jawanpuria demonstrate that optimal transport objectives exhibit "weak submodularity," allowing greedy algorithms to find sparse solutions in otherwise non-convex landscapes.
  • Multi-objective Optimization: Zhiyang Chen and Xia Yin proved that the Pareto volume (hypervolume) used to evaluate multi-objective solutions is submodular. This allows for the greedy selection of algorithm configurations that maximize the overall quality of the solution set.

By framing subset selection as the optimization of a submodular function, researchers have turned "needle-in-a-haystack" problems into structured tasks where simple, greedy choices lead to mathematically robust results.

Papers in this version

Showing 60 of 420 papers.

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_submodular_subset_selection_for_machine__43e9a5ff,
  title = {Submodular Subset Selection for Machine Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/submodular-subset-selection-for-machine-learning/rdr_43e9a5ffd9874209a4ef1100323409ee},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_submodular_subset_selection_for_machine__43e9a5ff_v1,
  title = {Submodular Subset Selection for Machine Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/submodular-subset-selection-for-machine-learning/rdr_43e9a5ffd9874209a4ef1100323409ee/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}