# Submodularity In Machine Learning and Artificial Intelligence

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

## Key facts

- Cited by 38 papers in the map (data through 14 Oct 2026).
- Builds on 67 of its 261 references that are in the map.
- First posted on arXiv 31 Jan 2022.

## Builds on (most cited first, 30 of 67)

- [Distilling the Knowledge in a Neural Network](https://mlsanity.com/paper/1503.02531/) (2015)
- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- [Deep Leakage from Gradients](https://mlsanity.com/paper/1906.08935/) (2019)
- [Adversarial Examples Are Not Bugs, They Are Features](https://mlsanity.com/paper/1905.02175/) (2019)
- [On Faithfulness and Factuality in Abstractive Summarization](https://mlsanity.com/paper/2005.00661/) (2020)
- [Deep Batch Active Learning by Diverse, Uncertain Gradient Lower Bounds](https://mlsanity.com/paper/1906.03671/) (2019)
- [Evaluating the Factual Consistency of Abstractive Text Summarization](https://mlsanity.com/paper/1910.12840/) (2019)
- [Dataset Condensation with Gradient Matching](https://mlsanity.com/paper/2006.05929/) (2020)
- [Do Deep Nets Really Need to be Deep?](https://mlsanity.com/paper/1312.6184/) (2013)
- [BatchBALD: Efficient and Diverse Batch Acquisition for Deep Bayesian Active Learning](https://mlsanity.com/paper/1906.08158/) (2019)
- [Dreaming to Distill: Data-free Knowledge Transfer via DeepInversion](https://mlsanity.com/paper/1912.08795/) (2019)
- [Generating Wikipedia by Summarizing Long Sequences](https://mlsanity.com/paper/1801.10198/) (2018)
- [FEQA: A Question Answering Evaluation Framework for Faithfulness Assessment in Abstractive Summarization](https://mlsanity.com/paper/2005.03754/) (2020)
- [Dataset Condensation with Differentiable Siamese Augmentation](https://mlsanity.com/paper/2102.08259/) (2021)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Dataset Meta-Learning from Kernel Ridge-Regression](https://mlsanity.com/paper/2011.00050/) (2020)
- [GLISTER: Generalization based Data Subset Selection for Efficient and Robust Learning](https://mlsanity.com/paper/2012.10630/) (2020)
- [Dataset Distillation with Infinitely Wide Convolutional Networks](https://mlsanity.com/paper/2107.13034/) (2021)
- [Evaluating Gradient Inversion Attacks and Defenses in Federated Learning](https://mlsanity.com/paper/2112.00059/) (2021)
- [Coresets via Bilevel Optimization for Continual Learning and Streaming](https://mlsanity.com/paper/2006.03875/) (2020)
- [Bottom-Up Abstractive Summarization](https://mlsanity.com/paper/1808.10792/) (2018)
- [Soft-Label Dataset Distillation and Text Dataset Distillation](https://mlsanity.com/paper/1910.02551/) (2019)
- [Generative Teaching Networks: Accelerating Neural Architecture Search by Learning to Generate Synthetic Training Data](https://mlsanity.com/paper/1912.07768/) (2019)
- [Flexible Dataset Distillation: Learn Labels Instead of Images](https://mlsanity.com/paper/2006.08572/) (2020)
- [Submodular Combinatorial Information Measures with Applications in Machine Learning](https://mlsanity.com/paper/2006.15412/) (2020)
- [On Extractive and Abstractive Neural Document Summarization with Transformer Language Models](https://mlsanity.com/paper/1909.03186/) (2019)
- [What Have We Achieved on Text Summarization?](https://mlsanity.com/paper/2010.04529/) (2020)
- [Learning From Less Data: A Unified Data Subset Selection and Active Learning Framework for Computer Vision](https://mlsanity.com/paper/1901.01151/) (2019)
- [PRISM: A Rich Class of Parameterized Submodular Information Measures for Guided Subset Selection](https://mlsanity.com/paper/2103.00128/) (2021)
- [A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization](https://mlsanity.com/paper/1508.04874/) (2015)

## Built on by (most cited first, 30 of 38)

- [MetaMath: Bootstrap Your Own Mathematical Questions for Large Language Models](https://mlsanity.com/paper/2309.12284/) (2023)
- [Data Distillation: A Survey](https://mlsanity.com/paper/2301.04272/) (2023)
- [CultureLLM: Incorporating Cultural Differences into Large Language Models](https://mlsanity.com/paper/2402.10946/) (2024)
- [Weight Ensembling Improves Reasoning in Language Models](https://mlsanity.com/paper/2504.10478/) (2025)
- [A Formal Perspective on Byte-Pair Encoding](https://mlsanity.com/paper/2306.16837/) (2023)
- [CulturePark: Boosting Cross-cultural Understanding in Large Language Models](https://mlsanity.com/paper/2405.15145/) (2024)
- [Submodular Reinforcement Learning](https://mlsanity.com/paper/2307.13372/) (2023)
- [Infinite Recommendation Networks: A Data-Centric Approach](https://mlsanity.com/paper/2206.02626/) (2022)
- [Global Reinforcement Learning: Beyond Linear and Convex Rewards via Submodular Semi-gradient Methods](https://mlsanity.com/paper/2407.09905/) (2024)
- [Neural Set Function Extensions: Learning with Discrete Functions in High Dimensions](https://mlsanity.com/paper/2208.04055/) (2022)
- [COMI: Coarse-to-fine Context Compression via Marginal Information Gain](https://mlsanity.com/paper/2602.01719/) (2026)
- [Near-Optimal Multi-Agent Learning for Safe Coverage Control](https://mlsanity.com/paper/2210.06380/) (2022)
- [Sequential Attention for Feature Selection](https://mlsanity.com/paper/2209.14881/) (2022)
- [Accelerating Batch Active Learning Using Continual Learning Techniques](https://mlsanity.com/paper/2305.06408/) (2023)
- [Cluster-aware Semi-supervised Learning: Relational Knowledge Distillation Provably Learns Clustering](https://mlsanity.com/paper/2307.11030/) (2023)
- [Measuring Diversity: Axioms and Challenges](https://mlsanity.com/paper/2410.14556/) (2024)
- [Online Submodular Coordination with Bounded Tracking Regret: Theory, Algorithm, and Applications to Multi-Robot Coordination](https://mlsanity.com/paper/2209.12429/) (2022)
- [Looking Beyond the Known: Towards a Data Discovery Guided Open-World Object Detection](https://mlsanity.com/paper/2510.00303/) (2025)
- [Farzi Data: Autoregressive Data Distillation](https://mlsanity.com/paper/2310.09983/) (2023)
- [Exploration with Principles for Diverse AI Supervision](https://mlsanity.com/paper/2310.08899/) (2023)
- [FedCore: Straggler-Free Federated Learning with Distributed Coresets](https://mlsanity.com/paper/2402.00219/) (2024)
- [Communication- and Computation-Efficient Distributed Submodular Optimization in Robot Mesh Networks](https://mlsanity.com/paper/2407.10382/) (2024)
- [COBRA: COmBinatorial Retrieval Augmentation for Few-Shot Adaptation](https://mlsanity.com/paper/2412.17684/) (2024)
- [Prompting Test-Time Scaling Is A Strong LLM Reasoning Data Augmentation](https://mlsanity.com/paper/2510.09599/) (2025)
- [Classroom AI: Large Language Models as Grade-Specific Teachers](https://mlsanity.com/paper/2601.06225/) (2026)
- [Theoretical Analysis of Submodular Information Measures for Targeted Data Subset Selection](https://mlsanity.com/paper/2402.13454/) (2024)
- [STONE: A Submodular Optimization Framework for Active 3D Object Detection](https://mlsanity.com/paper/2410.03918/) (2024)
- [MentalArena: Self-play Training of Language Models for Diagnosis and Treatment of Mental Health Disorders](https://mlsanity.com/paper/2410.06845/) (2024)
- [Unifying and Optimizing Data Values for Selection via Sequential Decision-Making](https://mlsanity.com/paper/2502.04554/) (2025)
- [DiRe: Diversity-promoting Regularization for Dataset Condensation](https://mlsanity.com/paper/2512.13083/) (2025)

## Abstract (arXiv)

In this manuscript, we offer a gentle review of submodularity and supermodularity and their properties. We offer a plethora of submodular definitions; a full description of a number of example submodular functions and their generalizations; example discrete constraints; a discussion of basic algorithms for maximization, minimization, and other operations; a brief overview of continuous submodular extensions; and some historical applications. We then turn to how submodularity is useful in machine learning and artificial intelligence. This includes summarization, and we offer a complete account of the differences between and commonalities amongst sketching, coresets, extractive and abstractive summarization in NLP, data distillation and condensation, and data subset selection and feature selection. We discuss a variety of ways to produce a submodular function useful for machine learning, including heuristic hand-crafting, learning or approximately learning a submodular function or aspects thereof, and some advantages of the use of a submodular function as a coreset producer. We discuss submodular combinatorial information functions, and how submodularity is useful for clustering, data partitioning, parallel machine learning, active and semi-supervised learning, probabilistic modeling, and structured norms and loss functions.