Introducing GIST: The Next Stage in Smart Sampling | Google Research

GIST is a data-subset selection algorithm designed to balance diversity and utility when training on massive datasets. It converts the difficult diversity–utility optimization problem into a series of thresholded graph problems and uses a bicriteria greedy strategy to find a high-quality subset efficiently. The algorithm guarantees at least half the value of the optimal solution, while the authors prove that improving beyond a 0.56 approximation is NP-hard.

Why Smart Sampling Is Difficult

• Large ML systems need to process datasets that are increasingly expensive to store, analyze, and train on.
• Subset selection aims to choose a smaller but representative set of examples.
• Diversity prevents redundant selections by maximizing the minimum distance between selected points, typically in embedding space.
• Utility measures how much relevant or unique information the subset provides, modeled using monotone submodular functions.
• Optimizing both objectives simultaneously is NP-hard:
  • A diversity-only method may select irrelevant examples.
  • A utility-only method may select many similar examples from one highly relevant cluster.

How GIST Works

Diversity Thresholding

• GIST fixes a candidate minimum distance rather than optimizing the distance directly.
• It builds a graph in which two data points are connected when they are closer than the chosen threshold.
• Connected points are considered too similar to coexist in the selected subset.
• Selecting points that are not connected enforces the desired spacing between examples.

Utility-Constrained Independent Sets

• For each threshold, GIST seeks a high-utility independent set: a group of points with no edges between them.
• This corresponds to selecting valuable examples without choosing mutually conflicting or overly similar points.
• Because maximum independent set is NP-complete and lacks practical general-purpose approximation algorithms, GIST uses a specially designed bicriteria greedy method.
• The algorithm repeatedly selects high-scoring points and excludes nearby candidates, effectively creating “no-go zones” around selected data.

Searching Across Thresholds

• GIST evaluates all relevant distance thresholds derived from the dataset.
• It greedily constructs a candidate subset for each threshold.
• It returns the best candidate found across these runs.
• If the optimal solution achieves minimum distance (d), GIST obtains comparable utility while guaranteeing a minimum distance of roughly (d/2).

Theoretical Guarantees

• GIST is presented as the first algorithm with a strong provable guarantee for this diversity–utility tradeoff.
• Its output has at least half the value of the absolute optimum.
• The authors also prove that finding a solution worth more than 0.56 of the optimum is NP-hard.
• These results provide a mathematical guarantee that GIST is not merely producing empirically good subsets, but making a bounded tradeoff between informativeness and coverage.

Practical Evaluation

• GIST was evaluated against several common subset-selection approaches in ML applications.
• Comparisons included:
  • Random, a simple baseline that often provides reasonable diversity.
  • Margin, which selects examples the model is uncertain about but does not explicitly promote diversity.
  • k-center, which minimizes representation gaps by keeping all data points close to a selected representative.
  • Submod, which combines utility with an older formulation of diversity.
• The experiments, including image-classification benchmarks, reportedly show that GIST outperforms state-of-the-art alternatives while retaining formal guarantees.

GIST is therefore a practical choice when subset selection must preserve both broad data coverage and task relevance. Its main advantage is combining competitive real-world performance with a clear approximation guarantee, rather than relying solely on heuristic results.