# Composable Coresets for Constrained Determinant Maximization and Beyond

Sepideh Mahabadi  Microsoft<EMAIL_ADDRESS>Thuy-Duong Vuong
Stanford University<EMAIL_ADDRESS>
(February 2022)

###### Abstract

We study the task of determinant maximization under partition constraint, in
the context of large data sets. Given a point set $V\subset{\mathbb{R}}^{d}$
that is partitioned into $s$ groups $V_{1},\cdots,V_{s}$, and integers
$k_{1},...,k_{s}$ where $k=\sum_{i}k_{i}$, the goal is to pick $k_{i}$ points
from group $i$ 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 fairness and data summarization.

We study the design of composable coresets for the constrained determinant
maximization problem. Composable coresets are small subsets of the data that
(approximately) preserve optimal solutions to optimization tasks and enable
efficient solutions in several other large data models including the
distributed and the streaming settings. In this work, we consider two regimes.
For the case of $k>d$, we show a peeling algorithm that gives us a composable
coreset of size $kd$ with an approximation factor of $d^{O(d)}$. We complement
our results by showing that this approximation factor is tight. For the case
of $k\leq d$, we show that a simple modification of the previous algorithms
results in an optimal coreset verified by our lower bounds.

Further, we extend the above results in two directions: In particular, first
we extend the result to all strongly Rayleigh distributions, and several other
experimental design problems. Second, we show coreset construction algorithms
under the more general laminar matroid constraints. Moreover, our approach
provides a generalization of the directional height lemma of [Indyk-Mahabadi-
OveisGharan-Rezaei–ICML’19], and also the exchange inequality lemma of [Anari-
Liu-OveisGharan-Vinzant-Vuong–STOC’21]. Finally, as an application of our
result, we improve the runtime of the algorithm for determinantal maximization
under partition constraint in the recent work of [Anari-Vuong–COLT’22] from
$O(n^{2^{s}}k^{2^{s}})$ to $O(n{\operatorname{poly}}(k)),$ making it only
linear in the number of points $n$.

##  1 Introduction

Given a set of $n$ vectors $V=\\{v_{1},\cdots,v_{n}\\}$ in ${\mathbb{R}}^{d}$,
and a parameter $k$, the goal of the _determinant maximization_ problem is to
choose a subset $S\subseteq V$ of $k$ vectors such $\det(\sum_{v\in
S}v_{i}v_{i}^{\top})$ is maximized. Geometrically, if $k\leq d$, this
determinant is equal to the volume squared of the parallelepiped spanned by
the points in $S$. The best approximation factor for the problem in this
regime is due to the work of [Nik15] who shows a factor of $e^{k}$, and it is
known that an exponential dependence on $k$ is necessary [CM13]. On the other
hand if $k>d$, the problem is known as the D-optimal design problem, and the
best known approximation algorithm for it achieves a factor of
$\min\\{e^{k},(\frac{k}{k-d})^{d}\\}$, which is always at most $\leq 2^{d}$
and becomes a constant when e.g. $k\geq d^{2}$ [Mad+19]. Determinant
maximization and its variants have applications in computational geometry,
experimental design, machine learning, and data summarization. In particular,
the determinant of a subset of points is one way to measure the diversity of
the subset, and thus they have been studied extensively over the last decade
in this context [MJK17, Gon+14, KT+12, Cha+15, KT11, Yao+16, Lee+16].

The determinant maximization as well as other diversity maximization problems
have been considered under partition and more generally matroid constraints
[Mad+20, NS16, AMT13, MMM20, Add+22]. In the simpler case of partition
constraint, the data set $V$ is partitioned into $s$ groups
$V_{1},\cdots,V_{s}$ and we are provided with $s$ numbers
$k_{1},\cdots,k_{s}$, and the goal is to pick $k_{i}$ points from group $i$
such that the overall determinant (or more generally diversity) of the chosen
$k=\sum_{i}k_{i}$ points is maximized. This can be used to control the
contribution of each group in a summary: e.g. bound the number of movies from
each genre in a recommendation system, and has further applications in the
context of fair data summarization. More generally, given a matroid
$([n],\mathcal{I})$ of rank $k$, the problem of finding a basis of the matroid
that maximizes the determinant admits a $\min\\{k^{O(k)},O(d)^{d^{3}}\\}$
approximation, and it improves to
$\min\operatorname{}\mathopen{}\\{e^{O(k)},d^{O(d)}\mathclose{}\\}$ for the
estimation problem when the goal is to only estimate the value of the optimal
solution [Mad+20, NS16, Bro+22].

As most applications of determinant maximization needs to deal with large
amounts of data, there has been a large body of work on solving this problem
in large data models of computation [MJK17, WIB14, Pan+14, Mir+13, Mir+15,
MZ15, Bar+15]. One such strong model that we focus on in this work, is
composable coreset. Coreset is generally defined as a small subset of the data
that approximately preserves the optimal solution to an optimization problem
[AHV+05]. Composable coresets [Ind+14] are coresets with an additional
composability property: union of multiple coresets should contain a good
solution for the union of the original data sets (see Section 2.3 for a formal
definition). Having a composable coreset for an optimization task
automatically gives a solution for the same task in several massive data
models including distributed/parallel algorithms and streaming algorithms.

Composable coresets have been designed for determinant maximization problem,
where for $k\leq d$, one can get an $k^{O(k)}$\- approximate coreset of size
$O(k)$ which is also known to be tight [Ind+20, Mah+19]. Further for $k\geq
d$, if the solution is allowed to pick vectors from $V$ with repetition, then
one can get a coreset of size $\tilde{O}(d)$ with an approximation factor of
$\tilde{O}(d)^{d}$. In this work we study construction of coresets for
constraint determinant maximization in the remaining setting of “without
repetition", as well as getting coresets for the problem in all regimes under
the partition and laminar matroid constraints.

###  1.1 Our results

In this work, we show efficient construction of composable coreset for
determinant maximization under partition and laminar matroid constraints as
shown in Table 1, and verified in Theorem 28. Our results hold more generally
for Strongly Rayleigh distributions (see Theorem 26), and are obtained via
showing an improved exchange inequality for determinant when $k>d.$

| size | approximation | condition | reference
---|---|---|---|---
$k\leq d$ | $\tilde{O}(k)$ | $\tilde{O}(k)^{2k}$ | cardinality | [Ind+20, Mah+19]
$k\geq d$ | $\tilde{O}(kd)$ | $\tilde{O}(d)^{2d}$ | cardinality (with repetition) | [Ind+20]
$k\geq d$ | $kd$ | $d^{2d}$ | cardinality (without repetition) | This work
$k\leq d$ | $sk$ | $k^{2k}$ | partition | This work
$k\geq d$ | $kd$ | $d^{2d}$ | partition | This work
$k\leq d$ | $k^{2k}$ | $k^{2k}$ | laminar | This work
$k\geq d$ | $(kd)^{k}$ | $d^{2d}$ | laminar | This work
Table 1: The table shows our upper bound results on composable coresets for
determinant maximization. Here $s$ is the number of groups in the partition
constraints. Note that the third row follows from our results on partition
constraint but we spell it out to compare to the previous result.

In Theorem 31, we further show application of our results to get composable
coresets for other experimental design problems in the “without repetition"
settings for all regular objective functions (this generalizes [Ind+20]’s
result for experimental design in the with replacement setting).

We complement our results with the following lower bounds that are shown in
Section 6.

  * •

We show (in Lemma 32) that for $k\leq d$, any composable coreset for the
problem under partition constraint that has finite approximation factor, must
have size at least $\Omega(sk)$. This shows that our results on partition
constraint is essentially tight. This is because our approximation factor
matches that of [Ind+20] for the unconstrained version of the problem which is
known to be tight.

  * •

We show (in Lemma 33) that for $k\geq d$, any composable coreset with a finite
approximation factor must have a size of at least $k+d(d-1)$.

  * •

Lastly, we show (in Theorem 35) that for $d\leq k\leq{\operatorname{poly}}(d)$
and coreset of size polynomial in $k,$ the approximation of $d^{O(d)}$ is
essentially the best possible.

Finally, we show application of our results to the recent result of [AV21] for
determinant maximization under partition constraint and improve its runtime
from $O(n^{2^{s}}k^{2^{s}})$ to $O(n{\operatorname{poly}}(k)),$ making it only
linear in the number of points $n$ (see Lemma 29).

###  1.2 Overview of the techniques

Le us give a brief overview of our approach. As mentioned earlier, for $k\leq
d$, the determinant of any subset $T\subseteq V$ of $k$ selected vectors,
i.e., $\det(\sum_{v\in T}vv^{\intercal})$ corresponds to the (square of) the
volume spanned by vectors in $T$. [Mah+19] shows that in this case, any local
maximum $U\subseteq V$ of size $k$ for the $\det(\cdot)$ approximately
preserves the $k$-directional height of the vectors $V$, meaning that for any
set $S\subset{\mathbb{R}}^{d}$ of $k$ vectors and any $v\in S\cap V,$ one can
replace $v$ with some $u$ in $U$ so that the distance $d(u,\mathcal{H})$ from
$u$ to the $(k-1)$-dimensional subspace $\mathcal{H}$ spanned by
$S\setminus\operatorname{}\mathopen{}\left\\{v\mathclose{}\right\\}$ is at
least $\frac{1}{k}$ the distance from $v$ to $\mathcal{H},$ thus

$k\det(uu^{\intercal}+\sum_{w\in
S\setminus\operatorname{}\mathopen{}\left\\{v\mathclose{}\right\\}}ww^{\intercal})\geq\det(\sum_{w\in
S}ww^{\intercal}).$

This immediately implies that $U$ is also a $k^{O(k)}$ composable coreset
w.r.t $\det(\cdot)$ [[, see]for details]mahabadi2019composable. We generalize
the notion of directional height to the setting when $k\geq d,$ by showing
that for $U$ of size $d$ being a local maximum w.r.t. $\det(\cdot)$, then for
$S\subset{\mathbb{R}}^{d}$ of size $k$ and $v\in S\cap V$, there exists $u\in
U$ s.t.

$\det(duu^{\intercal}+\sum_{w\in
S\setminus\operatorname{}\mathopen{}\left\\{v\mathclose{}\right\\}}ww^{\intercal})\geq\det(\sum_{w\in
S}ww^{\intercal}).$

This already implies that $U$ is a composable coreset for determinant
maximization in the with repetition setting, i.e., when the selected subset is
allowed to be a multi-set. However, for the without repetition setting, we
need to additionally ensure that
$(S\setminus\operatorname{}\mathopen{}\left\\{v\mathclose{}\right\\})\cup\operatorname{}\mathopen{}\left\\{u\mathclose{}\right\\}$
is a proper subset, i.e., $u\not\in
S\setminus\operatorname{}\mathopen{}\left\\{v\mathclose{}\right\\}.$ We apply
the idea of peeling coreset, which was previously applied to construct robust
coresets, i.e., coresets that can handle outliers [AHY08, Abb+13]. Our
construction repeatedly peels away local optimum solutions from the input set,
and takes the union of all the peeled local optimums to be the final coreset.
By pigeon hole principle, this ensures that any given set $S$ who is not
contained in the coreset must have no intersection with at least one of the
peeled-away local optimums, thus we can replace an element of $S$ by an
element inside this local optimum without creating a multiset.

For determinant maximization under partition matroid constraint, our coreset
construction is simple and intuitive when $k\leq d$: it is the union of the
coresets for each part of the partition constraint. For $k\geq d,$ we obtain a
coreset of size $kd$ and approximation factor $d^{O(d)}$ by letting the
coreset to be the union of the peeling coresets for each part $P_{i}$ of the
partition.

