mlsanityData to 7 Oct 2026

Submodular Combinatorial Information Measures with Applications in Machine Learning

arXiv 2006.15412 ↗First posted 27 Jun 2020cs.LG cs.DS cs.ITcited by 88

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 6; 2022: 12; 2023: 10; 2024: 24; 2025: 18; 2026: 18.

88 papers.

Sort:

By area:

  1. 2022DeepCore: A Comprehensive Library for Coreset Selection in Deep Learningcited by 146
  2. 2023InfoBatch: Lossless Training Speed Up by Unbiased Dynamic Data Pruningcited by 90
  3. 2021SIMILAR: Submodular Information Measures Based Active Learning In Realistic Scenarioscited by 83
  4. 2021PRISM: A Rich Class of Parameterized Submodular Information Measures for Guided Subset Selectioncited by 50
  5. 2023Dataset Quantizationcited by 47
  6. 2021Effective Evaluation of Deep Active Learning on Image Classification Taskscited by 37
  7. 2022Submodularity In Machine Learning and Artificial Intelligencecited by 37
  8. 2022Unifying Approaches in Active Learning and Active Sampling via Fisher Information and Information-Theoretic Quantitiescited by 28
  9. 2025A Coreset Selection of Coreset Selection Literature: Introduction and Recent Advancescited by 28
  10. 2021TALISMAN: Targeted Active Learning for Object Detection with Rare Classes and Slices using Submodular Mutual Informationcited by 27
  11. 2023Repeated Random Sampling for Minimizing the Time-to-Accuracy of Learningcited by 26
  12. 2025SCOPE: Saliency-Coverage Oriented Token Pruning for Efficient Multimodel LLMscited by 23
38 more
  1. 2024A CLIP-Powered Framework for Robust and Generalizable Data Selectioncited by 20
  2. 2024SHED: Shapley-Based Automated Dataset Refinement for Instruction Fine-Tuningcited by 19
  3. 2024Coreset Selection for Object Detectioncited by 18
  4. 2024CodeACT: Code Adaptive Compute-efficient Tuning Framework for Code LLMscited by 15
  5. 2021Active Learning in Bayesian Neural Networks with Balanced Entropy Learning Principlecited by 14
  6. 2024DELIFT: Data Efficient Language model Instruction Fine Tuningcited by 14
  7. 2024Dataset Quantization with Active Learning based Adaptive Samplingcited by 13
  8. 2022CLINICAL: Targeted Active Learning for Imbalanced Medical Image Classificationcited by 9
  9. 2024Distilling Long-tailed Datasetscited by 9
  10. 2024Adaptive Dataset Quantizationcited by 9
  11. 2021Submodular Mutual Information for Targeted Data Subset Selectioncited by 8
  12. 2022Submodlib: A Submodular Optimization Librarycited by 8
  13. 2023Dataset Distillation in Latent Spacecited by 7
  14. 2022Active Data Discovery: Mining Unknown Data using Submodular Information Measurescited by 6
  15. 2022Neural Estimation of Submodular Functions with Applications to Differentiable Subset Selectioncited by 6
  16. 2024Color-Oriented Redundancy Reduction in Dataset Distillationcited by 6
  17. 2024Contributing Dimension Structure of Deep Feature for Coreset Selectioncited by 5
  18. 2025Data-efficient LLM Fine-tuning for Code Generationcited by 5
  19. 2025Dataset Condensation with Color Compensationcited by 5
  20. 2023Beyond Active Learning: Leveraging the Full Potential of Human Interaction via Auto-Labeling, Human Correction, and Human Verificationcited by 4
  21. 2024Automatic Combination of Sample Selection Strategies for Few-Shot Learningcited by 4
  22. 2024Calibrated Dataset Condensation for Faster Hyperparameter Searchcited by 4
  23. 2024Dataset Growthcited by 4
  24. 2024Sub-SA: Strengthen In-context Learning via Submodular Selective Annotationcited by 4
  25. 2024Structural-Entropy-Based Sample Selection for Efficient and Effective Learningcited by 4
  26. 2025Fewer May Be Better: Enhancing Offline Reinforcement Learning with Reduced Datasetcited by 4
  27. 2025Looking Beyond the Known: Towards a Data Discovery Guided Open-World Object Detectioncited by 4
  28. 2022PLATINUM: Semi-Supervised Model Agnostic Meta-Learning using Submodular Mutual Informationcited by 3
  29. 2022Pareto Optimization for Active Learning under Out-of-Distribution Data Scenarioscited by 3
  30. 2024Spectral Greedy Coresets for Graph Neural Networkscited by 3
  31. 2025Advances in Set Function Learning: A Survey of Techniques and Applicationscited by 3
  32. 2025Coresets from Trajectories: Selecting Data via Correlation of Loss Differencescited by 3
  33. 2025Rethinking Long-tailed Dataset Distillation: A Uni-Level Framework with Unbiased Recovery and Relabelingcited by 3
  34. 2026Query-Conditioned Evidential Keyframe Sampling for MLLM-Based Long-Form Video Understandingcited by 3
  35. 2026Multimodal Distribution Matching for Vision-Language Dataset Distillationcited by 3
  36. 2023INGENIOUS: Using Informative Data Subsets for Efficient Pre-Training of Language Modelscited by 2
  37. 2023STREAMLINE: Streaming Active Learning for Realistic Multi-Distributional Settingscited by 2
  38. 2023Efficient and Robust Quantization-aware Training via Adaptive Coreset Selectioncited by 2

50 most cited of 88 All 88 (JSON)