Composable Coresets for Determinant Maximization: Greedy is Almost Optimal
Authors: Siddharth Gollapudi
Sepideh Mahabadi
Varun Sivashankar
Venue: NeurIPS 2023 poster (2023)
Keywords: Determinant Maximization
Composable Coresets
Greedy Algorithm
DPP
TL;DR: We show that the greedy algorithm provides an almost optimal composable coreset for the determinant maximization problem.

Abstract: 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.

Composable Coresets for Determinant Maximization: Greedy is Almost Optimal*
Siddharth Gollapudi Microsoft Research
Sepideh Mahabadi Microsoft Research smahabadi cwwcofoff..ccooooom
Varun Sivashankar Microsoft Research
sgollapu@berkelley edu
varunsiva@priicetonn.co
Abstract
Given set vectors in RR,, the goal of the determinant maximization problem is pick & 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 data, this problem has been studied the relevant composable coreset setting. In particular, [IMGR20) showed that
get composable coresets with optimal approximation factor of ((k)* for the problem, and that a local search algorithm achieves an almost optimal approximation guar- antee of (R)))2 In this work, show that the widely-use Greedy algorithm also provides composable coresets with an almost optimal approximation factor
(k))a, 3k which improves over the previously known guarantee of C**², and supports the prior experimental results showing the practicality of the greedy algorithm as a coreset. Our main result follows by showing 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 factor of at most (1 + Vk). 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 real data sets.
Introduction
In the determinant maximization problem, we are given set P of vectors in R and a parameter k < d. The objective is to find a subset S = f.i...., Uk that the volume squared of the parallelepiped spanned by the points the subset Equivalently, the volume squared of set S, denoted by vol( ), is equal to the determinant of the Gram matrix of the vectors S. Determinant maximization is the MAP-inference of determinantal point processes, and both of these problems as well their variants have found numerous applications data summarization, machine learning, experimental design, and computational geometry. In particular, the determinant of 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 GCGS14]
C P consisting of l: vectors such that
maximized.
KT 12 (SGSS55 KTII YFZ 16 [CYO16].
The best approximation factor for the problem in this regime is due the work of Ni who shows a factor of c and it is known that an exponential dependence on k is necessary [CMI13] unless = NP. However, the most common algorithm used for this problem in practical applications is natural greedy algorithm. In this setting, the algorithm first picks the vector with the largest norm,
*This is equal contribution paper
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

and then greedily picks the vector with largest perpendicular component to the subspace spanned by the current set of picked vectors, thus maximizing the volume greedily in each iteration. This algorithm is known to have an approximation factor of (k!)² (CM199)
As in most applications of determinant maximization one needs work with large amounts of data, there has been an increasing interest in studying determinant maximization in large data models of computation [MJK17 WIB 14, PIG 14, MKSKI3 [KBKI5 MZ15 BENWI5). One such model that we focus on in this work is the composable coreset setting [MMM14 Intuitively, composable
coresets are small "summaries" of data set with the composability property: for the summaries of multiple datasets, the union of the summaries should make good summary for the union of the datasets. More precisely, in this setting. instead of a single set of vectors P. there are m sets Pi...., Pm R... In this context, a mapping function e that maps a point set to one of its subsets called a-composable coreset for determinant maximization, if for any collection of point sets Pi, Pi...., Pm..
MAXDET k (U (U[])((P)))
(P.))
MAXDET P
where MAXDET & is used to denote the maximum achievable determinant with parameter k. (Sim- ilarly, MAXVOL; is used to denote the maximum volume, with MAXVOL = MAXDET For clarity, we note that the mapping function c can only view its input data set P. and has no knowledge of other data sets while constructing c(P.). [IMMM]4] showed that a composable coreset for task automatically gives an efficient distributed and an efficient streaming algorithm for the same task.
Indeed, composable coresets have been used for determinant maximization. In particular, [MGR20
MIGRI9], presented a composable coresct of size O( log k) with approximation factor of Okk)* using spectral spanners, which they showed to be almost tight. In particular, the best approximation factor one can get is ((()=-((k) (Theorem I 1.4). As the above algorithm is LP-based and does not provide the best performance in practice, they proposed to use the greedy algorithm followed by a local search procedure, and showed that this simple algorithm also yields coreset of size k with an almost optimal approximation guarantee of ((k)a They also proved that the greedy algorithm alone yields C*²² guarantee for composable coresets, which is far larger than the optimal approximation of (k)) for this problem.
MKSK13), an improved analysis of the greedy algorithm in the coreset setting is very desirable. Furthermore, both of these prior work implied that greedy performs well in practice in the context of distributed and composable coreset settings [MKSK]3] and in particular its performance is comparable to that of the local search algorithm for the problem [MGR[9]
Since the greedy algorithm provides a very good performance in practice [MIGR19
Our contribution. In this paper, we close this theoretical gap: we prove that the greedy algorithm provides a -colposcco coreset for the determinant maximization problem (Theorem 4). This explains the very good performance of this algorithm on real data previously shown in [MGRR9 MKSKI3]. We achieve this by proving an elegant linear algebra result on the local optimality of the greedy algorithm: swapping single point from the greedy solution with vector that was not picked by the greedy algorithm can increase the volume by a factor of at most (1 + vk). We further show that this is tight up to the additive constant 1. As an application of our result, we give a proof that the locality property can recover and in fact marginally improve the k guarantee of the greedy algorithm of [M1109] for the offline volume maximization problem.
Finally, in Section 4 we run experiments to measure the local optimality of the greedy algorithm on real data, and show that this number is much smaller in practice than the worst case theoretically guaranteed bound. In fact, in our experiments this number is always less than 1.5 even for l even as large as 300. Again this explains the practical efficiency of the greedy algorithm as a coreset shown in [9 MKSK13].
1.1 Preliminaries
1.1.1 The Greedy Algorithm
Recall the standard offline setting for determinant maximization, where one is required to pick vectors out of the vectors in P of maximum volume. Here, (CM109) showed that greedily picking
2

---

the vector with the largest perpendicular distance to the subspace spanned by the current solution (or equivalently, greedily picking the vector that maximizes the volume as in Algorithm([) outputs set of vectors that is within k! of the optimal volume. Formally, if Greedy(P) P) is the output of Algorithm| then
MAXVOL k!
vol(Greedy(P))
1.1.2 Local Search for Composable Coresets
In [MGRR99] the authors show that the greedy algorithm followed by the local search procedure with parameter e (as described in Algorithm 2) provides (2k(1 + +)))*-composale
coreset for determinant maximization. A locally optimal solution can thus be naturally defined as follows:
Definition 1 ((1 + e)-Locally Optimal Solution). Given a point set P C n and c(P) C P with [c(P)] = k, say c(P) is a (1 e)-locally optimal solution for volume maximization if for any v E PP)) and any w E P c(P).
vol(e(P) - + w) (1 + e) vol(c(P))
Given the output of the greedy algorithm Greedy P). one can obtain a locally optimal solution using series of swaps: if the volume of the solution can be increased by factor of (1 + E) by swapping vector in the current solution with a vector in the point set P that has not been included, we make the
swap. Since vol (o(Gredyy(()) ()) is within a factor of k! of the optimal, we will make at most log(1+e) swaps. This is precisely the local search algorithm (Algorithm For any point set P. we denote the output of Algorithm by LS(P).
logg
In MIGRI9,, the authors prove that local search yields ccooppsaabeee coreset for determinant maximization. Formally, they prove the following.
Theorem 2. Let Pi..... P... C Rd. For each = 1....,,, m, ler LS(P.) be the output of the local
search algorithm (Algorithm 2 with parameter e. Then
MAXDET & P.) I (2k(1 + e))²² MAXDET (U LS(P.))
(4)
Remark 3. Even though [MIGRI9] treats small constant in [o, 1). the proof for Theorem above holds for any non-negative e.
1.2 Outline of our approach
In [MGR]9] the authors prove Theorem 2 for local search using reduction to related problem called k-directional height. The authors then use similar ideas to prove that the output of the greedy algorithm is also composable coreset for determinant maximization. However, since we do not know a priori whether greedy is (1 + c)-locally optimal, the guarantee they obtain is significantly weaker: they only prove that the greedy algorithm yields a ((2k) 3* 3 = Ck² -composable coreset for determinant maximization. This is clearly far from the desired bound of kO(M)
To improve the analysis of the greedy algorithm in the coreset setting, ask the following natural question:
Can we prove that the output of the greedy algorithm is already locally optimal?
We answer this question positively. Our main result is Theorem where we show that for any point set P. Greedy(P)) (P) is a (1 -ooolocllly optimal solution. In other words, the greedy algorithm has the same guarantee as local search with the parameter = VT. This circumvents the loose reduction from greedy to the k-directional height problem and directly implies the following improved guarantee for the greedy algorithm in the coreset setting:
Theorem 4.
MAXDET (U,))) < (2 + Vk)) MAXDET (L Greedy(P.))
(5)
Thus, the greedy algorithm also provides (2k(1 + vk))2k coW)-composaall coreset for determinant maximization, which is near the optimal (((k)))
3