For the laminar matroid constraint case, we apply the peeling coreset idea to
ensure that for any subset $S$ satisfying the laminar constraint, there exists
one peeled-away subset $U$ s.t. replacing an element of $S$ by an element of
$U$ will not violate the laminar constraint.

Our construction also applies to the experimental design problem with respect
to other objective functions. When replacing the base-level building blocks,
i.e., the local optimum w.r.t $\det(\cdot)$, in our construction with spectral
spanners [Ind+20], we can ensure that the (union of) the coresets contains a
feasible fractional solution as a combination of input vectors that achieves a
good value. However, the algorithm to round the fractional solution to an
integral solution under matroid constraint only exists in limited cases for
objective function other than the determinant.

For lower bound on the size of composable coreset for determinant maximization
under partition constraint, for $k\leq d$, we show that any coreset that
achieves a finite approximation factor needs to contain at least $k$ vectors
in each part of the partition. For $k\geq d$, we show an analogous result,
that any coreset that achieves finite approximate factor needs to contain at
least $d$ vectors in at least $d$ parts of the partition. The proof that the
approximation factor of $d^{O(d)}$ is the best possible when $k\geq d$ is
similar to [Ind+20]’s proof for the case $k\leq d.$

##  2 Preliminaries

Let $[n]$ denote the set
$\operatorname{}\mathopen{}\left\\{1,\cdots,n\mathclose{}\right\\}.$ For a set
$U,$ we use $\binom{U}{k}$ to denote the family of all size-$k$ subsets of
$U.$ For a matrix $L\in{\mathbb{R}}^{n\times n}$ and $S\subseteq[n]$, we use
$L_{S}$ to denote the principal submatrix of $L$ whose rows and columns are
indexed by $S.$ For sets $U,W,$ we use $U+W$ and $U-W$ to denote $U\cup W$
(union) and $U\setminus W$ (set-exclusion) respectively. For singleton
subsets, we abuse notation and write $U-e$ ($U+e$ resp.) for
$U-\operatorname{}\mathopen{}\left\\{e\mathclose{}\right\\}$
($U+\operatorname{}\mathopen{}\left\\{e\mathclose{}\right\\}$ resp.).

We use $\mathbb{S}_{d}^{+}$ to denote the set of all positive semi-definite
symmetric matrices in ${\mathbb{R}}^{d\times d}.$

######  Definition 1 (Local optima).

For a function $\mu:\binom{[n]}{k}\to{\mathbb{R}}_{\geq 0}$ and $\zeta\geq 1$,
we say $U$ is an $\zeta$-approximate local optima of $\mu$ iff
$\zeta\mu(U)\geq\max_{e\in U,f\in[n]\setminus U}\mu(U-e+f).$

When $\zeta=1,$ we simply refer to $U$ as a local optima.

###  2.1 Matroids

We say a family of sets $\mathcal{B}\subseteq\binom{[n]}{k}$ is the family of
bases of a matroid if $\mathcal{B}$ satisfies the basis exchange axiom: for
any two bases $B_{1},B_{2}\in\mathcal{B}$ and $x\in B_{1}\setminus B_{2},$
there exists $y\in B_{2}\setminus B_{1}$ such that $B_{1}-x+y\in\mathcal{B}.$
We call $k$ the rank of the matroid, and $[n]$ the ground set of the matroid.
We let the family of independent sets of the matroid be
$\mathcal{I}=\operatorname{}\mathopen{}\left\\{I\in
2^{[n]}\mathrel{}\mathclose{}\middle|\mathopen{}\mathrel{}\exists
B\in\mathcal{B}:I\subseteq B\mathclose{}\right\\}.$

The family $\binom{[n]}{k}$ of all size-$k$ subsets of $[n]$ form the set of
bases of the _uniform matroid_ of rank $k$ over $[n].$

We define two simple classes of matroids that are widely used in applications.

######  Definition 2 (Partition matroid).

Given a partition of $[n]$ into $P_{1},\cdots,P_{s}$ and integers
$k_{1},\cdots,k_{s},$ the associated partition matroid is defined by: a set
$I\subseteq[n]$ is independent iff $\operatorname{}\mathopen{}\lvert I\cap
P_{i}\mathclose{}\rvert\leq k_{i}$, for $\forall i\in[s].$ The rank of the
matroid is $k:=\sum_{i=1}^{s}k_{i}.$

######  Definition 3 (Laminar matroid).

A family $\mathcal{F}$ of subsets of $[n]$ is laminar iff for any
$F_{1},F_{2}\in\mathcal{F}$ either $F_{1}$ and $F_{2}$ are disjoint or $F_{1}$
contains $F_{2}$ or $F_{2}$ contains $F_{1}.$ Given a laminar family
$\mathcal{F}$ and integers $k_{F}$ for each $F\in\mathcal{F},$ the associated
laminar matroid is defined by: a set $I\subseteq[n]$ is independent iff
$\operatorname{}\mathopen{}\lvert I\cap F\mathclose{}\rvert\leq k_{S}$, for
$\forall F\in\mathcal{F}.$ The maximal independent sets have the same
cardinality $k,$ and they form the bases of the laminar matroid.

We assume that $k_{F}>0$, for $\forall F\in\mathcal{F},$ otherwise we can
remove the set $F$ from $\mathcal{F}$ and all elements in $F$ from the ground
set. For two sets $F_{1},F_{2}$ in $\mathcal{F}$ s.t. $F_{1}\subseteq F_{2},$
we can assume $k_{F_{2}}>k_{F_{1}},$ otherwise the constraint on $I\cap F_{1}$
is redundant and $F_{1}$ can be removed from the laminar family. We call such
a laminar family _non-redundant_.

###  2.2 Determinant maximization and experimental design problems

Given vectors $v_{1},\cdots,v_{n}\in{\mathbb{R}}^{d}$ and a parameter $k,$
determinantal point processes (DPPs) samples a size-$k$ subset $S$ of $[n]$
s.t.

$\operatorname{\mathbb{P}}\mathopen{}[S\mathclose{}]\sim\det(\sum_{i\in
S}v_{i}v_{i}^{\intercal}).$

This distribution favors diversity, since sets of vectors that are different
from each other are assigned higher probabilities. The fundamental
optimization problem associated with DPPs, and probabilistic model in general,
is to find a "most diverse" subset by computing
$\arg\max_{S}\operatorname{\mathbb{P}}\mathopen{}[S\mathclose{}]$ i.e. solving
the maximum a priori (MAP) inference problem.

When $k\leq d$, $\operatorname{\mathbb{P}}\mathopen{}[S\mathclose{}]$ is
proportional to the squared volume of the parallelepiped spanned by the
elements of $S,$ thus MAP-inference for DPPs is also known as the volume
maximization problem.

#### Experimental design

In the experimental design problem (under matroid constraint), we are
additionally given a matroid $\mathcal{M}=([n],\mathcal{I})$ with set of bases
$\mathcal{B},$ and the goal is to find a set $S\in\mathcal{B}$ so that
$\sum_{i\in S}v_{i}v_{i}^{\intercal}$ optimizes a given objective function
$f:\mathbb{S}_{d}^{+}\to{\mathbb{R}}.$ When the matroid constraint is the
uniform matroid we simply refer to the problem as experimental design under
cardinality constraint, or simply the experimental design problem. The most
popular and well-studied objective functions include:

  * •

D(eterminant)-design: $f(A)=\det(A)^{1/d}.$

  * •

A(verage)-design: $f(A)=-\text{Tr}(A^{-1})/d$

  * •

E(igen)-design: $f(A)=-\operatorname{}\mathopen{}\lVert
A^{-1}\mathclose{}\rVert_{2}$

  * •

T(race)-design: $f(A)=d/\text{Tr}(A)$

The above objective functions are _regular_ (see Definition 4). [ALW17] shows
that under uniform matroid i.e. cardinality constraint, any fractional
feasible solution of a regular function can be rounded into an integral
solution while incurring only $O(1)$ loss in the objective function. For
laminar matroids, [LZ21] shows the same results for $D$-design and $A$-design
when $k_{F}\geq Cd$ for $\forall F\in\mathcal{F}$ and for some absolute
constant $C.$ For general matroid and $f(\cdot)=\det(\cdot),$ [Mad+20] shows
that a fractional feasible solution can be rounded into an integral solution
while suffering a $d^{O(d)}$ loss _in expectation_.

######  Definition 4.

A function $f:\mathbb{S}_{d}^{+}\to{\mathbb{R}}$ is regular if it satisfies
the following properties

  * •

Monotonicity: for any $A,B\in\mathbb{S}_{d}^{+},$ if $f(A)\leq f(B)$ for
$A\preceq B.$

  * •

Concavity: for $A,B\in\mathbb{S}_{d}^{+}$ and $t\in[0,1]$, we have
$f(tA+(1-t)B)\geq tf(A)+(1-t)f(B).$

In particular, this implies the existence of an efficient algorithm that
solves the continuous relaxation

$\max_{s_{1},\cdots,s_{n}}f(\sum_{i\in
1}^{n}s_{i}v_{i}v_{i}^{\intercal})\text{ s.t. }s_{i}\in[0,1]\text{ and
}\sum_{i=1}^{n}s_{i}\leq k.$

  * •

Reciprocal linearity: for any $A\in\mathbb{S}_{d}^{+}$ and $t\in(0,1),$
$f(tA)=t^{-1}f(A).$

People have also studied the setting where $S$ is allowed to be a multiset.
This is known as the experimental design problem _with repetition_ [ALW17,
Mad+19], as opposed to the _without repetition_ setting where $S$ needs to be
a proper subset. The _with repetition_ setting is generally easier: it can be
reduced to the without repetition setting by duplicating each vector $k$
times. Composable coreset for experimental design problem (under cardinality
constraint) in the with repetition setting has been studied in [Ind+20]. In
this work we generalize [Ind+20]’s result to the without repetition setting.

###  2.3 Composable coresets

In the context of the optimization problem on
$\mu:\binom{[n]}{k}\to{\mathbb{R}}_{\geq 0}$, a function $c$ that maps any set
$V\subseteq[n]$ to one of its subsets is called an $\alpha$-composable coreset
([Ind+14]) if it satisfies the following condition: given any integer $m$ and
any collection of sets $V_{1},\cdots,V_{m}\subseteq[n]$

$\alpha\cdot\max\operatorname{}\mathopen{}\left\\{\mu(S)\mathrel{}\mathclose{}\middle|\mathopen{}\mathrel{}S\subseteq\bigcup_{i=1}^{m}c(V_{i})\mathclose{}\right\\}\geq\max\operatorname{}\mathopen{}\left\\{\mu(S)\mathrel{}\mathclose{}\middle|\mathopen{}\mathrel{}S\subseteq\bigcup_{i=1}^{m}V_{i}\mathclose{}\right\\}.$

We also say $c$ is a coreset of size $t$ if $\operatorname{}\mathopen{}\lvert
c(V)\mathclose{}\rvert\leq t$ for all sets $V$. Composable coresets are very
versatile; when a composable coreset is designed for a task, they
automatically imply efficient streaming and distributed algorithms for the
same task.

###  2.4 Directional height

######  Definition 5 (Directional height and $k$-directional height [Mah+19]).

For a set $V\subseteq{\mathbb{R}}^{d}$ of vectors and a unit vector $x,$ the
directional height of $V$ w.r.t $x$ is $h(V,x)=\max_{v\in
V}\operatorname{}\mathopen{}\lvert\langle v,x\rangle\mathclose{}\rvert.$

The $k$-directional height w.r.t a $(k-1)$-dimensional subspace $H$ is
$d(V,H)=\max_{v\in V,x\in H^{\top}}\operatorname{}\mathopen{}\lvert\langle
v,x\rangle\mathclose{}\rvert$ where $H^{\top}$ is the $(d-k+1)$-dimensional
subspace perpendicular to $H.$

