Research map / Learning theory and algorithms / Submodular and game algorithms

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

NeurIPS 2025 · Learning theory and algorithms › Submodular and game algorithms · approach: Streaming submodular algorithms · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes GIST, a threshold-sweeping bicriteria greedy algorithm for max-min diversification with monotone submodular utility, giving a 1/2-approximation, a 0.5584 hardness bound, and improved 2/3 results for linear utility, with ImageNet data-sampling experiments.

Problem

Selecting a size-at-most-k subset that maximizes a monotone submodular utility plus a max-min diversity term (min pairwise distance) in a metric space.

Approach

Sweep over distance thresholds d and run a greedy maximal independent set routine on the intersection graph at each threshold (greedy submodular selection subject to pairwise distance >= d), returning the best solution; this yields a bicriteria guarantee that gives a 1/2-approximation for the joint objective.

Key results

• GIST achieves a 1/2-approximation for MDMS (and 2/3 for linear utility), with NP-hardness of approximation within 0.5584.
• On ImageNet at 30% budget, GIST-submod reaches 67.24% top-1 vs 66.23% for random and 66.71% for k-center.
• On synthetic data GIST dominates simple, greedy, and random for all k, while greedy performs poorly for k >= 100.

Measured effects reported in the paper

Surprising findings

• The standard greedy algorithm has no constant-factor approximation guarantee for the joint objective f, since the diversity term can drop when items are added.
• The objective f is not submodular, so classic submodular guarantees do not apply directly.

Limitations

• Gap between the 0.5 approximation and the 0.5584 hardness remains open.
• ImageNet experiments use a small ResNet-56 and a single embedding-based pipeline, with gains of about 1 point over baselines in places.
• GIST requires sweeping many distance thresholds, giving O(nk log(1/eps)/eps) style oracle cost.

Experimental setup

Datasets: ImageNet synthetic Gaussian points with uniform weights

Benchmarks: ImageNet

Metrics: top-1 accuracy objective value f(S)

Baselines: random simple 0.387-approximation greedy margin sampling k-center submod

Builds on: greedy k-center 2-approximation submodular greedy (Nemhauser et al.) margin sampling max-sum diversification

Closest papers by meaning

• Streaming Robust Submodular Maximization: A Partitioned Thresholding Approach (NeurIPS 2017 · similarity 0.87)
• Weakly Submodular Maximization Beyond Cardinality Constraints: Does Randomization Help Greedy? (ICML 2018 · similarity 0.87)
• Non-monotone Submodular Maximization with Nearly Optimal Adaptivity and Query Complexity (ICML 2019 · similarity 0.87)
• Joint M-Best-Diverse Labelings as a Parametric Submodular Minimization (NeurIPS 2016 · similarity 0.86)
• Multinoulli Extension: A Lossless Yet Effective Probabilistic Framework for Subset Selection over Partition Constraints (ICML 2025 · similarity 0.86)
• Practical $0.385$-Approximation for Submodular Maximization Subject to a Cardinality Constraint (NeurIPS 2024 · similarity 0.85)