GIST: Greedy Independent Set Thresholding for Max-Min Diversification with Submodular Utility
Authors: Matthew Fahrbach
Srikumar Ramalingam
Morteza Zadimoghaddam
Sara Ahmadian
Gui Citovsky
Giulia DeSalvo
Venue: NeurIPS 2025 poster ()
Keywords: approximation algorithm
submodular maximization
max-min diversification
data sampling
subset selection
Primary area: optimization

Abstract: This work studies a novel subset selection problem called *max-min diversification with monotone submodular utility* (MDMS), 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 MDMS is to maximize $f(S) = g(S) + \lambda \cdot \text{div}(S)$
subject to a cardinality constraint $|S| \le k$,
where
$g(S)$ is a monotone submodular function
and
$\text{div}(S) = \min_{u,v \in S : u \ne v} \text{dist}(u,v)$ is the *max-min diversity* objective.
We propose the `GIST` algorithm, which gives a $\frac{1}{2}$-approximation guarantee for MDMS
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.

GIST: Greedy Independent Set Thresholding for Max-Min Diversification with Submodular Utility
Matthew Fahrbach"
Srikumar Ramalingam"
Morteza Zadimoghaddam"
Google fahrbach@google.co com
Google
Google
rsrikumar@google.com
zadimegoggle.co
Sara Ahmadian
Gui Citovsky Google gci gcitovsky@gooogle.com
Giulia DeSalvo
Google sahmadian@@ooggee.co com
Google giuliadegoogle.com
Abstract
This work studies a novel subset selection problem called max-min diversification with monotone submodular utility (MDMS), which has wide range of applications in machine learning, c.g., data sampling and feature selection. Given a set of points a metric space, the goal of MDMS is to maximize f(S) = g(S) A div(S) subject to a cardinality constraint |S| S k where gSS) is monotone submodular function and div(S) ming,veS dist(u, (u, v) is the max-min diversity objective. We propose the GIST algorithm, which gives a /2-approximation guarantee for MDMS by approximating series of maximum independent set problems with a bicriteria greedy algorithm. We also prove that it is NP-hard to approximate within factor of 0.5584. Finally, we show our empirical study that GIST outperforms state-of-the -htt-offt benchmarks for single-shot data sampling task on ImageNet.
Introduction
Subset selection is ubiquitous and challenging problem at the intersection of machine learning and combinatorial optimization, finding applications areas such as feature selection, recommendation systems, and data summarization, including the critical task of designing pretraining sets for large language models [59, 3]. Data sampling in particular is an increasingly important problem given the unprecedented and continuous streams of data collection. For example, one self-driving vehicle generates -80 terabytes of data daily from LiDAR and imaging devices [34], and academic datasets have scaled dramatically from 1.2M images in ImageNet [54] to 5B in Laion [56].
Subset selection often involves balancing competing objectives: we rely on the utility (or weight) of individual items to prioritize them, while simultaneously trying to avoid selecting duplicate or near-duplicate items to ensure diversity. When selecting a small subset, this process should guarantee that the chosen set is good representation of the original dataset-often called coverage. The intricate trade-offs between utility, diversity, and coverage are often expressed through an objective function. It is often significant challenge to design efficient algorithms with strong approximation guarantees for constrained subset selection problems, even when leveraging tools and techniques from combinatorial optimization such as submodular maximization, k-center clustering, and convex hull approximations.
This paper studies novel subset selection problem called max-min diversification with monotone submodular utility (MDMS). Given points V in metric space, a nonnegative monotone submodular
Equal contribution.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

function g 9:24 + Rzo, diversity strength À 2 0, and cardinality constraint k, our goal is to solve
S = arg max g(S) + X div(S)
SgV
subject to |S| S
where div(S) = min uuu dist(u, v) is the max-min diversification term [2, 2,,40,88, Maximizing the submodular term g(S) aims select points that are the most valuable or informative. A purely utility-driven algorithm, however, can lead to redundancies where very similar points are chosen. To counteract this, we add the A div(S) term to encourage selecting points that are well spread out in the metric space, which effectively penalizes subsets with closely clustered elements. Note that À a knob that controls the trade-off between these two terms, acting as a regularization strength for subset selection problems.
The most relevant prior work is by Borodin al. [13]. They combine monotone submodular utility and the max-sum diversity term Eu,es dist(u, v). in contrast to our max-min div(S) in (1). They give greedy /2-approximation algorithm and extend their results to general matroid constraints via local search. An earlier contribution by Gollapudi and Sharma [26] combined linear utillity (instead of monotone submodular function) and the max-sun diversity term, subject to the strict constraint [S] k; to design ranking system for search engines. These approaches focus on maximizing the sum of pairwise distances, but our max-min formulation ensures that the selected points have high utility and are maximally separated, leading to less redundant and more representative subsets.
Our contributions
We summarize the main contributions of this work below:
In Section 2, we formalize the MDMS problem and present a simple a.387-approximation algorithm warm-up show how the competing terms in the objective function interact.
In Section 3, we present the GIST algorithm, which achieves 1/~aaproxximatinn guarantee for MDMS by approximating a series of maximum independent set problems with bicriteria greedy algorithm and returning the best solution. In the special case of linear utility functions g{S) Eves w(v), we prove that GIST offers a stronger //aaapproximation guarantee.
In Section 4, we prove that is NP-hard to approximate MDMS to within factor of 0.5584 via careful reduction from the maximum coverage problem. For linear utilities, we match the guarantees of GIST and prove a tight (2/3 + e)-hardness of approximation, for any > assuming P F NP. In the more restricted case of a linear utility function and the Euclidean metric, we prove APX coxplempleteness.
In Section 5, our experiments show that GIST outperforms baselines for MDMS on synthetic data (in particular the classic greedy algorithm). Then we show that GIST can be used to build better single-shot subsets of training data for an image classification benchmark on ImageNet compared to margin sampling and k-center algorithms, demonstrating the benefit of optimizing for blend of utility and diversity.
1.2 Related work
Submodular maximization. Submodular maximization subject to cardinality constraint i is an NP-hard problem, i.e., maxscvijsiss, (S)). For monotone submodular functions, Nemhauser et al. [47] proved that the greedy algorithm achieves (1 - 1/e)- -aprroximatinn which is asymptotically optimal unless P = NP [23]. The non- monotone case is substantially less understood, but Buchbinder and Feldman [14] recently gave a 0.401 -pprrxiaxxinni algorithm and Qi [48] improved the hardness of approximation to 0.478. Over the last decade, there has also been significant research on distributed algorithms for submodular maximization in the MapReduce [44, 43, 9, 10, 39, 33] and low-adaptivity models [7, 19, 22, 8, 5, 16, 17].
Diversity maximization. The related max-min diversification problem max div(S) has rich history in operations research due to its connection to facility location, and is also called the p-dispersion problem. uses the stricl constraint [S] = k;; otherwise, if [S] S k we can maximize div(S) with two diametrical points. Tamir [58] gave simple greedy //>-approximation algorithm for

---

max-min diversification. and Ravi et al. [51] proved (1/2+e) inairroxiiiiiiiiiiiiitt.... for any E > 0. unless P= NP. Indyk et al. [30] gave a distributed //>aaprrxximation algorithm composable coresets for diversity and coverage maximization. Borassi et al. [12] designed a //-aaproxximation algorithm in the sliding window model. For asymmetric distances, Kumpulainen et al. [38] recently designed a (//6)))aapproimaation algorithm. There are also many related works on mixed-integer programming formulations, heuristics, and applications to drug discovery [20, 52, 55, 60, 37, 40, 61, 42].
Bhaskara et al. [1]] studied the sum-min diversity problem maxssÇV Eues dist(u, S') {u}), providing the first constant-facto approximation algorithm with a //s guarantee. Their algorithm is based novel linear- programrrog relaxation and generalizes matroid constraints. They also proved the first inapproximability result of 1/2 under the planted clique assumption.
Diversity maximization has also recently been studied with fairness constraints. Given partition of the points into m groups, they ensure k2 E [&,, uu] points are selected from each group i E [m], subject to |S| = k Ee kü This line of work can be categorized as studying fair max-min [46, 2, 61], sum-min [11, 41], and max-sum [1, 41] diversity objectives.
Data sampling. In the realm of dataset curation and active learning, there have been several lines of work that study the combination of utility and diversity terms. Greedy coreset methods based on k-center have been successfully used for data selection with and without utility terms [50, 57]. Ash et al. [6] use k-means++ seeding over the gradient space of a model to balance uncertainty and diversity. Wei et al. [62] introduce several submodular objectives, e.g., facility location, and use them to diversify a set of uncertain examples in each active learning iteration. Citovsky et al. [18] cluster examples represented by embeddings extracted from the penultimate layer of a partially trained DNN, and use these clusters to diversify uncertain examples in each iteration. Our work differs from these and several others (e.g,, Kirsch et al. [35], Zhdanov [63]) in that directly incorporate the utility and diversity terms into the objective function.
2 Preliminaries
Submodular function. For any 9: : 2V + R20 and S, S g(S ( (T) be the marginal gain of g at S with respect to T. A function is submodular for every $ C V and v E V T, we have g(u | S) g(r TT,, where we overload the marginal gain notation for singletons. submodular function is monotone if for every $ C T C V. ((S) S (7))
Max-min diversity. For a set of n points V in metric space, define the max-min diversity function as
mi dist(u, v) FEV dist(u, v) if |S| <
if [S] 2 2,
div(S)= =
We take div(S) to be the diameter of V if|s] < 1 so that it is monotone decreasing. We extend the dis- tance function to take subsets S C V as input in the standard way, i.e., dist(u, S) minves dist(u, v). and define dist(u, Ø) xc.
MDMS problem statement. For any nonnegative monotone submodular function g: 22 - R2o and X 2 0, let
f(S) g(S) - div(S).
The max-min diversification with monotone submodular utility (MDMS) problem is to maximize f(S) subject to a cardinality constraint k:
S arg max f(S).
SCV:|Sisk
Let OPT = f(S*) denote the optimal objective value.
Remark 2.1. The objective function f(S) is not submodular (see Appendix A for a counterexample).
Intersection graph. Let Ga(V) be the intersection graph of V for distance threshold d, i.e., with nodes V and edges F= = [(u, v) E /2 u o v, dist(u, (,, u) < d). For any independent set of Ga(V) and pair of distinct nodes u, v S, we have dist(u, v) 2 d.
3

---

2.1 Warm-up: Simple 0.387 -apr--approoiiaaionn algorithm
The objective function S(S) is composed two terms, each of which is easy to (approximately) optimize in isolation. For the submodular term g(S), run the greedy algorithm to get S1 satisfying
g(Si) (1 1/e)- max g(S)
S
(1 1/c) gg()).
For the div(S) term, let S2 pair of diametrical points in V. Then, return the better of the two solutions. This gives ...87appproximation guarantee because, for any 0 S p 1, we have:
ALG smmple
max (
pp.g( + + (1-p) p) À divi(S2))
pp. 1/) g(5") + (1 - p) À div(S")
OPT,
where we set p e/(2e 1) the end by solving p- (1 (1-) 1-p. One our main goals is to improve over this baseline and prove complementary hardness of approximation results.
One of the most common algorithms for subset selection problems is the greedy algorithm that iteratively adds the item with maximum marginal value with respect to the objective function f. We show in Appendix B that the greedy algorithm does provide a constant-factor approximation guarantee.
3 Algorithm
In this section, we present the GIST algorithm for the MDMS problem and prove that it achieves an approximation ratio of 1/2 e. At a high level, GIST works by sweeping over multiple distance thresholds d and calling GreeddynndeeeddentSet subroutine on the intersection graph Ga(V) to find a high-valued maximal independent set. This is in contrast to the warm-up 0.387-aprrxximation algorithm, which only considers the two extreme thresholds d E {0, dmax)-
Greedy Ingededdddeeeeeettee builds the set (starting from the empty set) by iteratively adding v E V with the highest marginal gain with respect the submodular utility while satisfying dist(v, 2 d. This subroutine runs until either |S| = or S is maximal independent set of Ga(V).
GIST computes multiple solutions and returns the one with maximum value f(S). It first runs the classic greedy algorithm for monotone submodular functions to get an initial solution, which equivalent to calling (reedy_Indeeendentee with distance threshold d = O. Then, it considers the set distance thresholds + {(1 + +) Edmax/2 (1 + + S 2/a and E Z2o). The set D contains a threshold close to the target d² /2 where d' div(S*).2 For each d E D, GIST calls GreedyIndeepndent IndependentSet g, d, k) to find a set T of size at most k. If has a larger objective value than the best solution so far, it updates <- T. After iterating over all thresholds in D, it returns the highest- value solution among all candidates.
Theorem 3.1. For any E O, GIST outputs set S C V with |S| < k and f(8) 2 (1/2 -) - using Onk (LgE))))/E) submodular value oracle queries.
The main building block in our design and analysis of GIST is the following lemma, which is inspired by the greedy 2-approximation algorithm for metric k-center and adapted for monotone submodular utility functions.
Lemma 3.2. Let S be a maximum-value set of size at most with diversity at least d. In other words,
S
arg max
g(S)-
Let be the output of Grreddyindeeedentttet(.... d' k). If < d/2, then g(T) 2 g(S))/2 If this is not true, are in the special case where d' S Edmax. which analyze separately.

---

Algorithm 1 Max-min diversification with submodular utility via greedy weighted independent sets.
1: function poonts V. monotone submodular function 2 O, k)
Rgo, budget k; error > classic greedy algorithm
2: Initialize S +
Let dmax wEV dist(u, v)) be the diameter of V
4: Let I' t v } be two points such that dist(u, v) = dmax
5:
if f(T) > f(S) and k 2 then
6:
Update 5 +- T
7: Let D + {(1 + ++)+ Edmax (1+ s 2/c and i Zzo}
distance thresholds
8:
for threshold E do
9: Set T (reedo/nddeeddente(((.....
10: f(T) 2 f(5) then
11:
Update S +
return
1: function Greedy Snepoeetnneentttttooonnt V, monotone submodular function g 2 R2z-
distance d. budget k)
2: Initialize S
3: for i 1 to do
4:
Let C < (u V S di 2 d]
5:
if C = Ø then
6:
return S
S is maximal independent set of Ga(V)
7: Find 1. <- arg max (
8: Update S + (U)
return
Proof. Let W'' [T] and f .,,...,, ty be the points in T in selection order. Let B; fo V dist(t,, u) < d'} be the points in V the radius-d' open ball around f,. Since the distance between any pair of points in B; most 2d' < d, each set B, contains most one point in S7.
First we construct an injective map St + We say that B, covers point v E if E B,. For each covered E Sz, map it to t4, where is the minimum index for which B, covers If there is an s E S not covered by any set B,, then Indeedenedeee must have selected & points, i.c., [T' k. We map the uncovered points in S to arbitrary points in T while preserving the injective property.
Since g is monotone submodular function, we have
s(Si) 9(T
Σ g(s IT). eES
We use to account for g(s T) in terms of the values we gained in set T, For any s S2, let T, be the set of points added set T' in algorithm frredyIndependentSo of h(s)). Since Greedy Indddeedeeeeeettte iteratively adds points and never deletes points from T, we know T3 C By submodularity, g(s T) S g(s Tz). By the greedy nature of the algorithm, we also know that
right before the addition
((((s) T.) 2 g(s T.). We note that the sum of the former terms, ((h(s) nondecreasing. Thus, we conclude that
T.), is at most g(T") since h is injective and is
g(S²) g(T) S Σ g(8 T) < Σ g(((s) 7,) < 97)),
sES;
#ES;
which completes the proof.
Now that we have with this bicriteria approximation, we can analyze the approximation ratio of GIST.
Proof of Theorem 3.1. first prove oracle complexity of GIST. There are 1 logi+e
O (1/e)) thresholds in D. For each threshold, we call GreedyInddeendentser once. In each call for iterations, we find the maximum marginal-value point by scanning (in the worst case) all points. This requires at most nk oracle calls yielding the overall oracle complexity of the algorithm.
5

---

Let d' be the minimum pairwise distance between points in S The GIST algorithm iterates over set of thresholds D. The definition of D implies that at least one threshold d is in the interval [d" (2(1 + e)), d" /2), unless d" V Edmax- We deal with this special case later and focus on the case when such d exists.
Let I"' be the output of GreedyyIndeeendenttee for threshold value d. Since d < d2/2 Lemma 3.2 implies that
g(T) 2 22" g(Sg.) 2 2 g(S").
We also know from our choice of d that
div(T) 2 2(1 + +))
div(s").
Combining these inequalities gives us
f(T) 2 ((1+5)
OPT
2 -2) OPT.
It remains prove the claim for the case when d² < @dmmax GIST considers initial feasible sets and picks the better of the two as the initial value for T. The first set is the classic greedy solution [47] for the monotone submodular function g(S), and ignores the diversity term. It follows that
(1- (1- 9(5 2 (1 21-
S(T) z
(OPT - Aedmax)-
The second set contains two points with pairwise distance dmmax and ignores the submodular term. This yields the lower bound
f(T) 2 À dmax = ー dmax 2 f(T).
Combining (3) and (4), we get a final bound of f(T) (1 -1= 4
TTt which completes the proof. -
OPT
3.1 Linear utility
If (() = Eves w(v) is a linear utility with nonnegative weights w V R2o. then Theorem 3.1 gives us a (1/2- -ppprxxiippoi since this a special case submodularity. However, GIST offers stronger approximation ratio under this assumption.
Theorem 3.3. Let g(S) Eves w(vv be linear function. For any & > 0, GIST returns S V with S < k and f(S) 2 (2/3 e) OPT.
e).
We defer the proof to Appendix C. but explain the main differences. For linear functions, Lemma 3.2 can be strengthened to show that GreedyIndependenten for any d' d/2. Then, for some d E D, we get ALG max(g(S*) + A- [[2(11 +)), X d and the optimal convex combination of these two lower bounds gives the approximation ratio.
outputs set T such that g(T) 2 g(S)),
4 Hardness of approximation
We begin by summarizing our hardness results for MDMS. Assuming P / NP, we prove that:
Submodular utility. There is no polynomial-time 0.558--aprooiimation algorithm if is a nonnega- tive, monotone submodular function.
Linear utility.
There is no polynomial-tine time + E) approxiaaaio algorithm if is linear, for any e > O, for general distance metrics.
APX-completenee for linear utility functions even in the Euclidean metric, i.c., there is no polynomial-time approximation scheme (PTAS) for this problem.
4.1 General metric spaces
We build on the set cover hardness instances originally designed by Feige et [23, 25, 24], and then further engineered by Kapralov et al. [32]. We present the instances in [32, Scction 2] as follows:

---

Hardness of max k-cover. For any constants e, > and given collection/family of sets F partitioned into groups Fi. F2. Fk. it NP-hard distinguish between the following two cases:
YES case: there exists &s disjoint sets S; one from each Fi, whose union covers the entire universe.
NO case: for any S sets, their union covers at most (1 (1 1/6)* + + e--fccction of the universe.
The construction above can be done such that each set S; E F = - Fr has the same size. We note that the parameter k should be larger than any constant we set since there is always an exhaustive search algorithm with running time [F] to distinguish between the YES and NO cases. Therefore, we can assume, e-g., that k 2 1/e.
We use this max k-cover instance to prove hardness of approximation for the MDMS problem. Theorem 4.1. It is NP-hard to approximate MDMS within a factor of 2(1-1/e) for any 5 >
2[1-1/e]+1 +8 < 0.55836+
Proof sketch. We reduce an instance the max k-cover problem to MDMS to demonstrate how the inapproximability result translates. For any pair of sets in the collection F, their distance is defined to be 2 if and only they are disjoint; otherwise, it 1. Consequently, a selected sub-collection of F achieves the higher diversity score of 2 and only if all chosen sets mutually disjoint.
Given that all sets in F are uniform size and considering the upper bound the NO case on the union coverage for any collection of sets, polynomial-tine time algorithm can only find O(sk) pairwise disjoint sets. Thus, if an algorithm aims for a diversity score of 2 (by selecting only disjoint sets), forgoes most of the potential value from the submodular coverage function in the MDMS formulation. On the other hand, if the algorithm settles for the lower diversity score 1, it still cannot cover more than approximate fraction 1 (1 1/4)* & ss 1 1/c + of the universe.
Combining these two upper bounds on any polynomial-tine timee algorithm's performance with the fact that, in the YES case, the optimal solution covers the entire universe and achieves diversity score 2, establishes the claimed hardness approximation.
4.2 Linear utility
For the special case of linear utility functions, we prove a tight hardness result to complement our a/paapproximttion guarantee in Theorem 3.3.
Theorem 4.2. For any E > 0, there no polynomial-tin (2/3 + appproxximtii algorithm for the MDMS problem if g linear function, unless NP.
We defer the proof to Appendix D.2. Our construction builds on the work of Hästad [28] and Zucker-
man [64], which shows that the max clique problem does not admit an efficient n 1-9 ">-aaproxximation algorithm, for any constant f 0.
4.3 Euclidean metric
Our final result is for the Euclidean metric, i.c., S C _Rd and dist(x, y) = ||x - y/12- We build on a result of Alimonti and Kann [4] showing that the size of max independent set bounded-degree graph cannot be approximated to within a constant factor E, for any ε > 0, unless P = NP.
Lemma 4.3 (Alimonti and Kann [4, Theorem 3.21). The maximum independent set problem for graphs with degree at most 3 APX-complete.
Our second ingredient is an embedding function ha(v) that encodes graph adjacency in Euclidean space.
Lemma 4.4. Lei G = (V, be a simple undirected graph with n [V] m = |E), and max degree A. There exists an embedding he V - Butm such that if {u, E E then
[lho(u) - hoo hoa())- 51- 2
and if (u, v) of E then (u) ha(v)]l2 =
7

---

Theorem 4.5. MDMS is APX-complete for the Euclidean metric if g is linear function.
We sketch the main idea below and defer proofs to Appendix D. Let I(G) be the set of independent sets of G. Using Lemma 4.4, for any set of nodes S S V with |S| 2 2 in graph G with max degree < 3, we have the property:
S E(G) div(S) 1;
8 I[G)
div(s) < 1 2(--1) $1 1//ss.
The gap is at least 1/s for all such graphs (i.e., a universal constant), so setting À = 1 allows us to prove that MDMS inherits the APX-completeness of bounded-degree independent set.
Experiments
5.1
Warm-up: Synthetic dataset
first compare GIST against baseline methods on a simple MDMS task with normalized budget- additive utility function (i.e., monotone submodular) and a set of weighted Guassian points.
Setup. Generate n = 1000 points x, E Rd, for d = 64, where each x, ~ (N Lt) is i.d. and assigned uniform continuous weight w; ~ 10. For a, B E [0, 1). the objective function trades off between the average (capped) utility of the points and their min-distance diversity reward:
Σ ws. 5 (1-)) div((S) iE
f(S) = a --m
1:
We consider three baseline methods: random, simple, and greedy. random selects & random points, permutes them, and returns the best prefix since the objective function f(S) is non-monotone. simple the 3887-approximmtion algorithm Section 2.1. greedy builds S one point at time by selecting the point with index i = arg eax, (SSSssSSSSSS.... ( ((.-1) at each step i [k). and returns (ditt(u, v)/2 u, E V/
the best prefix arg max f(S)). GIST considers all possible since n 1000, which yields an exact e/saapproximation ratio.
=
Results. We plot the values of (SAG)) for the baseline methods and GIST, for each [ni, in Figure 1. GIST dominates simple. greedy, and random in all cases. greedy performs poorly for k 2 100, which is surprising since it is normally a competitive method for subset selection tasks. simple beats greedy for mid-rand range values of k ie.. & E [250, 900], but it is always worse than GIST. In Appendix 1, we sweep over and 3, and show how these hyperparameters affect the (SSLG) plots. Finally, remark that the plots in Figure are decreasing in k because (i) we use normalized budget-additive utility func- tion, and (ii) div(S) is monotone-decreasing function.
1.5
random
simple
1.4
greedy
GIST
1.3
1.1
1.0
Figure 1: f(SALG) for baseline methods and GIST, for each cardinality constraint E [n], on synthetic data with n 1000, 0.95, and 0.75.
5.2 Image classification
Our ImageNet data sampling experiment compares the top-1 image classification accuracy achieved by different single-shot subset selection algorithms.
Setup. We use the standard vision dataset ImageNet [54] containing ~1.3 million images and 1000 classes. We select 10% of the images uniformly at random and use them to train an initial ResNet--6 model 0, [29]. Then use the model 0y to compute 2048- dineedinnnsional unit-length embedding e,

---

Table 1: 1op-1 classification accuracy (%) ImageNet for different single-shot data downsampling algorithms. The cardinality constraint is expressed as a percent of the -1.3 million examples. The results are the average of three trials and the top performance for each k is shown in bold.
k (%)
random
margin
k-center
submod
GIST-margin
GIST-submod
30
66,23 = 0.15
65.97 + 0.33
66.71 0.57
66.52 0:21
66.90 0.19
67.24 +: 0.06
40
69.17 = 0.12
69.73
+ 0.38
70.06 + 0.06
70.71
# 0.24
70,51
# 0.12
70.76 + 0.35
50
71.05 = 0.16
72.33
+ 0.09
73.01 0.10
72.69
0.15
72.69
4 0.34
73.15 0.21
60
72.49 = 0.28
73.43
i: 0.06
73.60 0.31
74.20
0.08
74.34
0.01
74.30 1: 0.27
70
73.70
1 0.22
74.49
1: 0.22
74.24 1: 0.23
75.24
0.30
75.41 1 0.23
75.32 1: 0.19
80
74.42
0.39
75.01
0.05
75.17
+ 0.11
75.91 0.07
75.96 = 0.28
75,45 + 0.16
90
75.16 = 0.13
75.11 = 0.13
75.00 + 0.38
75.84 = 0.10
76.12 = 0.33
76.03 + 0.02
and uncertainty score for each example Z;. The margin-based uncertainty score of x; is given by 04 (Pr(y = b x;; 0n) Pr(y = V' x;: 0,)), which measures the difference between the probability of the best predicted class label b and second-best label // for an example. Finally, we use the fast maximum inner product search of Guo et al. [27] build A-nearest neighbor graph G in the embedding space using A = 100 and cosine distance, i.e., dist(x;, æ;) = 1 e; ej. We present all model training hyperparameters in Appendix
We compare GIST with several tfate-of-the-art benchmarks:
We draw samples from the dataset uniformly at random without replacement. This is a simple and lightweight approach that promotes diversity many settings and provides good solutions.
random:
margin [53]: Margin sampling selects the top-k points using the uncertainty scores us, i.e., based on how hard they are to classify. is not incentivized output a diverse set of training examples.
k-center [57]: We run the classic greedy algorithm for k-center on G. We take the distance between non-adjacent nodes to be the max distance among all pairs of adjacent nodes in G. submod: We select subset by greedily maximizing the submodular objective function
g(S) = 0's Σ
3
Σ sii,j), iJES
SES
subject to the constraint |S] < k where sii,j) = 1- dist(z,,, x.) is the cosine similarity between adjacent nodes in G. Similar pairwise-diverse
submodular objective functions have also been used in [45, 21, 31, 36, 49]. This is different diversity objective than div(S) that keeps g(5) submodular but allows it to be non-monotone. We tuned for best performance by selecting a, 0.9 and 3, 0.1.
Finally, we bootstrap the margin and submod objectives with MDMS and run GIST with e = 0.05:
GIST-margin: Let f(S) Eies u, (1 (1-a) div(S) for [o, 1]. This uses the same linear utility function as margin sampling. We optimize for performance and set a = 0.9.
GIST-submod: Let S(S) function in (5) with a, = 0.9 and 3, = 0.1. We optimize for performance and set a 0.95.
(S)) (1-cl a) div(S). where g(S) is the same submodular
Results. We run each sampling algorithm with cardinality constraint on the full dataset to get a subset of examples that we then use to train a new ResNet-56 model. We report the average top-1 classification accuracy of these models in Table GIST with margin or submodular utility is superior to all baselines. Interestingly, there is cut-over value of & where the best algorithm switches from GIST-submod to GIST-margin We also observe that GSST-sd and GIST-margin outperform submod and margin, respectively. This demonstrates how div(S) encourages diversity in the set of sampled points and improves downstream model quality. The running time of margin and submod 3-4 minutes per run on average. GIST is similar to the margin or submodular algorithms for given distance threshold d. The end-to-end running time is dominated by training ImageNet models, which takes more than few hours even with several accelerators (c.g., GPU/TPU chips).

---

Conclusion
We introduce novel subset selection problem called MDMS that combines the utility of the selected points (modeled as monotone submodular function g) with the div(S) minaa,eSSuupt dist(u, v) diversity objective. We design and analyze the GIST algorithm, which achieves //2-approximation guarantee by solving series of maximal-weight independent set instances on intersection graphs with the Indedddeddeeeeetttee bicriteria-aproxximatoo algorithm. We complement GIST with a 0.5584 hardness of approximation. It is an interesting open theory problem to close the gap between the 0.5 approximation ratio and 0.5584 imapproximability For linear utilities, we show that GIST achieves a 2/3-appn a/pappoxximaiion and that it is NP-hard to find (2/s + e) aaapproximaatin, for any 0.
Our empirical study starts by comparing GIST existing methods for MDMS on a simple synthetic task to show the shortcomings of baseline methods (in particular the greedy algorithm). Then we compare the top-1 image classification accuracy of GIST and state-of-the-an data sampling methods for ImageNet, demonstrating the benefit of optimizing the trade-off between a submodular utility and max-min diversity.
References
[1] 7. Abbassi, V. S. Mirrokni, and M. Thakur. Diversity maximization under matroid constraints. In Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 32-40, 2013.
[2] R. Addanki, A. McGregor, A. Meliou, and Z. Moumoulidou. Improved approximation and scalability for fair max-min diversification, In Proceedings of the 25th International Conference Dutabase Theory, pages 7:1-7:21, 2022.
[3] A. Albalak, Y. Elazar, S. M. Xie, S. Longpre, N. Lambert, X. Wang, N. Muennighoff, B. Hou, L. Pan, H. Jeong. C. Raffel, S. Chang, Hashimoto, and W. Y. Wang. survey on data selection for language 2024.
models. ArXiv, abs/2402.
[4] P. Alimonti and V. Kann. Some APX-completeness results for cubic graphs. Theoretical Computer Science, 237(1-2):123-11 134, 2000.
[5] G. Amanatidis, F. Fusco, P. Lazos, S. Leonardi, A. Marchetti Spaneetti-paccamela. and R. Reiffenhäuser. Submod- ular maximization subject to a knapsack constraint: Combinatorial algorithms with near-optimal adaptive complexity. In International Conference on Machine Learning, pages 231 1-42. PMLR, 2021.
[6] J. T. Ash, C. Zhang, A. Krishnamurthy, J. Langford, and A. Agarwal. Deep batch active learning by diverse, uncertain gradient lower bounds. In Proceedings of the 8th International Conference on Learning Representations, 2020.
[7] F. Balkanski and Y. Singer. The adaptive complexity of maximizing a submodular function. In Proceedings of the 50th annual ACM SIGACT Symposium Theory of Computing, pages 1138-1151, 2018
[8] E. Balkanski, A. Rubinstein, and Y. Singer. An exponential speedup in parallel running time for submodular maximization without loss in approximation. In Proceedings of the Thirtieth Annual ACM SIAM Symposium on Discrete Algorithmss pages 283-302. SIAM, 2019.
[9] R. Barbosa, A. Enc, H. Nguyen, and J. Ward. The power of randomization: Distributed submodular maximization on massive datasets. In International Conference on Machine Learning, pages 1244.124.. PMLR, 2015.
[10] R. Barbosa, A. Ene, H. Nguyen, and J. Ward. A new franework for distributed submodular maximization. 2016 IEFE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 645-654, Icce, 2016.
[11] A. Bhaskara, M. Ghadiri, V. Mirrokni, and O. Svensson. Linear relaxations for finding diverse elements in metric spaces. Advances in Neural Information Processing Systems, 29:4098 4106, 2016.
[12] M. Borassi. A. Epasto, S. Lattanzi, S. Vassilvitskii, and M. Zadimoghaddam. Better sliding window algorithms to maximize subadditive and diversity objectives. In Proceedings of the 38th ACM SIGMOD- SIGACT-SIGAI Symposium Principles of Database Systems, pages 254-268, 2019.
[13] A. Borodin, A. Jain, H. C. Lee, and Y. Ye. Max-sum diversification, monotone submodular functions, and dynamic updates. ACM Transactions on Algorithms (TALG), 13(3):1-25 25, 2017.
10

---

[14] N. Buchbinder and M. Feldman. Constrained submodular maximization via new bounds for dr-submodular functions. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 1820-1831, 2024.
[15] M. Böther, A. Sebastian, P. Awasthi, A. Klimovic, and S. Ramalingam. On distributed larger-than larger-than-memory subset selection with pairwise submodular functions. Proceedings of the 8th MLSys Conference, 2025.
[16] Y. Chen and A. Kuhnle. Practical and parallelizable algorithms for non-monotone submodular maximization with size constraint, Journal of Artificial Intelligence Research, 79:599-637, 2024.
[17] Y. Chen, W. Chen, and A. Kuhnle. Breaking barriers: Combinatorial algorithums for non-monotone sub- modular maximization with sublinear adaptivity and 1/c approximation. arXiv preprint arXiv:2502.0706 2025.
[18] G. Citovsky, G. DeSalvo, C. Gentile, L.. Karydas, A. Rajagopalan, A. Rostamizadeh, and S. Kumar. Batch active learning at scale. Advances in Neural Information Processing Systems, 11111193319444 2021.
[19] A. Ene and H. L. Nguyen. Submodular maximization with nearly-optimal approximation and adaptivity in nearly-linear time. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 274-282. SIAM, 2019.
[20] E. Erkut. The discrete p-dispersion problem. European Journal of Operational Research, 46(1):48-60 1990.
[21] M. Fahrbach, V. Mirrokni, and M. Zadimoghaddam. Non-monotone submodular maximization with nearly optimal adaptivity and query complexity. In International Conference on Machine Learning, pages 1833-1842. PMLR, 2019.
[22] M. Fahrbach, V. Mirrokni, and M. Zadimoghaddam. Submodular maximization with nearly optimal approximation, adaptivity and query complexity. In Proceedingy of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 255-273. SIAM, 2019.
[23] U. Feige. A threshold of In n for approximating set cover. Journal of the ACM, 45(4):634 652, 1998.
[24] U. Feige and J. Vondrák. The submodular welfare problem with demand queries. Theory of Computing. 6 (1):247-290, 2010.
[25] U. Feige, L. Lovász, and P. Tetali. Approximating min set cover. Algorithuica,, 40:219-234, 2004.
[26] S. Gollapudi and A. Sharma. An axiomatic approach for result diversification. In Proceedings of the 18th International Conference on World Wide Web, pages 381 1-390, 2009.
(27] R. Guo, P. Sun, E. Lindgren, Q Geng, D. Simcha, F. Chern, and S. Kumar. Accelerating large-scale inference with anisotropic vector quantization. In International Conference Machine Learning, pages 3887-3896, 2020.
[28] J. Håstad. Clique hard to approximate within nt==, In Proceedings of 37th Conference on Foundations of Computer Science, pages 627-636, 1996.
[29] K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 770 770-778, 2016.
[30] P. Indyk, S. Mahabadi. M. Mahdian, and V. S. Mirrokni. Composable core-sets for diversity and coverage maximization. In Proceedings of the 33rd ACM SGGMOD-SIGACTSSIGAR Symposiun on Principles of Database Systems, pages 100-108, 2014.
[31] R. Iyer, N. Khargoankar, Bilmes, and H. Asanani. Submodular combinatorial information measures with applications in machine learning. In Proceedings of the 32nd International Conference on Algorithmic Learning Theory, 2021.
[32] M. Kapralov, Post, and J. Vondrák. Online submodular welfare maximization: Greedy is optimal. In Proceedings of the Twenty-Fourd Annual ACM SIAM Symposium on Discrete Algorithmms, pages 1216-1225. SIAM, 2013.
[33] E. Kazemi, S. Minace, M. Foldman, and A. Karbasi. Regularized submodular maximization at scalc. In International Conference on Machine Learning, pages 5356-5366 PMLR, 2021.
[34] F. Kazhamiaka, M. Zaharia, and P. Bailis. Challenges and opportunities for autonomous vehicle query systems. In Proceedings of the Conference Innovative Data Systems Research, 2021.
11

---

[35] A. Kirsch, J. Van Amersfoort, and Y. Gal. Batchbald: Efficient and diverse batch acquisition for deep bayesian active learning, Advances in Neural Information Processing Systems, 32, 2019.
[36] S. Kothawade, N. Beck, K. Killamsetty, and R. Iyer. SIMILAR: Submodular information measures based
active learning in realistic scenarios. In Advances in Neural Information Processing Systems, 2021.
[37] J. Kudela. Social distancing as p-dispersion problem. JEEE Access, 8: 199402-44941,,02222
[38] Kumpulainen, F. Adriaens, and N. Tatti. Max-min diversification with asymmetric distances. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 1440-1450, 2024.
[39] P. I Liu and J. Vondrák. Submodular optimization in the MapReduce model. In 2nd Symposium on Simplicity in Algoritlums, volume 69, pages 18:1-18:10. Schloss Dagstuhl- L.cibniz-7entrum für Informatik, 2019.
[40] Lozano-Osorio, A. Martinez-Gavann R. Martí, and A. Duarte. Max-min dispersion with capacity and cost for a practical location problem. Expert Systems with Applications, 200: I 16899, 2022.
[41] S. Mahabadi and Trajanovski. Core-sets for fair and diverse data summarization. Advances Neural Information Processing Systems, 2023.
[42] T. Meinl, C. Ostermann, and M. R. Berthold. Maximum-score diversity selection for early drug discovery. Journal of Chemical Information and Modeling, 51(2)23772477, 2011.
[43] V. Mirrokni and M. Zadimoghaddam. Randomized composable core-sets for distributed submodular maximization. Proceedings of the Forty-Seventh Annual ACM Symposiun on Theory of Computing. pages 153-162, 2015.
[44] B. Mirzasoleiman, A. Karbasi, R. Sarkar, and A. Krause, Distributed submodular maximization: Identifying representative elements in massive data, Advances in Neural Information Processing Systems, 26, 2013.
[45] B. Mirzasoleiman, A. Badanidiyura, and A. Karbasi. Fast constrained submodular maximization: Person- alized data summarization. In International Conference on Machine Learning, pages 1358-1367. PMLR, 2016.
[46] Z. Moumoulidou, A. McGregor, and A. Meliou. Diverse data selection under faimess constraints. In Proceedings of the 24th International Conference on Database Theory, pages 13:1-13:25, 2020.
[47] G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher. An analysis of approximations for maximizing submodular set functions Mathematical Programming, 14:265 294, 1978.
[48] B. Qi. On maximizing sums of non-monotone submodular and lincar functions. Algorithmica, 86(4); 1080-1 133,, 2024.
[49] S. Ramalingam, D. Glasner, K. Patel, R. Vemulapalli, S. Jayasumana, and S. Kumar. Balancing constraints and submodularity in data subset selection. CoRR, abs/2104. 1120004.88835 12835, 2021.
[50] S. Ramalingam, P. Awasthi, and S. Kumar. A weighted k-center algorithm for data subset selection, 2023. URL https://arxivv http:///axxxv..ggabbbae htsp//bs/23313 10602.
[51] S. S. Ravi, J. Rosenkrantz, and G. K. Tayi. Heuristic and special case algorithms for dispersion problems. Operations Research, 42(2):299-310, 1994.
[52] M. G. Resende, R. Martí, M. Gallego, and A. Duarte. GRASP and path relinking for the max min diversity problem. Computers & Operations Research. 378 508, 2010.
[53] D. Roth and K. Small. Margin-based active learning for structured output spaces. Proceedings of the 17th European Conference on Machine Learning, 2006.
[54] O. Russakovsky, J. Deng, Su, J. Krause, S. Satheesh, S. Ma. Z. Huang, A. Karpathy, A. Khosla, M. Bernstein, et al. Imagenet large scale visual recognition challenge. International Journal of Computer Vision, 1 115:211 1 1522,, 2015.
[55] F. Sayyady and Y. Fathi. An integer programming approach for solving the p-dispersion problem, European Journal of Operational Research, 253(1 (321162,,,2 2016.
[56] C. Schuhmann, Beaumont, R. Vencu, C. Gordon, R. Wightman, M. Cherti, T. Coombes, A. Katta,
C. Mullis, M. Wortsman, P. Schramowski, S. Kundurthy, K. Crowson, L. Schmidt, R. Kaezmarezyk, and J. Jitsev. LAION-50 5B: An open large-scal scale dataset for training next generation image- image-text models. In Proceedings of the Conference Neural Information Processing Systems, 2022.
12

---

[57] O. Sener and S. Savarese. Active learning for convolutional neural networks: A core-set approach. In Proceedings of the 6th International Conference on Learning Representations. 2018.
[58] A. Tamir. Obnoxious facility location graphs. SIAM Journal on Discrete Mathematics, 4(4):550-567,
1991.
[59] G. Team, P. Georgiev, I. Lei. R. Burnell, L. Bai, A. Gulati, G. Tanzer, D. Vincent, Z. Pan, S. Wang, et al. Gemini 1.5: Unlocking multimodal understanding across millions of tokens of context. arXiv preprint arXiv:2403.0555 2024.
[60] G. K. Tutunchi and Y. Fathi. Effective methods for solving the bi-criteria p-center and p-dispersion problem. Computers Operations Rexearch, 101:43-54, 2019.
[61] Y. Wang. M. Mathioudakis, Li, and F. Fabbri. Max-min diversification with fairness constraints: Exact and approximation algorithms. In Proceedings of the 2023 SIAM International Conference on Data Mining (SDM), pages 91-99. SIAM, 2023.
[62] Wei, Iyer, J. Bilmes. Submodularity in subset selection and active learning. International Conference on Machine Learning, pages 1954-1963, 2015.
[63] Zhdanov, Diverse mini- biti-batch active learning. arXiv preprint arXiv:1901.0595: 2019.
[64] D. Zuckerman. Linear degree extractors and the inapproximability of max clique and chromatic number. In Proceedings of the 38th Annual ACM Symposium on Theary of Computing, pages 6-996, 2006.
13

---

A f(S) is not submodular
Consider the instance on four points N {a, b, c, d] S R where a 0, = 1, and d 2 with the (one-dimensional) Euclidean metric, i.e., all the points are collinear. Let g(S) = for all 5 S V. For f(S) to be submodular, it must hold that for every T C N and x E N T.
f(Su [x}) f(S) > -
However, = b,5 (a.c) and T = {a, c. d), we have:
f(S) f(fa,b,c) f(fa,c)) =
( f(T) - f(fa,b, - f(fa,c,d)) = 0 0000-- -
so f(S) is not submodular.
In this instance, ((S) is not monotone. However, similar monotone but still not submodular f(S) can be defined by setting gSS) = Eves w(r) where w(v) for every v E N.
B Greedy does not give a constant-factor approximation guarantee
The objective function f is highly non-monotone since the diversity term can decrease we add items. Consequently, the standard greedy algorithm, which rejects any item with a negative marginal gain, have arbitrarily poor performance.
We demonstrate this with hard instance. Let the submodular part the objective be gSS) |S]. For the diversity component, define the distance between specific pair (u, v) to be dist(u, v) = 2 + 25, while for all other pairs (1t y) * (u. v), we have dist(æ; y) 1+ The greedy algorithm first selects the set {u, v). achieving value of [((u,)) v)) g( (u, w)) dist v) = 4 2s. The algorithm then terminates because adding any subsequent item gives a submodular gain of but causes a diversity loss of 1 + E, resulting in a negative marginal gain. An optimal solution of size k. however, can achieve a value of at least & from the submodular term alone. The resulting approximation ratio for greedy is at most (4 2r)/k, which approaches 0 as k grows. Thus, greedy offers constant-factor approximation guarantee. Furthermore, modifying greedy to accept items with negative marginal construct instances where optimal solution value is
value does not solve this problem since dominated by a diversity term such that selecting any set of size l reduces the diversity term to zero.
C Missing analysis for Section 3
C.1 Proof of Theorem 3.3
The following result is a tighter analysis of the bicriteria approximation of Crreedynndeeendenntte (Lemma 2) if (S) is linear function. This is the key ingredient for improving the approximation ratio of GIST to 2/3 E.
w(v) be a linear function with nonnegative weights w : V - R20- Let Sa be a max-weight independent set of the intersection graph GV(V) of size at most IfT is the output of Gr
Lemma C.1. Let
g, d', k), for d' S d/2, then w w() 2 w(S)).
Proof. Let = [T'l and &,, ....... te be the points T in the order that Greedy I Independent selected them. Let B, {u V dist(f;, v) < d') be the points in V contained in the radius-d' open ball around t,. First, we show that each B, contains at most one point in S If this is not true, then some B, contains two different points u, E Sg. Since dist(..)) is metric, this means
dist(u, u, v) < dist(u, t.) + dist(t;, v) < d' + d' < d 2 + d/2
d
which contradicts the assumption that St an independent set of Ga(V). Note that it possible to have B, n B3 # Ø, for i & since these balls consider all points in V.
14

---

Now let C S V be the set of uncovered points (by the open balls) that become covered when GreedyIndeepedentsee
selects t, Concretely, C, B, (B, U...U -, Each C₁ contains at most one point in S2 since R. n S I 1. Moreover, if s e C. then w((4) 2 w(()) because the points are sorted in non-inereasing order and selected if uncovered.
Let A = C₁ U .... C be the set of points covered by the algorithm. For each point E S n. there is exactly one covering set C₁ corresponding to follows that
Σ
w(s) S
E
w(4)).
#ES
It remains to account for the points in S \ A. If we have any such points, then [T] = k since the points in S A are uncovered at the end of the algorithm. Further, for any 4 E 7 and & E S \ A, have w(4,) 2 w(() since 4 selected and the points sorted by non-increasing weight. Therefore, we can assign each 8 E S \ A to unique C₁ such that C2 n S = 2. It follows that
Σ w(s) S
E
w(t,).
SESTAA
Adding the two sums together in (6) and (7) completes the proof.
Theorem 3.3. Let g(S) Eves w(v) be linear function. For any E >> 0, GIST returns S V with S S i and f(S) 2 (2/3 - c) OPT.
Proof of Theorem 3.3. Let d' be the minimum distance between two distinct points in S*. There are two cases: d² < Edmax and d" Edmax- In the first case, outputting the k heaviest points (Line 2 of GIST) yields a (1 - E) approximatio.. To see this, first observe that
OPT 2 A dmax A
e OPT d.
The sum of the heaviest points upper bounds g(S*), so we have
ALG g(S)) OPT A d 2 (1 - OPT.
Now consider the where d' > mdm GIST tries threshold d [d" (2 + +)), d² /2), so Lemma C.I implies that Greedy Inddd/edeeeeeeentttt... d, k) outputs set T such that
d'
f(T) (
(SS)) X.
(8)
2(1 +1++e) =)
The max-diameter check on Lines 3-6 give us the lower bound
ALG 2 A dmax 2 A d".
(9)
Combining (8) and (9), the following inequality holds for any S ps
ALG 2 p. (9(55) + + 2(1+ + $)
d'
+ (1-p)) d-
=p'g(S") + 1 + +
p
> d.
2(1 21++))
To maximize the approximation ratio 0, we set p
2/3 by solving p p/2. Therefore,
2
3(1 +8) ) x
1
ALG >
0(S)) +
1
+
(10)
3
3
1
1
0(S +
1+
x.
3
3
1+e)
2 ((*)
1
+
(2
(2-6) >
3
2
- OPT,
3
which completes the proof.
15

---

D Missing analysis for Section 4
D.I Proof of Theorem 4.1
Theorem 4.1. It is NP-hard to approximate MDMS within factor of 2(1-1/e) for any 5 > 0.
2[1-1/e)+T +0 < 0.55836+
Proof. We construct our instance based on the collection of sets above as follows. We set min (8, 8² /6) and c 1. As mentioned above, we can assume that k > 1/c + since there is always a brute force polynomial time algorithm for constant & to distinguish between YES and NO instances.
Suppose there are n sets SI, S2, S,, in the collection F. We represent these n with n points in the MDMS instance. We overload the notation to show the corresponding point with S; too. For any subset of sets/points T, the submodular value g(T) is defined the cardinality of the union of corresponding sets, i.e., the coverage submodular function. In other words, g(T) UUs.eT S,
The distances between points/scts either d or 2d. If two sets are disjoint and belong to two separate partitions F, and Fr,, their distance 2d, Otherwise, we set their distance to So for any two sets S,5' belonging the same group Fr. their distance is set to d. Also, for any two sets with nonempty intersection, we set their distance to d too. Any other pair of points will have distance 2d.
We set d to be (1 1/c)U where U is the cardinality of the union of all sets, i.e., U -Use Sl. Finally, we set À = to complete the construction of MDMS instance.
In the YES case, the optimum solution is the family of k disjoint sets from different groups that cover the entire universe. The value of optimum this case 2d U (2(1 1/e) + 1)U.
The algorithm has two possibilities: (case a) the algorithm gives up on the diversity objective and selects & sets with minimum distance d, (case b) it aims for a diversity term of 2d. In case (a), the submodular value is at most (1 (1 - 1/*)* + E)U because of the property of the NO case. We note that if the algorithm finds a of i sets with union size above this threshold, we conclude that we have a YES instance, which contradicts the hardness result.
The limit of the upper bound for the submodular value as l goes to infinity is 1 1/e + e. We use its expansion series derive:
1 Te
5
1 (1-
2ek
24ck2
The sequence of negative terms declines in absolute value with rate of at least l/k. Thus, the absolute value of their total sum is at most the first deductive term 1/2ck times 1/(1 1/k) = k/(A: (I: 1), which gives the simpler bound:
(1-1)
(1
2
k
2e(k 1)
Since l 1 at least 1/e, the submodular value in case (a) does not exceed:
1 ( +
+
1- - 28 U
2e(k
Recall that d = (1 1/aJU, so the ratio what the algorithm achieves case (a) and the optimum solution of YES case is most:
1/e + 22)U +
2(1 1/e) +
+ 2d
2(1 - 1/e) +
2(1 - 1/c)
2(1 - 1/e) +1 +
In case (b), the algorithm is forced to pick only disjoint sets to maintain a minimum distance of 2d. This means if the algorithm picks sets, their union has size é. U//.. This is true because all sets in JF have the same size and we know in the YES case, the union of & disjoint sets covers the entire
16

---

universe hence each set has size 0/4. For the special case of & = 1, we know that only 1/4 < fraction universe is covered. We upper bound the covered fraction in terms of for the other cases. The property of the NO case implies the following upper bound on &
8
S1
+E.
We use the binomial expansion of (1 1/4) and note that each negative term exceeds its following positive term in absolute value. This is because of the cardinality constraint 8 k. Therefore,
11-
Ele ((e-1)
Ele - 1)(e - 2)
2
1
1.
k
2h
61-3
E(L
1)
2 1
k
3k2
L
2 1
k
6k
where the second last inequality holds since & - 2 l and the last inequality holds because 2 and consequently
2 f/2. We can now revise the initial inequality:
s (1 - (1 (1-1/4) +8)
< 1 6 +
S. 8.
6
Thus, the fraction of the universe that the algorithm covers, namely f/k, is at most v S 6. In case (b), the ratio what the algorithm achieves, and the optimum solution of YES case is at most:
U 2d
2(1 - 1/2) + 2(1 -/e) 2(1 1/c) +1 2(1 1/c)+1 +1
5.
U + 2d
This concludes the proof in both cases (a) and (b).
D.2 Proof of Theorem 4.2
Theorem 4.2. For any e > 0, there no polynomial-time ( + apppprxximttioonn algorithm the MDMS problem if g is a linear function, unless P = NP.
Proof. First, recall that clique is subset of vertices in an undirected graph such that there is an edge between every pair of its vertices. Håstad [28] and Zuckerman [64] showed that the maximum clique problem does not admit an - aapproximation for any constant O, unless NP = This implies that there is no constant-factor approximation algorithm for maximum clique. In other words, for any constant < 5 < there exists graph and threshold integer value i such that NP-hard to distinguish between the following two cases:
YES instance: graph G has clique of size k.
NO instance: graph G does not have clique of size greater than dk:
We reduce this instance of the maximum clique decision problem MDMS with objective function (2) as follows. Represent each vertex of graph G with a point in our ground set. The distance between pair of points 2 if there an edge between their corresponding vertices in G, and
otherwise.
Use the same threshold value of & (in the YES and NO instance above) for the cardinality constraint later in the proof. We
on S, and each weight w((v) a/s for some parameter that also set À = 1 a. In YES instance, selecting clique of size k as set S results in the maximum possible value of the objective:
OPT a k
k (1 a) 2 = 2 a.
(11)
17

---

In NO instance, the best objective value that can be achieved in polynomial-ting time is the maximum of the following two scenarios: (a) selecting k points with minimum distance or (b) selecting at most Åk vertices forming clique with minimum distance 2. The maximum value obtained by any polynomial-time algorithm is then
ALG max + (1-a) a, d + (1 (1- -01- a) -2
max 1, 2 ()a}
We make these two terms equal by setting a = 1/(2- any algorithm achieve in the NO case and the optimum value in the YES case is
-26. 8). Thus, the gap between the maximum value
1
2
-
1/(2 6)
3 25
To complete the proof, it suffices to show that the ratio above is at most 2/33 We separate the 2/s term as follows:
2 5 5 2/3- (3- (3- 8/3 2
8
28
28
3
65
Therefore, we must choose value of ā satisfying $/19 66) S e. Since s 1, the denominator 9 66 is positive. Equivalently, we want to satisfy:
9
1 E
6
By setting 8 < 91 6ε), we satisfy the required incquality and achieve the inapproximability gap the theorem statement.
D.3 Proof of Lemma 4.4
Let G = (V, E) be a simple undirected graph. Our goal is to embed the vertices of V into Rd for some d > 1, in way that encodes the adjacency structure of G. Concretely, want construct function hG V - R such that:
(h)(u) - ho(u)]l2 if (u.v) & E, and
(lo(u)) - ha(vlle - - sa if {u, v) E E,
for the largest possible value of EG E (0.
Construction. Let n = |V] and m = E Augment G by adding a self-loop to each node to get = (V, E'). We embed V using G' since each node now has positive degree. Let deg' be the degree of u in G' and N' (v) be the neighborhood of u in G'.
Define total ordering on E' (e.g.. lellcoraaaaay by sorted endpoints {u, v)). Each edge E E' corresponds an index in the embedding dimension JE'| = m +.. We consider the embedding function that acts as degree-normalizer adjacency vector:
i
ha(v),
2 (F)
(12)
if v ge.
Lemma 4.4. Let G = (V,E) be a simple undirected graph with n = [V] m = [E), and max
degree A. There exists embedding he V - n+m such that if {u, v E E then
[[ha(u) - hoo
2(A+1)
and if (u, v) of E then (1) ha(v)]l2 =
18

---

Proof. If {u, o/ & E, then we have
2
-0)
[ - 10(
E
+ Σ
0
2 deg (u)
deg (v)
cEN(U)
(EN'(v)
Σ
Σ
1
+
deg (u)
2
deg'
(v)
(E)
cEN'(o)
1
2
1.
This follows because the only index where both embeddings can be nonzero is {u, v), if it exists. Now suppose that fu, e) E. It follows that
[1a((u) - hb(v)l
(v
E
E
22 (V2deg(u)
deg'(u) (E)
(o))(e) dog'(v)
2 (w)
deg' (u) -1 + deg'( (v) -1
1 2 2dc' (v)
1
2
V
2deg (u)
2 dec' (v)
2d
4 (u) dog'(v)
1 + 2 V
deg' (u) deg (v)
$ 1
A+1
The previous incquality follows from deg' (v) = deg(v) +1 + 1. For any æ E [0, 1], we have
VI - 1--51--3
I 2'
so it follows that
(ic(u))ha(t)lla S
<
A A+1
2(A
which completes the proof.
D.4
Proof of Theorem 4.5
Theorem 4.5. MDMS is APX-complete for the Euclidean metric if g is linear function.
Proof. We build the hardness of approximation for the maximum independent set problem for graphs with maximum degree A 3. Alimonti and Kann [4, Theorem 3.2] showed that this problem is APX-complete, there exists an Eg such that there is polynomial-time (1 60)- approximation algorithm unless NP = P. Hence, there exists graph G with max degree A = 3 and threshold integer value & such that NP-hard distinguish between the following two cases:
YES instance: graph has an independent set of size k.
NO instance: graph does not have an independent set of size greater than - (1-
We reduce this instance of bourded-degree maximum independent set to MDMS with objective function (2) as follows. Embed each node of the graph into Euclidean space using the function ho(w) in Lemma 4.4. We use the same threshold value of k (between YES and NO instances above) for the cardinality constraint on set S, and we set each weight w(e) = о/4 for some parameter a that set later in the proof. We also set X
19

---

In YES instance, selecting an independent set of size & as the set S results in the maximum value of objective (2):
OPT a k
k (1 a) 1=
since l ha (v)ll 1 for any two distinct points u, since there is no edge between and in graph G.
In NO instance, the best objective value that can be achieved in polynomial-time is the maximum of the following two scenarios: (a) selecting k points with minimum distance at most (21((((++1)
1 1-1/8, (b) selecting at most (1 -0)= vertices forming an independent with minimum distance equal to 1. The maximum value obtained by any polynomial-time algorithm is then
AL.G = max (a( - 5o) + (1 a)) 1,a + (1 (1 1188))
max 1 En a, (7 o)/8).
We make these two terms equal by setting o value any algorithm can achieve in the NO case and the optimum value in the YES case is upper bounded by
Therefore, the gap between the maximum
E0
- a= 1
=1 -1.
1/eo +
Since Eo is a constant, E1 := E0/(</eo + 8) is also a constant. This completes the proof of APX-completeness.
E
Additional details for Section 5
E.1
Synthetic dataset
We extend our comparison of baseline algorithms in Section 5.1 by sweeping over values of a, f in the objective function.
Figure 2: Baseline comparison with (0.85, 0.90, 0.95, 1.00) and 0.75.
C-1
Figure 3: Baseline comparison with 0.95 and 8 E (0.60, 0.70, 0.80, 0.90).
E.2 Image classification
Hyperparameters for ImageNet classification. We generate predictions and embeddings for all points using coarsely-traines ResNet-56 model [29] trained on a random 10% subset of Im- ageNet [54]. We use SGD with Nesterov momentum 0.9 with 450/90 epochs. The base learning rate 1, and reduced by a tenth at 30, 69, and 80. We extract the penultimate layer features to produce 2048-dimensional embeddings of each image. We use the same hyperparameters as the original ResNet paper [29] with budgets and one-shot subset selection experiments designed in the same manner [49].
20

---

Rumning times. The end-to-ent running time is dominated by ImageNet model training, which takes more than a few hours even with accelerators (c.g.. GPU/TPU chips). The subset selection algorithms that use margin and submodular sampling range between 3-4 minutes per run an average. GIST subset selection is similar to the margin or submodular algorithms for given distance threshold d. By using parallelism for different d values, we can keep the GIST csumood subset selection runtime the same as the submod algorithm. In summary, the actual subset selection algorithm step is extremely fast (nearly negligible) compared to the ImageNet training time. Furthermore, we can exploit distributed submodular subset selection algorithms that can even handle billions of data points efficiently [15].
21

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract and introduction are short summaries of the results in our paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results It is fine to include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
be expected to generalize other settings.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: state that the theoretical analysis of the approximation guarantees are for the well-studied worst-case analysis framework. For the hardness results, we state the underlying computational complexity assumptions. For empirical results, we describe our findings about the specific experiments
and do not generalize claims beyond those.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
22

---

Answer: [Yes]
Justification: We provide the complete proof' of the approximation guarantee of our algo- rithm and the hardness results, including the underlying computational complexity assump- tions.
Guidelines:
The answer NA means that the paper does not include theoretical results,
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: The pseudocode for GIST is provided in Algorithm along with the necessary experimental settingshhperpprameeees in Section
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
23

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: The experimental setup and hyperparameters are provided in Section 5 and Appendix E.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please the NeurlPS code and data submission guidelines (https://nips.cc/
stw.oddeuubimssoooooo...o. ssinioolicyyy for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //iis. cctpublic///cccccccccccccccccclc httg///id////eeuiuuee SoloodeSumisssionnee. swiiisolioyyyyy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Yes, provide exact dataset, model architecture, and hyperparameters for model training in Section 5 and Appendix E.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: The plot of ((S) for the random algorithm in Figure is just for trial highlight the non-moneen con-monotonicity of the objective function (as opposed to plotting the mean). The error bars for top-1 classification accuracies are provided in Table for all the algorithms considered: random, margin, k k-center, submod, EEST-margin, and GIST GIST-submod.
Guidelines:
The answer NA means that the paper does not include experiments.

---

The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [No]
Justification:
The experiments we present are medium size and can run a personal machine.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification:
The paper conforms with the Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: To the best of our knowledge, our work does not have negative societal impacts. The newly designed algorithms are for data summarization and data curation steps of the learning pipeline and are orthogonal to further tasks involved in socictal impacts.
25

---

Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The only data introduced in this paper is set of Gaussian points with uniform random weights.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification:
The owners of ImageNet [54] and ResNet-56 [29] are properly cited.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
26

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
If assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paper ayperswire thcode. com/ com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
The only asset introduced is set of Gaussian points with uniform random weights. We standard NumPy setup to generate these points and weights with seed 0. Moreover, we expect the results to hold for any seed by concentration.
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/codeemmodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and sereenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
27

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this paper does not involve LLMs as any important, original, non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy (ht petttp::/neurips. /tterrppp..cccooffeeeee//////// for what should or should not be described.
28


Reviews:
[{"review_id": "iyFR7qYRFG", "reviewer": "Reviewer_t8m7", "summary": "This paper proposes and develops algorithms for an optimization problem where we maximize a monotone submodular function plus a weighted diversity function. This formulation should capture applications such as data summarization where we not only seek coverage (with the monotone submodular function), but also diversity (through the weighted diversity function). In particular, they consider a max-min diversification term for the second part of the funciton. This objective is not submodular, so novel algorithms must be proposed. While related objectives have been studied several times (e.g. [13]), their particular objective has not been.\n\nThey develop the algorithm GIST, which is a 1/2 approximation algorithm. GIST is simple, in fact it looks like they are making guesses of the maxmin distance and running greedy algorithms for each of those guesses. In addition, they develop hardness of approximation results for their novel problem, and several other results for the special case of linear submodular functions. Finally, an experimental section is included where alternative baselines are compared to GIST.", "questions": "- See weaknesses above", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths\n- They propose a novel optimization problem which seems to have applications.\n- Novel algorithms are developed with constant factor approximation guarantees.\n- They have a hardness result for their problem.\n- They have an experimental section to back up their theoretical claims.\n\nWeaknesses\n- I am unclear about how this new optimization problem is beneficial over existing formulations that capture both coverage and diversity. In particular, within non-monotone submodular optimization, people have considered objectives such as Determinantal Point Processes (DPP) [1] in order to get diverse sets. If we were to take a monotone submodular function and add a weighted functions such as a DPP, then overall we would have a non-monotone submodular function that captures both coverage and diversity, and there exists many algorithms for this setting. What is the benefit to applications of the formulation in this paper over this alternative one?\n- The development and analysis of GIST looks like it doesn't require a ton of theoretical novelty, it sort of reminds me of a combination of the greedy algorithm, the streaming algorithms in submodular optimization, and the doubling algorithm. But it appears new for this problem.\n\n[1]Kulesza, Alex, and Ben Taskar. \"Determinantal point processes for machine learning.\" Foundations and Trends® in Machine Learning 5.2–3 (2012): 123-286.", "was_revised": true, "final_justification": "I have read the rebuttal of the authors, as well as the other reviews. I maintain my opinion that the paper should be accepted.", "rebuttal": "Thank you for your supportive review and careful observations. Please see our answers to your questions below.\n\n> What is the benefit to applications of the formulation in this paper over a [non-monotone submodular DPP-based] alternative?\n\nWe agree that determinantal point processes (DPPs) are an effective method for modeling diversity, as they operate as log-submodular, non-monotone functions that capture the full range of interactions between selected items.\n\nOur work explores a valid alternative. We model diversity primarily through pairwise interactions, while higher-order effects are captured implicitly through the submodular term from the theoretical perspective. For our target applications, we observed that this pairwise approach was sufficient to achieve the desired level of diversity. We also note that with the scale of datasets these days, capturing higher-order interactions between points (beyond pairwise) is very challenging and makes the computational cost prohibitive unless very efficient algorithms are designed for the specific objectives, e.g., log-DPP plus submodular.\n\nA key distinction between these methods also lies in their theoretical approximation guarantees. Using a log-DPP term for diversity would render the objective non-monotone submodular (as you observed), restricting the best possible approximation guarantee to be at most $0.478$ subject to a cardinality constraint $k$ [1], unless a better approximation algorithm is designed specifically for this DPP-based objective. In contrast, `GIST` gives a $1/2$-approximation guarantee and designing an algorithm with a better than $1/2$-approximation for MDMS remains an interesting open question.\n\n> The development and analysis of GIST looks like it doesn't require a ton of theoretical novelty … but it appears new for this problem.\n\nWe believe the simplicity of GIST is an advantage, making it a more practical solution and accessible in a wider range of applications. We argue that the two-stage structure of the algorithm by \"guessing\" the target diversity (distance threshold) and optimizing based on that initial decision is crucial. We provide the following evidence to show that the standard `greedy` approach *fails to achieve any constant-factor approximation guarantee*.\nOur objective function $f$ is highly non-monotone since the diversity term can decrease as we add more items. Consequently, the standard `greedy` algorithm that adds the best item at each step while rejecting any item with a negative marginal gain, can have an arbitrarily poor performance.\n\nWe demonstrate this with a hard instance. Let the submodular part of the objective be $g(S) = |S|$. For the diversity component, define the distance between a specific pair $(u,v)$ to be $\\text{dist}(u, v) = 2 + 2 \\varepsilon$, while for all other pairs $(x,y) \\ne (u,v)$, we have $\\text{dist}(x, y) = 1 + \\varepsilon$. The `greedy` algorithm first selects set $\\{u, v\\}$, achieving a value of $f(\\{u,v\\}) = g(\\{u,v\\}) + \\text{dist}(u,v) = 4+2\\varepsilon$. The algorithm then terminates because adding any subsequent item gives a submodular gain of 1 but causes a diversity loss of $1 + \\varepsilon$, resulting in a negative marginal gain.\n\nAn optimal solution of size $k$, however, can achieve a value of at least $k$ from the submodular term alone. The resulting approximation ratio for `greedy` is therefore at most $(4 + 2\\varepsilon) / k$​, which approaches 0 as $k$ grows. Thus, `greedy` offers no constant-factor approximation guarantee.\n\n**References**\n\n[1] B. Qi. “On maximizing sums of non-monotone submodular and linear functions.” Algorithmica, 2024."}, {"review_id": "NRiNZdlda5", "reviewer": "Reviewer_syZ1", "summary": "This paper studies a novel subset selection problem named max-min diversification with monotone submodular utility, which can be applied in feature selection, recommendation systems, and data summarization. First, this paper formalizes the problem and presents a simple warm-up algorithm. Next, this paper presents the GIST algorithm and proves that a 1/2-approximation guarantee can be achieved. In the special case of linear utility functions, the approximation guarantee can be further improved to 2/3. This paper then demonstrates the hardness of this problem under various restrictions. Finally, this paper presents two experiments, one on synthetic data and the other on real-world data, to demonstrate its performance in various tasks, including data sampling.", "questions": "See weaknesses.", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\nS1. This is a comprehensive piece of work, comprising a warm-up algorithm, a formal algorithm, a substantial proof of approximation guarantee and harness, and experiments that demonstrate the algorithm's strengths. The lemmas and theorems in this paper are well-supported by theoretical proofs, and the algorithm is well-supported by sufficient experimental results. \n\nS2. The submission is clearly written and well organized. The proof process is clear enough for readers to understand its correctness. The experimental setting is described well, allowing readers to understand and potentially reproduce the results.\n\nS3. The topic and results are impactful for the community and society, as they address the diversity of data selection, and the algorithm can be implemented in many real-world applications with minimal expenses.\n\n**Weaknesses**\n\nW1. The analysis for the time complexity can be complemented in detail. For instance, Theorem 3.1 presents the time complexity of GIST, but the proof or demonstration is not included. \n\nW2. The experiments included in this paper are convincing enough, but comparing the running time between GIST and other traditional algorithms can further indicate the performance of the GIST algorithm.", "was_revised": true, "final_justification": "Thanks for the rebuttal. I will keep my score.", "rebuttal": "Thank you for your supportive review and articulating the strengths of our paper. Please see our answers to your questions below.\n\n> The analysis for the time complexity can be complemented in detail. For instance, Theorem 3.1 presents the time complexity of GIST, but the proof or demonstration is not included.\n\nThanks for catching the missing oracle query complexity analysis in the proof of Theorem 3.1. We will include it in the final version. It is essentially the number of distance thresholds that the algorithm tries times the query complexity of the `GreedyIndependentSet` subroutine.\n\n> The experiments included in this paper are convincing enough, but comparing the running time between GIST and other traditional algorithms can further indicate the performance of the GIST algorithm.\n\nThe end-to-end running time is dominated by training ImageNet models, which takes more than a few hours even with several accelerators (e.g., GPU/TPU chips). The subset selection algorithms that use margin and submodular sampling range between 3–4 minutes per run on an average. GIST subset selection is similar to the margin or submodular algorithms for a given distance threshold $d$. By using parallelism for different $d$ values, we are able to keep the `GIST-submod` subset selection runtime the same as the `submod` algorithm. In summary, the actual subset selection algorithm step is extremely fast (nearly negligible) compared to the ImageNet training time. It also runs on cheaper CPUs compared to ML accelerators. We will be happy to add these details in the final version."}, {"review_id": "jMQDrHDLuv", "reviewer": "Reviewer_tLCc", "summary": "The problem considered in this paper is to maximize a set function $f(S) = g(S) + \\lambda div(S)$ subject to $|S| \\le k$, where $g$ is a non-negative monotone submodular function and $div(S)$ is the minimum distance between two points in $S$. In data subset selection problems, $g(S)$ represents coverage of information of $S$, and $div(S)$ represents diversity of $S$. This paper proposes a clean $(0.5-\\epsilon)$-approximation algorithm with running time $O(n k \\epsilon^{-1} \\log(1/\\epsilon))$, while also providing an impossibility result of $0.5584$-approximation under P $\\neq$ NP assumption. In the special case of linear $g$, the proposed algorithm is $(2/3-\\epsilon)$-approximation and the impossibility result is tight. Another hardness result is the APX-completeness in the case of linear $g$ and Euclidean metric. The experimental result on data subset selection from ImageNet shows that the proposed method outperforms standard benchmarks (such as random selection and choosing data close to the margin) in terms of prediction accuracy.", "questions": "No question.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The algorithmic idea is simple and can be applicable to many other problems in the future. An important observation is that monotone submodular maximization with an independent set constraint has a bicriteria $1/2$-approximation algorithm. So if $div(S^*)$ for the optimal set $S^*$ is known in advance, $1/2$-approximation can be obtained. Since it is unknown, the proposed algorithm applies the bicriateria algorithm for multiple possible values of $div(S^*)$ and takes the maximal one.\n- It is nice to see the tight $(2/3+\\epsilon)$-approximation hardness result for linear $g$.\n- The experimental results are also very good. They show superiority of the proposed method not only in terms of the objective function, but also in terms of the prediction accuracy in data subset selection problems.\n\n---\nWeaknesses:\n- I have no concern.\n\n\n---\nTypos:\n- In the pseudocode Algorithm 1, the domain of $g$ should be $2^V$, not $V$.", "was_revised": true, "final_justification": "There is no specific change in my evaluation, and I keep my positive score.", "rebuttal": "Thank you for the supportive review and for catching the typo about the domain of $g$. We appreciate the careful read."}, {"review_id": "4qRnSBH454", "reviewer": "Reviewer_i9Xd", "summary": "The paper studies the min-distance variant of the submodular+diversification problem with a cardinality constraint. An iterative greedy algorithm (GIST) is proposed, and its approximation guarantees are analysed. The results are the paired with approximation hardness bounds. Experimental results indicates the utility of GIST in objective values and downstream performance in one-shot image classifcation (w. GIST acting as a sample selector).", "questions": "Line 591: do you mean \"the distance is 2 if there is NO edge\"?", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The contribution is significant as it gives a practical method for a problem relevant to the field of machine learning. As far as I know, this variant of the problem is studied for the first time in this paper.\n\nThe paper is mostly well-written. The contributions are clearly stated and met. The theoretical results are strong and comprehensive. The proofs are made easy to follow with the use of intuitive connection to graph-theoretical results. The findings give a narrow bound for the approximation factor.\n\nHowever, the baseline greedy heuristic is not examined (i.e, choosing $\\text{argmax}_{v}f(x|T)$). If there is a reason for this (e.g., no constant-factor approximation), it should be stated.\n\nSome comments regarding Section 5. It is not stated which value of the error term ($\\varepsilon$) is used for GIST in the experiments. Also, the results in Figure 1 would be more meaningful if normalized by f(OPT). Although, considering that these are random instances, the lack of best-known values is excusable. Finally, for the image classification task, statistical tests are called for since randomness is involved. The test procedure could be explained in Appendix.\n\nWhile the results on linear utility is interesting academically, this special case is not really relevant to the suggested applications of the problem (e.g., data sampling). Different directions that might be more relevant include specific distance metrics, or other types of constraints (an example of fairness constraints is mentioned).", "was_revised": true, "final_justification": "The rebuttals sufficiently addressed the comments, the most concerning of which refers to the novelty of the proposed method.", "rebuttal": "Thank you for your supportive review. Please see our answers to your questions below.\n\n> … the baseline greedy heuristic is not examined … If there is a reason for this (e.g., no constant-factor approximation), it should be stated.\n\nThe objective function $f$ is highly non-monotone since the diversity term can decrease as we add more items. Consequently, the standard `greedy` algorithm, which rejects any item with a negative marginal gain, can have an arbitrarily poor performance.\n\nWe demonstrate this with a hard instance. Let the submodular part of the objective be $g(S) = |S|$. For the diversity component, define the distance between a specific pair $(u,v)$ to be $\\text{dist}(u, v) = 2 + 2 \\varepsilon$, while for all other pairs $(x,y) \\ne (u,v)$, we have $\\text{dist}(x, y) = 1 + \\varepsilon$. The `greedy` algorithm first selects set $\\{u, v\\}$, achieving a value of $f(\\{u,v\\}) = g(\\{u,v\\}) + \\text{dist}(u,v) = 4+2\\varepsilon$. The algorithm then terminates because adding any subsequent item gives a submodular gain of 1 but causes a diversity loss of $1 + \\varepsilon$, resulting in a negative marginal gain.\n\nAn optimal solution of size $k$, however, can achieve a value of at least $k$ from the submodular term alone. The resulting approximation ratio for `greedy` is therefore at most $(4 + 2\\varepsilon) / k$​, which approaches 0 as $k$ grows. Thus, `greedy` offers no constant-factor approximation guarantee. Moreover, modifying `greedy` to accept items with negative marginal value does not solve this, as one can construct instances where an optimal solution's value is dominated by a diversity term that any $k$-sized set diminishes to zero. We will add this discussion about `greedy` to the paper for completeness.\n\n> While the results on linear utility is interesting academically, this special case is not really relevant to the suggested applications of the problem (e.g., data sampling).\n\nWe agree that using a linear utility could be too special in some cases. That said, it helps understand the theoretical landscape of the optimization problem and set of tractable objectives.\n\n> It is not stated which value of the error term ($\\varepsilon$) is used for GIST in the experiments.\n\nThis is an oversight on our end. Thank you for catching this.\n\nIn the warm-up synthetic experiments (Section 5.1), we set $D$ to be all possible pairwise distances since $n = 1000$. The running time is $O(nk \\cdot n^2)$ and the algorithm yields an exact $2/3$-approximation ratio.\n\nIn the image classification experiments (Section 5.2), we used $\\varepsilon = 0.05$. We will add these details to the paper.\n\n> Finally, for the image classification task, statistical tests are called for since randomness is involved. The test procedure could be explained in Appendix.\n\nWe followed the experimental setup in “Active learning for convolutional neural networks: A core-set approach” [Sener–Savarese, ICLR 2017] by reporting the mean and standard deviation over multiple trials to be backwards compatible with the literature. We will include the raw loss values from each trial in the appendix to increase transparency.\n\n> Line 591: do you mean \"the distance is 2 if there is NO edge\"?\n\nNo, \"the distance between a pair of points is 2 if there is an edge\" is the correct formulation because the YES instance in the hardness example has a clique of size $k$, e.g., $k$ vertices forming a complete subgraph and objective value in Eq. (11). Alternatively, one can phrase the NP-hard instance with independent sets instead of cliques; in this case, we should set distance to 2 when there is no edge."}]

Author rebuttal:

Meta-review: The paper introduces and studies a novel problem formulation for size-constrained subset selection where the goal is to maximize the sum of a monotone submodular function and a diversity function that captures the minimum distance between any two points in the chosen subset. The paper gives an algorithm for the problem that achieves a 1/2 approximation and it shows that the problem is NP-hard to approximate within a factor of 0.5584. The paper shows an improved approximation guarantee when the submodular function is linear and it provides an experimental evaluation to support the theoretical results. The reviewers appreciated the main contributions of the paper, including the novel problem formulation that provides a more tractable formulation that incorporates diversity, the strong theoretical guarantees established, and the experimental evaluation. The author response and the subsequent discussion sufficiently addressed the reviewers' questions and concerns. Overall, there was consensus among the reviewers that the paper meets the threshold for acceptance.
Decision: Accept (poster)