Composable Coresets for Determinant Maximization: Greedy is Almost Optimal

Given a set of $n$ vectors in $\mathbb{R}^d$, the goal of the \emph{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 \textit{composable 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 $C^{k^2}$, 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+\sqrt{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.

Paper

Similar papers

Peer review

Reviewer KpLA5/10 · confidence 5/52023-06-23

Summary

The paper investigates the composable coresets for the determinant maximization problem that aims to pick $k$ vectors with the maximum volume. The authors prove that the widely-used greedy algorithm also provides composable coresets with an approximation factor of $O(k)^{3k}$, followed by showing a local optimality property for greedy. Empirical results show that the local optimality of the greedy algorithm is even lower.

Strengths

- The topic of DPP is relevant. - The technical result is solid. - The observation of local optimality for greedy is of independent interest.

Weaknesses

- The paper is a follow-up work of [IMGR20]. The improved analysis for the greedy algorithm is interesting but not the first result of a composable coreset. - The studied problem is limited, e.g., only consider unconstrained DPP in which every set $P_i$ selects exactly $k$ vectors.

Questions

- Can the theoretical result extend to other settings of DPP, e.g., different $P_i$ selects a different number of vectors, or certain constrained DPP? - The observation of local optimality for greedy is interesting, does it have other applications?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

No. I suggest discussing some social impact, e.g., whether the greedy is better or worse for fairness issues than local search.

Reviewer vec76/10 · confidence 4/52023-07-06

Summary

This work studies the determinant maximization problem, in which the input is a set of $n$ vectors in $d$ dimensions, and the goal is to select a subset of $k\leq d$ of these vectors which maximizes the determinant of the Gram matrix of the $k$ vectors, which is also the volume of the parallelepiped spanned by the vectors. This is an important classical problem with connections to diversity. A popular heuristic for this problem is the greedy algorithm, which iteratively builds a set of vectors one at a time by selecting the vector that maximizes the improvement in the current volume. In prior work, an analysis of the greedy algorithm was given, which showed that it gives a $C^{k^2}$ factor approximation. However, the best known lower bound is $\Omega(k^{k-o(k)})$ (for composable coresets? not sure what the exact setting is here). This work shows that the analysis of the greedy algorithm can in fact be tightened to approximately match this upper bound, giving an approximation factor of $O(k)^{3k}$. This result is shown by proving that the greedy algorithm is approximately locally optimal, which in turn implies the approximation guarantee from results shown in prior work.

Strengths

The analysis of greedy is an extremely important and old question (the prior bound is over 10 years old), and the authors provide a very nice improvement to this result, and achieves a tight approximation over some class of algorithms. The analysis is nontrivial to carry out.

Weaknesses

While the result is very important, the techniques might be viewed as incremental over the analysis of local search given in prior work, and the paper doesn't give much intuition or discussion on why this result might have been missed in prior work.

Questions

* I could not find the referenced lower bound of $\Omega(k^{k-o(k)})$ in prior work (I checked https://arxiv.org/abs/1907.03197 and https://arxiv.org/abs/1807.11648), I would appreciate a pointer to a specific theorem stating this. In particular, I would like to understand the exact setting in which this lower bound applies.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Yes

Reviewer 3pA16/10 · confidence 3/52023-07-07

Summary

The paper gives a tighter analysis for the greedy algorithm for constructing composable coreset for the determinant maximization problem. The greedy algorithm performs well in practice; however, the previous analysis was giving an approximation factor much farther from the lower bound. The authors in the paper bring the approximation factor for greedy algorithm much closer to the lower bound. this is achieved by showing that by just swapping a single point from the greedy solution with a vector obtained using local search approach does not increase the volume (determinant) by much. The authors also perform some experiments to show that in practice this local optimality property of greedy algorithm is actually much better than theoretical bounds.

Strengths

The paper is well written and clear. I tried to go through the proofs and unless I have missed something, the proofs are sound. Infact the proofs look quite elegant using techniques from simple linear algebra. Code is provided for the empirical results. By closing the gap between the lower bound and the approximation factor given by the greedy algorithm, the paper is able to give better explanation for the good performance of greedy algorithm in practice.

Weaknesses

The only weakness I could think of is that the contribution is only theoretical and does not really have much practical implication as greedy algorithm was already known to perform nicely in practice. The simplicity of the proof techniques while not really a weakness may not excite the community much from the novelty perspective.

Questions

Please refer to weaknesses.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

Please refer to weaknesses.

Reviewer rYtN6/10 · confidence 3/52023-07-07

Summary

The paper considers the problem of picking k among n vectors that maximize the volume of the parallelepiped spanned by the selected vectors, which is equal to the squared determinant of the corresponding Gram matrix. In particular, the authors focus on the composable coreset setting of the problem where given a large dataset split into multiple subsets, the aim is to find small summaries (coreset) of each subset such that the union of the summaries is a good summary of the full dataset. Existing work showed that the best approximation possible for this problem is $\Omega(k)^{k - o(k)}$ and that an LP-based algorithm achieves almost optimal $\tilde{O}(k)^k$-approximation. Another Greedy algorithm followed by local search, which works better in practice than the LP-based one, was also shown to achieve ${O}(k)^{2k}$-approximation, while the Greedy algorithm alone is only shown to achieve $C^{k^2}$ for some constant $C$. This paper provides an improved approximation guarantee of ${O}(k)^{3k}$ for the Greedy algorithm, by providing an almost tight bound on the local optimality of the solution outputted by Greedy. The presented numerical results also show that the local optimality of the Greedy solution is significantly lower than the theoretical upper bound on real and random datasets.

Strengths

- The paper provides a new analysis to the greedy algorithm which significantly improves upon its known approximation guarantee. Even though this approximation is still worse than the guarantees achieved by the LP-based and the Greedy + local search algorithms, this result is interesting as in practice the greedy algorithm performs better than the LP-based one, and skipping the local search stage saves time. - The theoretical results are correct and experimental results illustrate nicely that the local optimality of the Greedy solution in practice is significantly better than the theoretical bound.

Weaknesses

- The paper is not well self-contained; several details are omitted in the discussion and proofs which affect clarity (see questions for details).

Questions

Suggestions to improve clarity: - The Greedy algorithm description in the preliminaries Section 1.1.1 does not match the pseudocode in Algorithm 1 with no mention of the relation between them. It is good to explicitly discuss the relation between the two, even if this is possibly well known. - In the proof of Theorem 5, the vectors in V are implicitly assumed to be linearly independent. This should be stated explicitly, explaining why this can be assumed without loss of generality. - Provide details for the expression of $\mathrm{vol}(V)$ given in Theorem 5 and for why $|a^j_l| \leq 1$, or at least a clear reference. Similarly for other steps in this proof and other ones. - Provide a reference for Lemma 6. - In the experiments, do you use the data points directly as feature vectors, or you apply a kernel as in prior work? Minor comments/suggestions: - using $\mathrm{vol}(S)$ to denote the square volume is a bit confusing. I propose to use $\mathrm{vol}^2(S)$. - typo line 87: $(2 k ( 1 + \epsilon))^k \rightarrow (2 k ( 1 + \epsilon))^{2k}$ - typo line 154: $a^j_i \rightarrow |a^j_i|$

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

yes

Reviewer vec72023-08-10

Thank you for the clarification on the lower bound.

I encourage the authors to include this reference in the main text, since it is crucial for understanding the claim of optimality. If you could give at least a partial answer to the question "why this result might have been missed in prior work", this would be very helpful. In particular, the main trick seems to be the use of the matrix determinant lemma, but this seems to be a common tool in the area of determinant maximization, so I find it somewhat surprising that this kind of observation was not made before. Would it be possible to give some more insight into what might have been the "key" that prior work didn't have, or maybe a particular difficulty in the calculations? It is of course possible that it was just missed, I'm just wondering if the authors had any take on this.

Authorsrebuttal2023-08-11

We will make sure to include the reference in the final version. Regarding why this was missed previously, in short, those papers were pursuing different approaches as described below. Our goal however was to understand the local optimality property of the greedy algorithm and answering "does the greedy algorithm have similar properties as the local search algorithm?" While simple in retrospect, it is not clear why it should be helpful at the first look. Please see below for more details. In the composable coreset setting, in [MIGR19]: they used a more geometric based approach. In particular, the key idea was that a coreset for the directional height problem implies a composable coreset for determinant maximization. So it remained to show that a simple determinant maximization algorithm yields a coreset for directional height. The authors observed that local search was very helpful in proving the k-directional heights result. When the authors returned to the vanilla greedy algorithm, they tried to analogously perform the same reduction, but without the local optimality assumption. Without local optimality, the guarantee was much weaker. Our key contribution is the "local optimality property" of the greedy algorithm. Therefore we can directly use the result of [MIGR19] on Local Search, to get our result for greedy, thus bypassing the lossy reduction which tries to get a coreset for directional height directly from greedy. In the composable coreset setting in [IMGR20]: they follow an approach based on spectral spanners. Their goal was to get the best constant in the exponent (e.g. k^{k/2}) and thus their algorithm is based on solving an LP and is not optimized for simplicity and practical use. In the offline setting: the reason it was probably missed is that swapping a vector into the greedy solution can break the "structure" of the greedy solution after even the first swap, so the vectors have to be carefully introduced in a sequence. So thinking of the structural property of local optimality would not be the first approach: indeed, [CMI09] iteratively compares the greedy and optimal solutions in a very different manner.

Reviewer rYtN2023-08-11

Response to rebuttal

Thank you for your response and additional experiment. The additional derivation of the $k!$ guarantee of offline greedy is also interesting. I highly recommend including more detailed explanations of the proof steps, beyond what you stated in the rebuttal. This would increase the readability of the paper to a wider audience.

Authorsrebuttal2023-08-11

Thank you for finding this application interesting and for your comment. We will certainly describe the proof steps in further detail for the final version.

Authorsrebuttal2023-08-16

We hope that our responses have clarified all questions about our paper, and we will make sure to incorporate your feedback in our final version. If you believe that all major concerns have been addressed, could you please consider increasing the scores to support the inclusion of our paper in NeurIPS? Thank you so much!

Reviewer 3pA12023-08-17

Replying to Rebuttal

Thanks for the response. I will keep my score

Program Chairsdecision2023-09-21

Decision

Accept (poster)

© 2026 NYSGPT2525 LLC