######  Theorem 6 (Coreset for $k$-directional height [Mah+19]).

For $k\leq d$ and $V\subseteq{\mathbb{R}}^{d}$, any size $k$ local optimum $U$
w.r.t $\det(\cdot)$ inside $V$ approximately preserves the $k$-directional
height i.e. for any $(k-1)$-dimensional subspace $H$

$d(U,H)\geq\frac{1}{k}d(V,H).$

where for a point set $P$, we define $d(P,H)=\max_{p\in P}d(p,H)$.

###  2.5 Spectral spanner

######  Definition 7 ([Ind+20]).

For a set of vectors $V\subseteq{\mathbb{R}}^{d}$, a subset $U\subseteq V$ is
a $\alpha$-spectral spanner of $V$ iff for any $v\in V,$ there exists a
distribution $\mu_{v}$ of vectors in $U$ s.t.

$vv^{\intercal}\preceq\alpha\operatorname{\mathbb{E}}_{u\sim\mu_{v}}\mathopen{}[uu^{\intercal}\mathclose{}]$

######  Theorem 8 ([Ind+20, Proposition 4.2,Lemma 4.6]).

Given $V\subseteq{\mathbb{R}}^{d},$ there exists an efficient algorithm that
constructs $\tilde{O}(d)$-spectral spanner of size $\tilde{O}(d).$

###  2.6 Strongly Rayleigh distribution and exchange inequalities

For a distribution $\nu:\binom{[n]}{\ell}\to{\mathbb{R}}_{\geq 0},$ its
generating polynomial is

$g_{\mu}(z_{1},\cdots,z_{n})=\sum_{S\in\binom{[n]}{k}}\mu(S)\prod_{i\in
S}z_{i}.$

######  Definition 9.

A distribution $\nu:\binom{[n]}{\ell}\to{\mathbb{R}}_{\geq 0}$ is strongly
Rayleigh or real-stable if its generating polynomial $g_{\nu}$ does not have
roots in the upper-half of the complex plane i.e.
$g_{\nu}(z_{1},\cdots,z_{n})\neq 0$ if
${\operatorname{Im}}(z_{1}),\cdots,{\operatorname{Im}}(z_{n})\geq 0.$

Strongly Rayleigh distributions satisfy the following exchange inequality,
which implies that for any local optimum subset $U$ w.r.t a strongly Rayleigh
distribution $\nu,$ and a given set $W\in{\operatorname{supp}}(\nu),$ we can
replace an element of $S$ for an element of $U$ while approximately preserving
the evaluation in $\nu(\cdot).$

######  Lemma 10.

Exchange inequality [Ana+20, Lemma 26] Let
$\nu:\binom{[n]}{\ell}\to{\mathbb{R}}_{\geq 0}$ be strongly Rayleigh. Let
$V\subseteq[n]$ be an arbitrary subset. For $\zeta\geq 1$, let $U$ be a
$\zeta$-local-optimum (w.r.t. $\nu$) inside $V,$ with $\nu(U)\neq 0.$ For
$W\in\binom{[n]}{\ell},and$ $e\in W\setminus U$

$\nu(W)\nu(U)\leq\ell\sum_{j\in U\setminus W}\nu(W-e+j)\nu(U+e-j)$

In particular, if $e\in V$ then by approximate local optimality of $U$ inside
$V$, we have

$\nu(W)\leq\zeta\ell\sum_{j\in U}\nu(W-e+j)\leq(\zeta\ell)^{2}\max_{j\in
U}\nu(W-e+j)$

where we implicitly understand that if $j\in W-e$ then $W-e+j$ is not a proper
set, and $\nu(W-e+j)=0.$

In the context of determinant maximization with given input vectors
$v_{1},\cdots,v_{n}\in{\mathbb{R}}^{d}$, for any $k\leq d$,
$\nu(S)=\det(\sum_{i\in S}v_{i}v_{i}^{\intercal})$ defines a strongly Rayleigh
distribution over $\binom{[n]}{k}$ [BBL09, AGR16].

When the number of chosen vectors $k$ is larger than the dimension $d,$ by
Cauchy-Binet formula

$\det(\sum_{i\in
S}v_{i}v_{i}^{\intercal})=\sum_{W\in\binom{S}{d}}\det(\sum_{i\in
W}v_{i}v_{i}^{\intercal}).$

Let $\mu:\binom{[n]}{k}\to{\mathbb{R}}_{\geq 0}$ be defined by
$\mu(S)=\det(\sum_{i\in S}v_{i}v_{i}^{\intercal})$ then $\mu$ is strongly
Rayleigh (see Proposition 11). Moreover,
$\mu(S)=\sum_{W\in\binom{S}{d}}\nu(W)$ for
$\nu:\binom{[n]}{d}\to{\mathbb{R}}_{\geq 0}$ defined by
$\nu(W)=\det(\sum_{i\in W}v_{i}v_{i}^{\intercal})$ where $\nu$ is itself
strongly Rayleigh. In this setting, we can obtain stronger exchange inequality
for $\mu$ that leads to an improved approximation factor for composable
coresets w.r.t $\mu$ (see Section 3).

######  Proposition 11.

For $\nu:\binom{[n]}{\ell}\to{\mathbb{R}}_{\geq 0}$ is strongly Rayleigh and
$k\geq\ell,$ define $\mu:\binom{[n]}{k}\to{\mathbb{R}}_{\geq 0}$ by
$\mu(S)=\sum_{W\in\binom{S}{\ell}}\nu(W)$ then $\mu$ is strongly Rayleigh.

###### Proof.

Consider the elementary symmetric polynomial

$e_{k-\ell}(z_{1},\cdots,z_{n})=\sum_{L\in\binom{[n]}{k-\ell}}\prod_{i\in
L}z_{i}$

then $e_{k-\ell}$ is real stable i.e. has no roots in the upper half plane.
Since the same is true for $g_{\nu}$, the product $g_{\nu}e_{k-\ell}$ also has
no root on the upper half plane [[, see e.g.]Proposition 3.1 for a
proof]BBL09. Consider the linear map
$\phi:{\mathbb{R}}[z_{1},\cdots,z_{n}]\to{\mathbb{R}}[z_{1},\cdots,z_{n}]$
that maps monomial $z_{1}^{\alpha_{1}}\cdots z_{n}^{\alpha}$ to itself if
$\alpha_{i}\leq 1$ for $\forall i,$ and to $0$ otherwise. This map preserves
real-stability of polynomial [BB09], and $\phi(g_{\nu}e_{k-\ell})=g_{\mu},$
thus $g_{\mu}$ is real stable, and $\mu$ is strongly Rayleigh. ∎

##  3 Improved exchange inequalities and the peeling coreset

As mentioned in the overview of the techniques, if $U$ is a composable coreset
for $V$ with respect to the function $\mu(\cdot)$, then for any set $S,$ we
can replace an element in $S\cap V$ with an element of $U$ while not reducing
$\mu(\cdot)$ by much. We formalize that intuition with the following
definition.

######  Definition 12.

Given $\tilde{\mu}:[n]^{k}\to{\mathbb{R}}_{\geq 0}$ and $V\subseteq[n],$ we
say $U\subseteq V$ is _value-preserving_ with respect to $\tilde{\mu}$ if for
any $S\in\binom{[n]}{k}$ and $e\in S\cap V,$ there exists $f\in
U\setminus(S-e)$ s.t. $\tilde{\mu}(S)\leq\tilde{\mu}(S-e+f).$

The following lemma shows the relationship between value-preserving sets and
coresets.

######  Lemma 13.

Suppose functions $\mu,\tilde{\mu}:\binom{[n]}{k}\to{\mathbb{R}}_{\geq 0}$
satisfies that $\mu(S)\leq\tilde{\mu}(S)\leq\alpha\mu(S)$ for $\forall S,$ and
coreset map $c$ satisfy $U:=c(V)\subseteq V$ is _value-preserving_ with
respect to $\tilde{\mu}$ then $c$ gives $\alpha$-composable coreset with
respect to $\mu.$

###### Proof.

Consider a collection of sets $V_{1},\cdots,V_{m},$ let $U_{i}:=c(V_{i})$ for
$\forall i\in[m],$ and $S$ be an arbitrary size-$k$ subset of
$\bigcup_{i=1}^{m}V_{i}.$ Since $U_{i}$ is value-preserving w.r.t.
$\tilde{\mu},$ for any $e\in S\cap V_{i},$ we can replace $e$ with $f\in
U_{i}\setminus(S-e)$ while keeping $\tilde{\mu}(\cdot)$ non-decreasing. Thus,
we successively replace $E:=S\setminus\bigcup_{i=1}^{m}U_{i}$ with
$L\subseteq\bigcup_{i=1}^{m}U_{i}$ while ensuring that

$\tilde{\mu}(S)\leq\tilde{\mu}(S-E+L)$

Moreover, $S-E+L\in\bigcup_{i=1}^{m}U_{i}$ and

$\mu(S)\leq\tilde{\mu}(S)\leq\tilde{\mu}(S-E+L)\leq\alpha\mu(S-E+L).$

By choosing $S$ s.t.
$\mu(S)=\max\operatorname{}\mathopen{}\left\\{\mu(S)\mathrel{}\mathclose{}\middle|\mathopen{}\mathrel{}S\subseteq\bigcup_{i=1}^{m}V_{i}\mathclose{}\right\\}$
we get the desired conclusion. ∎

We show that an (approximate) local optima with respect to $\det(\cdot)$ is
value preserving for suitably chosen functions. When $k\leq d,$ [Mah+19] shows
that any size-$k$ local optimum $U$ with respect to $\det(\cdot)$
approximately preserves $k$-directional height (see Theorem 6), and hence is a
value-preserving set with respect to $\tilde{\mu},$ where $\tilde{\mu}$ is
defined by

$\tilde{\mu}(S)=\det(\sum_{i\in S}k^{\mathbf{1}[i\in
U]}v_{i}v_{i}^{\intercal})$

This is easy to see since for $\operatorname{}\mathopen{}\lvert
S\mathclose{}\rvert=k\leq d,$ $\mu(S)=\det(\sum_{v\in S}vv^{\intercal})$ is
precisely the square of the volume spanned by vectors in $S$ i.e.
$\mu(S)=\text{Vol}^{2}(\operatorname{}\mathopen{}\left\\{v\in
S\mathclose{}\right\\})$ and
$\tilde{\mu}(S)=k^{2\operatorname{}\mathopen{}\lvert U\cap
S\mathclose{}\rvert}\text{Vol}^{2}(\operatorname{}\mathopen{}\left\\{v\in
S\mathclose{}\right\\}).$

Below, we show that for $k\geq d,$ a size-$d$ local optimum $U$ is value-
preserving with respect to $\tilde{\mu}$ defined by

$\tilde{\mu}(S)=\det(\sum_{i\in S}d^{2\times\mathbf{1}[i\in
U]}v_{i}v_{i}^{\intercal}).$ (1)

Observe that, by Cauchy-Binet’s formula, for $k\geq d$ and
$\operatorname{}\mathopen{}\lvert S\mathclose{}\rvert=k$

$\det(\sum_{i\in
S}v_{i}v_{i}^{\intercal})=\sum_{W\in\binom{S}{d}}\det(\sum_{i\in
W}v_{i}v_{i}^{\intercal}).$

We can generalize this setting by considering
$\nu:\binom{[n]}{\ell}\to{\mathbb{R}}_{\geq 0}$ and
$\mu:\binom{[n]}{k}\to{\mathbb{R}}_{\geq 0}$ by111Think of $\ell$ as being
equal to $d$

