# Composable Coresets for Determinant Maximization: Greedy is Almost Optimal

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 23 references that are in the map.
- First posted on arXiv 26 Sep 2023.

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

- [Randomized Composable Core-sets for Distributed Submodular Maximization](https://mlsanity.com/paper/1506.06715/) (2015)
- [Streaming Non-monotone Submodular Maximization: Personalized Video Summarization on the Fly](https://mlsanity.com/paper/1706.03583/) (2017)
- [The Power of Randomization: Distributed Submodular Maximization on Massive Datasets](https://mlsanity.com/paper/1502.02606/) (2015)
- [Efficient Sampling for k-Determinantal Point Processes](https://mlsanity.com/paper/1509.01618/) (2015)
- [Randomized Rounding for the Largest Simplex Problem](https://mlsanity.com/paper/1412.0036/) (2014)
- [Composable Core-sets for Determinant Maximization: A Simple Near-Optimal Algorithm](https://mlsanity.com/paper/1907.03197/) (2019)
- [Large-Margin Determinantal Point Processes](https://mlsanity.com/paper/1411.1537/) (2014)
- [Composable Core-sets for Determinant Maximization Problems via Spectral Spanners](https://mlsanity.com/paper/1807.11648/) (2018)
- [Diversifying Sparsity Using Variational Determinantal Point Processes](https://mlsanity.com/paper/1411.6307/) (2014)

## Abstract (arXiv)

Given a set of n vectors in ℝd, the goal of the determinant maximization problem is to pick k vectors with the maximum volume. Determinant maximization is the MAP-inference task for determinantal point processes (DPP) and has recently received considerable attention for modeling diversity. As most applications for the problem use large amounts of data, this problem has been studied in the relevant textitcomposable coreset setting. In particular, [Indyk-Mahabadi-OveisGharan-Rezaei--SODA'20, ICML'19] showed that one can get composable coresets with optimal approximation factor of tilde O(k)k for the problem, and that a local search algorithm achieves an almost optimal approximation guarantee of O(k)2k. In this work, we show that the widely-used Greedy algorithm also provides composable coresets with an almost optimal approximation factor of O(k)3k, which improves over the previously known guarantee of Ck2, and supports the prior experimental results showing the practicality of the greedy algorithm as a coreset. Our main result follows by showing a local optimality property for Greedy: swapping a single point from the greedy solution with a vector that was not picked by the greedy algorithm can increase the volume by a factor of at most (1+√k). This is tight up to the additive constant 1. Finally, our experiments show that the local optimality of the greedy algorithm is even lower than the theoretical bound on real data sets.