2024/05/29 by Matthew Fahrbach, Fahrbach, Matthew, Srikumar Ramalingam +9
Computer Science · Decision Sciences · #Big Data Technologies and Applications #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Time Series Analysis and Forecasting
paper · pdf · doi:10.48550/arxiv.2405.18754
openalex publication_date 2024/05/29 · openalex created_date 2024/05/31 · openalex updated_date 2026/07/30
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) + λ⋅ div(S) subject to a cardinality constraint |S| ≤ k, where g(S) is a monotone submodular function and div(S) = minu,v ∈ S : u ≠ v dist(u,v) is the max-min diversity objective. We propose the GIST algorithm, which gives a (1)/(2)-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 GIST outperforms state-of-the-art benchmarks for a single-shot data sampling task on ImageNet.