$\mu(S)=\sum_{W\in\binom{S}{\ell}}\nu(W).$ (2)

We will assume that $\nu$ is strongly Rayleigh, and consequently satisfies the
exchange inequality in Lemma 10. Because Lemma 10 only applies to local optima
with $\nu(S)>0$, it will be more convenient to work with a full-support
distribution i.e. $\nu(S)>0$ for $\forall S\in\binom{[n]}{\ell}.$ Fortunately,
we can approximately any strongly Rayleigh distribution $\nu$ with a full-
support strongly Rayleigh distribution a.k.a. strictly real stable
distribution. In other words, for any $\epsilon>0$ there exists a strongly
Rayleigh distribution $\tilde{\nu}:\binom{[n]}{\ell}\to{\mathbb{R}}_{\geq 0}$
s.t. $\forall S:\tilde{\nu}(S)>0$ and
$\operatorname{}\mathopen{}\lvert\tilde{\nu}(S)-\nu(S)\mathclose{}\rvert\leq\epsilon.$
Moreover, $\tilde{\nu}$ can be efficiently computed given $\nu$ (see the main
theorem of [Nui68], [BH19, Proof of Proposition 2.2] and [Brä20, page 7]). We
include a formal statement and a simple proof for completeness.

######  Proposition 14.

Let $\nu:\binom{[n]}{\ell}\to{\mathbb{R}}_{\geq 0}$ be strongly Rayleigh. For
any $\epsilon>0$, there exists strongly Rayleigh
$\tilde{\nu}:\binom{[n]}{\ell}\to{\mathbb{R}}_{>0}$ that approximates $\nu$
i.e.
$\operatorname{}\mathopen{}\lvert\nu(S)-\tilde{\nu}(S)\mathclose{}\rvert\leq\epsilon.$

###### Proof.

By [Nui68], for $i,j\in[n]$ and $s\in{\mathbb{R}}_{\geq 0},$ the following
operator preserves strongly Rayleigh/real-stability of polynomials

$T_{i,j,s}g=g+sz_{j}\frac{\partial g}{\partial i}$

for $g\in{\mathbb{R}}[z_{1},\dots,z_{n}].$

If $\nu(S)=0$, for $\forall S$, then we can let $\tilde{\nu}(S)=\epsilon$ for
$\forall S.$ W.l.o.g. assume $\nu(S)\neq 0$ for
$S=\operatorname{}\mathopen{}\left\\{1,\dots,\ell\mathclose{}\right\\}.$ Let
$g$ be the generating polynomial for $\nu$ and let

$f=\prod_{i\in[n],j\in[n]}T_{i,j,s}g=T_{1,1,s}\circ\dots\circ T_{1,n}\circ
T_{2,1,s}\circ\dots T_{2,n,s}\circ\dots\circ T_{n,n,s}g$

then $f$ is strongly Rayleigh. It is easy to see that for small enough $s,$
$f$ approximates $g.$ One practical choice for $s$ is
$s=\epsilon(\sum_{S}\nu(S))^{-c}$ for some $c>1;$ computing the partition
function $\sum_{S}\nu(S)$ can be done efficiently and even in
$\tilde{O}(1)$-parallel time for distributions of interest e.g. DPP. The map
from $f$ to the multi-affine part $f^{MAP}$ of $f$ preserves real stability
[BBL09] (recall that for
$f(z_{1},\dots,z_{n})=\sum_{(\alpha_{i})_{i=1}^{n}\in{\mathbb{N}}^{n}}c(\vec{\alpha})\prod_{i=1}^{n}z_{i}^{\alpha_{i}},$
the multiaffine part of $f$ is
$f^{MAP}(z_{1},\dots,z_{n})=\sum_{(\alpha_{i})_{i=1}^{n}\in{0,1}^{n}}c(\vec{\alpha})\prod_{i=1}^{n}z_{i}^{\alpha_{i}}.$
Now we only need to check that $f^{MAP}$ has positive coefficients. Indeed,
for
$S=\operatorname{}\mathopen{}\left\\{i_{1},\dots,i_{\ell}\mathclose{}\right\\}$
consider the coefficient of the monomial $z^{S}=\prod_{i\in S}z_{i}$ in $f$
and $f^{MAP}:$ it is a sum which includes the term

$\prod_{j=1}^{\ell}(sz_{i_{j}}\frac{\partial}{\partial
z_{j}})\nu([\ell])z^{[\ell]}=z^{S}s^{k}\nu([\ell])>0$

thus the coefficient of $z^{S}$ in $f^{MAP}$ is positive. ∎

######  Remark 15.

We remark that a $O(1)$-approximate local optima of size $\ell$ w.r.t
$\det(\cdot)$ can be found in time $O(n{\operatorname{poly}}(\ell)^{4})$ using
a combination of simple heuristic such as greedy and local search (also known
as Fedorov exchange algorithm). The same algorithmic result holds more
generally for all strongly Rayleigh distribution
$\nu:\binom{[n]}{\ell}\to{\mathbb{R}}_{\geq 0}$ [[, see]for
details]anari2021sampling,ALOVV21).

In the remaining of the paper, we will consider the problem of maximizing the
function $\mu:\binom{[n]}{k}\to{\mathbb{R}}_{\geq 0}$ under matroid constraint
where $\mu(S)=\sum_{W\in\binom{S}{\ell}}\nu(W)$ and
$\nu:\binom{[n]}{\ell}\to{\mathbb{R}}_{>0}.$

######  Remark 16.

This set-up of $\mu$ encompasses determinant maximization for both cases of
$k\leq d$ and $k\geq d$. More concretely, for the former case, we set $\ell=k$
and for the latter case we set $\ell=d$. We will explain this in more details
in Theorem 28.

For some constant $\zeta\geq 1$ to be specified later, let
$\phi(W)=(\zeta\ell)^{2\operatorname{}\mathopen{}\lvert W\cap
U\mathclose{}\rvert}.$ We define $\tilde{\mu}:[n]^{k}\to{\mathbb{R}}_{\geq 0}$
by:

$\tilde{\mu}(S)=\sum_{W\in\binom{S}{\ell}}\phi(W)\nu(W)$

This is the proper generalization of Eq. 1. We observe the following simple
fact.

######  Fact 17.

$\mu(S)\leq\tilde{\mu}(S)\leq(\zeta\ell)^{2\ell}\mu(S).$

######  Lemma 18.

For $V\subseteq[n],$ let $U$ be a $\zeta$-approximate local optimum inside $V$
with respect to $\nu,$ for $\zeta=O(1).$ For any $e\in(V\cap S)\setminus U,$
there exists $f\in U$ s.t.

$\tilde{\mu}(S)\leq\tilde{\mu}(S-e+f).$

###### Proof.

Consider $W\in\binom{S}{\ell}$ with $e\in W.$ Using Lemma 10,

$\nu(W)\leq\ell^{\prime}\sum_{f\in U}\nu(W-e+f)$

with $\ell^{\prime}=\zeta\ell.$

Summing over all such $W$ we have

$\displaystyle\sum_{W\in\binom{S}{\ell}:e\in W}\phi(W)\nu(W)$
$\displaystyle\leq\ell^{\prime}\sum_{f\in U}\sum_{W:e\in W}\phi(W)\nu(W-e+f)$
$\displaystyle\leq(\zeta\ell)^{2}\max_{f\in U}\sum_{W\in\binom{S}{\ell}:e\in
W}\phi(W)\nu(W-e+f)$ $\displaystyle=\sum_{W\in\binom{S}{\ell}:e\in
W}\phi(W-e+f^{*})\nu(W-e+f^{*})$

with $f^{*}$ being the maximizer of the second line. The desired inequality
then follows by adding $\sum_{W\in\binom{S-e}{\ell}}\phi(W)\nu(W)$ to both
sides. ∎

We have just shown how to exchange $e\in(S\cap V)\setminus U$ for $f\in U$
while keeping $\tilde{\mu}$ non-decreasing. However, we still need to ensure
that $S-e+f$ is a proper set i.e. ensure that $f\not\in S-e.$ To do so, we
need a slightly more elaborate coreset construction.

######  Definition 19 (Peeling-coreset).

Given $V\subseteq[n],$ and a number $k_{V}\geq 1$, define the
$(V,k_{V},\zeta)$-peeling coreset $U$ as follows:

  * •

Let $U_{0}=\emptyset.$

  * •

For $i=1,\cdots,k_{V},$ let $V_{i}:=V\setminus\bigcup_{j=0}^{i-1}U_{j}$, and
let $U_{i}\subseteq V_{i}$ be a $\zeta$-approximate local optimal w.r.t. $\nu$
inside $V_{i}.$

  * •

Let $U=\bigcup_{i=1}^{k_{V}}U_{i}.$

Note that the $U_{i}$’s are disjoint and $\operatorname{}\mathopen{}\lvert
U\mathclose{}\rvert\leq k_{V}\ell.$

######  Lemma 20.

The $(V,k_{V})$-peeling coreset $U$ constructed in Definition 19 is a value-
preserving subset of $V$ with respect to
$\hat{\mu}:[n]^{k}\to{\mathbb{R}}_{\geq 0}$ s.t.

$\hat{\mu}(S)=\textbf{1}[S\in\binom{[n]}{k}\land\operatorname{}\mathopen{}\lvert
S\cap V\mathclose{}\rvert\leq k_{V}]\tilde{\mu}(S)$

###### Proof.

Fix $S\in\binom{[n]}{k}$ s.t. $\operatorname{}\mathopen{}\lvert S\cap
V\mathclose{}\rvert\leq k_{V}$ and $e\in(S\cap V)\setminus U.$ Since $S$ has
at most $k_{V}-1$ elements inside222$\operatorname{}\mathopen{}\lvert S\cap
U\mathclose{}\rvert\leq\operatorname{}\mathopen{}\lvert(S\cap V)\setminus
e\mathclose{}\rvert\leq k_{V}-1.$ $U=\bigcup_{j=1}^{k}U_{j}$ there exists
$j\in[k_{V}]$ where $S\cap U_{j}=\emptyset.$ Note that $e\in(S\cap V)\setminus
U\subseteq(S\cap V_{j})\setminus U_{j},$ thus there exists $f\in U_{j}$ s.t.
$\tilde{\mu}(S)\leq\tilde{\mu}(S-e+f).$ Since $S\cap U_{j}=\emptyset,$ $f$ is
not in $S-e.$ ∎

######  Lemma 21.

For $V\subseteq[n]$ and $\zeta\geq 1$, the $\zeta$-approximate local optimum
$U$ w.r.t $\mu$ is a value-preserving subset of $V$ w.r.t $\hat{\mu}$ defined
by $\hat{\mu}(S)=(\zeta k)^{2\operatorname{}\mathopen{}\lvert U\cap
S\mathclose{}\rvert}\mu(S).$

###### Proof.

We use the fact that $\mu$ is strongly Rayleigh, and Lemma 10. For any
$S\in\binom{[n]}{k}$ and $e\in(S\cap V)\setminus U,$ there exists $j\in
U\setminus S$ s.t.

$\mu(S)\leq(\zeta k)^{2}\mu(S-e+j)$

Multiplying both sides by $(\zeta k)^{2\operatorname{}\mathopen{}\lvert U\cap
S\mathclose{}\rvert}$ and using the fact that
$\operatorname{}\mathopen{}\lvert(S-e+j)\cap
U\mathclose{}\rvert=\operatorname{}\mathopen{}\lvert S\cap
U\mathclose{}\rvert+1$ we have

$\hat{\mu}(S)\leq\hat{\mu}(S-e+j)$

∎

######  Lemma 22 (Composability of value-preserving subsets).

