# GPU-Accelerated Optimizer-Aware Evaluation of Submodular Exemplar Clustering

arXiv: https://arxiv.org/abs/2101.08763 · HTML: https://mlsanity.com/paper/2101.08763/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 26 references that are in the map.
- First posted on arXiv 21 Jan 2021.

## Builds on (most cited first, 4 of 4)

- [Streaming Non-monotone Submodular Maximization: Personalized Video Summarization on the Fly](https://mlsanity.com/paper/1706.03583/) (2017)
- [Submodular Streaming in All its Glory: Tight Approximation, Minimum Memory and Low Adaptive Complexity](https://mlsanity.com/paper/1905.00948/) (2019)
- [Beyond 1/2-Approximation for Submodular Maximization on Massive Data Streams](https://mlsanity.com/paper/1808.01842/) (2018)
- [Very Fast Streaming Submodular Function Maximization](https://mlsanity.com/paper/2010.10059/) (2020)

## Built on by (most cited first, 1 of 1)

- [Scalable Submodular Policy Optimization via Pruned Submodularity Graph](https://mlsanity.com/paper/2507.13834/) (2025)

## Abstract (arXiv)

The optimization of submodular functions constitutes a viable way to perform clustering. Strong approximation guarantees and feasible optimization w.r.t. streaming data make this clustering approach favorable. Technically, submodular functions map subsets of data to real values, which indicate how "representative" a specific subset is. Optimal sets might then be used to partition the data space and to infer clusters. Exemplar-based clustering is one of the possible submodular functions, but suffers from high computational complexity. However, for practical applications, the particular real-time or wall-clock run-time is decisive. In this work, we present a novel way to evaluate this particular function on GPUs, which keeps the necessities of optimizers in mind and reduces wall-clock run-time. To discuss our GPU algorithm, we investigated both the impact of different run-time critical problem properties, like data dimensionality and the number of data points in a subset, and the influence of required floating-point precision. In reproducible experiments, our GPU algorithm was able to achieve competitive speedups of up to 72x depending on whether multi-threaded computation on CPUs was used for comparison and the type of floating-point precision required. Half-precision GPU computation led to large speedups of up to 452x compared to single-precision, single-thread CPU computations.