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

Thank you for your supportive review. Please see our answers to your questions below.

… the baseline greedy heuristic is not examined … If there is a reason for this (e.g., no constant-factor approximation), it should be stated.

The 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.

We 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.

An 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.

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).

We 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.

It is not stated which value of the error term ($\varepsilon$) is used for GIST in the experiments.

This is an oversight on our end. Thank you for catching this.

In 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.

In the image classification experiments (Section 5.2), we used $\varepsilon = 0.05$. We will add these details to the paper.

Finally, for the image classification task, statistical tests are called for since randomness is involved. The test procedure could be explained in Appendix.

We 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.

Line 591: do you mean "the distance is 2 if there is NO edge"?

No, "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.

Thank you for the supportive review and for catching the typo about the domain of $g$. We appreciate the careful read.

Thank you for your supportive review and articulating the strengths of our paper. Please see our answers to your questions below.

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.

Thanks 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.

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.

The 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.

Thank you for your supportive review and careful observations. Please see our answers to your questions below.

What is the benefit to applications of the formulation in this paper over a [non-monotone submodular DPP-based] alternative?

We 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.

Our 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.

A 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.

The development and analysis of GIST looks like it doesn't require a ton of theoretical novelty … but it appears new for this problem.

We 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. Our 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.

We 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.

An 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.

References

[1] B. Qi. “On maximizing sums of non-monotone submodular and linear functions.” Algorithmica, 2024.