Consider disjoint $V_{1},\cdots,V_{m}$ with $U_{i}$ being a value preserving
subset of $V_{i}$ w.r.t $\tilde{\mu},$ then $U:=\bigcup_{i=1}^{m}U_{i}$ is a
value-preserving subset of $V:=\bigcup_{i=1}^{m}V_{i}$ w.r.t $\tilde{\mu}.$

###### Proof.

Consider $S\subseteq[n]$ and $e\in(S\cap V)\setminus U.$ Clearly, $e\in(S\cap
V_{i})\setminus U_{i}$ for some $i\in[m].$ Since $U_{i}$ is value-preserving
w.r.t $\tilde{\mu},$ there exists $j\in U_{i}\subseteq U$ s.t.
$\tilde{\mu}(S)\leq\tilde{\mu}(S-e+f).$ ∎

##  4 Composable coresets for partition and laminar matroids

We construct composable coresets for determinant maximization under laminar
matroid constraint. To build intuition, we first describe composable coresets
for the simpler case of partition matroid. The idea is to build a peeling
coreset of suitable size for each part of the partition which define the
parition matroid.

As in section Section 3, given a matroid $\mathcal{M}$ with the set of bases
$\mathcal{B}$, we consider the problem of maximizing $\mu(S)$ (under matroid
constraint) where $\mu(S)=\sum_{W\in\binom{S}{\ell}}\nu(W)$ and
$\nu:\binom{[n]}{\ell}\to{\mathbb{R}}_{\geq 0}$ is strongly Rayleigh. Let
$\mu_{\mathcal{M}}$ be the restriction of $\mu$ to the set of bases of
$\mathcal{M}$ i.e.
$\mu_{\mathcal{M}}(S)=\mathbb{1}[S\in\mathcal{B}(\mathcal{M})]\mu(S).$

######  Definition 23.

Consider a partition matroid $\mathcal{M}=([n],\mathcal{I})$ defined by the
partition $P_{1},\cdots,P_{s}$ of $[n]$ and
$k_{1},\cdots,k_{s}\in{\mathbb{N}}.$ Fix constant $\zeta\geq 1.$ For
$V\subseteq[n],$ the composable coreset $U$ for $V$ w.r.t. $\mu_{\mathcal{M}}$
is constructed as follows:

  * •

When $k>\ell:$ $U$ is the union of $(V\cap P_{i},k_{i},\zeta)$-peeling
coresets for each $i\in[s],$ thus $\operatorname{}\mathopen{}\lvert
U\mathclose{}\rvert=k\ell.$

  * •

When $k=\ell:U$ is the union over $i\in[s]$ of the $\zeta$-approximate local
optimum w.r.t. $\nu$ in $V\cap P_{i},$ thus $\operatorname{}\mathopen{}\lvert
U\mathclose{}\rvert=s\ell=sk.$

######  Lemma 24.

The coreset constructed in Definition 23 has an approximation factor of
$(\zeta\ell)^{2\ell}.$

###### Proof.

Note that in both cases, by Lemmas 20 and 21, $U$ is the union of value-
preserving subsets $U_{i}$ of $V\cap P_{i}$ w.r.t
$\tilde{\mu}_{\mathcal{M}}(S)=\mathbf{1}[S\in\mathcal{B}]\sum_{W\in\binom{S}{\ell}}(\zeta\ell)^{2\operatorname{}\mathopen{}\lvert
W\cap U\mathclose{}\rvert}\nu(W).$ Thus, by Lemma 22, $U$ is a value-
preserving subset of $V$ w.r.t $\tilde{\mu}_{\mathcal{M}}.$ 17 and Lemma 13
together imply that $U$ is $\ell^{2\ell}$-composable coreset w.r.t.
$\mu_{\mathcal{M}}.$ ∎

We generalize the above construction to all laminar matroids.

######  Definition 25.

Consider a laminar matroid over the ground set $[n]$ defined by a laminar
family $\mathcal{F}$ and the associated integers $(k_{S})_{S\in\mathcal{F}}.$
Fix constant $\zeta\geq 1.$ For $V\subseteq[n],$ the coreset for $V$ is
constructed as follows:

  1. 1.

For each maximal set $F\in\mathcal{F},$ construct a coreset $U_{F}\subseteq
V\cap F$ by:

     * •

Let $D_{0}=\emptyset,V_{0}=V\cap F.$

     * •

For $i=1,\cdots,k_{S},$ let $U_{i}$ be the $\zeta$-approximate local optimal
w.r.t. $\nu$ in $V_{i}=V_{i-1}\setminus D_{i-1}.$ For $e\in U_{i},$ let
$F^{e}\in\mathcal{F}$ be the maximal _proper_ subset of $F$ containing $e$ or
$\operatorname{}\mathopen{}\\{e\mathclose{}\\}$ if no such $F^{e}$ exists. Let
$D_{i}:=\bigcup_{e\in U_{i}}F^{e}.$ For each $e\in U_{i}$ with
$F^{e}\neq\operatorname{}\mathopen{}\left\\{e\mathclose{}\right\\},$
recursively construct a coreset $U_{F^{e}}\subseteq V\cap F^{e}.$ Observe that
if no proper subset of $F$ is inside $\mathcal{F},$ then the coreset $U_{F}$
is precisely the $(V\cap F,k_{F})$ peeling-coreset.

     * •

The coreset for $F$ is the union of all $U_{i}$ and $U_{F^{e}}$ for $e\in
U_{i}.$

  2. 2.

The coreset $U$ of $V$ is the union of all coresets $U_{F}$ for maximal sets
$F\in\mathcal{F}$ and all elements $e\in V$ that do not belong to any set
$F\in\mathcal{F}.$

######  Theorem 26.

Consider $\nu:\binom{[n]}{\ell}\to{\mathbb{R}}_{\geq 0}$ that is strongly
Rayleigh and $\mu:\binom{[n]}{k}\to{\mathbb{R}}_{\geq 0}$ s.t.

$\mu(S)=\sum_{W\in\binom{S}{\ell}}\nu(W).$

Consider laminar matroid constraint $\mathcal{M}$ of rank $k$ defined by non-
redundant family $\mathcal{F}$ with cover number $r$ i.e.
$r:=\max_{e\in[n]}\operatorname{}\mathopen{}\lvert\operatorname{}\mathopen{}\left\\{F\in\mathcal{F}:e\in
F\mathclose{}\right\\}\mathclose{}\rvert.$ Definition 25 gives a
$(\zeta\ell)^{2\ell}$-composable coreset w.r.t $\mu$ under matroid constraint
$\mathcal{M}$ of size at most $(\zeta k\ell)^{r}\leq(\zeta k\ell)^{k}.$

###### Proof of the approximation factor.

Let
$\tilde{\mu}(S)=\sum_{W\in\binom{S}{\ell}}(\zeta\ell)^{2\operatorname{}\mathopen{}\lvert
W\cap U\mathclose{}\rvert}\nu(W).$ $U$ is a value-preserving subset of $V$
w.r.t the restriction $\tilde{\mu}_{\mathcal{M}}$ of $\tilde{\mu}$ to the set
of bases of the laminar matroid i.e.
$\tilde{\mu}_{\mathcal{M}}(S)=\mathbb{1}[S\in\mathcal{B}(\mathcal{M})]\tilde{\mu}(S).$
This combined with Lemma 13 immediately imply that $U$ is a
$\ell^{2\ell}$-composable coreset w.r.t $\mu_{\mathcal{M}}.$

We only need to show that $U_{F}$ is value preserving for each
$F\in\mathcal{F}.$ Fix $S\in\mathcal{B}$ and $h\in(S\cap V\cap F)\setminus
U_{F}.$ We claim that there exists $f\in U_{F}$ s.t. $S-h+f\in B$ and
$\hat{\mu}(S)\leq\hat{\mu}(S-h+f).$

We prove this by induction on $F.$ For the base case when $F$ has no proper
subset inside $\mathcal{F},$ then $U_{F}$ is the $(V\cap F,k_{F})$ peeling-
coreset, and the claim follows from Lemma 20. If $h\in D_{i}$ for some $i,$
then $h$ must be contained in a proper subset $F^{e}\in\mathcal{F}$ of $F$
where $e\in U_{i}$ and
$F^{e}\neq\operatorname{}\mathopen{}\left\\{e\mathclose{}\right\\}$333if
$F^{e}=\operatorname{}\mathopen{}\left\\{e\mathclose{}\right\\}$ then $h=e\in
U_{i}\subseteq U_{F}$, a contradiction and we can use the induction
hypothesis. Now, assume $h\not\in D_{i}$ for $\forall i\in[k_{F}].$ In
particular, this means $h\in V_{k_{F}}\subseteq\cdots\subseteq V_{1}=V\cap F$
and $D_{i}$ and $U_{i}$ are non-empty for all $i\in[k_{F}].$ Note that since
$D_{i}$’s are disjoint, and $S$ contains at most $k_{F}-1$ elements inside
$F,$ $S\cap D_{i}=\emptyset$ for some $i.$ In particular, $S\cap
U_{i}=\emptyset$ and $h\in(V_{i}\cap S)\setminus U_{i},$ so Lemma 18 implies
that there exists $f\in U_{i}$ s.t. $\hat{\mu}(S)\leq\hat{\mu}(S-h+f).$
Replacing $h$ with $f$ only affects the constraints for sets
$F^{\prime}\in\mathcal{F}$ containing $f.$ Consider such a set $F^{\prime}.$
$F^{\prime}$ must be contained inside $D_{i}$ by the definition of $D_{i},$
thus $S\cap F^{\prime}=\emptyset,$ and
$\operatorname{}\mathopen{}\lvert(S-h+f)\cap F^{\prime}\mathclose{}\rvert\leq
1\leq k_{F^{\prime}}.$ We just verify that $S-h+f$ is also a base of the
laminar matroid, thus

$\hat{\mu}(S-h+f)=\tilde{\mu}(S-h+f)\geq\tilde{\mu}(S)=\hat{\mu}(S).$

∎

###### Proof of upper bound on the size of the coreset.

For a set $H$ let $r_{H}:=\max_{e\in
H}\operatorname{}\mathopen{}\lvert\operatorname{}\mathopen{}\left\\{F\in\mathcal{F}:F\subseteq
H\land e\in F\mathclose{}\right\\}\mathclose{}\rvert.$ We show that
$\operatorname{}\mathopen{}\lvert
U_{F}\mathclose{}\rvert\leq(k_{F}\ell)^{r_{F}}$ for each $F\in\mathcal{F}$ by
induction on $r_{F}.$ For the base case $r_{F}=1,$ we have
$\operatorname{}\mathopen{}\lvert U_{F}\mathclose{}\rvert=k_{F}\ell,$ by
Definition 19. Fix $F\in\mathcal{F}$ with $r_{F}\geq 2$ and suppose the
induction hypothesis holds for $r<r_{F}.$ Using the definition of $U_{F},$ we
can bound

$\operatorname{}\mathopen{}\lvert
U_{F}\mathclose{}\rvert\leq\sum_{i=1}^{k_{F}}\operatorname{}\mathopen{}\lvert
U_{i}\mathclose{}\rvert+\sum_{e\in\bigcup_{i=1}^{k_{F}}U_{i}}\operatorname{}\mathopen{}\lvert
U_{F^{e}}\mathclose{}\rvert\leq_{(1)}k_{F}d+(k_{F}\ell)(d\max_{F^{\prime}\subseteq
F:F^{\prime}\in\mathcal{F}}k_{F^{\prime}})^{r_{F}-1}\leq_{(2)}(k_{F}\ell)^{r_{F}}$

where in (1) we use the fact that $r_{F^{e}}<r_{F}$ since $F^{e}$ is a proper
subset of $F,$ and in (2) we use

