Composable Coresets for Constrained Determinant Maximization and Beyond

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.