# Submodular Combinatorial Information Measures with Applications in Machine Learning

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

## Key facts

- Cited by 88 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Jun 2020.

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

- [DeepCore: A Comprehensive Library for Coreset Selection in Deep Learning](https://mlsanity.com/paper/2204.08499/) (2022)
- [InfoBatch: Lossless Training Speed Up by Unbiased Dynamic Data Pruning](https://mlsanity.com/paper/2303.04947/) (2023)
- [SIMILAR: Submodular Information Measures Based Active Learning In Realistic Scenarios](https://mlsanity.com/paper/2107.00717/) (2021)
- [PRISM: A Rich Class of Parameterized Submodular Information Measures for Guided Subset Selection](https://mlsanity.com/paper/2103.00128/) (2021)
- [Dataset Quantization](https://mlsanity.com/paper/2308.10524/) (2023)
- [Submodularity In Machine Learning and Artificial Intelligence](https://mlsanity.com/paper/2202.00132/) (2022)
- [Effective Evaluation of Deep Active Learning on Image Classification Tasks](https://mlsanity.com/paper/2106.15324/) (2021)
- [Unifying Approaches in Active Learning and Active Sampling via Fisher Information and Information-Theoretic Quantities](https://mlsanity.com/paper/2208.00549/) (2022)
- [A Coreset Selection of Coreset Selection Literature: Introduction and Recent Advances](https://mlsanity.com/paper/2505.17799/) (2025)
- [TALISMAN: Targeted Active Learning for Object Detection with Rare Classes and Slices using Submodular Mutual Information](https://mlsanity.com/paper/2112.00166/) (2021)
- [Repeated Random Sampling for Minimizing the Time-to-Accuracy of Learning](https://mlsanity.com/paper/2305.18424/) (2023)
- [SCOPE: Saliency-Coverage Oriented Token Pruning for Efficient Multimodel LLMs](https://mlsanity.com/paper/2510.24214/) (2025)
- [A CLIP-Powered Framework for Robust and Generalizable Data Selection](https://mlsanity.com/paper/2410.11215/) (2024)
- [SHED: Shapley-Based Automated Dataset Refinement for Instruction Fine-Tuning](https://mlsanity.com/paper/2405.00705/) (2024)
- [Coreset Selection for Object Detection](https://mlsanity.com/paper/2404.09161/) (2024)
- [CodeACT: Code Adaptive Compute-efficient Tuning Framework for Code LLMs](https://mlsanity.com/paper/2408.02193/) (2024)
- [Active Learning in Bayesian Neural Networks with Balanced Entropy Learning Principle](https://mlsanity.com/paper/2105.14559/) (2021)
- [DELIFT: Data Efficient Language model Instruction Fine Tuning](https://mlsanity.com/paper/2411.04425/) (2024)
- [Dataset Quantization with Active Learning based Adaptive Sampling](https://mlsanity.com/paper/2407.07268/) (2024)
- [CLINICAL: Targeted Active Learning for Imbalanced Medical Image Classification](https://mlsanity.com/paper/2210.01520/) (2022)
- [Distilling Long-tailed Datasets](https://mlsanity.com/paper/2408.14506/) (2024)
- [Adaptive Dataset Quantization](https://mlsanity.com/paper/2412.16895/) (2024)
- [Submodular Mutual Information for Targeted Data Subset Selection](https://mlsanity.com/paper/2105.00043/) (2021)
- [Submodlib: A Submodular Optimization Library](https://mlsanity.com/paper/2202.10680/) (2022)
- [Dataset Distillation in Latent Space](https://mlsanity.com/paper/2311.15547/) (2023)
- [Active Data Discovery: Mining Unknown Data using Submodular Information Measures](https://mlsanity.com/paper/2206.08566/) (2022)
- [Neural Estimation of Submodular Functions with Applications to Differentiable Subset Selection](https://mlsanity.com/paper/2210.11033/) (2022)
- [Color-Oriented Redundancy Reduction in Dataset Distillation](https://mlsanity.com/paper/2411.11329/) (2024)
- [Contributing Dimension Structure of Deep Feature for Coreset Selection](https://mlsanity.com/paper/2401.16193/) (2024)
- [Automatic Combination of Sample Selection Strategies for Few-Shot Learning](https://mlsanity.com/paper/2402.03038/) (2024)

## Abstract (arXiv)

Information-theoretic quantities like entropy and mutual information have found numerous uses in machine learning. It is well known that there is a strong connection between these entropic quantities and submodularity since entropy over a set of random variables is submodular. In this paper, we study combinatorial information measures that generalize independence, (conditional) entropy, (conditional) mutual information, and total correlation defined over sets of (not necessarily random) variables. These measures strictly generalize the corresponding entropic measures since they are all parameterized via submodular functions that themselves strictly generalize entropy. Critically, we show that, unlike entropic mutual information in general, the submodular mutual information is actually submodular in one argument, holding the other fixed, for a large class of submodular functions whose third-order partial derivatives satisfy a non-negativity property. This turns out to include a number of practically useful cases such as the facility location and set-cover functions. We study specific instantiations of the submodular information measures on these, as well as the probabilistic coverage, graph-cut, and saturated coverage functions, and see that they all have mathematically intuitive and practically useful expressions. Regarding applications, we connect the maximization of submodular (conditional) mutual information to problems such as mutual-information-based, query-based, and privacy-preserving summarization -- and we connect optimizing the multi-set submodular mutual information to clustering and robust partitioning.