$(\max_{F^{\prime}\subseteq
F:F^{\prime}\in\mathcal{F}}k_{F^{\prime}})^{r_{F}-1}+1\leq(k_{F}-1)^{r_{F}-1}+1\leq
k_{F}^{r_{F}-1}.$

Thus the induction hypothesis holds for all $r.$

Suppose the maximal set(s) in $\mathcal{F}$ are $F_{1},\cdots,F_{t},$ and let
$R:=[n]\setminus\bigcup_{i=1}^{t}F_{t}.$ Then the rank of the laminar matroid
is $k=\operatorname{}\mathopen{}\lvert
R\mathclose{}\rvert+\sum_{i=1}^{t}k_{F_{t}},$ and

$\operatorname{}\mathopen{}\lvert
U\mathclose{}\rvert=\operatorname{}\mathopen{}\lvert
R\cup\sum_{i=1}^{t}U_{F_{t}}\mathclose{}\rvert\leq\operatorname{}\mathopen{}\lvert
R\mathclose{}\rvert+\sum_{i=1}^{t}(k_{F_{t}}\ell)^{r}\leq(k\ell)^{r}.$

∎

######  Remark 27.

For any laminar family $\mathcal{F}$ of rank $k,$ we can construct a
$d^{O(d)}$-coreset of size
$\operatorname{}\mathopen{}\lvert\mathcal{F}\mathclose{}\rvert dk$ by taking
the union of all value-preserving subsets of
$V\cap(F\setminus\bigcup_{F^{\prime}\subseteq
F,F^{\prime}\in\mathcal{F}}F^{\prime}).$ However, the size of the coreset
might be as bad as linear in $n.$ Indeed, consider the laminar family defined
by:
$F_{i}=\operatorname{}\mathopen{}\left\\{2i+1,2i+2\mathclose{}\right\\},k_{F_{i}}=1$
for $\forall i\in[n/2]$ and $F_{0}=[n],$ $k_{F_{0}}=k$ then Definition 25
gives a coreset of size444We can improve the bound to $kd^{2}$ by a more
careful analysis. $\leq k^{2}d^{2}$ whereas the naive construction gives a
coreset of size $\geq(n/2)d.$

We immediately obtain the following corollary about determinant maximization
under matroid constraints.

######  Theorem 28.

For the determinant maximization matroid constraints with input vectors
$v_{1},\cdots,v_{n}\in{\mathbb{R}}^{d},$ we obtain the following results:

  1. 1.

Partition matroid defined by partition $P_{1},\cdots,P_{s}$ of $[n],$
Definition 23 gives:

     * •

For $k\leq d:$ $k^{2k}$-composable coreset of size $O(sk).$

     * •

For $k\geq d:$ $d^{2d}$-composable coreset of size $O(kd).$

  2. 2.

Laminar matroid:

     * •

For $k\leq d:$ $k^{2k}$-composable coreset of size $O(k^{2k}).$

     * •

For $k\geq d:$ $d^{2d}$-composable coreset of size $O((kd)^{k}).$

###### Proof.

We show how to adapt the setting of
$\nu:\binom{[n]}{\ell}\to{\mathbb{R}}_{\geq 0}$ and
$\mu:\binom{[n]}{k}\to{\mathbb{R}}_{\geq 0}$ where
$\mu(S)=\sum_{W\in\binom{S}{\ell}}\nu(W)$ with $\nu$ being strongly Rayleigh
to the determinant maximization setting.

  * •

For $k\leq d:$ we let $\ell=k$ and $\mu(S)=\nu(S)=\det(\sum_{i\in
S}v_{i}v_{i}^{\intercal})$ for $|S|=k.$ By replacing $\ell$ with $k$ we get
the stated result.

  * •

For $k\geq d:$ we let $\ell=d,$ $\nu(W)=\det(\sum_{i\in
W}v_{i}v_{i}^{\intercal})$ for $\operatorname{}\mathopen{}\lvert
W\mathclose{}\rvert=\ell$ and $\mu(S)=\nu(S)=\det(\sum_{i\in
S}v_{i}v_{i}^{\intercal})$ for $|S|=k.$

∎

Recall that $O(1)$-approximate local optima can be found in time
$O(n{\operatorname{poly}}(k))$ (see Remark 15). Thus, our coreset construction
is highly efficient: it takes time $O(n{\operatorname{poly}}(k))$ for the case
of partition matroid constraint. As a corollary, we obtain a quasilinear
algorithm for MAP-inference for DPP under partition matroid constraint.

######  Lemma 29.

Consider a partition matroid $\mathcal{M}=([n],\mathcal{I})$ of rank $k$
defined by the partition $P_{1},\cdots,P_{s}$ of $[n]$ and
$k_{1},\cdots,k_{s}\in{\mathbb{N}}.$ Given input vectors
$v_{1},\cdots,v_{n}\in{\mathbb{R}}^{d},$ there exists a
$O(n{\operatorname{poly}}(k))$ algorithm that outputs a
$\min(k^{O(k)},d^{O(d)})$-approximation for the determinant maximization under
partition matroid constraint $\mathcal{M}$.

###### Proof.

W.l.o.g. we can assume $k_{i}\geq 1\forall i.$ We construct coreset $U$ as in
Theorem 28 Note that since $k_{1}+\cdots+k_{s}=k$ and $k_{i}\geq 1$, we have
that $s\leq k$ thus the size of $U$ is $O(k^{2})$ for both cases $k\leq d$ and
$k\geq d.$ We can restrict the ground set to $U$ and use the existing
efficient algorithms [Bro+22] to get a
$\min\operatorname{}\mathopen{}\left\\{k^{O(k)},d^{O(d)}\mathclose{}\right\\}$-approximation
for constrained determinant maximization with input vectors from $U$, which is
also a
$\min\operatorname{}\mathopen{}\left\\{k^{O(k)},d^{O(d)}\mathclose{}\right\\}$-approximation
for the original constrained determinant maximization problem. ∎

##  5 Other experimental design problems

In this section, we generalize our composable coreset construction to other
experimental design problems such as $A$-design, $E$-design, etc.

The main idea is to replace the local optimum in the coreset construction with
an $\alpha$-spectral spanner. By replacing local optimum with spectral
spanner, we can ensure that the coreset contains a high-valued feasible
fractional $x$ in the convex hull $P(\mathcal{M})\subseteq[0,1]^{n}$ of the
matroid polytope of $\mathcal{M},$ which can be rounded to an integral
solutions for uniform matroid constraint and certain class of laminar matroid
constraint.

######  Theorem 30 (Rounding for experimental design, [Mad+20]).

Consider the experimental design problem with objective function $f(\cdot)$
and input vectors $v_{1},\cdots,v_{n}\in{\mathbb{R}}^{d}$ under matroid
constraint $\mathcal{M}$ of rank $k.$ For any fractional $x\in
P(\mathcal{M})\subseteq[0,1]^{n},$ there exists
$z\in\mathcal{B}(\mathcal{M})\subseteq\operatorname{}\mathopen{}\left\\{0,1\mathclose{}\right\\}^{n}$
s.t.

  * •

When $f(A)=\det(A):$

$\min\operatorname{}\mathopen{}\left\\{d^{O(d)},2^{O(k)}\mathclose{}\right\\}f(\sum_{i=1}^{n}z_{i}v_{i}v_{i}^{\intercal})\geq
f(\sum_{i=1}^{n}x_{i}v_{i}v_{i}^{\intercal})$

The factor $d^{O(d)}$ can be improved to $2^{O(d)}$ when $\mathcal{M}$ is a
partition matroid.

  * •

When $k\geq d,$ $\mathcal{M}$ is the uniform matroid and $f$ is regular:

$O(1)f(\sum_{i=1}^{n}z_{i}v_{i}v_{i}^{\intercal})\geq
f(\sum_{i=1}^{n}x_{i}v_{i}v_{i}^{\intercal})$

  * •

When $k\geq d,$ $\mathcal{M}$ is a laminar matroid defined by the laminar
family $\mathcal{F}$ and $(k_{F})_{F\in\mathcal{F}}$ with $k_{F}\geq Cd$ for
$\forall F\in\mathcal{F}$ for some large absolute constant $C$, and
$f(A)=-Tr(A^{-1})/d$ :

$O(1)f(\sum_{i=1}^{n}z_{i}v_{i}v_{i}^{\intercal})\geq
f(\sum_{i=1}^{n}x_{i}v_{i}v_{i}^{\intercal})$

We show $\tilde{O}(d)$-composable coreset of size $\tilde{O}(dk)$ for
experimental design problems in the without repetition setting.

######  Theorem 31.

Given input vectors $v_{1},\cdots,v_{n}\in{\mathbb{R}}^{d},$
$V\subseteq\operatorname{}\mathopen{}\left\\{v_{1},\cdots,v_{n}\mathclose{}\right\\}$
and a number $k_{V}\geq 1,$ the $(V,k_{V})$-spectral peeling coreset $U$ is
defined by the same procedure as in Definition 19, but replacing the local
optimal $U_{i}$ by a $O(d)$-spectral spanner $U_{i}$ of $V_{i}$ (see
Definitions 7 and 8).Then $\operatorname{}\mathopen{}\lvert
U\mathclose{}\rvert\leq\tilde{O}(k_{V}d).$ For any $S$ with
$\operatorname{}\mathopen{}\lvert S\cap V\mathclose{}\rvert\leq k_{V},$ there
exists a distribution $\mu_{v}$ for $v\in S\cap V$ with disjoint supports s.t.
${\operatorname{supp}}(\mu_{v})\subseteq U$ and for any regular objective
function $f:$

$f(\sum_{v\in S}vv^{\intercal})\leq f(\sum_{v\in
S}\operatorname{\mathbb{E}}_{u\sim\mu_{v}}\mathopen{}[duu^{\intercal}\mathclose{}])$

Consequently, for $k_{V}=k,$ $U$ is a $\tilde{O}(d)$-composable coreset for
the experimental design problem under cardinality constraint $k$ w.r.t $f.$

###### Proof.

Consider the set $(S\cap V)\setminus U.$ Since
$\operatorname{}\mathopen{}\lvert S\cap V\mathclose{}\rvert\leq k_{V},$ there
is an injective map $\pi:(S\cap V)\setminus U\to[k_{V}]$ s.t. $S\cap
U_{\pi(v)}=\emptyset$ for each $v\in(S\cap V)\setminus U.$ For each
$v\in(S\cap V)\setminus U$, since $v\in V_{\pi(v)}$, we can use the fact that
$U_{\pi(v)}$ is a spectral spanner of $V_{i}$ to deduce that there exists
$\mu_{v}$ supported on $U_{\pi(v)}$ where

$vv^{\intercal}\preceq
d\operatorname{\mathbb{E}}_{u\sim\mu_{v}}\mathopen{}[uu^{\intercal}\mathclose{}].$

Note that $\mu_{v}$ are disjoint by injectivity of $\pi.$ The claim then
follows from the monotonicity of $f.$

For sets $V_{1},\cdots,V_{m}$ let $U^{\prime}_{i}$ be the $(V_{i},k)$-peeling
coreset for $V_{i}.$ Let $V^{\prime}:=\bigcup_{i=1}^{m}V_{i}$ and
$U^{\prime}:=\bigcup U^{\prime}_{i}.$

Let $S\in\binom{V^{\prime}}{k}$ be a subset that maximizes $f(\sum_{v\in
S}vv^{\intercal})$. Using the above argument, we obtain that $U^{\prime}$
contains a fractional solution $s\in[0,1]^{U^{\prime}}$ s.t. $\sum s_{i}=k$
and

$f(\sum_{v\in S}vv^{\intercal})\leq df(\sum_{i\in
U^{\prime}}s_{i}v_{i}v_{i}^{\intercal})\leq
O(d)f(\sum_{u\in\tilde{S}}uu^{\intercal})$