---

Section 2 is dedicated to proving that greedy is (1 + Vk)-locally optimal (Theorem We also show that this local optimality result of (1 + vk) for the greedy algorithm is tight up the additive constant 1. In Section 4 we show that on real and random datasets, the local optimality constant e is much smaller than the bound + vE, which serves as an empirical explanation for why greedy performs much better in practice than what the theoretical analysis suggests.
Algorithm I Greedy Algorithm
Algorithm 2 Local Search Algorithm
Input: A point set P C Rd and integer k.
Input: point set P C R integer k; and 0.
Output: A set C P of size k.
Initialize C C=00 =0. 0.
Output: A set C P of size Initialize C 0.
for to do
Add peple vol(C to C.
for fori= 1 to k do
end for Return
Add argmax vol(C + +p) to end for repeat
If there are points q E P and p E C such that
vol(C + (1
replace p with q. until No such pair exists. Return C.
2 Greedy is Locally Optimal
Theorem 5 (Local Optimality). Let V Greedy(P) (U1,...,tt, 4k S P be the output of the greedy algorithm. Let ukt1 P PPT V be a vector not chosen by the greedy algorithm. Then for all , k,
vol(V vs vx+11 51 vol(V)
(6)
Proof. If rank(P) k; then the result is trivial. So we may assume rank(P) 2 and is linearly independent. Fix any e; E V. Our goal is to show that vol(V Us + Uk+1) S (1 + vk) vol(V). This trivially holds when ie by the property of the greedy algorithm, assume 1 S 1
Let (ui,..., ug. 3 be the set of orthogonal vectors constructed by performing the Gram-Schmidt algorithm on {ur..... Uk, 1k+1). Formally, let G. span (1i, )2 Define v/ vn and 1/द it - (T 1) for 2....,ka + where (v) denotes the projection of the vector u onto the subspace G. Note that
k
vol(V) II 10/
j=1
For each j = i+ 1,..., k, + 1, write
1y I(G,)))(T,)) + Σ ofvl
1mi
II(()-1)())) w
We must have that |ag1 < by the greedy algorithm because if |a/| 1, the vector ey would have been chosen before vt. Further, a² = 1 by definition of Gram-Schmidt. The vector wy is what remains of Uy once subtract its projection onto the first i - 1 vectors.

---

We are interested in bounding the following quantity:
vol(V V/3 + uk+1) vol(v1. 4/- 01410-1-111 Ukr uk+1)
vol(o):-... 1/ , 0k, uk+1)
vol(e)..... 1/ W441... wk: wk+1)
vol(e)....... v/-1) vol( wky wk-1)
1 vol(w:+1,.... wk. wk+1)
Therefore, it suffices to prove the following:
vol(w:+1,.... WK, wk+1) - (1 vk)
|0/ll2 j=1
To establish this, we consider two cases. Recall that 0/4+1 Me+1 (vx). We analyze the cases
where v/+1 * 0 and v = 0 separately, although the ideas are similar. Claim 7 and Claim below, we establish the desired bound stated in Eq. (7) for 1/441 * 0 and 2 = respectively Theorem 5 then follows immediately.
To prove Claim and Claim 8 the following well-known lemma will be useful. proof can be found in [D077.
Lemma 6 (Matrix Determinant Lemma). Suppose M is an invertible matrix. Then det(M + "v²") = (1 + x M M det(M)
(8)
Claim 7. Suppose u/41 # O. Then
vol(w;+1,.... Wk; wk+1)
(Vk++
II 10/l2
(9)
Proof. Define the matrix B
[w0+1] ... lwy [k++1] Note that det(BB B)
vol(w)+1..... Wk: w 2 is the quantity we are interested in bounding. For clarity,
i+ a
o vi rl41 ot
a
a/ 1/42
BT
k+ a
k k+1 ak
o
+ 1
We define the matrix A by just removing the of terms from B as follows:
++2 1'+1
a 2 + 2/42
AT
a 1/41 + + ax k+ 0/ + 1/411
Since (0%, 0z) = 0 for all / i, we have that
A"A=A"A+ wn"
where the column vector u is given by
" = || (a i+l
i+2
a #+1)
a
Since Jaद] < for j = 1,
+ 1 by the nature of the greedy algorithm, we have that
||u11 < (k + 1) k|
(10)
5

---

We now bound the desired volume quantity. Let M = A. M is clearly positive cenindefinite matrix. In fact, because we assumed that 1/441 O, it will turn out that M is positive definite and thus invertible. For now, assume that M1 exists. We will compute the inverse explicitly later.
vol(w++1,,... wh: wk+ )² del(B² 13==_1 B)
det(AA + wu²)
(1 + v² M M- det(M)
[by Lemma
(1 > max (M (M) det (M)
where Amax (max is the largest eigenvalue of MM We will now show that M does in fact exist and bound Amax [M (). Consider the matrix and W defined as follows:
0
6422
0
E
W
a4+1
k+1
k+1
1
It is easy to check that EWT A², Therefore,
M = A A
WE = EDET
where the diagonal matrix given by
= diag (10/44 12 .l.................... 1 6 12
is easy to see that E has all eigenvalues equal 1, and so must be invertible with determinant 1. The same is obviously true for FT, F-1 and (F²)- well. It follows that
det(M) = det (D) = || 11?
Since 1/411 # O, we have that || [| > 0 for all j. so D clearly exists. It follows that
M (A7 A) -
Amax M (M < Amax (D-1)
10 1
Therefore,
vol(w:41.... wk. wk+1 )2 < (1 122 > (M (M-))) det(M)
k 1|l0:112
< 1
det(MM
|| 1|
det(M) +
k:
$ (1 + k)) 10
mm
Claim 8. Suppose o = 0. Then
(1 (1+ + vk) II &
vol(w:+1.
Wke wk+1) <
12/l2
(11)
Proof. The idea for this proof is similar to the previous claim. However, the main catch is that decomposing Td B into AT + un? (as defined in the proof of Claim 7 is no longer helpful because 2/41 = 0 implies that A A is not invertible. However, there is simple workaround.

---

Define the matrix B' = Note that the quantity we are interested in bounding. Recall that 1/4+1 by assumption. For clarity,
B³) vol( Wk: Wk+11
k+1 oi + ..... + aj
R+ 2//
+t V/ + 1/+1
(B')*
a
++2 2 of + 0 0+41 10/2 + o/42
o + 2/2
Note that (B") is the same 8" from the proof Claim exxept for moving the last row the position of the first row. This change is just for convenience in this proof.
Define the following coefficients matrix C E R (k- 1 (+++))++
++1
k
Q
+1
0
0
0
0
0
0
+2
0
1
0
0
0
0
((a
k+1 -)
a/11
k+1
dg
k+1
0
0 6+1
0
4+1
C" + texx
Define W = Tef] ... l..l, By construction, (B') = C(W').. Therefore
(W")"W- W = =DD' D' diag
follows that
dct((B')T B') = (ot(C(("))TWll det(C)² det()")
k det II 10
It remains to show that det(CC) < (1 Vk). We may assume that g.++1 2 0 by taking the negative of the first column if necessary. This does not affect the magnitude the determinant, Note that all eigenvalues of C" and (C")-1 are Further,
|0 < -itsk
(12)
|det(C)] (1 (C)) |de((C")
[by Lemma
|1 + x- (C')-teil
< + (C*)-11)
1 Vk
We now provide simple example where the output of the greedy algorithm is at best / locllly optimal, thus demonstrating that the locality result for greedy is optimal up to the constant
Theorem (Tightness of Local Optimality). There exists a point set P {ui, .... Uk Uk+1 from which the greedy algorithm picks V = fei...., }x and
vol(V - v1 wk+1) Vk
(13)
vol(V)
7

---

Proof. Let P = {Ui,..., Uk. Uk+1) where ti E R is the vector of all ones and = Vke;-1 for i= == ,,.... k + 1. Since the magnitude of every vector in P vk, the greedy algorithm could start by picking v1. The greedy algorithm will then pick any - 1 of the remaining & vectors. Without loss in generality, assume that the algorithm picks V fui..... dx}. Then vol(V) = (vk)*-1. On the other hand, vol(V 01 + Uk+1) = (Vk)*. The result follows.
3 Application to Standard Determinant Maximization
The greedy algorithm for volume maximization was shown to have an approximation factor of k! in
[CM109]. We provide completely new proof for this result with a slightly improved approximation factor.
Theorem 10. Let P be point set, Greedy(P) (U1,.... [Kk the output of the greedy algorithm, and MAXVOL the maximum volume of any subset of k vectors from P. Then
(AX)
vol(Greedy(P))
(14)
IT +vi)
Proof. Let S P be the set of k vectors with maximum volume. Without loss of generality and for simplicity of exposition, we assume that Greedy (P) n = Ø (the proof still goes through if this is the case). We will order S in a convenient manner.
Consider the set W1 = {w1 U with k + elements. Perform the greedy algorithm on W1 with steps. Clearly, greedy will choose v1 first and then some 1 of the remaining vectors. Label the left out vector W1.
Inductively define W4+1 (w1,..., Ve, U1+1 US (wi,... w:)). }), which has size k 1. Perform greedy on W++1 with steps. The first i + vectors chosen will be 01.-... U2 Di+1 by definition. Call the left out vector w1+1- We now have an ordering for S = (wi,..., W
Starting with the greedy solution, we will now perform k swaps obtain the optimal solution. Each swap will increase the volume by factor of at most with Greedy(P)) = {VI...., J. Note that this is also the output of greedy when applied to the set (r))dy(P) {wr} Wk. Swapping in wk place of Uk increases our volume by a factor of at most + Vk.
Vi. Initially, our solution starts
Our current set of vectors is now {UI,..., 11- w. By the ordering on S, this is also the greedy
output the set W (UI,..., , 1, Wk-1, w.). Therefore, we may swap in Wk-1 1 in place of #j-1 in our current set of vectors by increasing the volume by most a factor of (1 + vk). Proceeding in this manner, we can perform & swaps to obtain the optimal solution from the greedy solution by increasing our volume by a factor of at most (1 + Vk.**.
To obtain the slightly better approximation factor in the theorem statement, observe that in the proof of Theorem 5] swapping out the 7th vector from the greedy solution for a vector that was not chosen increases the volume only by a factor of (1 + / + 1 - i) < 1 + V (Eq. (10).Eq. (2)), and that swapping out the ht vector does not increase the volume at all. Therefore, the approximation factor of greedy is at most
I (1+ k - Vi)
W.l for k 2 7, which is (kl) While the improve- ment in the approximation factor is quite small, we emphasize that the proof idea is very different from the kl guarantee obtained in [CM109]
Remark 11. Note that [1 + Vi) < /kl
8

---

Experiments
In this section, we measure the local optimality parameter for the greedy algorithm empirically. We use two real world datasets, both of which were used as benchmarks for determinant maximization in immediately related work (MIGRII9 LIS16::
MNIST LBBH98] which has 60000 elements, each representing 28-by-20 bitmap image of drawn digit;
GENES BQK+ 14). which has 10000 elements, with each representing the feature vector of gene. The data set was initially used in identifying a diverse set of genes to predict breast cancer tumors. After removing the elements with some unknown values, have around 8000 points.
We measure the local optimality parameter both function of k. and a function of the data set size as explained in the next two subsections.
4.1 Local Optimality for Real and Random Datasets as a Function of
Experiment Setup: For both MNIST and GENES, consider collection of m 10 data sets, each with n = 3000 points chosen uniformly at random from the full dataset. We ran the greedy algorithm for & from 1 to 20 and measured the local optimality value (1 + <) as fucntion of k = 2, 4..., 20 for each of the 10 data sets in the collection. More precisely, for each such k took the maximum value of (1 + e) over every data in the collection. The reason we take the worst value of (1 + e), is that in the context of composable coresets, we require the guarantee to hold for each individual data set to be (1 + e)-locally optimal. We repeated this process for iterations and took the average. We plot this value as a function of k.
Further, to compare against random data set, for both MNIST and GENES, repeated the above experiment against a set of random points of the same dimension sampled uniformly at random from the unit sphere.
As shown in Fig. while the real world data sets have local optimality value (1 + e) higher than the random data sets, they are both significantly lower than (less than 1.4) the theoretical bound of (1 + Vk). This suggests that real world data sets behave much more nicely and are closer to random than the worst case analysis would suggest, which explains why greedy does so well in practice.
Results:
For the purpose of diversity maximization, the regime of interest is when k < n. However, we wanted to verify that the local optimality value does not increase much even when k: is much larger and closer to n. Since measuring local optimality is expensive when both and n are large, we ran the same experiment again, except with n 300 points per point set, and measuring the local optimality at & = 1,50, 100,... 300 in steps of 50. Again, as seen in Fig. local optimality stays much below + v (in fact less than 1.5) for larger values of k as well.
Detasel:
Spalion
20
10.0
160
13.0
25R
30
1/2
20.32
A25
10.00
17.
2010
Figure I: Local Optimality (1 (1+e) against & for GENES and MNIST datasets, and random datasets of the same dimension. Each stream had 10 point sets of size 3000, with ie ranging from 20.

---

Delasel: GENES
Delavel:: MVIST
Deal
Beal Datuse
1.9
1.4
Dataue
3.15
3.05
1.0
1.0
100
150
200
250
201
50 100
350
200
250
300
Figure 2: Local Optimality (1 (L+60 é) against for GENES and MNIST datasets, and random datasets of the same dimension. Each stream had 10 point sets of size 300, with from to 300 in steps of 50. Note that when & (1,n), trivially have that (1 + c) 1.
4.2 Local Optimality as Function of the Size of Point Sets
Experiment Setup: Here, we fix the value E (5, 10, 15, 20} and compute the local optimality value (1 + while increasing the size of the point sets. The point set size is varied from 500 to 4000 in intervals of 500. For each point set size, we chose a stream of 10 random point sets from the dataset and took the maximum value over 10 iterations. Once again, did this MNIST and GENES and took the average iterations.
Results: As shown in Fig. the local optimality parameter remains very low (lower than 1.2) regardless of the number of points in the data set, which is much smaller than (1 vk).
Dalaset: GENES
Dataset: M/IST
1,700
10
1.25
1.
Local Qetrmatt Typiton
30
L3300
1.20
1.100
1130
Number in
Mumbor PE
Figure 3: Local Optimality ++)) against Number Points in the Base Set for k 5, 10, 15, 20.
Conclusion
In this work, provided almost tight analysis of the greedy algorithm for determinant maxi- mization in the composable coreset setting: we improve upon the previous known bound of C to 0(k)3 which is optimal upto the factor 3 in the exponent. We do this by proving result on the local optimality the greedy algorithm for volume maximization. We also support our theoretical analysis by measuring the local optimality of greedy over real world data sets. It remains an interesting question to tighten the constant in the exponent or otherwise provide lower bound showing that in fact optimal.
10

---

References
[BENWI5] Rafael Barbosa, Alina Ene, Huy Nguyen, and Justin Ward. The power of randomization: Distributed submodular maximization massive datasets. In International Conference on Machine Learning, pages 1236-1244, 2015.
[BQK 14] Nematollah Kayhan Batmanghelich, Gerald Quon, Alex Kulesza, Manolis Kellis, Polina Golland, and Luke Bornn. Diversifying sparsity using variational determinantal point processes. arXiv preprint arXiv::44 2014.
[CGGS15] Wei-Lun Chao, Boqing Gong, Kristen Grauman, and Fei Sha. Large-margin determi- nantal point processes. In UAI, pages 191-200, 2015.
[CMI09] Ali Çivril and Malik Magdon-Ismail. On selecting maximum volume sub-matrix of matrix and related problems. Theoretical Computer Science, 410(47-49))4801-488 2009.
[CMI13] Ali Civril and Malik Magdon-Ismail. Exponential inapproximability of selecting a maximum volume sub-matrix. Algorishmica, 65(1):159-176, 2013.
[DZ07] Jiu Ding and Aihui Zhou. Eigenvalues of raek-one updated matrices with some applica- tions. Applied Mathematics Letters, 1223::2222222266 2007.
[GCGS14] Boqing Gong, Wei-Lan Chao, Kristen Grauman, and Fei Sha. Diverse sequential subset selection for supervised video summarization. In Advances in Neural Information Processing Systems, pages 2069-2077, 2014.
[IMGR20] Piotr Indyk, Sepideh Mahabadi, Shayan Oveis Gharan, and Alireza Rezaei. Composable core-sets for determinant maximization problems via spectral spanners. Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1675- 1694. SIAM, 2020.
[MMM114] Piotr Indyk. Sepideh Mahabadi, Mohammad Mahdian, and Vahab S Mirrokni. Com- posable core-sets for diversity and coverage maximization. In Proceedings of the 33rd ACM 100-108. ACM, 2014.
symposium on Principles of database systems, pages
[TT1]] Alex Kulesza and Ben Taskar. Learning determinantal point processes. 2011.
KT 12] Alex Kulesza, Ben Taskar, et al. Determinantal point processes for machine learning. Foundations and Trends in Machine Learning. 5(2-3)::23-2886 2012.
[LBBH98] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient- learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-25 23244, 1998.
[LCYO16] Donghoon Lee, Geonho Cha. Ming Hang- Yang, and Songhwai Oh. Individualness and determinantal point processes for pedestrian detection. European Conference on Computer Vision, pages 330-346. Springer, 2016.
[LJS16] Chengtao Li, Stefanie Jegelka, and Suvrit Sra. Efficient sampling for k-determinantal point processes. In Artificial Intelligence and Statistics, pages 1328-1337. PMLR, 2016.
[MIRR19] Sepideh Mahabadi, Piotr Indyk, Shayan Oveis Gharan, and Alireza Rezaei. Compos- able core-sets for determinant maximization: A simple near-optimal algorithm. In International Conference on Machine Learning, pages 4254-4263 PMLR, 2019.
[MJK17] Baharan Mirzasoleiman, Stefanie Jegelka, and Andreas Krause. Streaming non- monotone submodular maximization: Personalized video summarization on the fly. arXiv preprint arXiv:1706.03583 2017.
[MBK15]] Baharan Mirzasoleiman, Amin Karbasi, Ashwinkumar Badanidiyuru, and Andreas Krause. Distributed submodular cover: Succinetly summarizing massive data. In Advances in Neural Information Processing Systems, pages 2881-2889, 2015.
11

---

[MKSKI3] 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, pages 2049-2057, 2013.
[MZI5] Vahab Mirrokni and Morteza Zadimoghaddam. Randomized composable core-sets for distributed submodular maximization. In Proceedings of the forty-seventh annual ACM symposium Theory computing, pages 153-162. ACM, 2015.
[Nik15] Aleksandar Nikolov. Randomized rounding for the largest simplex problem. In Pro- ceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 861-870. ACM, 2015.
[PJG 14] Xinghao Pan, Stefanie Jegelka, Joseph Gonzalez, Joseph K Bradley, and Michael I Jordan. Parallel double greedy submodular maximization. In Advances in Neural Information Processing Systems, pages 118-126, 2014.
[WIB14] Kai Wei, Rishabh Iyer, and Jeff Bilmes. Fast multi-stage submodular maximization. In International conference machine learning, pages 1494-1502, 2014.
|YFZ 16] Jin-ge Yao, Feifan Fan, Wayne Xin Zhao, Xiaojun Wan, Edward Y Chang, and Jianguo Xiao. Tweet timeline generation with determinantal point processes. In AAAI, pages 3080-3086, 2016.
12


Reviews:
[{"review_id": "B2zUcRtodw", "reviewer": "Reviewer_rYtN", "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.\n", "questions": "Suggestions to improve clarity:\n- 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.\n- 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.\n- 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.\n- Provide a reference for Lemma 6.\n\n- In the experiments, do you use the data points directly as feature vectors, or you apply a kernel as in prior work?\n\nMinor comments/suggestions:\n- using $\\mathrm{vol}(S)$ to denote the square volume is a bit confusing. I propose to use $\\mathrm{vol}^2(S)$.\n- typo line 87: $(2 k ( 1 + \\epsilon))^k \\rightarrow (2 k ( 1 + \\epsilon))^{2k}$\n- typo line 154: $a^j_i \\rightarrow |a^j_i|$", "limitations": "yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "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.\n \n- 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.\n", "weaknesses": "- The paper is not well self-contained; several details are omitted in the discussion and proofs which affect clarity (see questions for details).\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "To Reviewer rYtN, \n\nWe thank you for your positive feedback. Below, we have addressed your comments and questions. \n\n-----\n\n> 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.\n\nThanks, we will add clarification about why picking the vector with the largest perpendicular distance to the current solution is the same as greedily picking the vector that maximizes the volume.\n\n-----\n\n>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.\n\nIf the greedy solution is not linearly independent, then that means the rank of the n vectors is less than k, so both the greedy and optimal volume is 0. In this case, Theorem 5 directly holds without proof. We will add this explicitly as suggested.\n\n----\n\n>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.\n\n* The main idea behind the volume expansion is that subtracting a vector's perpendicular components from other vectors does not change the volume, similar to the Gram-Schmidt volume computation. We will elaborate on this further in the final version. \n\n* |alpha_l^j| <= 1 directly holds by the property of the greedy algorithm: if |alpha_l^j| > 1, then v_j would have been chosen before v_i. We will add details about this. \n\n* We will ensure that appropriate explanations are added for any ambiguous steps.\n\n----\n\n> Provide a reference for Lemma 6.\n\nWe apologize for missing this reference. A proof for this lemma can be found in the paper titled _Eigenvalues of rank-one updated matrices with some applications_, by Jiu Ding and Aihui Zhou. We will include this reference in the final version of our paper.\n\n-----\n\n>In the experiments, do you use the data points directly as feature vectors, or you apply a kernel as in prior work?\n\nWe use the data points directly as feature vectors. However, we don't expect the results to vary much. As an example, we applied the RBF kernel with sigma = 6 as used in prior work and repeated Experiment 1 on the GENES dataset for k = 2,4,...,20 and the random dataset. The local optimality was still very close to 1 (figure attached in the global response). \n\n-----\n\n> using $\\mathrm{vol}(S)$ to denote the square volume is a bit confusing. I propose to use $\\mathrm{vol}^2(S)$.\n\nOur analysis focuses on $\\mathrm{vol}(S)$, while $\\mathrm{vol}^2(S)$ is the determinant. For $\\mathrm{vol}^2(S)=$ determinant, we obtain a guarantee of $k^{3k}$, while local search and the optimal algorithm are known to have guarantees of $k^{2k}$ and $k^k$ respectively. If we instead want to write the guarantees in terms of volume, they become $k^{1.5k}$, $k^k$ and $k^{k/2}$ for greedy, local search and optimal respectively. We will make this distinction more clear in the final version.\n\n------\n\n> typo line 87: $(2 k ( 1 + \\epsilon))^k \\rightarrow (2 k ( 1 + \\epsilon))^{2k}$\n\n> typo line 154: $a^j_i \\rightarrow |a^j_i|$\n\nWe apologize for the mistakes in the submission. We will correct all typos in the final version.\n"}, {"review_id": "fkhRxcBqy6", "reviewer": "Reviewer_3pA1", "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.", "questions": "Please refer to weaknesses.", "limitations": "Please refer to weaknesses.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is well written and clear. \nI 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.\nCode is provided for the empirical results. \nBy 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.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for reviewing our paper and your positive feedback. We argue that while this is primarily a theoretical contribution, it is valuable for the following reasons:\n- While it was already known that greedy does well in practice, our locality theorem, along with our experiments showing a lower value of local optimality on real datasets, provide a sound explanation for the strong practical performance of greedy in the context of composable coresets.\n\n- We further believe that the locality result on the greedy algorithm is a structural result, and may find uses in other contexts; we point the reviewer to the global response for an example on how this property recovers (and in fact slightly improves) the best analysis of Greedy in the offline setting.\n"}, {"review_id": "3XP8bDuXS9", "reviewer": "Reviewer_vec7", "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. \n\nA 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. ", "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.", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "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. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for reviewing our paper and your positive feedback. In what follows we address your concerns and questions. \n\n----------\n\n> While the result is very important, the techniques might be viewed as incremental over the analysis of local search given in prior work\n\n[IMGR20] discusses and analyzes the relationship between greedy and local search by utilizing a very lossy reduction to the k-perpendicular heights problem. In contrast, this paper provides a very different way of performing this reduction and is interesting in its own right.\n\n-------\n\n> I could not find the referenced lower bound of $\\Omega(k^{k-o(k)})$ in prior work ... 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.\n\nThe lower bound is **Theorem 1.4** in the arxiv version of reference **[IMGR20]** “Composable Core-sets for Determinant Maximization Problems via Spectral Spanners.” \n\nThe setting for our results is the **composable coreset** setting where the data is partitioned into multiple machines: machine $i$ holds the dataset $P_i$. The goal is to use greedy to summarize $P_i$, getting a subset $S_i=Greedy(P_i)$ such that $\\mathrm{MAXVOL}^2_k(S) >= (1/\\alpha) \\mathrm{MAXVOL}^2_k(P)$ where $S=\\sum_i S_i$, and $P = \\sum_i P_i$, and where for a set $A$ its $\\mathrm{MAXVOL}_k(A)$ is defined to be the maximum volume one can achieve by picking $k$ points in $A$. The lower bound shows that one cannot get $\\alpha$ which is smaller than $k^{k(1-o(1))}$.\n\nFinally, in the offline setting we show that locality property one can marginally improve the k! guarantee of volume maximization of [CMI09], to $(k!)^{(0.5 + o(1))}$. Please refer to the global response for the proof.\n\n--------\nPlease let us know if we can provide further clarification.\n"}, {"review_id": "alClxYh1c2", "reviewer": "Reviewer_KpLA", "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.", "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?\n- The observation of local optimality for greedy is interesting, does it have other applications?", "limitations": "No. I suggest discussing some social impact, e.g., whether the greedy is better or worse for fairness issues than local search.", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The topic of DPP is relevant.\n- The technical result is solid.\n- 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.\n- The studied problem is limited, e.g., only consider unconstrained DPP in which every set $P_i$ selects exactly $k$ vectors. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your positive feedback. Below, we have addressed your comments and questions.\n\n> 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.\n\nThis is correct. However, our algorithm closes this line of work ([MIGR'19], [IMGR20], and [MKSK13]) by showing that the practical greedy algorithm provides an almost optimal approximation guarantee. We note that the motivation of [MIGR19] for studying local search for composable coresets is because simplicity is desirable to ensure that the algorithm is practical. Greedy avoids a lot of computation that is required for local search with a comparable guarantee. Furthermore, this paper provides a very different way of analyzing the relationship between local search and the greedy algorithm in comparison to [IMGR20] and could be interesting in its own right.\n\n-----\n> The studied problem is limited, e.g., only consider unconstrained DPP in which every set $P_i$ selects exactly $k$ vectors.\n\n> 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?\n\nIn this paper, similar to [MIGR19] and [IMGR20], we consider the basic setting of unconstrained determinant maximization. The goal is to get as small of a coreset as possible for each pointset $P_i$ regardless of its initial size $|P_i|$. We want to emphasize that for this problem, a coreset of **size $k$ is always necessary** as otherwise we cannot get any approximation guarantee. (To see this consider the setting where $P_i$ contains $k$ points with very high volume but the rest of the point sets $P_j$ have all points equal to 0. In this case the coreset size should be at least k). \n\nIt is an interesting direction for future work to see if the greedy algorithm can be used to get a coreset for this problem under fairness constraint.\n\n---------\n\n> The observation of local optimality for greedy is interesting, does it have other applications?\n\nThe locality of greedy does have a consequence: the locality property directly recovers the k! guarantee of volume maximization in the offline case [CMI09], and marginally improves the guarantee to (k!)^(0.5 + o(1)). This is a different proof from the original paper and may be of interest independent of our composable coresets result. The statement and proof of this result can be found in the global response.\n\n------------\n> I suggest discussing some social impact, e.g., whether the greedy is better or worse for fairness issues than local search.\n\nWhile our experiments focus on computing the empirical *local optimality* of the greedy algorithm, we expect that neither of the greedy nor local search will provide a fair result (e.g. consider the scenario where there are two populations in the data set where one population contains points with much higher volume. In this setting, both the greedy and local search prefer that population and are not fair in that respect). \nIn order to get fair results one needs to change the formulation of this problem which is not the focus of this work.\n"}]

Author rebuttal:
We thank all the reviewers for their positive and constructive feedback.

Bellow, we give a proof that the locality property can recover and in fact marginally improve the k! guarantee for the offline version of the greedy algorithm [CMI09]. We will include it in the final version. While the focus of our paper is on composable coresets, we hope that this application in the offline case demonstrates why our structural result on local optimality could be useful in analyzing the greedy algorithms in other contexts as well.

------

### Theorem
Let $P$ be a point set, Greedy$(P) = \\{v_1,\ldots,v_k\\}$ the output of the greedy algorithm and $\text{maxvol}_k(P)$ the maximum volume of any subset of $k$ vectors from $P$. Then

$\text{vol}(\text{greedy}(P)) \geq \frac{maxvol_{k}(P)}{\prod_{i=2}^k (1+\sqrt{i})}$.

### Proof
Let $S \subseteq P$ be the set of $k$ vectors with maximum volume. Without loss of generality and for simplicity of exposition, we assume $S\cap \text{Greedy}(P) = \varnothing$ (the proof still goes through if this is not the case).

Consider the set $W_1 = \\{v_1\\} \cup S$ with $k+1$ elements. Perform the greedy algorithm on $W_1$ with $k$ steps. Clearly, greedy will choose $v_1$ first and then some $k-1$ of the remaining vectors. Label the left out vector $w_1$.

Inductively define $W_{i+1} = \\{v_1,\ldots,v_i,v_{i+1}\\} \cup (S - \\{w_1,\ldots,w_i\\})$, which has size $k+1$. Perform greedy on $W_{i+1}$ with $k$ steps. The first $i+1$ vectors chosen will be $v_1,\ldots,v_i,v_{i+1}$ by definition. Call the left out vector $w_{i+1}$. We now have an ordering for $S = \\{w_1,\ldots,w_k\\}$.

Starting with the greedy solution, we will now perform $k$ swaps to obtain the optimal solution. Each swap will increase the volume by a factor of at most $1+\sqrt{k}$. Initially, our solution starts with Greedy$(P) = \\{v_1,\ldots,v_k\\}$. Note that this is also the output of greedy when applied to the set $\text{Greedy}(P) \cup \\{w_k\\} = W_k$. Swapping in $w_k$ in place of $v_k$ increases our volume by a factor of at most $1+\sqrt{k}$.

Our current set of vectors is now $\\{v_1,\ldots,v_{k-1},w_k\\}$. By the ordering on $S$, this is also the greedy output on the set $W_{k-1} = \\{v_1,\ldots,v_{k-1},w_{k-1},w_k\\}$. Therefore, we may swap in $w_{k-1}$ in place of $v_{k-1}$ in our current set of vectors by increasing the volume by at most a factor of $(1+\sqrt{k})$. Proceeding in this manner, we can perform $k$ swaps to obtain the optimal solution from the greedy solution by increasing our volume by a factor of at most $(1+\sqrt{k})^k$. 

To obtain the slightly better approximation factor in the theorem statement, we observe that in the proof of theorem 5 in the paper, swapping out the $i^{\text{th}}$ vector from the greedy solution for a vector that was not chosen increases the volume only by a factor of $(1+\sqrt{k+1-i}) \leq 1 + \sqrt{k}$, and that swapping out the $k^{\text{th}}$ vector does not increase the volume at all. Therefore, the approximation factor of greedy is at most

$\prod_{i=1}^{k-1} (1+\sqrt{k+1-i}) = \prod_{i=2}^k (1+\sqrt{i})$.

### Remark
Note that $\prod_{i=2}^k (1+\sqrt{i}) < 2^k \sqrt{k!}$ for $k \geq 7$, which is $(k!)^{\frac{1}{2} + o(1)}$. While the improvement in the approximation factor is quite small, we emphasize that the proof idea is very different from the $k!$ guarantee obtained in [CMI09].

----------

Description of attached figure: We repeated Experiment 1 for the GENES dataset with the RBF kernel applied as requested in Review 1.


Meta-review: The reviewers are generally supportive of the paper. The reviewers appreciate the improved guarantee for the practical greedy algorithm, now qualitatively similar to the best known bound for all algorithms. On the other hand, some reviewers note that the techniques are not groundbreaking and could be perceived as incremental from the local search analysis. Nevertheless, several reviewers think the technique could be of independent interest, beyond the specific task considered. 

The authors are advised to improve the writing, especially by including the intuition and the connection between the new technique and other related problems from the discussion with the reviewers.
Decision: Accept (poster)