# On Distributed Larger-Than-Memory Subset Selection With Pairwise Submodular Functions

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 63 references that are in the map.
- First posted on arXiv 26 Feb 2024.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [LAION-5B: An open large-scale dataset for training next generation image-text models](https://mlsanity.com/paper/2210.08402/) (2022)
- [The Pile: An 800GB Dataset of Diverse Text for Language Modeling](https://mlsanity.com/paper/2101.00027/) (2020)
- [Not All Samples Are Created Equal: Deep Learning with Importance Sampling](https://mlsanity.com/paper/1803.00942/) (2018)
- [Lazier Than Lazy Greedy](https://mlsanity.com/paper/1409.7938/) (2014)
- [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)
- [Learning From Less Data: A Unified Data Subset Selection and Active Learning Framework for Computer Vision](https://mlsanity.com/paper/1901.01151/) (2019)
- [Adaptive Second Order Coresets for Data-efficient Machine Learning](https://mlsanity.com/paper/2207.13887/) (2022)
- [Ekya: Continuous Learning of Video Analytics Models on Edge Compute Servers](https://mlsanity.com/paper/2012.10557/) (2020)
- [PRISM: A Rich Class of Parameterized Submodular Information Measures for Guided Subset Selection](https://mlsanity.com/paper/2103.00128/) (2021)
- [Distributed Submodular Maximization](https://mlsanity.com/paper/1411.0541/) (2014)
- [Randomized Composable Core-sets for Distributed Submodular Maximization](https://mlsanity.com/paper/1506.06715/) (2015)
- [The Power of Randomization: Distributed Submodular Maximization on Massive Datasets](https://mlsanity.com/paper/1502.02606/) (2015)
- [Submodular meets Structured: Finding Diverse Subsets in Exponentially-Large Structured Item Sets](https://mlsanity.com/paper/1411.1752/) (2014)
- [A New Framework for Distributed Submodular Maximization](https://mlsanity.com/paper/1507.03719/) (2015)
- [A Weighted K-Center Algorithm for Data Subset Selection](https://mlsanity.com/paper/2312.10602/) (2023)
- [Submodular Optimization in the MapReduce Model](https://mlsanity.com/paper/1810.01489/) (2018)
- [Less is more: Selecting informative and diverse subsets with balancing constraints](https://mlsanity.com/paper/2104.12835/) (2021)
- [Scaling Submodular Maximization via Pruned Submodularity Graphs](https://mlsanity.com/paper/1606.00399/) (2016)
- [Efficient Parallel Algorithms for k-Center Clustering](https://mlsanity.com/paper/1604.03228/) (2016)
- [Almost Optimal Streaming Algorithms for Coverage Problems](https://mlsanity.com/paper/1610.08096/) (2016)
- [Class Subset Selection for Transfer Learning using Submodularity](https://mlsanity.com/paper/1804.00060/) (2018)

## Built on by (most cited first, 1 of 1)

- [GIST: Greedy Independent Set Thresholding for Max-Min Diversification with Submodular Utility](https://mlsanity.com/paper/2405.18754/) (2024)

## Abstract (arXiv)

Modern datasets span billions of samples, making training on all available data infeasible. Selecting a high quality subset helps in reducing training costs and enhancing model quality. Submodularity, a discrete analogue of convexity, is commonly used for solving such subset selection problems. However, existing algorithms for optimizing submodular functions are sequential, and the prior distributed methods require at least one central machine to fit the target subset in DRAM. At billion datapoint scale, even the subset may not fit a single machine, and the sequential algorithms are prohibitively slow. In this paper, we relax the requirement of having a central machine for the target subset by proposing a novel distributed bounding algorithm with provable approximation guarantees. The algorithm iteratively bounds the minimum and maximum utility values to select high quality points and discard the unimportant ones. When bounding does not find the complete subset, we use a multi-round, partition-based distributed greedy algorithm to identify the remaining subset. We discuss how to implement these algorithms in a distributed data processing framework and empirically analyze different configurations. We find high quality subsets on CIFAR-100 and ImageNet with marginal or no loss in quality compared to centralized methods, and scale to a dataset with 13 billion points.