for some $\tilde{S}\in\binom{U^{\prime}}{k},$ where the second inequality
follows from Theorem 30. ∎

Using similar construction and proof technique, we obtain
$\tilde{O}(d)$-composable coreset of size $\tilde{O}(dk)$ and
$\tilde{O}((dk)^{k})$ respectively for $A$-design under certain laminar and
partition matroid constraint $\mathcal{M}$ where $k_{F}\geq Cd$ for $\forall
F\in\mathcal{F}.$

##  6 Lower bound

In this section, we show that the coreset we constructed essentially attains
the best possible size and approximation factor. We first show that for
determinant maximization in ${\mathbb{R}}^{d}$ when $k\leq d$ under partition
matroid constraint, our coreset size is optimal.

######  Lemma 32.

Suppose $k\leq d.$ Consider a partition matroid
$\mathcal{M}=([n],\mathcal{I})$ defined by a partition $P_{1},\cdots,P_{s}$
and constraint $k_{1},\cdots,k_{s}.$ Let
$k:={\operatorname{rank}}(\mathcal{M})=\sum_{i=1}^{s}k_{i}.$ Any
$\alpha$-composable coreset for the determinant maximization problem under
partition matroid constraint $\mathcal{M}$ with size $t<sk$ must incur an
infinite approximation factor.

###### Proof.

Consider a partitioning of $n$ vectors in ${\mathbb{R}}^{d}$ into two sets
$V,V^{\prime}$ such that each $V\cap P_{i}$ consists of $d$ vectors that are
identical to the standard basis for ${\mathbb{R}}^{d}$ i.e. $V\cap
P_{i}=\operatorname{}\mathopen{}\left\\{e_{1},\cdots,e_{d}\mathclose{}\right\\}$
for each $i.$ We need to show that for any subset $U\subseteq V$ of size
$t<sk,$ we can choose the vectors in $V^{\prime}$ s.t. $\text{OPT}(V\cup
V^{\prime})\gg\text{OPT}(U\cup V^{\prime}).$ Indeed, fix one such subset $U,$
there must exists $i\in[s]$ s.t. $\operatorname{}\mathopen{}\lvert U\cap
P_{i}\mathclose{}\rvert\leq k-1.$ W.l.o.g., we can assume that $U\cap
P_{1}\subseteq\operatorname{}\mathopen{}\left\\{e_{1},\cdots,e_{k-1}\mathclose{}\right\\}.$
Choose $V^{\prime}$ s.t. $V^{\prime}\cap P_{1}=\emptyset,$ and $V^{\prime}\cap
P_{i}=\operatorname{}\mathopen{}\left\\{Me_{\sum_{j=1}^{i-1}k_{j}},\cdots,Me_{\sum_{j=1}^{i}k_{j}-1}\mathclose{}\right\\}$
for some arbitrarily large $M>0.$ Consider $S\subseteq V\cup V^{\prime}$ s.t.
$S\cap
P_{1}=\operatorname{}\mathopen{}\left\\{e_{1},\cdots,e_{k_{1}-1},e_{k}\mathclose{}\right\\}$
and $S\cap P_{i}=V^{\prime}\cap P_{i}$ for $i=2,\cdots,s$, then
$S\in\mathcal{M}$ and $\mu(S):=\det(\sum_{v\in
S}vv^{\intercal})=M^{2\sum_{j=2}^{s}k_{j}},$ thus $\text{OPT}(V\cup
V^{\prime})\geq M^{2\sum_{j=2}^{s}k_{j}}.$ On the other hand, for any
$S^{\prime}\in\binom{U\cup V^{\prime}}{k},$ either:

  * •

$S^{\prime}\cap P_{i}\subseteq V^{\prime}\forall i\geq 2:$ in this case
$\mu(S^{\prime})=0$555Even when we replace $\mu$ by a full-support
$\tilde{\mu}$ that approximate $\mu$ within distance $\epsilon$, we will have
$\tilde{\mu}(S)<\epsilon<\text{OPT}(V\cup V^{\prime})/M^{2}$ if we choose
$\epsilon$ small enough because all the vectors in $S^{\prime}$ are contained
in the $(k-1)$-dimensional subspace spanned by $e_{1},\cdots,e_{k-1}.$

  * •

$S^{\prime}\cap P_{i}\not\subseteq V^{\prime}$ for some $i\geq 2:$ in this
case $\mu(S^{\prime})\leq M^{2(\sum_{j=2}^{s}k_{j}-1)}$ since there are at
most $\sum_{j=2}^{s}k_{j}-1$ vectors in $S^{\prime}$ that are from
$V^{\prime}$ and thus have norm $M,$ while the remaining vectors are from $V$
and have norm $1.$

In either case, we have $\text{OPT}(U\cup V^{\prime})\leq
M^{2(\sum_{j=2}^{s}k_{j}-1)}\leq\text{OPT}(V\cup V^{\prime})/M^{2},$ thus
$\text{OPT}(V\cup V^{\prime})$ can be arbitrarily large compared to
$\text{OPT}(U\cup V^{\prime}).$ ∎

For $k\geq d,$ using similar arguments, we can show that any $\alpha$-coreset
for determinant maximization under partition constraint with finite
approximation factor $\alpha$ must have size $t\geq k+d(d-1).$

######  Lemma 33.

Suppose $k\geq d.$ Consider the partition matroid
$\mathcal{M}=([n],\mathcal{I})$ of rank $k$ defined by a partition
$P_{1},\cdots,P_{k}$ and constraint $k_{1}=\cdots=k_{k}=1.$ Any composable
coreset for the determinant maximization problem under partition matroid
constraint $\mathcal{M}$ with size $t<k+d(d-1)$ must incur an infinite
approximation factor.

###### Proof.

The construction is similar to the proof of Lemma 32. Let $V$ be s.t. $V\cap
P_{i}$ consists of
$\operatorname{}\mathopen{}\left\\{M_{i}e_{1},\cdots,M_{i}e_{d}\mathclose{}\right\\}$
with $M_{1}\geq M_{2}\geq M_{d}\gg M_{d+1}\cdots\geq M_{k}$ to be chosen
later. Let $U$ be a coreset for $V$ with finite approximation factor. Clearly,
$\operatorname{}\mathopen{}\lvert V\cap P_{i}\mathclose{}\rvert\geq 1.$ We
will show that $\operatorname{}\mathopen{}\lvert U\cap
P_{i}\mathclose{}\rvert=d$ for $i=1,\cdots,d,$ and thus conclude that
$\operatorname{}\mathopen{}\lvert
U\mathclose{}\rvert\geq(k-d)+d^{2}=k+d(d-1).$

For the base case of $i=0,$ the claim holds trivially. Suppose that the claim
hols for $i-1$ with $i\geq 1$. Then we show that it holds for $i.$ We assume
for contradiction that $\operatorname{}\mathopen{}\lvert U\cap
P_{i}\mathclose{}\rvert\leq d-1.$ W.l.o.g., assume $U\cap
P_{i}\subseteq{M_{i}e_{1},\cdots,M_{i}e_{i-1},M_{i}e_{i+1},\cdots,M_{i}e_{d}}.$
Indeed, define $V^{\prime}$ where $V^{\prime}\cap
P_{t}=\operatorname{}\mathopen{}\left\\{Me_{t}\mathclose{}\right\\}$ for
$t\in\operatorname{}\mathopen{}\left\\{1,\cdots,i-1,i+1,\cdots,d\mathclose{}\right\\}$
and $V^{\prime}\cap P_{t}=\emptyset$ otherwise. By choosing $M\gg M_{1}$ and
$M_{i}\gg M_{d}\gg M_{d+1},$ we can ensure that the optimal instance in $V\cup
V^{\prime}$ must contain $d-1$ vectors in $V^{\prime}$ and $M_{i}e_{i}\in
V\cap P_{i},$ thus

$\text{OPT}(V\cup V^{\prime})\geq(M^{d-1}M_{i})^{2}.$

On the other hand, for any $S\subseteq U\cup V^{\prime},$ either

  * •

$\operatorname{}\mathopen{}\lvert S\cap V^{\prime}\mathclose{}\rvert\leq d-1:$
in this case $\mu(S)\leq\binom{k}{d}(M^{d-2}M_{1}^{2})^{2}$ since any
$W\in\binom{S}{d}$ must contain at most $d-2$ vectors of norm $M$ from
$V^{\prime},$ and the remaining vectors have norm at most $M_{1}.$

  * •

$\operatorname{}\mathopen{}\lvert S\cap V^{\prime}\mathclose{}\rvert=d-1:$
since $U\cap P_{i}$ is in the span of $S\cap V^{\prime},$ any
$W\in\binom{S}{d}$ with $\det(\sum_{i\in W}v_{i}v_{i}^{\intercal})\neq 0$ must
consist of at most $d-1$ vectors of norm $M$ from $V^{\prime},$ and the
remaining vectors must have norm at most $M_{d+1},$ thus
$\mu(S)\leq\binom{k}{d}(M^{d-1}M_{d+1})^{2}$

In either case, $\text{OPT}(U\cup V^{\prime})$ can be arbitrarily smaller than
$\text{OPT}(V\cup V^{\prime}).$ ∎

Finally, we show that for $k\geq d,$ the approximation factor of $d^{O(d)}$ is
optimal. For $k\leq d,$ [Ind+20] shows that approximation factor of $k^{O(k)}$
is optimal.

The following construction is from [Ind+20, section 7.1]. We include this for
completeness.

######  Definition 34 (Hard input for composable coreset).

Let $\beta=o(d/\log^{2}d),$ $m=d/\log d$ so that $d^{d/m}=O(1).$ Consider
$G\subseteq{\mathbb{R}}^{m+1}$ of $d^{\beta+2}$ vectors s.t. for every two
vectors $p,q\in G,$ we have $\langle p,q\rangle\leq O(\frac{\sqrt{\beta}\log
d}{\sqrt{d}}).$

For $i=1,\cdots,d-m$, construct $X_{i}$ as follows: pick a random index
$\pi_{i}\in[n].$ Embed $G$ into the subspace spanned by
$\operatorname{}\mathopen{}\left\\{e_{1},\cdots,e_{m},e_{m+i}\mathclose{}\right\\}$
s.t. the $\pi(i)^{th}$ vectors in $G$ is mapped into $e_{m+i}.$

Choose a random rotation matrix $Q,$ and return $QX_{1},\cdots,QX_{d-m}$ and
$QY_{1},\cdots,QY_{m}$ with
$Y_{i}=\operatorname{}\mathopen{}\left\\{Me_{i}\mathclose{}\right\\}$ for a
large enough $M.$

######  Theorem 35.

For $d\leq k\leq d^{\gamma}$ and $\gamma^{\prime}$ s.t.
$\gamma\gamma^{\prime}=o(d/\log^{2}d),$ any composable coreset of size
$k^{\gamma^{\prime}}$ must incur an approximation of
$(\frac{d}{\gamma\gamma^{\prime}})^{d(1-o(1))}.$ For example, the theorem
applies when $\gamma,\gamma^{\prime}$ are constant, i.e. $d\leq
k\leq{\operatorname{poly}}(d)$ and the coreset has size
${\operatorname{poly}}(k).$

###### Proof.

For a set $V$ of vectors, let $V^{\times t}$ be the set where each vector in
$V$ is duplicated $t$ times. Let $\beta=\gamma\gamma^{\prime}.$ We use the
construction in Definition 34 where every vector is duplicated $t=k/d$ times.
Let $QX_{1}^{\times t},\cdots,QX_{d-m}^{\times t},QY_{1}^{\times
t},\cdots,QY_{m}^{\times t}$ be the input sets. Let
$S=\operatorname{}\mathopen{}\left\\{Me_{1},\cdots,Me_{m},e_{m+1},\cdots,e_{d}\mathclose{}\right\\}$
then $S^{\times t}$ has value $\mu(S)\geq(k/d)^{d}(M^{m})^{2}.$

