# Composable Coresets for Constrained Determinant Maximization and Beyond

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Nov 2022.

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

- [Core-sets for Fair and Diverse Data Summarization](https://mlsanity.com/paper/2310.08122/) (2023)

## Abstract (arXiv)

We study algorithms for construction of composable coresets for the task of Determinant Maximization under partition constraint. Given a point set Vsubset ℝd that is partitioned into s groups V1,cdots, Vs, and integers k1,...,ks, where k=sumi ki, the goal is to pick ki points from group Vi such that the overall determinant of the picked k points is maximized. Determinant Maximization and its constrained variants have gained a lot of interest for modeling diversity, and have found applications in the context of data summarization. When the cardinality k of the selected set is greater than the dimension d, we show a peeling algorithm that gives us a composable coreset of size kd with a provably optimal approximation factor of dO(d). When k≤ d, we show a simple coreset construction with optimal size and approximation factor. As a further application of our technique, we get a composable coreset for determinant maximization under the more general laminar matroid constraints, and a composable coreset for unconstrained determinant maximization in a previously unresolved regime. Our results generalize to all strongly Rayleigh distributions and to several other experimental design problems. As an application, we improve the runtime of the practical local-search based algorithm of [Anari-Vuong--COLT'22] for determinantal maximization under partition constraint from O(n2sk2s) to O(n k2s), making it only linear on the number of points n.