Tight Bounds for Volumetric Spanners and Applications
Authors: Aditya Bhaskara
Sepideh Mahabadi
Ali Vakilian
Venue: NeurIPS 2023 poster (2023)
Keywords: volumetric spanner
well-conditioned basis
determinant maximization
minimum volume enclosing ellipsoid
TL;DR: We give almost optimal volumetric spanners with respect to all p-norms.

Abstract: Given a set of points of interest, a volumetric spanner is a subset of the points using which all the points can be expressed using "small" coefficients (measured in an appropriate norm). Formally, given a set of vectors $X = [v_1, v_2, \dots, v_n]$, the goal is to find $T \subseteq [n]$ such that every $v \in X$ can be expressed as $\sum_{i\in T} \alpha_i v_i$, with $\Vert \alpha \Vert$ being small.  This notion, which has also been referred to as a well-conditioned basis, has found several applications, including bandit linear optimization, determinant maximization, and matrix low rank approximation. In this paper, we give almost optimal bounds on the size of volumetric spanners for all $\ell_p$ norms, and show that they can be constructed using a simple local search procedure. We then show the applications of our result to other tasks and in particular the problem of finding coresets for the Minimum Volume Enclosing Ellipsoid (MVEE) problem.

Tight Bounds for Volumetric Spanners and Applications
Aditya Bhaskara University of Utah
Sepideh Mahabadi
Microsoft Research-Redmont
bhaskaraaditta@@@aall.cc com
smahabadi @mi crosoft. com
Ali Vakilian
Toyota Technological Institute Chicago (TTIC)
vakilian@ttic..ddi
Abstract
Given a set of points of interest, a volumetric spanner is subset of the points using which all the points
be expressed using "small" coefficients (measured in appropriate norm). Formally, given a set of vectors x= (v1. u,,-.., ), the goal is to find T C [ri] such that every X can be expressed as Lier 034%, with [|c]] being small. This notion, which has also been referred to as a well-conditioned basis, has found several applications, including bandit linear optimization, deter- minant maximization, and matrix low rank approximation. In this paper, we give almost optimal bounds on the size of volumetric spanners for all l, norms, and show that they can be constructed using simple local search procedure. We then show the applications of our result other tasks and in particular the problem of finding coresets for the Minimum Volume Enclosing Ellipsoid (MVEE) problem.
Introduction
In many applications in machine learning and signal processing, important to find the right "representation" for collection of data points signals. As classic example, in the column subset selection problem (used in applications like feature selection, [Boutsidis et al.) (2008). the goal find small subset of given of vectors that can represent all the other vectors via linear combinations. In the sparse coding problem, the goal is to find basis or dictionary under which a collection of vectors admit sparse representation (see [Olshausen and Field 1997]).
In this paper, we focus on finding "bases" that allow us to represent a given set of vectors using small coefficients. A now-classic example is the notion of an Auerbach basis. Auerbach used an extremal argument to prove that for any compact subset X of Rdd there exists basis size d (that is subset of X) such that every E X can be expressed using coefficients of magnitude < 1 (see, e.g., [Lindenstrauss and Tzafriri 2013 ). This notion was rediscovered in the MIL community in the well-known work of Awerbuuh and Kleinberg (2008), and subsequently in papers that used such basis as directions of exploration in bandit algorithms. The term barycentric spanner has been used to refer Auerbach bases. More recently, the paper of Hazan and Karnin (2016) introduced an &2 version of barycentric spanners, which they called volumetric spanners, and use them obtain improved bandit algorithms.
linear combination of the basis vectors
The same notion has been used in the literature on matrix sketching and low rank approximation, where it has been referred to "well-conditioned basis" (or spanning subset); see Dasgupta et al.) [2009]. These works use well-coodditonee bases to ensure that every small norm vector (in some normed space) can be expressed combination of the vectors in the basis using small coefficients.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Recently, Woodruff and Yasuda [2023 used the results of (Todd] 2016 and [Kumar and Yildirim 2005] on minimum volume enclosing ellipsoids (MVEE) to show the existence of well-conditioned spanning subset of size (d log log d). (Note that this bound was already superseded by the work of Hazan and Karnin 2016]. who used different techniques.) Moreover, [Woodruff and Yasuda 2023] demonstrated the use of well-conditioned bases for a host of matrix approximation problems (in offline and online regimes) such as low-rank approximation problems, lp subspace embedding. and lp column subset selection.
Our main contribution in this paper to show that a simple local search al algorithm yields volumet- ric spanners with parameters that improve both lines of prior work by Hazan and Karin [0116] and and Woodruff and Yasuda (2023]. Our arguments also allow us to study the case of having gen-
eral E norm bound on the coefficients. Thus, we obtain a common generalization with the results of Awerbuch and Kleinberg (2008) on barycentric spanners (which correspond to the case p = 00).
Further our results can be plugged in, following the same approach of Woooduf and Yasuda (023 to obtain improvements on range of matrix approximation problems in these settings.
One application we highlight is the following. Volumetric spanners turn out to be closely related to another well-studied problem, that of finding the minimum volume enclosing ellipsoid (MVEE) for a given set of points, or more generally, for a given convex body K. This is a classic problem in geometry [Welzl, 1991, Khachiyan and Todd 1990]. The celebrated result of Fitz John (e.g., see [Ball [ characterized the optimal solution for general K. Computationally, the MVEE can be computed using a semidefinite programming relaxation [Boyd al. 2004]. , and more efficient algorithms have subsequently been developed; see [Cohen et al. 2019]. Coresets for MVEE (de- fined formally below) were used to construct well-conditioned spanning subsets in the recent work of Woodruff and Yasuda (2023). We give result in the opposite direction, and show that the local search algorithm for finding well-conditioned spanning sets can be used to obtain a coreset of size O(d/e). This quantitatively improves upon prior work, as we now discuss.
1.1 Our Results
We start with some notation. Suppose X = {ur, U2 ................................ Un is set of vectors in Rd We say that subset S C [n]] is a volumetric spanner (Hazan and Karnin 2016) or a well-conditioned spanning subset [Woodruff and Yasuda 2023), if for all E [n),, we can write v Eies açU; with |all2 < 1. More generally, we will consider the setting in which we are given parameters c, p. and we look to satisfy the condition ||a||p S (refer to Section 2 for a formal definition. Our main results here the following.
Volumetric spanners via local search. For the &g case, we show that there exists a volumetric spanner as above with |S| < 3d. Moreover, it can be found in polynomial time via a single-swap local search procedure (akin to ones studied the context of determinant maximization [Madan et al.. 2019). Furthermore, our approach demonstrates the existence of a volumetric spanner of size 2d 1, marking a substantial progress in addressing the question posed by Hazan and Karnin (2016). This helps to narrow the gap between the obvious d + 1 lower bound and their 12d upper bound.
In the case of p 2, there are two main prior works. The first is the work of Hazan and Karnin [2016). They obtain a linear sized basis, similar to our result. However, their result is weaker in terms of rumning time (by a factor roughly df), as well as the constants in the size of the basis. Moreover, our algorithm is much simpler, it is simply local search with an appropriate objective, while theirs involves running a spectral sparsification subroutine (that involves keeping track of barrier potentials, etc.) followed by a rounding step.
The second work is the recent result of Woodruff and Yasuda 2023
which utilizes the prior work by Todd [2016]. Their algorithm is simple, essentially employing a greedy approach. However, it incurs an additional log log d factor in the size of the spanner due to the analysis of the greedy algorithm. Removing this factor is interesting conceptually, as it shows that local search with an appropriate objective can achieve a stronger guarantee than the best known result for greedy.
General p norms. For the case of general fp norms, we show that a local search algorithm can still be used to find the near-optimal sized volumetric spanners. However, the optimal size exhibits three distinct behaviors:
2

---

For p = L, we show that there exist a set X of size n = exp(d) for which any & volumetric spanner of size strictly smaller than can only achieve ||a||| ((vn). See Theorem 3.8 for the formal statement.
For p E (1, 2). we show that Ep volumetric spanners that can achieve ||a||p I exist, but require |.S| = Ω ( log sy-2 For strictly smaller sized S, we show lower bound akin to the one above for p = 1. See Theorem 3.10
For p > 2, an lp volumetric spanner (achieving ||o||p < 1) of size 3d exists trivially because of the corresponding result for p 2. See Theorem 3.6 and Corollary 3.12
Our results show that one-swap local search yields near-optimal sized volumetric spanners for all lp norms. We note that a unified treatment of the lp volumetric spanner (for general p), along with matching lower bounds have not been done in any of the prior work. Existing results treated the cases p 2 and p = oo, using different techniques.
While well conditindd spanning subsets have several applications (Woodruff and Yasuda 2023 J. we highlight one in particular as it is classic problem. Given symmetric convex body K E Rd the minimum volume enclosing ellipsoid (MVEE) of K, denoted MVEE(K), is defined as the ellipsoid & that satisfies & 3 K, while minimizing vol(E). We show that for any K, there exists subset S of O (5) points of K, such that
Coresets for MVEE.
vol(MMEE(()) < (1 (1+ vol (MVEE
This result is formally stated in Theorem 4.2 We define such a set S to be a coreset, and while it is weaker than notions of coresets considered for other problems (see the discussion in Section 2.1 it is the one used in the earlier works of Todd [2016), Kumar and Yildirim [2005). We thus improve the size of the best known coreset constructions for this fundamental problem, indeed, by showing that simple local search yields the desired coreset. This is conceptually interesting, because it matches the coreset size for a much simpler object, that is the axis-parallel bounding box of set of points (which always has a coreset of size S 2d, obtained by taking the two extreme points along each axis).
Other applications. Our result can be used as blxck-box& to improve other results in the recent work of Woodruff and Yasuda [2033], such as entrywise Huber low rank approximation, average top A subspace embeddings and cascaded norm subspace embeddings and oblivious lp subsapce embdeddings. In particular, we show that the local search algorithm provides a simple existential proof of oblivious l, subsapce embdeddings for all p > 1. In this application, the goal is to find small size "spanning subset" of a whole subspace of points (i.e., given a matrix A, the subspace is Axxl, = 1)), rather than a finite set. Our results for oblivious lp subsapce embdedding improves the bounds of non-constructive solution of Woodruff and Yasuda 2023 by shaving a factor of log log d in size.
1.2 Related work
In the context of dealing with large data sets, getting simple algorithms based on greedy or local
search strategies has been a prominent research direction. A large number of works have been
on focusing to prove theoretical guarantees for these simple algorithms (e.g. [Madan et al.] 2019 Altschuler al. 2016 Mahabadi et al. 2019 Civril and Magdon-Ismail [009 Mirzasoleiman et al. [ and Vuong 2022)). ). Our techniques are inspired by these works, and contribute to this literature.
Well-conditioned bases are closely related to "column subset selection" problem, where the goal is to find small (in cardinality) subset of columns whose combinations can be used to approximate all the other columns of a matrix. Column subset selection has been used for matrix sketching, "interpretable" low rank approximation, and has applications to streaming algorithms as well. The classic works
of (Frieze et al. 2004 Drineas et al. 2006)] Boutsidis et al., 2009 all study this question, and indeed, the work of Boutsidis et al. 2009 exploit the connection to well-conditioned bases.
More broadly, with the increasing amounts of available data, there has been a significant amount of work data summarization, where the goal is to find small size set of representatives for data
set. Examples include subspace approximation [Achlioptas and McSherry 2207), projective cluster-
ing Deshpande et al. 2006 Agarwal and Procopiuc 2003 Agarwal and Mustafa 2004]. determinant
3

---

1995 Nikolov 2015 experimental design problems Pukelsheim 2006], sparsifers [atson et al. 2009 and coresets Agarwal et al.) 2005], which all have been extensively studied in the literature. Our results on coresets for MVEE are closely related to a line of work on contact points of the John Ellipsoid (these are the points at which an MVEE for convex body touches the body). (Srivastava (2012). improving upon work of Rudelson [197]. showed that any convex K in IRd can be well-aapprximmate by another body K' that has most (a contact points with its corresponding MVEE (and is thus "simpler"), While this result implies a coreset for K, it has a worse dependence on than our results.
maximization [Civril and Magdon- Ismail 2009 Grizzmann et al.
2 Preliminaries and Notation
Definition 2.1 (ly-volumetric spanner). Given a set of d vectors (Uihee C IR and 2 1, subset of vectors indexed by S C [r]] is c-approximate ln-volumetric spanner of size |S| if for every j E [n], Vi can be written as V Eies 047; where ||a]]p S.
In particular, when == the is denoted an lp-volumetric spanner of {Vi,"" " vn).
Determinant and volume. For a set of vectors (V1, ....... val E R det (Ei= u.o?) is equal to the square of the volume of the parallelopiped formed by the vectors U1, U2....y Va with the origin.
The determinant maximization problem defined as follows. Given n vectors vı, #2,..... Un E Rd, and parameter k, the goal is to find S C [n]] with |S| = k; so as to maximize det (Eies 1u ) In this paper, we will consider the case when 2 d. Fact 2.2 (Cauchy-Biine Binett formula). Let 01.
Rd, with n 2 d. Then
det
Σ 1
Σ det Σ yuu?
SChoL|S|=d
EES
Lemma 2.3 (Matrix Determinant Lemma). Suppose A is an invertible square matrix and are column vectors, then
det(A + un (1+ t "_A='' det(A).
Lemma 2.4
formula). Suppose A is an invertible square matrix and u, are column vectors. Then, A + wv" is invertible iff 1 0. A + O. In this case,
A uv A
(A + uv -o- A-
1 A-
We will also use the following inequality, which follows from the classic Hölder's inequality. Lemma 2.5. For any 1S p S and x E IR", ||>||p S // /n//-11/9[//l
2.1 Coresets for MVEE
As discussed earlier, for a set of points X C Rd, we denote by MVEE(X) the minimum volume enclosing ellipsoid (MVEE) of X. We say that S is coreset for MVEE on X if
vol(MVEE(X)) & (1 + e)d vol(MVEEE(S).
Strong vs. weak coresets. The notion above agrees with prior work. but it might be more natural (in the spirit of strong coresets considered for problems such as clustering; see, e.g.. Cehenn- Addad et al. (022)) to define coreset as a set S such that for any & D S, (1 + e)ε X. Indeed, this guarantee need not hold for the coresets we (and prior work) produce. An example is shown in Figure])
3 Local Search Algorithm for Volumetric Spanners
We will begin by describing simple local search procedures LocalSearch-R and LocalSearch-No The former allows "repeating" "ooeattin""ver vectors (i.e., choosing vectors that are already in the chosen set), while the latter does not.
LocalSearch-NN will be used for constructing well-conditioned bases, and LocalSearch-R will be used to construct coresets for the minimum volume enclosing ellipsoid problem.

---

Figure I: Suppose X the set all points (blue and black), and let S be the set of black points. While MVEE(X) MS)E(S), there can be ellipsoids like the one in red, that contain S but X even after scaling by small constant.
Algorithm Procedure LocalSearch-NR
1: Input: Set of vectors {V1, U2..... Un S Rd parameter >> integer r 2 d
2: Output: Set of indices
3: Initialize 5 of size using the greedy procedure described in the text
4: Define M = Eies ba5g
5: while 3 E S and j E [n] \ S such that det(M - -aa + m5a > (1+ (M) do
6: Set 5 + 8 {i} U [}}
7: M + M 1,67 + 1y2g
8: Return $
Initialization. The set S is initialized as the output of the standard greedy algorithm for volume maximization (Civril and Magdon-Ismaii 2009) running for d iterations, and then augmented with set of (r -dd d) arbitrary vectors from (U....., 2,
The procedure LocalSearch-RR R (where allow repetitions) is almost identical to Algorithm[] It uses the same initialization, however, the set S that is maintained is now multiset. More importantly, when finding j in the local search step. LocalSearch-R looks over all j E [n]] (including potentially j E S). Also in this case, removing i from S in Line 6 corresponds to removing "one copy" of
Procedure LocalSearch-R.
3.1 Running time of Local Search
We will assume throughout that the dimension of span(( U2,..., v,,)) is (i.e., the given vectors span all R4; this without loss generality, as we can otherwise restrict
span).
The following lemma bounds the running time of local search in terms of the parameters r, 8. We note that we only focus bounding the number of iterations of local search. Each iteration involves potentially computing nr determinants, and assuming the updates are done via the matrix determinant lemma and the Aherrann-Morrison formula. the total time is roughly Onndd)) This can be large for large n, r, and it is one of the well-known drawbacks of local search.
Lemma 3.1. The number of iterations of the while loop in the procedures LocalSearch-F and LocalSearch-Mi is bounded by
o 0 logr
Proof. In every iteration of the while loop, the determinant the maintained M increases by least a (1 + 6) factor. Thus, suppose we define S* to be the (multi-)set of [n] that maximizes det (M*) A,,,, where M - Vaia We claim that for the used by the algorithm initialization (and the corresponding M), we have
del det(M) S (2)at del(M).
(1)
This follows from observations. First, let T be the (multi-)set of [n]] that has size exactly d, and maximizes det (Eter ugog') ). Indeed, such set will not be a multi-set, as a repeated element will reduce the rank. From the bound of Civril and Magdon-Isman M satisfies
2009). have that at initialization,
det( Σ )yfs) < d! det(M).
5

---

make without loss of Next, by the Cauchy-Binee formula, we can decompose det(MF) into sum over sub- uub-determinant of d-sized subsets of the columns. Thus there are terms in the summation, Each such sub-determinant is at most det (Eer- (.aa) ), as T is the maximizer. This proves ①
Next, since the determinant increases by a factor (1 + 5) in every iteration, the number of iterations at most
[d log d + +d dlog(er/d)),
where we have used the standard bound of (i) S (E))
This completes the proof.
3.2 Analysis of Local Search
We now prove some simple properties of the Local Search procedures. Following the notation of Madan al. (2019), define the following. Given choice of S in the algorithm (which defines the corresponding matrix M), let
= of M U4
Tij of uy.
(2)
Note that M is invertible. The determinant of M does not decrease in the local search update (see condition in line 5) and the selected . in the initialization step is invertible. This easily follows from (a) the greedy algorithm is maximizing volume (which is proportional to determinant) and (b) the full set of vectors span a dimensional space (which is an assumption generality, as we can always work with the span of the vectors).
We remark that Tú is often referred to as the leverage score. We have the following (proof in Section
Lemma 3.2. Let .i..... Un E IR and let S be (multi-)set of indices in [n]. Define M Eies U.o/ and suppose M has full rank. Then,
EiSST = d,
For any i,j (n], Taj Tzi-
The following key lemma lets us analyze how the determinant changes when we perform swap.
Lemma 3.3. Let be a (multi-)set of indices and let Eies V.yi be full-rank. Let i, be any two indices. We have
det(M - vioi + +uzeg) = det(M) [(1 T1) TT) T
Remark. Note that the proof will not use any additional properties about j. They could be equal to each other, and i may or may not already be in S.
Proof. By the matrix determinant lemma (Lemma 2.3
dM + eyuu vovl') (M + Uz (1 of (M +;,o))
-det( + uy M MM of (M + (z u.)
(3)
Next, we apply Sherman-Morrison formula (Lemma
2.4] to get
M uu, M M-1
1 1- 1-
(M (M
+ -2,0))= =1 -1 u-v M
U1 1-
(4)
+ of M M-
1 1+
Combining the above two expressions, we get
T3 + det(M + +ub - (ooe) = det(
1+
Simplifying this yields the lemma.
The following lemma shows the structural property we have when the local search procedure ends.

---

Lemma 3.4. Let S be a (multi- Jset of indices and M = Eies 2iit as before. Let j E [n], and suppose that for all i E S, det(M "udo + ozuz) (1 + 8) det(M). Then we have
d rd
3 r +
Once again, the lemma does not assume anything about j being in S.
Proof. First, observe that for any j E [ni,, we have
Σ
1 M 0,0 M
uu - M MM uy = Tj.
2J
VES
FES
Combining this observation with Lemma 3.3 and summing over E S (with repetitions, if S is multi-set), have
(1 11+7)((
T:) TTg <r((1 5).
ES
Now using Lemma
3.2 get
(1 (1+ +
and simplifying this completes the proof of the lemma.
Since Lemma 3.4 does not make any additional assumptions about j, we immediately have: Corollary 3.5. The following properties hold for the output of the Local search procedures.
1. For LocalSearch-NR, the oulput S satisfies: for all j E [n]] S. <
d+ró
r-d+1
2. For LocalSearch-RR R, the output S satisfies: for all j E [n]. <
dtrd
r-d+1
3.3 Volumetric Spanners: Spanning Subsets in the & Norm
We use Lemma I.I and Corollary 3.5 to obtain the following.
Theorem 3.6 (Ey-volumetric spanner). For any set X = {V1, ....... vn of 2 d vectors in Rd and parameter 2 d, LocalSearch-NR outputs (max(1, (_trr 1/2 approximaate lz-volumetric spanner of X of size in O logr) iterations of Local Search.
In particular, setting size 3d in Old log d) iterations of Local Search. Furthermore, setting r = 2d and 5 = 0, LocalSearch-NFF implies the existence of an volvouumtriic spanner of size 2d - 1.
3d and ê 1/3, LocalSearch-NFF returns an lg-volumetric spanner of
Proof. Let S be the output of LocalSearch-NR with the parameters 6 X. Let U be the matrix whose columns are {w; E S}. We show how to express any uy X as Ua, where a E IR' is coefficient vector with ||a l2 being small.
For any E S, My can be clearly written with a being a vector that is in the row corresponding to fl and 0 otherwise, thus ||a|| = 1. For any j & S, by definition, the solution to Ua = is a = Utuj. where Ut is the Moore-Penrood pscudoinverse. Thus, we have
||a|| = = (z = uf
T..
Here we are using standard properties of the pscudoinverse. (These can be proved easily using the SVD). Hence, by Corollary 3.5 we have |all2 S --d+1
1/2
3.4 Spanning Subsets in the 4p Norm
now extend our methods above for all e--noss,, for p E (o). As outlined in Section 1.1 we three distinct behaviors. We begin now with the lower bound for p 1.
7

---

L1 21-volumetric spanner. For the case 1, we show that small sized spanning subsets do not exist for non-trivial upproximation factors.
Our construction is based on "almost orthogonal" sets of vectors.
Lemma 3.7. There exists a ser of exp(O(d)) unit vectors v1..... Um E F such that for every pair of j E [mm], (e,. uy>l - cv
d for some fixed constant c.
An example construction of almost orthogonal vectors is a collection of random vectors where each coordinate of each vector is picked uniformly random from { ( J (e.g., see (Dasgupta et al. 2009]).
Theorem 3.8 (Lower bound for é1-volumetric spanners). For any exp(S((d)) there exists set o vectors in Rd that has no o( log n "approximmaee { f1-volumetric spanner of size at most 1.
In other words, unless the spanning subset contains all vectors, it is not possible to get an --volueerri spanner with approximation factor ol log
Proof. Let X
(U) ( Un be set of n almost orthonormal vectors as in Lemmal 3.7 Suppose for the sake of contradiction, that there exists a spanning subset indexed by S that is strict subset of
[n]. Note that for every E [n] \ S and j E S, Kez, u5)l S cV log n2 So, for any representation of U/ terms of vectors S, i.e. 02 Ejes a50g.
log
(U, Uz)
Caylu, vy) s ||ll| of
jES
Hence, ||a|12 2 V logn as long as |S| < n.
Note that the lower bound nearly matches the easy upper bound that one obtains from l volumetric spanners (Theorem 3.6), described below:
Corollary 3.9. For any set of vectors X {Ui ..,, vo) an lz-volumetric spanner is also a 2 2v dapprooximate fi-volumetric spanner. Consequently, such a spanner of size O(d) exists and can be found in O(d d) iterations of Local Search.
The proof follows from the fact that if Jall2 1, ||a|] < v3d. for E Rdd (which is consequence of the Sauchy-Schward inequality). Note that the existence and construction of an f2 volumetric spanner of size 3d was shown Theorem 3.6
lp -plouummetric spanner for p E (1, Next, we apply the same argument as above for the case p E 21, Here, see that the lower bound is not strong: the size of the spanner and the approximation. Once again, the solution returned by LocalSearch-NR an almost optimal construction for spanning subsets in the l, norm. The proofs are deferred to Section B of the Supplement.
obtain trade-off between
Theorem 3.10 (Lower bound for f,-volumetric spanners for E (1,2)), For any value of S e(d) and 1 p < there exists set of n vectors in IRd that has no o(r (dd_ -aproxximate tp-volumetric spanner of size at most r.
In particular, a (1 (1-approximate) Ep-volumetric spanner V, has size Q ing
Next, we show that local search outputs almost optimal volvumeetti spanners. Theorem 3.11 (Construction of f,-volumetric spanners for p (1,2)). For any set of vectors
X = {1 ......, } C. Rd and p E (1,2), LocalSearch-NR outputs an O(r -11, d' >approxiimate volumettii spanner of X of size r.
)
In particular, the local search algorithm outputs a 1-approximate l ---volumetric spanner when -

---

fp-volumetric spanner for > 2. The result for > 2 simply follows from the results for fo-norm and the fact that ||~=|| $ || for any p 2 when || S
Corollary 3.12 (lp- volummeetii spanner for p > 2). For any set of vectors X {u), 02. ................................ vn C Rd LocalSearch-NNF output a 1-approximate ep-volumetric spanner of X of size r 3d in
O log d) iterations of Locul Search.
4 Applications of Local Search and Volumetric Spanners
We now give an application of our Local Search algorithms and volumetric spanners to the problem of finding coresets for the MVEE problem. For other applications, refer Section
Definition 4.1 (Minimum volume enclosing ellipsoid (MVEE)). Given set of points X {V1, U2..... Un S. Rd, define ( to be the ellipsoid of the minimum volume containing the points X U (-X,, where (-X) i-v e
While the MVEE problem is well-defined for general sets of points, we restricting to sets that symmetric about the origin. It is well-known (see Todd (0166) that the general case can be reduced to the symmetric one. Thus for any X, {X) is centered at the origin. Since & is convex, also define (.X) to be the ellipsoid the least volume containing conv(tv), I....... = where conv(-) refers to the convex hull.
As defined in Section 2.1 a coreset subset of that preserves the volume of the MVEE
Theorem 4.2. Consider a set of vectors X (wr," ... vn) c IRd. Let S be the output of the algorithm LocalSearch-R on X, with
== [(1 1 )d]
8 ed
(5)
4r
Then a coreset for the MVEE problem on X.
To formulate the MVEE problem, recall that any ellipsoid can be defined using a positive semidefi- nite (PSD) matrix H, as
E = x Ha < d),
and for & defined as such, have vol(E) -e up factor that only depends the dimension (i.e., is independent of the choice of the ellipsoid). Thus, to find E, we can consider the following optimization problem.
(MVEE): min det(((H)
subject to Hv; S d Vi e [n]. T
It is well known (e.g., Boyd al. (2004) that this is convex optimization problem. For any R with X; 2 0 for all E [m]. the Lagrangian for this problem can be defined as:
((H;A) In ded(())+
Σ Au Hu: d).
SEim]
Let OPT be the optimal value of the problem MVEE defined above. For any À with non-negative coordinates, we have
OPT 2 min C(H; A),
where the minimization is over the feasible set for MVEE; this is because over the feasible set, the second term of the definition of L(H; is < 0. We can then remove the feasibility constraint, and conclude that
OPT > min C(I;A),
Hzo

---

as this only makes the minimum smaller. For any given À with non -egattee coordinates, the minimizing can now be found by setting the derivative
H11
Aoaayy =0 = = == Σ
There is mild technicality here: if À chosen such that E; Aet,o is invertible, then min (H; = -cc. We will only consider À for which this is not the case. Thus, we have that for any À with non-negative coordinates for which Ei Acuzoy is invertible,
Σ Evono)) + +d-d) E A
OPT 2 det
(6)
We are now ready to prove Theorem 4.2 on small-sized coresets.
{U1, U21,02,.... Jn be the set of given points, and let be the output of the algorithm LecalSearch-R on X, with r, 8 chosen later in ()). By definition, S is a multi-set of size r, and we define to be its support. supp(S). We prove that T is coreset for the MVEE problem on X.
Proof of Theorem 4.2 Let X
To do so, define OPTx and OPT be the optimum values of the optimization problem MVEE defined earlier on sets and respectively. Since the problem on has fewer constraints, we have OPT, s OPT x, and thus we focus on showing that OPTx x S dll((1 + c) + OPTy. This will imply the desired bound on the volumes.
Let S be the multi-set returned by the algorithm LocalSearch-R, and let M :- Eies u.o Define X n where n, is the number of times appears in S. By definition, we have that Lie(n) d 1. Further, we define H == (Zie(n) Acvzof)) -1, ) we have H- + M.
Now, using Corollary 3.5
we have that for all j E [n].
d r8
r(d rō) -
d (1++--771 )
d d-1
rd
1 M 1
d+1
of r d+11
r-d+1
1
Our choice of parameters will be such that both the terms in the parentheses are (1 + e/4). For this, we can choose r, in (5).
H is a feasible solution to the optimization problem MVEE on X. This Thus, we have that H' = (1+c)
implies that OPTx < In (1 + +)) d In(1 + e) In de)( The last equality follows because
= det(H) (H)(H)/c² eM for a d-dimensional H, and any constant c.
Next, using the fact that the X; are supported T supp(S).
use 16 to conclude that
OPT, 2 det (endlt))) = - In det, where we also used the fact that Σ, = Together, these imply that OPTx S <dln(1 6) + OPT7, as desired.
5
Conclusion
We show that one-swap local search procedure can used to obtain an efficient construction of volumetric spanners, also known well-conditioned spanning subsets. This improves (and simplifies) two lines of work that have used this notion in applications ranging from bandit algorithms to matrix sketching and low rank approximation. We then show that the local search algorithm also yields nearly tight results for an f, analog of volumetric spanners. Finally, we obtain (ddee) sized coresets for the classic problem of minimum volume enclosing ellipsoid, improving previous results by d log log d term.
An interesting open problem arising from our work is that of developing an efficient algorithm to find a l2 volumetric spanner of size 2d While our local search approach demonstrates the existence of such spanner, it does not find it in polynomial time. Another interesting question is about further improving the gap: possible to obtain a volumetric spanner of size smaller than 2d for all instances?
10

---

Acknowledgments and Disclosure of Funding
The first author thanks the National Science Foundation for supporting his work via awards CCF- 2008688 and CCF-2047288.
References
D. Achlioptas and McSherry. Fast computation of low-rank matrix approximations, Journal of the ACM (JACM), 54(2):9-es 2007.
K. Agarwal and N. H. Mustafa. k-means projective clustering. In Proceedings of the twenty-third ACM SEGMOD-SIGACT-SIGARTT Sym Principles of database systems, pages 155-165, 2004.
P. K. Agarwal and C. M. Procopiuc. Approximation algorithms for projective clustering. Journal of Algorithms, 46(2):115-139, 2003.
K. Agarwal, S. Har-Peled, K. R. Varadarajan, al. Geometric approximation via coresets. Combinatorial and computational geometry, 52(1):1-30, 2005.
Altschuler, A. Bhaskara, G. Fu, V. Mirrokni, A. Rostamizadeh, and M. Zadimoghaddam. Greedy column subset selection: New bounds and distributed algorithms. In International conference on machine learning, pages 1539-25433 2016.
N. Anari and T.-D. Vuong. From sampling optimization discrete domains with applications to determinant maximization. In Conference on Learning Theory, pages 5596-5618, 2022.
B. Awerbuch and R. Kleinberg. Online linear optimization and adaptive routing. Journal of Computer and System Sciences, 74(1):97-114, 2008.
K. Ball. Ellipsoids of maximal volume in convex bodies. Geometriae Dedicata, 41(2):241-250, 1992.
D. Batson, D. A. Spielman, and N. Srivastava. Twice-ramanujan sparsifiers, Proceedings of the forty-first annual ACM symposium Theory of computing, pages 255-262, 2009.
C. Boutsidis, M. W. Mahoney, and P. Drineas. Unsupervised feature selection for principal compo- nents analysis. In Proceedings of the 14th ACM SIGKDD international conference Knowledge discovery and data mining, pages 61-69, 2008.
C. Boutsidis, M. W. Mahoney, and P. Drineas. An improved approximation algorithm for the column subset selection problem. In Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithmss, pages 968-977, 2009.
S. Boyd, S. P. Boyd, and L. Vandenberghe. Convex optimization. Cambridge university press, 2004.
A. Civril and M. Magdon-Isman On selecting maximum volume sub-matrix a matrix and related problems. Theoretical Computer Science, 410047-49):480144811, 2009.
M. B. Cohen, B. Cousins, Y. T. Lee, and X. Yang. near-optimal algorithm for approximating the john ellipsoid. In Conference Learning Theory, pages 849 979-873, 2019.
V. Cohen-Addad, D. Saulpic, and C. Schwiegelshohn. A new coreset framework for clustering. In S. Khuller and V. V. Williams, editors, 53rd Annual ACM SIGACT Symposium Theory of Computing (STOC), pages 169-182,, 2021.
A. Dasgupta, P. Drineas, B. Harb, R. Kumar, and M. W. Mahoney. Sampling algorithms and coresets for E, regression. SIAM Journal on Computing. 3865):2000-2778 2009,
A. Deshpande, I.. Rademacher, S. Vempala, and G. Wang. Matrix approximation and projective clustering via volume sampling. Theory of Computing, 2(1):225-24) 2006.
11

---

P. Drineas, M. W. Mahoney, and S. Muthukrishnan. Subspace sampling and relative-erro matrix approximation: Column-based methods. In 9th International Workshop on Approximation Algo- rithms for Combinatorial Optimization Problems, APPROX 2006 and 10th International Workshop on Randomization and Computation, RANDOM 2006, pages 316-326. Springer, 2006.
A. Frieze, R. Kannan, and S. Vempala. Fast conte-carlo algorithms for finding low low-rank approxima- tions. Journal of the ACM (JACM), 51(6):1025-1011, 2004.
P. Gritzmann, V. Klee, and D. Larman. Largest Geometry, 13:477-515, 1995.
J j-simplices in nn-polytopes. Discrete Computational
E. Hazan and Z. Karmin. Volumetric spanners: an efficient exploration basis for learning. Journal of Machine Learning Research, 2016.
L. G. Khachiyan and M. J. Todd. On the complexity of approximating the maximal inscribed ellipsoid for polytope. Technical report, Cornell University Operations Research and Industrial Engineering, 1990.
G. Kindler, A. Naor, and G. Schechtman. The UGC hardness threshold of the Lp grothendieck problem. Mathematics of Operations Research, 35(2):267-283, 2010.
Kumar and E. A. Yildirim. Minimum-volune enclosing ellipsoids and core sets. Journal of Optimization Theory and applications, 126(1):1-21, 2005.
J. Lindenstrauss and L. Tzafriri. Classical Banach Spaces I: Sequence Spaces. Ergebnisse der Mathematik und ihrer Grenzgebiete. Folge. Springer Berlin Heidelberg, 2013.
V. Madan, M. Singh, U. Tantipongpipat, and W. Xie. Combinatorial algorithms for optimal design. In Conference on Learning T'heory, pages 2200,2258, 2019.
S. Mahabadi, P. Indyk, S. O. Gharan, and A. Rezaei. Composable core-sets for determinant maxi- mization: A simple ncar-optimal algorithm. International Conference on Machine Learning, pages 4254-4263, 2019.
B. Mirzasoleiman, A. Karbasi, Sarkar, and A. Krause. Distributed submodular maximization: Identifying representative elements in massive data. Advances in Neural Information Processing Systems, 26, 2013.
A. Nikolov. Randomized rounding for the largest simplex problem. In Proceedings annual ACM symposium on Theory of computing, pages 861-870, 2015.
seventh
B. A. Olshausen and D. J. Field. Sparse coding with an overcomplete basis set: A strategy employed by VI? Vision Research, 37(23)33311-332 1997. ISSN 0042-6989.
Pukelsheim. Optimal design of experiments. SIAM, 2006.
M. Rudelson. Contact points of convex bodies. Israel Journal of Mathematics, 101:93-124, 1997.
N. Srivastava. On contact points of convex bodies. In Geometric Aspects of Functional Analysis: Israel Seminar 2006 2006-2010, pages 412, 2012.
M. J. Todd. Minimum-vollume ellipsoids: Theory and algorithms. STAM, 2016.
E. Welzl. Smallest enclosing disks (balls and ellipsoids). New Results and New Trends in Computer Science, volume 555 of Lecture Notes in Computer Science, pages 359-370. Springer, 1991.
D. P. Woodruff and T. Yasuda. New subset selection algorithms for low rank approximation: Offline and online. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 1802-1813, 2023.
12

---

A
Other Applications of Volumetric Spanners
We now show some direct applications of our construction of volumetric spanners.
A.1 Oblivious e, Subspace Embeddings
Oblivious subspace embeddings (OSEs) are a well studied tool in matrix approximation, where the goal is to show that there exist sketching matrices that preserve the norm (say the Ep norm) of all vectors an unknown subspace with high probability. The constructions and analyses OSEs rely on the existence of a well-conditioned spanning set for the vectors of interest. The following follows directly from Theorem 3.6 (note that we are only using our result for E2).
Theorem A.1 (Improvement of Theorem 1.11 1 in Woodruff and Yasuda 2023) ) Let E (1, and let A E Roxd There exists matrix R E RR for = 3d such that || lp = 1 for every E [s], and for every x E gd, || 1, there exists a E such that Ax = ARy and llvll2 S 1.
The Theorem follows by considering the set
== {Az: ||Az||p = 1},
and considering a well conditioned spanning subset in the l2 norm. Theorem 3.6 shows the existence of such subset with s 3d, thus the theorem follows.
However, note that the proof is non-constructive. In order to make it polynomial time, we need to show that the local search procedure can be implemented efficiently. For p > 2, this may be possible via the classic result of Kindler et al. [2100] on &, variants of the Gröthendieck inequality, but we note that the applications in Woodruuf and Yasuda 2023 require only the existential statement.
A.2 Entrywise Huber Low Rank Approximation
The Huber loss is classic method introduced as a robust analog the least squares error. significant amount of work has been dedicated to finding low-rank approximations of a matrix with the objective of minimizing the entry-wise Huber loss. The following offers slight improvement over [Woodruff and Yasuda 2023]
Theorem A.2. Let E Raad and let k > There exists a polynomial time algorithm that outputs subset S C [d] of columns in A of size O log d) and X E S such that
|| 1 X|I S O(k)
min rank(Au) Sk
IIA
-A&lHH
where AIS denotes the matrix whose columns are the columns of A indexed by S and || the entrywise Huber loss.
|| denotes
Note that the size of S reduced from O log log log d) O(k log d). The proof of Theorem A.2 follows from Theorem 1.6 in Woodrufff and Yasuda, [023) and our improved construction for fz-volumetric spanner, i.e., O(1) -approximate spanning subset of size ((d) (see Theorem 3.6).
A.3 Average Top ie Subspace Embedding
For a given vector E R", the average top k loss is defined as
||
|uab
where us denotes the ith largest coordinate in
Using the result of (Woodruff and Yasuda 2023 relating the problem of average top & subspace embedding to éy-volumetric spanners as a black box. we have the following theorems for small k (i.e., & < 3d) and large & (i.e., k > 3d) respectively.
Theorem A.3 (small k). Let A E Raxd and let h < 3d. There exists set S C [r]] size size (d) such
that for all x E Rdd
|||sT||AT, & ||Ax||AT, < <O(kkd) .14 |
where Als denotes the set of rows in A indexed by S.
13

---

Theorem A.4 (large k). Let A E Raxd and let l 2 ko where ko - O ()) Let Pi......P! Ps be
random partition of [n] into groups where t t= 0 + log }). For every i E [+], there exists a set S C. N₂ size O(d) such that with probability at least - 6, for all æ E R
| I ||Ax|lAT, S O(vtd) -1
where S = Ulelt) S and Als denotes the set of rows in A indexed by S.
both regimes, compared to [Woodruff and Yasuda 2023], our improved bounds for f2-volumetric spanner saves factor of log log d in the number of rows and a factor of vlog log d in the distortion. The proofs of above theorems respectively follows from Theorem 3.11 and 3.12 of [Woodruff and Yasuda 2023
together with our Theorem 3.6
A.4
Cascaded Norm Subspace Embedding
Next, explore the implications of the improved bound of é2- éz-oolumetiic spanner (i.e., Theorem 3.6 for embedding a subspace of matrices under (Il lec IIIl) clascaddd norm, which first evaluates an arbitrary norm of the rows and then return the maximum value over the rows.
The following a consequence of Theorem 3.13 in [Woodruff and Yasuda 2023] and our Theorem 3.6
We describe our result for the (lll ||ll)) clsscaddd norm, which first evaluates an arbitrary norm of rows and then return the maximum value over the n rows.
Theorem A.5 (illloo
III]) subspaceee embedding). Let A E Radd and ||I be any norm on R".
There exists a set [n] of size at most 3d such that for every E Rdxm
||s x|al S ||AX | (III S <O(vd)]AAss X X =I.l
B
Missing Proofs
B.1 Proof of Lemma 3.2
Proof. Note that the second part follows from the symmetry M (and thus also M-11) To the first part, note that we can write v²" M- (M-1, v,ee", where (U, V) refers to the entry-wise inner product between matrices U, V. which also equals (VU Using this,
ΣT= Σ (M (M- ) = (M- M) = Tr(!)= = d.
iES
ES
In the last equality, we used the symmetry of M.
B.2 Proof of Theorem 3.10
Proof. The proof follows from the same argument as before, Consider of > almost orthonormal vectors X = =[2,,.. 2n C Rd from Lemma 3.7
Consider index i [n]] \ S and let v; Ejes Uz By Lemma 2.5 for any p 1.
||l| 2 - ||all1 = rp c
log
In particular, to get a 1-approximate b volumetric spanner, i.c., ||al|p = the spanning subset must d
have size = 22(( log 2)
B.3 Proof of Theorem 3.11
Proof. By Corollary 3.5 the local search outputs set of vectors in X indexed by the set S C [n] of
size > d such that for every i [rx] S. is can be written linear combination of the vectors in
14

---

the spanner, 0; = Ejes Ugyy, such that ||a||2 S for any 1 < P<pp 2,
dará r-d-1
By Lemma 2.5 and setting ó d/r,
|alb S 5r²z2
( d rō
(--d41)
= = .d (d+ - -
1-1+11
In particular, we set r = O(d ) the subset of vectors S returned by LocalSearch-ND is an (exact) v-volmmetiic spanner; i.e., for every i E [n] S, ||a||p S 1. Finally, the runtime analysis follows immediately from Lemma
15


Reviews:
[{"review_id": "rrDxXO2Bco", "reviewer": "Reviewer_QwvL", "summary": "This paper considers the problem of constructing a volumetric spanner: a subset of vectors which allows to represent every other vector via a linear combination with coefficients whose lp-norm is small. The algorithms are based on local search and work for any lp-norm for p>=1. As a representative result (Theorem 3.6) one can find for a set X of size n>=d a subset of size at most 3d which can be used to represent all vectors in X via linear combinations with l2-norm of the coefficients <= 1. This requires O(d log d) iterations of local search. For l1-norm an exponential lower bound is given (Theorem 3.8). The result for p>2 follows trivially from Theorem 3.6 and for 1<p<2 a construction with certain parameters is given.\n", "questions": "– Line 17: sparse coding or problem?\n– See a question regarding applications below.\n", "limitations": "Yes", "rating": 6, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper has clear results and is well-written. I think I understand all the main results and techniques quite well.\n", "weaknesses": "The applications to machine learning problems are somewhat weak (a few examples are given in the intro to column subset selection and sparse coding, but I am not exactly sure what the implications of the results in this paper are for the applications).\n\nThe claim that MVEE is an application is that we get an improvement on the size of the best known coreset construction. What is the magnitude of this improvement? Does this yield an algorithmic speedup?\n\nThere is an application mentioned to [Woodruff, Yasuda’23] where a log log d factor can be shaved. Can you elaborate on the implications of this as well? The discussion in Appendix A.1 is hard to follow. Can you restate the WY’23 result and explain what the contribution here is?\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The applications to machine learning problems are somewhat weak (a few examples are given in the intro to column subset selection and sparse coding, but I am not exactly sure what the implications of the results in this paper are for the applications).\n\nPlease see our above message to all reviewers for discussion on applications of our results to machine learning.\n\n>The claim that MVEE is an application is that we get an improvement on the size of the best known coreset construction. What is the magnitude of this improvement? Does this yield an algorithmic speedup?\n\nAs mentioned in above (message to all reviewers), finding the “optimal” coreset size for MVEE has been studied in several previous works (including Kumar and Yildirim 2007, and Todd 2016). We improve the size from $O(d \\log \\log d)$ to $O(d)$, using an algorithm of similar complexity. Numerically, this is not much, but it shows that (a) finding min enclosing ellipsoids admits coresets of linear size, similar to much simpler problems, like finding an axis parallel bounding box, and (b) local search offers an improvement over greedy coordinate ascent. \n\n>There is an application mentioned to [Woodruff, Yasuda’23] where a log log d factor can be shaved. Can you elaborate on the implications of this as well? The discussion in Appendix A.1 is hard to follow. Can you restate the WY’23 result and explain what the contribution here is?\n\n[WY23] gives many “black box” applications of well conditioned spanning sets, including entrywise Huber error low rank approximation, oblivious subspace embeddings, etc. In all these works, we can instead use our construction; this gives an improvement by a factor $\\log \\log d$, and in many cases, gives the tight bounds. \n\n>Q. – Line 17: sparse coding or problem? – See a question regarding applications below.\n\nThanks, we will fix the typo, it should be “sparse coding problem”. This is only an example where choosing the basis is crucial, it is not directly relevant for us. "}, {"review_id": "1EbyJfefi8", "reviewer": "Reviewer_JkQ2", "summary": "This paper develops and analyzes a local-search algorithm for finding volumetric spanners under norms in the regime where the number of given vectors $n$ is at least as high as the dimension $d$ of these vectors. Moreover, a runtime of the algorithm is given and the size of the algorithm's output is compared to existing lower bounds. Finally, this paper presents applications of the algorithm to the minimum volume enclosing ellipsoid (MVEE) problem (in the paper's body) and other lower rank problems (in the appendices).", "questions": "Aside from the issues and questions pointed out in the “Weaknesses” section, I have a few minor suggestions/questions below:\n\n(1) Please use either $u_i$ or $\\lambda_i$ for the dual variables in the proof of Theorem, but do not use both.\n\n(2) Please make the use of parameter $r$ somewhere in Algorithm 1. At first glance, it appears to be an unused parameter, e.g., setting $r=d$ and $r=1000d$ has no effect on the result of the algorithm.\n\n(3) In equation (4), $r$ can be fractional. This doesn't seem to make sense in the context of the “Initialization” discussion after Algorithm 1.", "limitations": "Yes, the authors have sufficiently addressed the limitations of their work.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "The main novelty of the paper is the development of a (relatively) simple algorithm that obtains near-optimal results under different norms. A minor novelty is the improvement in the $\\ell_2$ case where the existing upper bound for computing well-conditioned coresets was improved from $O(d\\log\\log d)$ to $O(d)$. A particular point of originality is the application of the proposed algorithm to generate a concrete solution to $\\ell_p$ subspace embedding problem, in contrast to existing non-constructive solutions.", "weaknesses": "This paper suffers from three major weaknesses: (i) unfocused comparisons of the paper's results to existing literature, (ii) technical issues with the mathematical results, and (iii) the lack of important details in several parts of the paper. Below, I outline some specific instances:\n\n(i.1) [Woodruff and Yasuda, 2023] - How does the notion of “distortion” in Definition 1.2 of [Woodruff and Yasuda, 2023] factor into the analysis of this paper. For example, do the coreset generated by Algorithm have high distortion when applied to the well-conditioned $\\ell_2$ coreset problem?\n\n(i.1) Runtime and Solution Size - It is difficult for the reader to find how the proposed algorithm compares to existing literature, as comments are generally scattered throughout the paper. A table that compares runtime and solution size would help in improving this issue.\n\n(ii.1) Proof of Thm. 4.2 - Assuming that indeed $OPT_X \\leq (1+\\epsilon)d + OPT_T$, the only conclusion is that $vol(MVEE(X)) \\leq \\exp((1+\\epsilon)d) \\times vol(MVEE(S))$, which does not coincide with the definition at the beginning of Subsection 2.1, as claimed.\n\n(ii.2) Lemma 3.4 - The analysis seems to break down when $r\\leq d+1$, but $r$ does not appear to be restricted in the algorithm (indeed, the “Initialization” discussion following Algorithm 1 seems to suggest that $r=d, d+1$ are valid cases.\n\n(ii.3) Section 3.2 - How do we know that $M$ remains invertible throughout the entire runtime of the algorithm. None of the results (including Lemma 3.3) seem to suggest that $\\det M \\neq 0$.\n\n(iii.1) Algorithm 1 - What is the significance of the parameter $r$? Can I set it to $d$ to be optimal?\n\n(iii.2) Algorithm 1 - A description of the initialization subroutine and its properties is missing. This is important for the reader verify that the presented algorithm is valid, e.g., $M$ starts with full rank.\n\n(iii.3) Proof of Thm 4.2 - Why is $\\sum n_i = r$? \n\n(iii.4) Proof of Thm 4.2 - Why is $H^{-1} = M / r$? Specifically, why is $n_i = 1$ for all $i$ (which is needed for this identity to hold in general).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">(i.1) [Woodruff and Yasuda, 2023] - How does the notion of “distortion” in Definition 1.2 of [Woodruff and Yasuda, 2023] factor into the analysis of this paper. For example, do the coreset generated by Algorithm have high distortion when applied to the well-conditioned $\\ell_2$ coreset problem?\n\nThe notion of distortion in [WY23] is for low rank approximation, it is not related to volumetric spanner / well-conditioned basis, which is the subject of our paper. So in short, the question of distortion does not arise. \n\n>(i.1) Runtime and Solution Size - It is difficult for the reader to find how the proposed algorithm compares to existing literature, as comments are generally scattered throughout the paper. A table that compares runtime and solution size would help in improving this issue.\n\nThanks for the suggestion, we will add a clear discussion in the final version. Please see our response to Reviewer 5 (4Fat) as well.\n\n>(ii.1) Proof of Thm. 4.2 - Assuming that indeed $OPT_X \\le (1+\\epsilon)d + OPT_T$, the only conclusion is that $vol(\\mathrm{MVEE}(X)) \\le \\exp((1+\\epsilon)d) \\times vol(\\mathrm{MVEE}(S))$, which does not coincide with the definition at the beginning of Subsection 2.1, as claimed.\n\nThis is exactly the definition at the beginning of 2.1 – see the equation there. It is not a “strong coreset”, as we also discuss in Section 2.1.\n\n>(ii.2) Lemma 3.4 - The analysis seems to break down when $r \\le d+1$, but $r$ does not appear to be restricted in the algorithm (indeed, the “Initialization” discussion following Algorithm 1 seems to suggest that $r = d, d+1$ are valid cases.)\n\nYes, $r$ can be any value larger than or equal to d. Note that when $r = d, d+1$, the approximation guarantee is $\\Omega(d)$. So, as mentioned in Theorem 3.6, the more interesting values of r are larger, e.g. $r = 3d$ which results in $1$-approximation. Perhaps the reviewer is referring to the denominator being $r-d+1$. This becomes zero when $r = d-1$, not $d+1$.\n\n(If we misunderstood, please refer us to the point in the analysis you think it breaks.) \n\n>(ii.3) Section 3.2 - How do we know that $M$ remains invertible throughout the entire runtime of the algorithm. None of the results (including Lemma 3.3) seem to suggest that $\\det M \\neq 0$.\n\nNote that the determinant of $M$ does not decrease in the local search update (see condition in line 5). It remains to show that the selected M in the initialization step is invertible. This easily follows from (a) the greedy algorithm is maximizing volume (which is proportional to determinant) and (b) the full set of vectors span a d dimensional space (which was an assumption we can make without loss of generality, as we can always work with the span of the vectors).\n\nFor the sake of clarity, we will add this discussion to the “Preliminaries and Notation” section of the paper.  \n\n>(iii.1) Algorithm 1 - What is the significance of the parameter $r$? Can I set it to d to be optimal?\n\nAs also mentioned in (ii.2), one can set $r$ to any value $\\ge d$. However, there is a trade-off between the approximation factor and $r$. When $r = d$ (or $d + o(1)$), the approximation guarantee is $\\Omega(d)$. \nAlso as mentioned in Theorem 3.6, setting $r = 3d$, the approximation factor becomes one.\n\n>(iii.2) Algorithm 1 - A description of the initialization subroutine and its properties is missing. This is important for the reader to verify that the presented algorithm is valid, e.g., $M$  starts with full rank.\n\nIn Algorithm 1, it is mentioned that the pre-processing is described in the text. $M$ is a full rank matrix by the fact that we are maximizing the volume.\n\n>(iii.3) Proof of Thm 4.2 - Why is $\\sum n_i = r$?\n\n$n_i$ denotes the number of times index $i$ appears in $S$ (and size of $S$ as a multiset is $r$). So by definition, $\\sum n_i = r$. \n\n>(iii.4) Proof of Thm 4.2 - Why is $H^{-1} = M / r$? Specifically, why is $n_i = 1$ for all $i$ (which is needed for this identity to hold in general).\n\nBy the definition of $H$, $H^{-1} = \\sum_i \\lambda_i v_i v_i^T = \\sum_i (n_i / r) v_i v_i^T = (1/r) \\sum_i n_i v_i v_i^T = M$. In all of this, nowhere is it required that $n_i = 1$. What *is* needed is the invertibility of $H$. This is discussed in the answer to (ii.3) above.\n\n>(1). Please use either $u_i$ or $\\lambda_i$ for the dual variables in the proof of Theorem, but do not use both.\n\nThanks, we will fix this inconsistency.\n\n>(2). Please make the use of parameter r somewhere in Algorithm 1. At first glance, it appears to be an unused parameter, e.g., setting $r = d$ and $r = 1000d$ has no effect on the result of the algorithm.\n\nNo, $r$ is used in the Initialization step of the algorithm. The set $S$ is always of size $r$ – so it is indeed very crucial. We will add a note to make this more explicit. \n\nAnd of course, in Theorem 3.6, both approximation guarantee and runtime are functions of $r$ and $d$. So, $r$ plays a very important role in the final guarantee of the constructed volumetric spanner. \n\n>(3). In equation (4), $r$ can be fractional. This doesn't seem to make sense in the context of the “Initialization” discussion after Algorithm 1.\n\nWe will fix the typo and set it to be the ceiling of $(1 + 4/\\epsilon) d$\n"}, {"review_id": "zeOg2shzjF", "reviewer": "Reviewer_TY5V", "summary": "This paper looks at the problem of identifying volumetric spanners from a set of points  \\in \\RR^d. The paper shows a method of local search which can be extended to find near optimal bounds of volumetric spanners, improving on previous algorithms. The authors also apply it to an application called MVEE, where they provide better rates for finding coresets of MVEE than previously in the literature. \n\nThe authors start with the generalization of volumetric spanners to the c-approximate use-case and analyze their local search method to show that for an L2 volumetric spanner of size 3d, the local search would only take O(d log d) time. They also extend their results for general l_p cases for p = 1, p \\in (1,2) and p>2, the result holding trivially for the latter. \n\nThey analyze the coresets of MVEE problem to show that they can obtain coresets of size O(d/\\epsilon) using local search method, which is an improvement over previous methods which have O(d/\\epsilon^2) bounds. ", "questions": "Please look at the weakness section. ", "limitations": "N/A", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "I have not completely checked the proofs, but the results are strong if the proofs hold. \nParticularly important is their usage in the spanning subset setting/usecase, which is a frequent need in today's age of very large sized datasets and having a small sized subset spanning the majority of the data points  can open doors to a lot of efficient analysis with higher dimensional data, as well as help us perform matrix vector operations on such datasets more efficiently. \nThe problem is very easy to describe and motivate and the algorithm is easy to follow. ", "weaknesses": "The comparison of results is quite difficult to follow from the paper. In particular, it could be pretty easily explained by having a table or having a clear description of the best possible previous result and how much it was improved by through the local search method. I am also not clear about the degree of optimality, which can be more clearly stated in the description itself. It would also be useful to have a description of the degree of optimality of the previous attempts to solve this problem.  ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">The comparison of results is quite difficult to follow from the paper. In particular, it could be pretty easily explained by having a table or having a clear description of the best possible previous result and how much it was improved by through the local search method. I am also not clear about the degree of optimality, which can be more clearly stated in the description itself. It would also be useful to have a description of the degree of optimality of the previous attempts to solve this problem.\n\nWe thank the reviewer for this comment. We addressed this in the “message to all reviewers” above (common rebuttal), and we will add the discussion to the final version of the paper. \n\n"}, {"review_id": "w7vZdsTutO", "reviewer": "Reviewer_QeGT", "summary": "This paper studies the problem of constructing small volumetric spanners. Given a set S of points in R^d, (the l2 version of) the problem is to find a subset of S so that every point in S can be written as a linear combination of the subset points, with the l2 norm of the coefficients bounded above by 1. Analogous problems can be defined for other lp norms.\n\nThere is a simple and efficient greedy algorithm that by folklore results gets a spanner of size O(d log d); there is an improvement due to Todd that gets O(d log log d), and Hazan, Karnin, and Meka get 12d via methods involving the John ellipsoid and spectral sparsification. The main result of this paper is that a slight modification of the greedy algorithm actually computes a spanner of size 3d.", "questions": "N/A", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper gives a simpler and (slightly) better algorithm for computing an l2 volumetric spanner: specifically, a natural greedy approach works. It also gives simple extensions to other lp norms, and matching lower bounds.", "weaknesses": "The improvement in the spanner size is modest compared to prior work, and the algorithm is quite similar to known approaches (the only difference is that instead of iteratively adding elements to the spanner, each time we add a new element we also remove one), as is the analysis. I would not be entirely sure that this algorithm/analysis is not already present in the literature. However, since I could not find a reference I would err on the side of acceptance.\n\nIt would have been good to explicitly mention the bound obtained by the prior work (Hazan, Karnin, and Meka 2013). ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">The improvement in the spanner size is modest compared to prior work, and the algorithm is quite similar to known approaches (the only difference is that instead of iteratively adding elements to the spanner, each time we add a new element we also remove one), as is the analysis. I would not be entirely sure that this algorithm/analysis is not already present in the literature. However, since I could not find a reference I would err on the side of acceptance.\n\n>It would have been good to explicitly mention the bound obtained by the prior work (Hazan, Karnin, and Meka 2013).\n\nPlease see the “message to all reviewers” above (common rebuttal). As for the algorithm being known, it indeed is, as it is simply local search! But the key aspect of local search is the choice of the objective function. In this case, we use an appropriate determinant, and we have to argue that the output of local search with this objective is a well conditioned basis.\n\nWe also note that the general $\\ell_p$ case has interesting behavior which was not known before, and moreover, the exact same algorithm works for all $p$! (Earlier, the cases $p=2$ and $p=\\infty$ were handled by different methods).\n"}, {"review_id": "MzAiqZDIHS", "reviewer": "Reviewer_4Fat", "summary": "This paper researches the $\\ell_2$-volumetric spanner (or $\\ell_2$-well-conditioned spanning subset) for a given dataset $X$ based on the local search algorithm, in which each iteration implements a single swap to update the volumetric spanner $S$. More generally, the results are extended to $\\ell_p$-norm for any $p \\ge 1$. Furthermore, the proposed algorithm can be applied to build coresets of size $O(d/\\epsilon)$, which is independent of the number of data points $n$, for the minimum volume enclosing ellipsoid (MVEE) problem. ", "questions": "In Line 37-39, this paper claims that it improves both lines of prior work [Hazan, Karnin, and Meka'13] and [Woodruff and Yasuda'23]. What are the aspects of improvements? ", "limitations": "See Weaknesses. ", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "(1) The proposed algorithm is very easy to understand and the paper is well-written.  \n(2) This paper presents strict proof for the proposed algorithm.  \n(3) The coresets for the minimum volume enclosing ellipsoid problem are of size $O(d / \\epsilon)$ which is independent of the number of points $n$. \n", "weaknesses": "1. For the $\\ell_2$-volumetric spanner case  \n(1) In the paper [Hazan, Karnin, and Meka'13] (see Theorem 1.1), the  $1$-approximate spanner $S$ has size $|S| = 12 d$ and the running time is $O(n^{3.5} + n^3 d + d^5)$.  \n(2) In the paper [Woodruff and Yasuda'23] (see Theorem 3.4 and Corollary 3.5), the $(1+\\epsilon)$-approximate spanner $S$ has size $|S| = O(d \\log\\log{d} + d / \\epsilon)$ and the running time is $\\widetilde{O}((\\text{nnz}(A) + d^2) d / \\epsilon)$, where $\\text{nnz}(A) = O(nd)$.  \n(3) In this paper, setting $\\delta = O(\\epsilon)$ gives the $(1+\\epsilon)$-approximate spanner $S$ of size $|S| = O(d)$ and the running time $O(n d^4 \\log{d} / \\epsilon)$.  \nFrom the above comparison, we can see that the running time is much worse than that of [Woodruff and Yasuda'23] taking $\\epsilon \\in (0, 1)$ as a constant.  \n2. This paper gives the coresets for MVEE with size $|S| = O(d / \\epsilon)$ and running time $O(n d^4 \\log (d/\\epsilon) / \\epsilon^2)$. The size of coreset is impressive, but the running time and approximation ratio $(1+\\epsilon)^d$ are not satisfactory. In the paper [Cohen, Cousins, Lee, and Yang'19] (see Theorem 1.1), the $\\sqrt{d}$-approximate ellipsoid can be obtained in time $O(n d^2 \\log (n/d) / \\epsilon)$. The coreset is a proxy of dataset $X$, but computing the coreset of $X$ in this paper takes much more time than computing the approximate ellipsoid of $X$ directly in the paper of Cohen et al. For me, this is a critical drawback. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> For the $\\ell_2$-volumetric spanner case\n> (1) In the paper [Hazan, Karnin, and Meka'13] (see Theorem 1.1), the 1-approximate spanner $S$  has size $|S| = 12d$ and the running time is $O(n^{3.5} + n^3d +d^5)$.\n> \n> (2) In the paper [Woodruff and Yasuda'23] (see Theorem 3.4 and Corollary 3.5), the ($1+\\epsilon$)-approximate spanner $S$  has size $|S| = O(d \\log \\log d + d/\\epsilon)$ and the running time is $\\tilde{O}( (\\mathrm{nnz}(A) + d^2) d/\\epsilon)$, where $\\mathrm{nnz}(A) = O(nd)$.\n> \n> (3) In this paper, setting $\\delta = O(\\epsilon)$ gives the ($1+\\epsilon$)-approximate spanner $S$ of size $|S| = O(d)$ and the running time $O(nd^4 \\log d / \\epsilon)$. From the above comparison, we can see that the running time is much worse than that of [Woodruff and Yasuda'23] taking $\\epsilon \\in (0,1)$ as a constant.\n\nFor point (1), note that our algorithm (see Theorem 3.6) returns a 1-approximate spanner $S$ with size $3d$ in $O(d \\log d)$ iterations (which means $O(nd^4 \\log d)$ time even if we do a naive implementation – more on this below). So, both spanner size and runtime in our algorithm are better. Moreover, we don't need to appeal to the machinery on spectral sparsification, barrier potentials, etc.  to obtain our result.\n\nFor points (2) and (3), we first note that the greedy algorithm of [Woodruff and Yasuda 23] (henceforth [WY23]) needs to do essentially the same computation as us: they have to compute which vector to add in order to maximize the determinant (i.e., to compute a leverage score). Indeed, [WY23] refers to an earlier work of [Todd] for this step. The $\\mathrm{nnz}(A)$ bound is obtained by using sketching methods to speed up the computation of leverage scores. We can use exactly the same methods for quickly computing leverage scores in our local search step. [Todd] needs to perform $d$ steps of greedy addition (each step involving computing appropriate leverage scores, which takes $\\mathrm{nnz}(A)$ time), while we need to perform $d \\log d$ rounds of local search. Since each round involves (a) removing each of the elements in $S$ one at a time, (b) computing which new vector to add to $S$, similar to greedy addition. So the running time of each local search step is $|S| \\times \\mathrm{nnz}(A) = O(d \\times \\mathrm{nnz}(A))$. The number of rounds is larger by a factor $\\log d$ as we noted above, so the overall runtime is worse than [WY23] by a factor $d\\log d$. \n\nThis may be too high a price to pay for improving a $\\log \\log d$ factor in some applications, but we have the interesting conceptual message that local search gives a strict improvement over the best known guarantee for greedy. Also, our analysis is simple and direct, it does not require appealing to the result of Todd, and the connection to MVEE. (Indeed, in Section 4, we use the connection to MVEE in the opposite direction, obtaining a better result for MVEE.) \n\n\n> This paper gives the coresets for MVEE with size $|S| = O(d/\\epsilon)$ and running time $O(nd^4 \\log(d/\\epsilon) / \\epsilon^2)$. The size of coreset is impressive, but the running time and approximation ratio $(1+\\epsilon)^d$ are not satisfactory. In the paper [Cohen, Cousins, Lee, and Yang'19] (see Theorem 1.1), the $\\sqrt{d}$-approximate ellipsoid can be obtained in time O(nd^2 log(n/d) / \\epsilon). The coreset is a proxy of dataset $X$, but computing the coreset of $X$ in this paper takes much more time than computing the approximate ellipsoid of $X$ directly in the paper of Cohen et al. For me, this is a critical drawback.\n\nThe work on fast algorithms for John’s ellipsoids *measures approximation differently*. A $\\sqrt{d}$-approximation in that context translates to a $(\\sqrt{d})^d$-approximation to the volume (because if we scale a body by $c$, the volume in $d$ dimensional space grows by a factor of $c^d$). So in this sense, our construction is much stronger in terms of approximation ratio. [This is a natural question that readers may have, so we will add the above to the final version.]\n\nSecond, as we mentioned above, using sketching methods for computing leverage scores, our running time can be brought down to $O(d^2 + \\mathrm{nnz}(A))(d^2 \\log d) / \\epsilon$, which is about $d \\log d$ worse.\n\n> Question. In Line 37-39, this paper claims that it improves both lines of prior work [Hazan, Karnin, and Meka'13] and [Woodruff and Yasuda'23]. What are the aspects of improvements?\n\nWe described the improvements over prior works in our responses above. We also listed them more clearly in the common rebuttal above (see “Message to all Reviewers”). We will add this discussion to the final version.\n"}]

Author rebuttal:

**Message to all Reviewers.**

We thank all reviewers for their careful and constructive comments. Here we are addressing the question regarding the application of our result to machine learning and the improvement of our work over prior works. Then, we will answer all other questions in the individual responses. Please let us know if you have any further questions/comments. 

**Applications to Machine Learning.**  (The following are mentioned briefly in the introduction, but we can expand on them in the final version.) Well conditioned bases were introduced and studied by Awerbuch and Kleinberg (2008) and Hazan et al. (2013), as a good “exploration basis” for bandit algorithms on convex domains. Bandit optimization is a fundamental and well-studied problem in ML –which itself has many applications– and our results give improvements over these prior work (explained below).

The second main application is matrix low-rank approximation. The problem of finding a small (in cardinality) subset of columns whose combinations can be used to approximate all the other columns of a matrix is called “column subset selection”. It has been used for matrix sketching, “interpretable” low rank approximation, and has applications to streaming algorithms as well.  The classic works of Frieze and Kannan 1997; Drineas, Mahoney and Muthukrishnan 2006; Boutsidis et al. (cited in the paper) all study this question. Well conditioned bases are closely related to column subset selection, and indeed, the works of Boutsidis et al. exploit this connection. The recent paper of Woodruff and Yasuda (STOC 2023) expands on this, using well conditioned bases for a host of matrix approximation problems.

Third, well conditioned bases are closely related to determinantal point processes (DPP) and diversity maximization, also well studied in the ML literature. Indeed, our techniques are derived from work in this space.

Finally, as we point out in the paper, we obtain coresets for the classic problem of min volume enclosing ellipsoids (MVEE). Coresets are an object of extensive study in ML, used to obtain a “representative” sample of a given dataset. Many works have tried to construct “optimal” sized coresets for various data analysis problems, like clustering and low rank approximation. We do this for MVEE, obtaining coresets of size linear in the dimension. This is conceptually interesting, because it matches the coreset size for a much simpler object – the axis-parallel bounding box (which always has a coreset of size $\le 2d$, obtained by taking the two extreme points along each axis).

**Improvement over prior work, significance of the results.** We will highlight the following discussion in the final version. 

First off, we note that a unified treatment of the $\ell_p$ well-conditioned bases (for general $p$), along with matching lower bounds has not been done in any of the prior work. Existing results treated the cases $p=2$ and $p=\infty$, using different techniques.

For $p=2$, there are two main prior works. The first is the work of Hazan et al. 2013. They obtain a linear sized basis, similar to our result. However, their result is weaker in terms of running time (by a factor roughly $d^2$), as well as the constants in the size of the basis. Moreover, our algorithm is much simpler, it is simply local search with an appropriate objective, while theirs involves running a spectral sparsification subroutine (that involves keeping track of barrier potentials, etc.) followed by a rounding step.

The second work is the recent result of Woodruff and Yasuda (2023). Here the algorithm is simple – basically a greedy addition (and thus the running time is comparable to ours, up to a logarithmic factor). However, the authors incur an additional $\log \log d$ factor, due to the analysis of the greedy algorithm (which itself was from a prior work of Todd 2016). Removing this factor is interesting conceptually, as it shows that local search with an appropriate objective can achieve something stronger than the best known result for greedy. 


Meta-review: Although several reviewers had major technical concerns about the paper, and whether its contributions represented a genuine improvement over previous work, the discussion period resolved these concerns, and nearly all reviewers eventually agreed that the paper should be accepted. The remaining concern is about the novelty of the algorithm, but the authors make a compelling argument that the lack of novelty is itself a discovery, since it demonstrates that an existing and very simple method is nearly optimal, which was not previously known. The authors should consider emphasizing this further in their revision.
Decision: Accept (poster)