# GIST: Greedy Independent Set Thresholding for Max-Min Diversification with Submodular Utility

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 65 references that are in the map.
- First posted on arXiv 29 May 2024.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [ImageNet Large Scale Visual Recognition Challenge](https://mlsanity.com/paper/1409.0575/) (2014)
- [LAION-5B: An open large-scale dataset for training next generation image-text models](https://mlsanity.com/paper/2210.08402/) (2022)
- [Gemini 1.5: Unlocking multimodal understanding across millions of tokens of context](https://mlsanity.com/paper/2403.05530/) (2024)
- [Deep Batch Active Learning by Diverse, Uncertain Gradient Lower Bounds](https://mlsanity.com/paper/1906.03671/) (2019)
- [BatchBALD: Efficient and Diverse Batch Acquisition for Deep Bayesian Active Learning](https://mlsanity.com/paper/1906.08158/) (2019)
- [A Survey on Data Selection for Language Models](https://mlsanity.com/paper/2402.16827/) (2024)
- [Batch Active Learning at Scale](https://mlsanity.com/paper/2107.14263/) (2021)
- [Diverse mini-batch Active Learning](https://mlsanity.com/paper/1901.05954/) (2019)
- [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)
- [Randomized Composable Core-sets for Distributed Submodular Maximization](https://mlsanity.com/paper/1506.06715/) (2015)
- [Regularized Submodular Maximization at Scale](https://mlsanity.com/paper/2002.03503/) (2020)
- [Constrained Submodular Maximization via New Bounds for DR-Submodular Functions](https://mlsanity.com/paper/2311.01129/) (2023)
- [Submodular Maximization with Nearly Optimal Approximation, Adaptivity and Query Complexity](https://mlsanity.com/paper/1807.07889/) (2018)
- [Non-monotone Submodular Maximization with Nearly Optimal Adaptivity and Query Complexity](https://mlsanity.com/paper/1808.06932/) (2018)
- [The Power of Randomization: Distributed Submodular Maximization on Massive Datasets](https://mlsanity.com/paper/1502.02606/) (2015)
- [An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation](https://mlsanity.com/paper/1804.06355/) (2018)
- [Submodular Maximization with Nearly-optimal Approximation and Adaptivity in Nearly-linear Time](https://mlsanity.com/paper/1804.05379/) (2018)
- [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)
- [Submodular Maximization subject to a Knapsack Constraint: Combinatorial Algorithms with Near-optimal Adaptive Complexity](https://mlsanity.com/paper/2102.08327/) (2021)
- [Diverse Data Selection under Fairness Constraints](https://mlsanity.com/paper/2010.09141/) (2020)
- [On Maximizing Sums of Non-monotone Submodular and Linear Functions](https://mlsanity.com/paper/2205.15874/) (2022)
- [Practical and Parallelizable Algorithms for Non-Monotone Submodular Maximization with Size Constraint](https://mlsanity.com/paper/2009.01947/) (2020)
- [Core-sets for Fair and Diverse Data Summarization](https://mlsanity.com/paper/2310.08122/) (2023)
- [Improved Approximation and Scalability for Fair Max-Min Diversification](https://mlsanity.com/paper/2201.06678/) (2022)
- [Max-Min Diversification with Fairness Constraints: Exact and Approximation Algorithms](https://mlsanity.com/paper/2301.02053/) (2023)
- [On Distributed Larger-Than-Memory Subset Selection With Pairwise Submodular Functions](https://mlsanity.com/paper/2402.16442/) (2024)

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

- [Accelerated Relax-and-Round for Concave Coverage Problems](https://mlsanity.com/paper/2605.06900/) (2026)

## Abstract (arXiv)

This work studies a novel subset selection problem called max-min diversification with monotone submodular utility (textsfMDMS), which has a wide range of applications in machine learning, e.g., data sampling and feature selection. Given a set of points in a metric space, the goal of textsfMDMS is to maximize f(S) = g(S) + λ · textttdiv(S) subject to a cardinality constraint |S| ≤ k, where g(S) is a monotone submodular function and textttdiv(S) = minu,v ∈ S : u ne v dist(u,v) is the max-min diversity objective. We propose the textttGIST algorithm, which gives a frac12-approximation guarantee for textsfMDMS by approximating a series of maximum independent set problems with a bicriteria greedy algorithm. We also prove that it is NP-hard to approximate within a factor of 0.5584. Finally, we show in our empirical study that textttGIST outperforms state-of-the-art benchmarks for a single-shot data sampling task on ImageNet.