On the other hand, let $c(QX_{i}^{\times t})$ be an arbitrary coreset of size
$k^{\gamma^{\prime}}\leq d^{\beta}$ for $QX_{i}^{\times t}.$

As observed in [Ind+20, Lemma 7.2], the probability that
$C_{i}:=c(QX_{i}^{\times t})$ contains $Qe_{m+i}$ is bounded by
$\operatorname{}\mathopen{}\lvert c(QX_{i}^{\times
t})\mathclose{}\rvert/\operatorname{}\mathopen{}\lvert QX_{i}^{\times
t})\mathclose{}\rvert\leq 1/d^{2}.$ Thus, with probability $\geq 1-1/d,$ we
have $Qe_{m+i}\not\in c(QX_{i}^{\times t})$ for all $i\in[d-m].$ Assume that
this happens. Then for any $u\in C_{i}$

$\langle\sum_{i=m+1}^{d}e_{i}e_{i}^{\intercal},uu^{\intercal}\rangle\leq
O(\frac{\beta\log^{2}d}{d})$

thus for any $u_{1},\cdots,u_{m}$ in
$\mathcal{C}:=\bigcup_{i=1}^{m}c(QY_{i}^{\times
t})\cup\bigcup_{i=1}^{d-m}c(QX_{i}^{\times t})$

$\det(\sum_{i=m+1}^{d}(Me_{i})(Me_{i})^{\intercal}+\sum_{i=1}^{m}u_{i}u_{i}^{\intercal})\leq
M^{2m}(\max\langle\sum_{i=m+1}^{d}e_{i}e_{i}^{\intercal},uu^{\intercal}\rangle)^{d-m}\leq
M^{2m}\operatorname{}\mathopen{}\left\lparen\frac{O(\sqrt{\beta})\log
d}{d}\mathclose{}\right\rparen^{2(d-m)}.$

Hence, with probability at least $1-1/d,$ any size-$d$ subset $W$ in
$\mathcal{C}$ has $\det(\sum_{v\in W}vv^{\intercal})\leq
M^{2m}\operatorname{}\mathopen{}\left\lparen\frac{O(\sqrt{\beta})\log
d}{d}\mathclose{}\right\rparen^{2(d-m)},$ thus by Cauchy Binet, any size-$k$
subset $S$ in $\mathcal{C}$ has

$\mu(S)\leq\binom{k}{d}M^{2m}\operatorname{}\mathopen{}\left\lparen\frac{O(\sqrt{\beta})\log
d}{d}\mathclose{}\right\rparen^{2(d-m)}.$

Thus the approximation factor is at least
$\frac{1}{e^{d}}(d/(O(\sqrt{\beta})\log d)^{2})^{d-m}$ with $m=o(d).$

∎

## References

  * [Abb+13] Sofiane Abbar et al.  “Diverse near neighbor problem”  In _Proceedings of the twenty-ninth annual symposium on Computational geometry_ , 2013, pp. 207–214
  * [Add+22] Raghavendra Addanki, Andrew McGregor, Alexandra Meliou and Zafeiria Moumoulidou  “Improved Approximation and Scalability for Fair Max-Min Diversification”  In _arXiv preprint arXiv:2201.06678_ , 2022
  * [AGR16] Nima Anari, Shayan Oveis Gharan and Alireza Rezaei  “Monte Carlo Markov chain algorithms for sampling strongly Rayleigh distributions and determinantal point processes”  In _Conference on Learning Theory_ , 2016, pp. 103–115  PMLR
  * [AHV+05] Pankaj K Agarwal, Sariel Har-Peled and Kasturi R Varadarajan  “Geometric approximation via coresets”  In _Combinatorial and computational geometry_ 52.1 Cambridge University Press Cambridge, 2005
  * [AHY08] Pankaj K Agarwal, Sariel Har-Peled and Hai Yu  “Robust shape fitting via peeling and grating coresets”  In _Discrete & Computational Geometry_ 39.1 Springer, 2008, pp. 38–58
  * [ALW17] Zeyuan Allen-Zhu, Yuanzhi Li and Yining Wang  “Near-Optimal Discrete Optimization for Experimental Design: A Regret Minimization Approach”  In _Mathematical Programming_ 186, 2017  DOI: 10.1007/s10107-019-01464-2
  * [AMT13] Zeinab Abbassi, Vahab S Mirrokni and Mayur Thakur  “Diversity maximization under matroid constraints”  In _Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining_ , 2013, pp. 32–40
  * [Ana+20] Nima Anari, Kuikui Liu, Shayan Oveis Gharan and Cynthia Vinzant  “Log-Concave Polynomials IV: Exchange Properties, Tight Mixing Times, and Faster Sampling of Spanning Trees”  In _CoRR_ abs/2004.07220, 2020  arXiv: https://arxiv.org/abs/2004.07220
  * [AV21] Nima Anari and Thuy-Duong Vuong  “From Sampling to Optimization on Discrete Domains with Applications to Determinant Maximization”  In _arXiv preprint arXiv:2102.05347_ , 2021
  * [Bar+15] Rafael Barbosa, Alina Ene, Huy Nguyen and Justin Ward  “The power of randomization: Distributed submodular maximization on massive datasets”  In _International Conference on Machine Learning_ , 2015, pp. 1236–1244
  * [BB09] Julius Borcea and Petter Brändé n  “The Lee-Yang and Pólya-Schur programs. II. Theory of stable polynomials and applications”  In _Communications on Pure and Applied Mathematics_ 62.12 Wiley, 2009, pp. 1595–1631  DOI: 10.1002/cpa.20295
  * [BBL09] Julius Borcea, Petter Brändén and Thomas Liggett  “Negative dependence and the geometry of polynomials”  In _Journal of the American Mathematical Society_ 22.2, 2009, pp. 521–567
  * [BH19] Petter Brändén and June Huh  “Lorentzian polynomials”  arXiv, 2019  DOI: 10.48550/ARXIV.1902.03719
  * [Brä20] Petter Brändén  “Spaces of Lorentzian and real stable polynomials are Euclidean balls”  arXiv, 2020  DOI: 10.48550/ARXIV.2012.04531
  * [Bro+22] Adam Brown et al.  “Determinant Maximization via Matroid Intersection Algorithms”  arXiv, 2022  DOI: 10.48550/ARXIV.2207.04318
  * [Cha+15] Wei-Lun Chao, Boqing Gong, Kristen Grauman and Fei Sha  “Large-Margin Determinantal Point Processes.”  In _UAI_ , 2015, pp. 191–200
  * [CM13] Ali Civril and Malik Magdon-Ismail  “Exponential inapproximability of selecting a maximum volume sub-matrix”  In _Algorithmica_ 65.1 Springer, 2013, pp. 159–176
  * [Gon+14] Boqing Gong, Wei-Lun Chao, Kristen Grauman and Fei Sha  “Diverse sequential subset selection for supervised video summarization”  In _Advances in Neural Information Processing Systems_ , 2014, pp. 2069–2077
  * [Ind+14] Piotr Indyk, Sepideh Mahabadi, Mohammad Mahdian and Vahab S Mirrokni  “Composable core-sets for diversity and coverage maximization”  In _Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems_ , 2014, pp. 100–108  ACM
  * [Ind+20] Piotr Indyk, Sepideh Mahabadi, Shayan Oveis Gharan and Alireza Rezaei  “Composable core-sets for determinant maximization problems via spectral spanners”  In _Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms_ , 2020, pp. 1675–1694  SIAM
  * [KT+12] Alex Kulesza and Ben Taskar  “Determinantal point processes for machine learning”  In _Foundations and Trends® in Machine Learning_ 5.2–3 Now Publishers, Inc., 2012, pp. 123–286
  * [KT11] Alex Kulesza and Ben Taskar  “Learning determinantal point processes”, 2011
  * [Lee+16] Donghoon Lee, Geonho Cha, Ming-Hsuan Yang and Songhwai Oh  “Individualness and determinantal point processes for pedestrian detection”  In _European Conference on Computer Vision_ , 2016, pp. 330–346  Springer
  * [LZ21] Lap Chi Lau and Hong Zhou  “A local search framework for experimental design”  In _Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA)_ , 2021, pp. 1039–1058  SIAM
  * [Mad+19] Vivek Madan, Mohit Singh, Uthaipon Tantipongpipat and Weijun Xie  “Combinatorial algorithms for optimal design”  In _Conference on Learning Theory_ , 2019, pp. 2210–2258  PMLR
  * [Mad+20] Vivek Madan, Aleksandar Nikolov, Mohit Singh and Uthaipon Tao Tantipongpipat  “Maximizing Determinants under Matroid Constraints”  In _2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)_ , 2020, pp. 565–576
  * [Mah+19] Sepideh Mahabadi, Piotr Indyk, Shayan Oveis Gharan and Alireza Rezaei  “Composable core-sets for determinant maximization: A simple near-optimal algorithm”  In _International Conference on Machine Learning_ , 2019, pp. 4254–4263  PMLR
  * [Mir+13] Baharan Mirzasoleiman, Amin Karbasi, Rik Sarkar and Andreas Krause  “Distributed submodular maximization: Identifying representative elements in massive data”  In _Advances in Neural Information Processing Systems_ , 2013, pp. 2049–2057
  * [Mir+15] Baharan Mirzasoleiman, Amin Karbasi, Ashwinkumar Badanidiyuru and Andreas Krause  “Distributed submodular cover: Succinctly summarizing massive data”  In _Advances in Neural Information Processing Systems_ , 2015, pp. 2881–2889
  * [MJK17] Baharan Mirzasoleiman, Stefanie Jegelka and Andreas Krause  “Streaming Non-monotone Submodular Maximization: Personalized Video Summarization on the Fly”  In _arXiv preprint arXiv:1706.03583_ , 2017
  * [MMM20] Zafeiria Moumoulidou, Andrew Mc Gregor and Alexandra Meliou  “Diverse Data Selection under Fairness Constraints”  In _arXiv preprint arXiv:2010.09141_ , 2020
  * [MZ15] Vahab Mirrokni and Morteza Zadimoghaddam  “Randomized composable core-sets for distributed submodular maximization”  In _Proceedings of the forty-seventh annual ACM symposium on Theory of computing_ , 2015, pp. 153–162  ACM
  * [Nik15] Aleksandar Nikolov  “Randomized rounding for the largest simplex problem”  In _Proceedings of the forty-seventh annual ACM symposium on Theory of computing_ , 2015, pp. 861–870
  * [NS16] Aleksandar Nikolov and Mohit Singh  “Maximizing determinants under partition constraints”  In _Proceedings of the forty-eighth annual ACM symposium on Theory of Computing_ , 2016, pp. 192–201
  * [Nui68] Waa Nuij  “A Note on Hyperbolic Polynomials.”  In _Mathematica Scandinavica_ 23, 1968, pp. 69–72
  * [Pan+14] Xinghao Pan et al.  “Parallel double greedy submodular maximization”  In _Advances in Neural Information Processing Systems_ , 2014, pp. 118–126
  * [WIB14] Kai Wei, Rishabh Iyer and Jeff Bilmes  “Fast multi-stage submodular maximization”  In _International conference on machine learning_ , 2014, pp. 1494–1502
  * [Yao+16] Jin-ge Yao et al.  “Tweet Timeline Generation with Determinantal Point Processes.”  In _AAAI_ , 2016, pp. 3080–3086