# Complement Submodular Information Measures for Balanced and Robust Data Selection

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 33 references that are in the map.
- First posted on arXiv 23 May 2026.

## Builds on (most cited first, 11 of 11)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Submodular Combinatorial Information Measures with Applications in Machine Learning](https://mlsanity.com/paper/2006.15412/) (2020)
- [SIMILAR: Submodular Information Measures Based Active Learning In Realistic Scenarios](https://mlsanity.com/paper/2107.00717/) (2021)
- [Submodularity In Machine Learning and Artificial Intelligence](https://mlsanity.com/paper/2202.00132/) (2022)
- [TALISMAN: Targeted Active Learning for Object Detection with Rare Classes and Slices using Submodular Mutual Information](https://mlsanity.com/paper/2112.00166/) (2021)
- [Curvature and Optimal Algorithms for Learning and Minimizing Submodular Functions](https://mlsanity.com/paper/1311.2110/) (2013)
- [Polyhedral aspects of Submodularity, Convexity and Concavity](https://mlsanity.com/paper/1506.07329/) (2015)
- [A Memoization Framework for Scaling Submodular Optimization to Large Scale Problems](https://mlsanity.com/paper/1902.10176/) (2019)
- [Active Data Discovery: Mining Unknown Data using Submodular Information Measures](https://mlsanity.com/paper/2206.08566/) (2022)
- [Submodular Benchmark Selection](https://mlsanity.com/paper/2605.02209/) (2026)

## Abstract (arXiv)

Submodular optimization has become a fundamental paradigm for data selection, retrieval, summarization, and representation learning due to its ability to model coverage, diversity, and representativeness. However, classical submodular objectives optimize only the selected subset and do not explicitly preserve structural information between the selected subset and the remaining data. In many modern machine learning applications, including train/validation/test splitting, benchmark construction, and robust subset selection, the quality of a selection depends critically on preserving balanced structure across both the selected subset and its complement. In this work, we introduce Complement Submodular Information (CSI), a new class of complement-aware submodular objectives that quantify shared structural information between a subset and its complement. Our framework induces complement-aware variants of several classical submodular functions including Facility Location, Graph Cut, LogDet, Saturated Coverage, Set Cover, Probabilistic Set Cover, and Feature Based Functions. We analyze the theoretical properties of CSI objectives and show that they exhibit approximate monotonicity under bounded curvature conditions, leading to near-(1-1/e) greedy approximation guarantees. Empirically, CSI objectives consistently outperform standard submodular objectives on robust hidden-slice-aware subset selection. In particular, CSI objectives significantly improve preservation of coherent rare/tail semantic structure while simultaneously suppressing noisy and isolated outliers, leading to substantially improved downstream predictive performance. Synthetic experiments further illustrate how different CSI instantiations capture complementary notions of representativeness, diversity, connectivity, and balanced neighborhood preservation.