Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile Streaming
Authors: Gregory Dexter
Petros Drineas
David Woodruff
Taisuke Yasuda
Venue: NeurIPS 2023 poster (2023)
Keywords: dictionary learning
k means clustering
sketching
ptas
streaming
TL;DR: PTAS and streaming algorithms for dictionary learning and clustering via sketching

Abstract: Sketching algorithms have recently proven to be a powerful approach both for designing low-space streaming algorithms as well as fast polynomial time approximation schemes (PTAS). In this work, we develop new techniques to extend the applicability of sketching-based approaches to the sparse dictionary learning and the Euclidean $k$-means clustering problems. In particular, we initiate the study of the challenging setting where the dictionary/clustering assignment for each of the $n$ input points must be output, which has surprisingly received little attention in prior work. On the fast algorithms front, we obtain a new approach for designing PTAS's for the $k$-means clustering problem, which generalizes to the first PTAS for the sparse dictionary learning problem. On the streaming algorithms front, we obtain new upper bounds and lower bounds for dictionary learning and $k$-means clustering. In particular, given a design matrix $\mathbf A\in\mathbb R^{n\times d}$ in a turnstile stream, we show an $\tilde O(nr/\epsilon^2 + dk/\epsilon)$ space upper bound for $r$-sparse dictionary learning of size $k$, an $\tilde O(n/\epsilon^2 + dk/\epsilon)$ space upper bound for $k$-means clustering, as well as an $\tilde O(n)$ space upper bound for $k$-means clustering on random order row insertion streams with a natural "bounded sensitivity" assumption. On the lower bounds side, we obtain a general $\tilde\Omega(n/\epsilon + dk/\epsilon)$ lower bound for $k$-means clustering, as well as an $\tilde\Omega(n/\epsilon^2)$ lower bound for algorithms which can estimate the cost of a single fixed set of candidate centers.

Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile Streaming
Gregory Dexter
Petros Drineas
Department of Computer Science
Department of Computer Science
Purdue University gdexter@purdue.. edu
Purdue University pdrineasSpurdue edu
David P. Woodruff Computer Science Department Camegie Mellon University dwoodrufêcs cmu. edu
Taisuke Yasuda
Computer Science Department Carnegie Mellon University taisukey@cs. cmu. edu
Abstract
Sketching algorithms have recently proven to be powerful approach both for designing low-space streaming algorithms well fast polynomial time approxi- mation schemes (PTAS). In this work, we develop new techniques to extend the applicability of kketching-based approaches the sparse dictionary learning and the Euclidean k-means clustering problems. In particular, we initiate the study the challenging setting where the dictionary/clustering assignment for each of the n input points must be output, which has surprisingly received little attention in prior work. On the fast algorithms front, we obtain PTAS's for the k-means clustering problem, which generalizes to the first PTAS for the sparse dictionary learning problem. On the streaming algorithms front, we obtain new upper bounds and lower bounds for dictionary learning and k-means clustering. particular, given design matrix A E gn turnstile stream, we show an Ö(nr + dk dk/c) space upper bound for r-sparse dictionary learning of size k an Ó(n/² dk/c) space upper bound for k-means clustering, as well an Ö(n) space upper bound for k-means clustering on random order row insertion streams with natural "bounded sensitivity" assumption. On the lower bounds side, we obtain general ((n/ dk:/s) lower bound for k-means clustering, well ((n/c2) lower bound for algorithms which estimate the cost of single fixed set candidate centers.
approach for designing
Introduction
A classic idea in machine learning and signal processing for efficiently handling large datasets is to approximate them by simpler or more structured surrogate datasets. Many methods this direction have long been considered, including low rank approximation, which approximates a given dataset by one that lies on low-dimensional subspace, k-means clustering, which approximates given dataset by at most & distinct points, and sparse dictionary learning Olshausen and Field [199],, which approximates a given dataset by lincar combinations of elements of a small dictionary of size k with r-sparse coefficient vectors (i.c., vector with at most nonzero entries). We focus on the latter two problems this work:
Definition 1.1 (r-sparse dictionary learning). Let ym C Rdd be a set of n vectors dimensions, and let A E Roxd be the matrix with the ith row set to a'. Then for a matrix X E Bank with
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

r-sparse rows and dictionary D E Bkxd, we define the dictionary learning cost to be
cost (2.D) = |XD - Al
In the r-sparse dictionary learning problem, we seek to minimize cost(X, (XD)) D) over all X E X and D E gixdd where X' denotes the set of all k matrices with r-sparse rows.
Definition 1.2 (Euclidean k-means clustering). Let {a') S R be a set of n vectors in d dimensions, and let A E [uxd be the matrix with the ith row set to a'. Then, for matrix X E g with standard basis vectors in its rows and a set of centers C E Ik we define the k-means clustering cost to be
cost(X, C) = |XC- AlP--
In the k-means clustering problem, we seek to minimize cost,(X, C) over all X E X and C E Rkxd, where X denotes the set of all n x matrices with standard basis vectors as rows.
While dictionary learning and clustering have found extraordinary success in various applications in practice, they are known to be computationally difficult problems to solve [Mahajan et al.) 2012 Natarajan [995]. and thus there has been intense focus on developing approximation algorithms and heuristics for these problems, such as those hased on greedy methods [Lloyd] 1982 Das and Kempe
2011 or convex relaxations [Donoho and Elad 2003
Fuchs 2004 Cohen-Addad et al. 2022a
In this work, we study algorithms for sparse dictionary learning and k-means clustering in two distinct settings via unified set of techniques based on sketching. Sketching [Woodruli] 20 4b)] broadly speaking, refers to techniques for compressing large matrices by linear maps. and includes methods such as oblivious sketching and nonuniform sampling. Classically, sketching has been applied to design low- memmomory algorithms in the streaming setting, when the input presented to the algorithm as a sequence of updates. More recently, sketching has been shown to be invaluable for designing fast algorithms as well. In particular, there has been a line of work which shows how sketching techniques can be applied to obtain polynomial time approximation schemes (PTAS) for variety of NP-hard problems ranging from clustering [Feldman et al., [007] to weighted low rank approximation [Razenshteyn et al., 2016 to tensor decompositions [Song al. 2019]. We study such sketching-baa braeiigg--aedddddeo algorithms for sparse dictionary learning and Euclidean k-means clustering. both in the offline setting where we obtain the first PTÁS for sparse dictionary learning, as well as in the turnstile streaming and other streaming models. In particular, in the streaming setting, we initiate the study of solving these problems in the setting where the algorithm must output the assignment of the points to the dictionary/cllsteringg which has received surprisingly little attention in prior work.
1.1 Our contributions
1.1.1 PTAS for dictionary learning and clustering
We start with discussion of our results on designing fast PTAS's. Our main contribution that highlight from this section is the first PTAS for sparse dictionary learning, which also gives a new and simple approach towards designing a PTAS for k-means clustering.
typical approach for designing PTAS's for shape fitting problems such as dictionary learning and clustering is to first find a smaller instance whose solution approximates the original instance, and then to solve the smaller instance using any algorithm, where even an inefficient algorithm will be tractable due to the smaller size of the instance. A representative work which takes such approach for the k-means clustering problem is that of Feldman et al. 2007 which uses coresets to implement the first step of finding smaller instance. Here, coresets for k-means clustering are weighted subset of the original data points such that the cost of any candidate set of centers approximates the cost when applied to the original dataset. Furthermore, the size of this coresct can be taken to be poly(k/e), and thus solving for an optimal set of centers on this subset of points can be done in time independent of the number of points n. Due to this natural approach, there has been a long line of work on obtaining smaller coresets for k-means clustering [Feldman and Langberg 2011
Braverman
et al. 2016 Bachem et al. 2018 Cohen-Addad et al. 2021 2022b
On the other hand, for the sparse dictionary learning problem, similar results are strikingly lacking. The only previous work we are aware of is a coreset construction for the sparse dictionary learning
problem due to Feldman et al. 2013). However, the construction of the coreset in this work requires an algorithm for computing an approximately optimal dictionary, which prevents its use in designing

---

fast PTAS's to solve the dictionary learning problem in the first place. To address this problem, we first show that a completely different coreset technique due to Tukan et al. [022] for the projective clustering problem can in fact be applied to the sparse dictionary learning problem. Notably, this technique uses John ellipsoids to construct coresets rather than using a nearly optimal solution to the dictionary learning problem, and thus avoids computing approximately optimal dictionaries. In turn, this allows us to obtain the first PTAS for the dictionary learning problem. Our argument additionally combines this coreset construction with sparsity-counting technique together with polynomial system solvers Renegar 1992a bl to efficiently solve a smaller version of the original problem. Our techniques also yield new PTAS for k-means clustering, which is arguably simpler than prior approaches such as the algorithm of Feldman et al. [2077]. We give a full discussion of our results and techniques for our PTAS for sparse dictionary learning in Section 2
1.1.2 Dictionary learning and clustering on streams
As our next contribution, we study algorithms for dictionary learning and clustering in turnstile streams and other related models of streaming. In the turnstile streaming model, the input undergoes arbitrary entrywise insertions and deletions:
Definition 1.3 (Turnstile stream). We say that an input matrix A E Rgxd is presented in a turnstile stream if A is initialized to 0 and receives entrywise updates Aij t As. A for A R.
We initiate a systematic study of the dictionary learning and clustering problems in the setting where the assignment of the points to their sparse set of dictionary elements or clusters must be output together with the dictionary/cluster centers. Indeed, even for the popular Euclidean k-means clustering problem, almost all prior work that we are aware of only focus on outputting either only the cluster partitions, or the centers, but do not study the problem of recovering both. We address this problem by providing dimensionality reduction technique that applies to k-means, sparse dictionary learning, and more generally to any problem of the form minxe X'. XD - A
A approach for designing low-space streaming algorithms for clustering is to apply the standard Hoinson-Lindessteen lemma (Johnson and Lindenstrauss 1984 Boutsidis et al. 2010 Cohen et al.)
2015. Becchetti et al. 2019, Makarychev et al. 2019). This result states that if G E Raxa is an appropriately scaled dense Gaub-Ga matrix for O(e (og(k/e)), then for any partition of A into kt clusters, the k-means clustering cost of AG approximates the k-means clustering cost of A up to (1 E) factor. Furthermore, AG can be efficiently maintained in the turnstile streaming model (Definition 1.3) using just ns = 2n) space, due to the linearity of the sketch G. Note however that, naively, we cannot retrieve the corresponding centers of a clustering found by this method, since we have only stored the s-dimensional sketches of the n points, and additional information must be stored in order to retrieve d-dimensional cluster centers which achieve (1 + e) approximation. In fact, we note in Theorem 4.1 that there is in fact a (((kk/e) space lower bound if we wish to output centers C E Rxx which achieve (1 + c) approximation, so the sketch AG is provably insufficient for outputting both nearly optimal assigmment X and centers C when n ö(cdk). We give full discussion of our approaches for sketching and streaming algorithms for A: means clustering and dictionary learning and how we overcome this problem Sections and S
On the other hand, a study of lower bounds for the k-means clustering problem in the streaming setting when the assignment of points must be output notably lacking in prior work as well. The main challenge in this setting is in obtaining the right dependence on and e. Indeed, an 2(n) lower bound is immediate, since the size of the output is at least (T)) when we need to output assignments of the points to its appropriate cluster (in fact, we show in Theorems 4.3 and 4.4 an (2(n) lower bound follows even for outputting a constant factor approximation of the cost or centers). On the other hand, the previous upper bound using the -ininsson--nddestrrrrs lemma to compute a nearly optimal assignment to clusters requires Ö( 2n) bits of space. Note that there are many lower bounds that show that roughly - dimensions are required to apply the Baanson--Lnndnstter
lemma in various settings Nelson and Nguyēn [2014), Kane et al. [2010]. Larsen and Nelson| (2166] 2017]. Makarychev et al. 2019]. However, it is not clear whether or not this implies that c bits must be stored for all points in order to cluster them to (1 e) -)aaproxximatel optimal clustering solution. Indeed, it may be possible that bits are required only for much fewer than n points, while the vast majority of the n input points requires only Ö(n) bits of space to assign to an approximately optimal center.
3

---

We present two lower bounds to partially address the question of impossibility results for assigning points to clusters in turnstile streams. Our main lower bound result is the following, which establishes an ((c n) lower bound to output a (1 + c)-neally optimal clustering. While this does not match the upper bound given by the Johnson-Lindenssrruus lemma, it shows that we cannot hope for a Öm)) upper bound in the turnstile streaming model in general.
Suppose a turnstile streaming algorithm outputs centers { S Rd as well as assignments of n points to the centers, which achieves a (1 + e) approximattll optimal solution to the k-means clustering problem. Then, the algorithm must use at least (n/cc) bits of space over any constant number of passes.
Theorem 1.1 (Informal restatement of Theorem C.1 ==
As second lower bound result, we also show that the Jehnson-Lindenstranle if we require our algorithm to give a nearly optimal assignment of the input points to fixed set of candidate centers. That is, we show in Theorem 4.2 that there is fixed set of centers such that, if turnstile streaming algorithm can assign each of the n. imput points to cluster such that the cost is at most (1 + e) times the cost of the optimal assignment, then at least ()( 2n) bits must be stored. A more detailed discussion of our lower bounds is given in Section
lemma is nearly tight
Finally, we show that under some natural settings, one can obtain upper bounds that circumvent the lower bounds presented above. Indeed, we show that if we work in the random order row arrival streaming model, in which the input stream corresponds to the rows of A that arrive in a uniformly random order, then we can obtain upper bounds that depend on the maximum sensitivity of the input stream, and in particular, we obtain an upper bound using only ((n) bits of space if the maximum sensitivity is sufficiently small (Theorem 4.5). Here, bounded sensitivity assumption states that there are no points that can take up sigmificant fraction of the objective function, and can also be interpreted as way to formalize a "well-clustered" instance.
2 Fixed parameter PTAS for sparse dictionary learning
2.1 PTAS for r-sparse dictionary learning
In this section, we provide an algorithm which solves the r-sparse dictionary learning problem (Definition I.I in time polynomial in the input matrix size (n) and dimension (d) up to c-relative error, for fixed and e. Additionally, we show that a similar approach can used to provide an algorithm for k-means (Definition] 1.2) that matches the current best dependency on n, d, and l up to lower terms. First, we introduce a dimensionality reduction method that applies to both problems.
2.2 Dimensionality reduction
Our first step is to reduce the dimensionality of the given problem. Since the only difference between k-means and sparse dictionary learning is the constraint on the left factor, X, use the same sketching approach to reduce both problems. Consider the following general definition:
General problem: Let X C Raak and A E Raxd Let l < n,.. d. Define the optimal solution as:
(x", "T,D")=
argmin
|XD A
(1)
XEX.DEREx4
The following theorem states that one may efficiently reduce the dimensionality of A in sparse dictionary learning or k-means. We briefly sketch the ideas behind the reduction. Intuitively, the regression guarantee of Theorem 3.1 in Clarkson and Woodrufi (209) states that if S is a rank k < d fz-embedding matrix, then D = argmin ISX*D- A} will be a good approximation to the optimal solution of the original problem. While we do not know X*, this guarantee implies that there is an approximately optimal dictionary, D. in the row space of SA. We can then restrict the optimization problem to consider only dictionaries in this lower dimensional space. Therefore, we only need to consider the error residual this lower dimensional space, so we may reduce the dimension of the problem by applying an affine-embedding matrix T and then applying SVD to find the dominant singular subspace of SAT. Finally, we project the rows of to this dominant subspace. We can then solve the lower dimensional problem and map the solution to the original space.

---

Theorem 2.1. There is an algorithm which solves the problem in ① up to E (0. 1) relative enorr with constant probability in (nnzz(A) + (n + d) poly(k/e)) time plus the time needed solve:
min
|
XEX DER
to within e-relative frrorfor = Ok lo)( and some some A' E R with constant probability.
In the rest of this section, we assume that d = poly(k/e) for clearer exposition, since the above theorem implies we can reduce to this case efficiently.
2.3 Algorithm for sparse dictionary learning
The first component of our algorithm for sparse dictionary learning is coreset construction that reduces the size of the problem from n to a size that is logarithmic in n. We achieve this by first leveraging an existing coreset construction for projective clustering by [Tukan et al. [2022] In the (e, m)-poojective clustering problem, the goal is to find a set of & me-dimensional subspaces that minimizes the sum of the squared Euclidean distances of the input vectors {a J²=1 the closest subspace. Observe that, in the r-sparse dictionary problem, the minimum cost of a dictionary is the sum of the squared Euclidean distances of the input vectors to the (*) subspaces spanned by any subset of vectors of the & vectors in the dictionary. Hence, coreset which preserves the projective
clustering cost when = (+) will also preserve the cost of dictionary in sparse dictionary learning.
After applying the coreset, we have reduced the size of the sparse dictionary problem to be at most logarithmic in n. This allows to guess the sparsity pattern of the optimal left factor X*, since most entries each row of X* may be nonzero. For each guess of the sparsity pattern of X*, we find an approximately optimal solution under this constraint by recognizing this polynomial optimization problem. We apply the decision algorithm of Renegar 1992a] using binary search to determine each entry of D and the nonzero entries of X done in Razenshteyn et al. (016). At some point we guess the sparsity pattern of X*, and hence attain an e-relative error solution to the sparse dictionary problem. The next theorem formally states the assumptions and guarantees of our algorithm, which is formalized in Algorithm D in the appendix.
Theorem 2.2. For an input for the r-sparse dictionary learning problem (Definition 1.1 with error tolerance (0, 1) such that the entries of A have bounded bit complexity, Algorithm returns X X and D Rkxd satisfying:
I&D AllF S (1++)
min DER
|XD - AllF;
in poly(n) time with constant probability, when k. r, and 1/c are bounded by constant
2.4 Algorithms for k-means
The same general approach of applying dimensionality reduction and coreset construction along with guessing the sparsity pattern of X can be used to achieve a Exxed-parameter PTAS for k-means well. However,
can achieve an improved time complexity matching the current best dependency on k and up to lower order terms by further reducing the problem using results on leverage score sampling. Specifically,
combine Theorem 17 in Woodruff (014b) and Theorem 3.1 in Clarkson and Woodruff 2009) to prove the following lemma.
Lemma 2.1. There a set of matrices C R with exactly one non-zero entry per column such that for any A E R and B Bx there exists S S. so that if:
X argmin |S(AX- B)llF Xegkxd
-B)IF and X" argmin AX B[E
XeRlxd
then,
JAX S -B|F-.
Furthermore, S depends only on n, ki and e; and |S| n 0 Aluck)
If' & and not assumed to be constant, then the time complexity is exp((81 (x) logn).
5

---

After applying coreset construction to reduce the k-means problem to size poly(k/e). we can efficiently apply the above lemma to then reduce the problem to size (k/e). Then, we brute force over all possible left-factors to find X The following theorem states our results formally.
Theorem 2.3. For any input A E _axd and
(0, 1), Algorithm 2
will return feasible solution to D), satisfying:
the k-means clustering problem (Definition 1.2
(X,
XD - A S c1+
min XEX
XXD - XD
DERAX
with constant probability. Furthermore, Algorithm time.
2 runs in n (o-ooy(k/e)) + exp( polylog(k/oo)
3 Turnstile streaming algorithms
In this section, we consider the the turnstile streaming model (see Definition 1.3). We provide upper bounds the space needed to compute an c-relative error solution the k-means problem and restricted form of the sparse dictionary learning problem in a turnstile stream. We do this by showing that these approximately optimal solutions can be computed from few small linear sketches of the original data matrix, and any linear sketch can be trivially maintained in a turnstile stream by linearity of the updates. A key idea behind these algorithms is applying the guess-the-sketch approach introduced in Razenshteyn et al. 2016 along with the following theorem.
Theorem 3.1. (Theorem 3.1 in Clarkson and Woodruff (2009) Given 8, E O, suppose A and B are matrices with rows, and A has rank at most k. There is an m = O(k log(1/8))e) such that, if S is an m x n sign matrix, then with probability at least 1 - 8, if argminx ||(AX B)I
and X argminx ||XX- -B] then ||A B|I (1 AX - Bl]
Notice that, if we knew the optimal solution X* exactly, then by the previous theorem we could
compute an approximately optimal dictionary D exactly as D = (SX*) ( SSA. The key observation that, since S is random sign matrix and the rows of X are standard basis vectors, the set (SX X E
X.SE (+ke)(())))x0)) is not too large. Also, we can approximately solve minxex ||X A for a fixed D with constant probability by solving X = minxex |[XD A)T where T is a
moderately sized affine embedding matrix. Since the number of possible (X, δ) is not too large, an
éz-embedding matrix, W, can be used to approximate ITD A for every possible (X,
Our streaming algorithm relies carefully balancing the roles of the three sketching matrices to minimize the size of the sketches, using the weakest guarantee possible for each component. In particular, it is critical to use the affine embedding matrix T to only preserve the error for fixed D instead of every subproblem and instead subproblem provides an approximate solution to the overall problem.
the f2-embedding matrix W to identify which
Theorem 3.2. (I) There are distributions of random sketching matrices T E Rdxt, S Rexn, and W E Ruxnd, with t ([llognk)//a s= O(&), and w O W vec(A) suffice to compute (1 + -)approximmaee solution to the k-means problem with at least constant probability, where vec( A) E Ind is the flattening of A.
es log(n)) such that SA, AT, and
(2) There is an algorithm which computes turnstile model with at least constant probability using Ó(n/² + dk/c) space for d (oly(k/c) in n 1,12// fc) additional time.
approximaa solution the k-means problem in the
The previous proof critically relies on the fact that (SX X E X' S E {=1]mx=] is finite set that not too large. We must therefore introduce the following restricted form of the sparse dictionary problem.
Definition 3.1. (Discrete r-sparse dictionary problem) Let X be the space of n x k matrices with al most non-zero entries per row and non-zero entries laking values in (-D,-(D) D0...,-1.00 1, I.. 11), DY. The goal of this problem is solve the following optimization problem:
X",
argmin
[XD -Alrr
XEX
where A E 1gaxd is arbitrary input matrix.

---

Under this constraint that the solution is in discrete space the proof of the streaming algorithm for sparse dictionary learning proceeds essentially the same as for k-means while accounting for the larger solution space.
Theorem 3.3. (1) There are distributions of random sketching matrices T E R S R and W E IR Roxdnd, with t (r log(nkD)//e) = and w O log(nD)) such that SA, AT, and W vec(A) suffice to compute (1 + aaapproxxmmaee solution to the discrete r-sparse dictionary problem (Definition 3.7) with at least constant probability.
(2) There is an algorithm which computes (1 + e) -approximate solution to the r-sparse dictionary problem in the turnstile model with at least constant probability using (nrr/e² + dkk/e) space for d >> poly(k/ (k/6)) / in k" (uD)O00) (e) additional time.
Removing the restriction that X* belongs to the restricted space would be an interesting future problem. However, issues that the entries of X may be very large, since the rows of D may not be orthogonal, and a uniform discretization is required to apply a guess-the-sketar argument.
4 Streaming lower bounds for Euclidean k-means clustering
We introduce slightly different definitions of the k-means clustering problem than the one used in Definition 1.2 to facilitate the notation of our lower bound arguments this section.
Definition 4.1 (k-means clustering cost). Let {a') S IR be a set of vectors in d dimensions. Then, we define the k-means clustering cost of centers c' c² ..... ch E IR to be
cost(c', e
min ||a - cl11.
Definition 4.2 (Approximate solutions to k-means clustering). Let {a'l S Rd be a set of vectors in d dimensions. Let
OPT = min cost(c 2 ,..
et o o gRd
We say that an algorithm outputs an e-approximate solution the k-means clustering problem if the algorithu outputs one of the following:
Partition: a partition C²2 C² C²,...,,C** C C [nx] such that
||a a¹ (1+
iE
where 2 Tot Eiecs at.
Centers: centers ét 62 .......h Rdd such that cost (,t,,,,,,.._.) .,,...,,?h) S (1 +)OPT.
Cost: a number c 2 such that OPT S c +)OP.
4.1 Lower bounds for k-means clustering
Our most technically involved and delicate lower bound result is the following theorem, which shows that nearly optimally solving k-means clustering to (1 + e) accuracy requires (((ne)) bits of space:
Theorem 1.1 (Informal restatement of Theorem C.I Let k = d = Ō(1fe). Suppose turnstile streaming algorithm outputs centers {e)) C Red as well as assignments of n points to the centers, which achieves a (1 + c)-pprooximately optimal solution to the k-means clustering problem. Then, the algorithm must use at least ((n/e) bits of space over any constant number of passes.
We defer the full proof to Appendix and give a proof sketch in this section to illustrate the most important ideas.
7

---

The hard instance: set disjointness. The starting point to our lower bound is the information theoretic communication complexity lower bound for the set disjointness problem due to Bar- Yossef et al. [004]. In the two-party set disjointness problem, two players Alice and Bob each have bit vector A, B E (0, 1)dd in d dimensions, and they must determine whether there exists a coordinate j E [d] such that A, B; = 1 or not. The work of Bar- Yossef et al. (2004) shows that in order to solve this problem. Alice and Bob must exchange messages that reveal at least (2(d) bits of information about their inputs, which in turn implies an ()(d) communication complexity lower bound for this problem, as well as an (nd) communication complexity lower bound for solving a constant fraction of n independent instances of the same problem. Furthermore, the hard instance of Bar- Yossef et al. 2004 has a simple input distribution: the vectors (A, B) are such that the jth coordinate (A', B²) drawn either as (0, 0) with probability 1/2 or (1, 0) with probability 1/4 or (0, 1) with probability 1 1/4, except for one coordinate, which may take the value (1, 1).
We aim to make use of this result as follows. Consider the vector Z A A B. This vector has entries in {0. 1), except possibly for one entry, which could be 2. If we have n such vectors, then we expect good clustering into k- = d clusters to cluster all points with Zj 2 together. Such a clustering would be able to output the index of the intersection of A and B. which intuitively requires more information than just determining whether there is an intersection not, and thus should also require ((d) bits of information cost. Furthermore, we can choose the dimension d to be roughly 1/e, so that the cost of clustering Z to the "correet" center will have cost of (dd) ((1/e), while clustering Z to the incorrect center will incur an additional error of (1), which is an e fraction of the cost.
Cost caleulations. The main challenge in carrying out the idea in the previous paragraph is in arguing that the target optimal clustering that we wish to discover indeed is a nearly optimal clustering, and that significant deviations from this clustering result in a large cost. This involves showing lower bound on the cost of any clustering.
Our first step is to obtain lower bound on the cost of any clustering of n random bit vectors in d dimensions. If we first fix a set of centers {cr 1/k 1 then the minimum distance between a random bit vector Z and any of the el can be bounded by using Chernoff bounds. which implies a lower bound of d/4 - (log d) on this quantity in expectation (Lemma C.4.. Note, however, that this lower bound is not high enough to prevent nearly optimal solution from just assigning points according to the best clustering of the random bits while ignoring the one entry that takes the value of Z, = which means that the clustering need not solve the problem of identifying the intersection coordinate between A and B.
To address this problem, we need to make the cost of ignoring the intersection coordinate much more costly. We do this by instead considering the multi-party set disjointness problem, so that now have t = O(Vlog d) players rather than just 2, each with an input vector A E {0, 13d, so that Z = Σt Si= A() is now random bit vector except for a single entry with L rather than 2. Now, clustering which does not correctly identify the intersection coordinate will pay a cost of roughly 12 = Olog d), which is large enough to overcome the potential savings from good clustering of the random bit coordinates. We also "plant" the target centers á¹ by adding roughly n/ copies of each of our target centers el as part of the input instance (Lemma so that choosing centers á that are significantly different from e² must incur large cost. In particular, we can get the guarantee that on average, ||el a 112 < o(1)
At this point, we can argue that most of the l centers are the centers that expect, i.e., roughly t on one coordinate and 1/2 on the rest of the coordinates. Thus, if we cluster a point Z whose center expect to be á but is clustered some other aه" and furthermore aه is close to our expected center c' then we must incur an additional Ollog d) cost which is too expensive. However, there is still the possibility that for the very small number of clusters è which do not satisfy ||el - è [|3 < o1), these centers could be assigned a very large number of points with very low cost. We also show that this cannot be the case, by arguing that if a large number of points are assigned to very few clusters, then the cost must be large (Lemma C.S) With this lemma hand, we are able to show our main result in Theorem CT by carefully combining the various cost contribution bounds discussed previously.
8

---

4.1.1 Lower bound for outputting nearly optimal centers
We note that an 9 [dk /c) lower bound follows from an earlier lower bound for low rank approximation
due to Woodruff 2014a even for row arrival streams:
Definition 4.3 (Row arrival stream). We say that algorithm outputs an c-approximate solution to the k-means clustering problem in the row arrival streaming model if the input vectors {a²} S IR4 arrive at time.
Theorem 4.1. Suppose that an algorithum outputs centers { 1j=1 S "R that achieves (1 + e)- approximately optimal solution to the k-means clustering problem after one pass through row arrival stream (Definition 4.3 Then, the algorithm must use at least ((dk/e) bits of space.
We briefly justify why the techniques of Woodruff 2014a
imply Theorem 4.1 The result of Woodrutf 2014a constructs distribution over O(k/e) d matrices such that one can recover arbitrary random bit among (dk random bits by appending set of k: "query" rows and then computing (1 -aapproximately optimal low rank approximation to the resulting matrix. Furthermore, it is shown that nearly optimal rank approximation is obtained by approximating all but rows by zero vectors. Such a rank & approximation in fact corresponds to clustering solution, and thus the immediately applies to our k-means clustering setting as well.
proof of Woodruff 2014a
4.2 Lower bounds for center cost query data structures
Next, we study lower bounds against streaming algorithms which have the guarantee of approximating the cost of an arbitrary but fixed of centers. We formalize the guarantee we study Definition 4.4 Definition 4.4 (Center cost query data structure). We say that Q is an e-approximate center cost query data structure for the means clustering problem for the instance {a J==1 for any centers ,..., Rd, outputs one of the following:
Partition: partition C¹ ,,C.....,
C c S [ra] such that
la
et 1 < (1 + cost(ct c....,
Cost: a number c 2 such that cost(c',
c (1 cost(c', ct)
Our first lower bound is an ((n/e²) bit space lower bound for a center cost query data structure which can output a partition for k-means clustering with k = 2. We proceed by standard encoding argument, showing that any such data structure must encode (2nn(²2) many random bits. We provide the full proof in Appendix D.I.
Theorem 4.2. Lete E (0, 1/3) and 2. Suppose that an algorithm maintains an / ap-pproxiim center cost query data structure for k-means clustering that outputs partition (Definition 4.4) over a row arrival stream (Definition 4.3) Then, the algorithm must use at least 2(n//22 bits of space, any constant number of passes.
4.3 Approximation of costs and centers
We show ((n) space memory bounds when we only need to estimate the optimal cost or centers achieving nearly optimal cost, up to constant factor. Our lower bounds in this section are simpler reductions from the set disjointness problem Razborov / 1990
Bar- Yossef et al. 2004). Proofs are
provided in Appendix D.2 and D.3
Theorem 4.3 (Lower Bound for Estimating k-Means Clustering Cost). Let k = and let X' be the set of matrices X gaxk with standard basis vectors as rows. Let Any randomized algorithm which outputs a number e 2 0 satisfying
min
|
AAI 2c
(2)
XEX
in constant number of passes over turnstile stream requires M(1) bits of space.

---

Theorem 4,4 (Lower Bound for Computing Approximate Centers). Let k = 3 and let X be the set of matrices X R with standard basis vectors as rows. Let d 1. Any randomized algorithm which outpus centers D E lxxd satisfying
min XEX
XD
A
<2
min XEX,DERUXA
XD
A
in a constant number passes over a tursstile stream requires Q(n) bits of space.
4.4 New upper bounds random order streams
In this section, we show some new upper bounds showing that presented lower bounds. In particular, in random order row arrival streams with bounded sensitivity, show that the first segment of the stream is sufficient to obtain approximately optimal centers, and these can in turn be used to nearly optimally cluster the rest of the stream. We give the full proof of this result in Appendix D.4
go beyond the previously
Theorem 4.5. Suppose that the rows of A E Igx arrive in random order row arrival stream. Furthermore, suppose that the sensitivities of each row a' are bounded by a, that is,
min I|a' d11
sup
a
Ex=1 minj a|e
e
Then, there is an algorithm which, with constant probability, outputs a (1 + c)-nearly optimal clustering with partitions and centers using
Óonkddee e + dk/fe E + n.).
bits of space. In particular, if S et /kd, then this algorithm uses just Ö(n dk/e) bits of space.
5 Open directions
We conclude with several questions left open by our work.
1. In our PTAS for sparse dictionary learning of Theorem 2.2 can the bit complexity assump- tion be removed?
2. In the turnstile streaming setting, our main question settling the space complexity of k-means clustering with assignments. Currently, the upper bound is Ó(n/c²) (c2 bits whereas our lower bound in Theorem C.I is ((n/e) bits. Can this factor gap be closed by improving the upper bound the lower bound?
3. In random order streaming model, gave k-means clustering upper bound using bounded sensitivity assumption in Theorem 4.5 Can this assumption be removed? What upper bounds and lower bound are possible in this model?
Acknowledgments and Disclosure of Funding
We thank the anonymous reviewers for useful feedback on improving the presentation of this work. Petros Drineas and Gregory Dexter were partially supported by NSF AF 1814041, NSF FRG 1760353, and DOE-SC0022085. David P. Woodruff and Taisuke Yasuda were supported by Simons Investigator Award.
References
Olivier Bachem, Mario Lucic, and Silvio Lattanzi. One-shot coresets: The case of k-clustering, In
International conference on artificial intelligence and statistics, pages 784-792. PMLR, 2018,
Ziv Bar-Yoe Yossef, T. S. Jayram, Ravi Kumar, and D. Sivakumar. An information statisties approach to data stream and communication complexity. J. Comput. Syst. Sei,, 68(4):002-33,, 2004. doi: 10. 10.1011/j jcss 2003. 1.006. URL https: :/to:i://ooii org/ 1016/101111111 2003. 2000.11.000...0 11.006
10

---

Luca Becchetti, Mare Bury, Vincent Cohen-Addad, Fabrizio Grandoni, and Chris Schwiegelshohn. Oblivious dimension reduction for k-means: beyond subspaces and the Johnson-lindensiin lemma. In Proceedings of the 51st annual ACM SIGACT symposium on theory of computing, pages 1039-1050, 2019.
Christos Boutsidis, Anastasios Zouzias, and Petros Drineas. Random projections for SkS-means clustering. In John D. Lafferty, Christopher K. Williams, John Shawe-Taylor, Richard S. Zemel, and Aron Culotta, editors, Advances in Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems 2010. Proceedings of meeting held 6-9 December 2010, Vancouver, British Columbia, Canada, pages ran Associates, Inc., 2010. URL https:/pproceeddnng www.e/dddnnnnn.uiiss..o. www.rppp.cc/ppppe//011////////// 7227644488466ee66666644444433443 www.aarrr......ccocoaaooaa...... html
Cur-
Christos Boutsidis, David P Woodruff, and Peilin Zhong. Optimal principal component analysis in distributed and streaming models. In Proceedings of the forty-eigtth annual ACM symposium on Theory of Computing, pages 236-249, 2016.
Vladimir Braverman, Dan Feldman, and Harry Lang. New frameworks for offline and streaming coreset constructions. CoRR, abs/1612.00889, 2016.
Kenneth Clarkson and David Woodruff. Numerical linear algebra in the streaming model. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 205-214, 2009.
Michael B Cohen, Sam Elder, Cameron Musco, Christopher Musco, and Madalina Persu. Dimen- sionality reduction for k-means clustering and low rank approximation, In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 163-172, 2015.
Vincent Cohen-Addad, David Saulpic, and Chris Schwiegelshohn. A coreset framework for clustering. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC '21: 53rd Annual ACM SIGACT Symposium Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 169-182. ACM, 2021.
Vincent Cohen-Addad, Hossein Esfandiari, Vahab S. Mirrokni, and Shyam Narayanan. Improved approximations for euclidean k-means and k-median, via nested quasi-independen sets. In Stefano Leonardi and Anupam Gupta, editors, STOC 22: 54th Annual ACM SIGACT Symposium
Theory of Computing. Rome, Italy, June 20 24, 2022, pages 1628. ACM, 2022a. doi: 10.1 10.114533519935 3. URL htlhhttps::0. //doi. org/ 10. 111511...1111111111 35199933 3520011
Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, and Chris Schwiegelshohn. Towards optimal lower bounds for k-median and k-means coresets. In Stefano Leonardi and Anupam Gupta, editors, STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 24, 2022, pages 1038-1051. ACM, 2022b.
Vincent Cohen-Addad, Kasper Green Larsen, David Saulpie, Chris Schwiegelshohn. and Omar Ali Sheikh-OOmat Improved coresets for euclidean k-means. In NeurlPS, 2022c. URL http://papers. mips. wctpscerepppppeeeeeeee fiapprr_flle/eeeeeeeeepeeeppsesr (tlle//paper/2022/nnaa Confereentoooooootoo html
Abhimanyu Das and David Kempe. Submodular meets spectral: Greedy algorithms for subset selection, sparse approximation and dictionary selection. In Lise Getoor and Tobias Scheffer, editors, Proceedings of the 28th International Conference Machine Learning, ICML 2011, Bellevue, Washington, USA, June 28 July 2, 20/ I, pages 1057-1064. Omnipress, 2011, URL .dff
David L. Donoho and Michael Elad. Optimally sparse representation in general (nonorthogonal)
dictionaries via /' minimization. Proc. Natl. Acad. Sci. USA, 100(5):2197-22000 2003. ISSN 0027- URL Jtt.sttts://doi http:////0....rg00001/////////// wttpppaa.......0.00000 0437847100
8424. doi: 10. 1...1777/paa.043877770000
Dan Feldman and Michael Langberg. A unified framework for approximating and clustering data. In
Lance Fortnow and Salil P. Vadhan, editors, Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA. USA. 6-8 June 2011, pages 569-578. ACM, 2011.
11

---

Dan Feldman, Morteza Monemizadeh, and Christian Sohler. A ptas for k-means clustering based on weak coresets. In Proceedings of the twenty-thin eeid annual symposium on Computational geometry, pages 11 1-18, 2007.
Dan Feldman, Micha Feigin, and Nir Sochen. Learning big (image) data via coresets for dictionaries. Journal of mathematical imaging and vision, 46:276-291 2911 2013.
Manuel Fernandez, David P. Woodruff, and Taisuke Yasuda. Tight kernel query complexity of kernel ridge regression and kernel k-means clustering. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California. USA, volume 97 of Proceedings of Machine Learning Research, pages 0055-7063. PMLR, 2019. URL BRLt:tt///pcceeeee/ v97/yasuda19a.hvm html
mlr. press/
J-J Fuchs. On sparse representations in arbitrary redundant bases. IEEE transactions on Information theory, 5006):1341-11444 2004.
William B. Johnson and Joram Lindenstrauss. Extensions of Lipschitz mappings into Hilbert space. In Conference in modern analysis and probability (New Haven, Conn., 1982), volume 26 of Contemp. Math., pages 189-206. Amer. Math. Soc., Providence, RI, 1984. doi: 10. 10.1000/comm/ 026/737400. URL httpss//:///0 org/ 10. 100.0.090//co/ 0090//comm/026/7774000
Daniel M. Kane, Jelani Nelson, and David P. Woodruff. On the exact space complexity of sketching and streaming small norms. Moses Charikar, editor, Proceedings of the Twenty-Firs Annual ACM-SIAM Symposium Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 1161-1178. SIAM, 2010.
Kasper Green Larsen and Jelani Nelson. The johnson--indenstrauss lemma is optimal for linear dimensionality reduction. In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, 43rd International Colloquium on Automata, Languages, and Programminng ICALP 2016, July 11-15, 2016, Rome, Italy. volume 55 of LIPles, pages 82:1-82:11. für Informatik, 2016.
Schloss Dagstuhl-
Kasper Green Larsen and Jelani Nelson. Optimality of the johnson-lindenstrau lemma. In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA. USA, October 15-17, 2017, pages 633 1336688.7 IEEE Computer Society, 2017.
Simin Liu, Tianrui Liu, Ali Vakilian, Yulin Wan, and David P Woodruff. On learned sketches for randomized numerical linear algebra. 2020.
Stuart P. Lloyd. Least squares quantization in PCM. IEEE Trans. Inf. Theory, 28(2):129-133) 1982. doi: 10. 109//TT.199) 1056489. URL http://////a...0r11111111//////1 1982. 1056489
Meena Mahajan, Prajakta Nimbhorkar, and Kasturi R. Varadarajan. The planar k-means problem is np-hard. Theor. Comput. Sci., 442:13-21, 2012. doi: .0.10.66..es.201000...44 URL https
//doi.org/10. org/10../1100 1016/ tcs. 2010. 05.00...... 034
Konstantin Makarychev, Yury Makarychev, and Ilya Razenshteyn. Performance of johnson- lindenstrauss transform for k-means and k-medians clustering. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 1027-1038, 2019.
B. K. Natarajan. Sparse approximate solutions to linear systems. SIAM J. Comput., 24(2): 227-234, 1995. doi: 10.113779009753792444000
URL https://doi. www.dooooogg/.... 1137/
500975337992204000
Jelani Nelson and Huy L. Nguyên. Lower bounds for oblivious subspace embeddings. In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors, Automata, Languggss, and Programmingg 41st International Colloquium, ICALP 2014. Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I, volume 8572 of Lecture Notes in Computer Science pages 883-894. Springer, 2014.
Bruno Olshausen and David Field. Sparse coding with an overcomplete basis set: A strategy employed by vI? Vision research, 37123):311-3325, 1997.
12

---

Alexander A Razborov. On the distributional complexity of disjointness. In Automata, Languages and Programming: 17th International Colloquium Warwick University, England, July 16 20, 1990 Proceediiggs 17, pages 249-253. Springer, 1990.
Iya P. Razenshteyn, Zhao Song. and David P. Woodruff. Weighted low rank approximations with provable guarantees. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 250-263, ACM, 2016. doi: 10.114552897511888977333 URL
https://doi.oon org/ 10
James Renegar. On the computational complexity and geometry of the first-order theory of the reals. part i: Introduction. preliminaries. the geometry of semi-algebraic sets. the decision problem for the existential theory of the reals. Journal of symbolic computation, 13(3):255-29,, 1992a.
James Renegar. On the computational complexity of approximating solutions for real algebraic formulae. SIAM Journal on Computing, 21(6):1008-1025 1992b.
Zhao Song, David P. Woodruff, and Peilin Zhong. Relative error tensor low rank approximation. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithuss, SODA 2019, San Diego California, USA, January 6-9, 2019, pages 2772- 2789. SIAM, 2019. doi: 10.1137/1 001113771177811111954222222 URL https::/ddoo org/10 1137/1 9781611975482 172
Murad Tukan, Xuan Wu, Samson Zhou, Vladimir Braverman, and Dan Feldman. New coresets for projective clustering and applications. In International Conference on Artificial Intelligence and Statistics, pages 5391-5415. PMLR, 2022.
David Woodruff. Low rank approximation lower bounds row-update streams. In Zoubin Ghahramani, Max Welling, Corinna Cortes, Neil D. Lawrence, and Kilian Q. Weinberger, ed- itors, Advances in Neural Information Processing Systems 27: Annual Conference on Neu- ral Information Processing Systems 2014, December 8-13 2014, Montreal, Quebec, Canada, pages 1781-1789, 2014a. URL https: htttps::/ppoceeedinnng www.roeeedingn.nuuuiiieeeeeeeeee newr www.rips.ccppppprreeeeeeee httpcc/aaaaer/21///aaaa/
1854444450007772222662222228 aba.aeboooeeebbbbbabbbaa........ html
David P. Woodruff. Sketching as tool for numerical linear algebra. Foundations and Trends@ in Theoretical Computer Science, (011-)):1-157, 2014b.
David P. Woodruff and Taisuke Yasuda. New subset selection algorithms for low rank approximation: Offline and online. In Symposium Theory of Computing Conference, STOC'23. ACM, 2023.
13


Reviews:
[{"review_id": "M3vgW3ZNK6", "reviewer": "Reviewer_ZwUH", "summary": "This paper presents results for the k-means and sparse dictionary problems, both of which ask to summarize an $n$ point data set in $d$ dimensions in terms of $k$ points. In the former we map each point to a center, in the latter, we are allowed sparse linear combinations of points. The paper considers two models, the streaming model (various versions of it) and the \"standard\" model where the goal is to comes up with an algrithm that is polynomial in $n. d$,  but $k, \\epsilon$ are treated as constants, and the dependence on these can be arbitrary.  They present both upper and lower bounds. \n\nTheir lower bound results are:\n- An $\\Omega(n/\\epsilon)$ streaming lower bound for $k$ means clustering. This beats the trivial $\\Omega(n)$ lower bound but it falls short of the $O(n/\\epsilon^2)$ upper bound from JL. The proof is by a reduction from set disjointness, as is standard in streaming. The authors argue that their reduction is delicate and uses the structure of the hard instances from BYJKS'04. \n- An $\\Omega(dk/\\epsilon)$ lower bound which follows from earlier work by Woodruff.\n- They give some other lower bounds for restricted models. \n\nThey also give results on PTASES for both problems. The idea behind both is to reduce the dimensionality of the points using various kinds of sketches. The exact sketches needed for these are chosen with some care. In low dimensions, one can afford a brute-force enumeration or similarly costly algorithm (this general idea goes back to the early work on coresets). They also give some results in the turnstile streaming model, but the results seem to have some caveats about the parameters/solution space.\n\n\n\n\n\n\n", "questions": "If you wanted to reader to focus on one result or key idea which you see as the main contribution of your work, what would it be? \n\nI would suggest that the writeup focus on one or two main results, and defer the other results for the expert reader.", "limitations": "NA", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The problems considered are important and well-studied in the literature, the results will be of interest to people working in the general area os sketching/streaming.\n\n- I like the fact that they give unified results for $k$-means and the sparse dictionary problems. \n\n- The results seem to rely on a deep understanding of the prior work in the area, and on using exactly the right tools needed in each setting. ", "weaknesses": "- The paper has too many results, at least some of them rather partial or for rather restricted models. I have a hard time deciding what the main contribution of the paper is. No one result stood out either in terms of the statement, or in terms of new techniques. \n\n- Some of the results seem a touch incremental, they come from applying prior ideas in a new setting. I realize that knowing what tools are applicable is no mean feat, given the vast literature. But I could not discern too much originality. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> The paper has too many results, at least some of them rather partial or for rather restricted models. I have a hard time deciding what the main contribution of the paper is. No one result stood out either in terms of the statement, or in terms of new techniques.\n\n> I would suggest that the writeup focus on one or two main results, and defer the other results for the expert reader.\n\nBecause the main contribution of our work is an exploration of a problem/setting which has not received much attention in the past, we believe that this work would be incomplete without including discussions about some of our more straightforward or partial results. We have attempted to highlight two technical highlights (discussed further in the next response) in Section 1.1. We will try to rewrite this section, as well as subsequent discussions, to focus more on these technical highlights, while still mentioning our other results and their connections to the landscape of results for PTAS and streaming algorithms for sparse dictionary learning and k-means clustering.\n\n> If you wanted the reader to focus on one result or key idea which you see as the main contribution of your work, what would it be?\n\nThe overall message is that we initiate the study of k-means clustering and sparse dictionary learning (with assignment) in the PTAS and turnstile streaming settings, which we show are both amenable to techniques from the sketching literature. We would also like to reiterate that, surprisingly, prior work has not considered the task of outputting assignments for $k$-means or sparse dictionary learning in a stream despite its practical importance, and we hope our work will bring much-needed attention to this important problem. Technically, perhaps the two most interesting results (requiring the most \"technical novelty\") we would like to highlight are the first PTAS for sparse dictionary learning, as well as an $\\Omega(n/\\epsilon)$ lower bound for k-means clustering in turnstile streams. The first result uses a new reduction to coresets for projective clustering, while the latter uses a reduction to multi-party set disjointness (rather than the standard two-party problem), which requires delicate arguments to reason about optimal solutions to random instances of k-means clustering.\n\n> Some of the results seem a touch incremental, they come from applying prior ideas in a new setting. I realize that knowing what tools are applicable is no mean feat, given the vast literature. But I could not discern too much originality.\n\nWhile our techniques indeed rely on several standard results for our main technical results, such as the use of coresets for the sparse dictionary learning PTAS and set disjointness lower bounds for the k-means clustering communication lower bound, we argue that several innovations are still needed to make our proofs go through.\n\nFor our sparse dictionary learning PTAS, the use of coresets to design a PTAS is indeed a well-known idea. However, the standard idea of building coresets for this problem by first computing an approximately optimal solution does not work in our setting, as the computation of an approximate solution is our goal to begin with. Instead, we show a reduction to coresets for projective clustering, which is a new connection to the best of our knowledge, and furthermore use the fact that there exist constructions for such coresets that do not need an approximately optimal solution, which uses a recent work of Tukan et al 2022. Note that older coreset constructions for projective clustering (e.g. https://people.csail.mit.edu/dannyf/stoc11.pdf) do not have this property.\n\nFor our k-means clustering communication lower bound, one of the main challenges we face is to understand the optimal cost of a k-means clustering instance up to a $(1+\\epsilon)$ relative factor, which is highly nontrivial since k-means clustering is an NP-hard problem in general, and we must exploit the structure of the specific instance at hand in order to characterize the cost of instances. This challenge is further complicated by the fact that our instance must be a dense random instance in order to use the set disjointness lower bounds, unlike some other lower bound results in other models shown in earlier work which have simpler instances to reason about that are supported on standard basis vectors (e.g., https://arxiv.org/abs/1905.06394, https://arxiv.org/abs/2202.12793). We introduce new techniques such as boosting the \"signal\" of the clustering instance with only a small decrease in the communication lower bound by using multi-party set disjointness, which we believe is a new interesting application of multi-party lower bounds. Note that with a standard two-party set disjointness argument, a nearly optimal k-means clustering may not necessarily solve the set disjointness problem, since the cost savings from clustering this coordinate correctly is only two, while the cost savings from finding the optimal clustering of the random bits could be much larger.\n\nAdditionally, our turnstile streaming algorithms relies on a delicate argument combining a sketched multiple linear regression guarantee, affine-embedding, and JL-embedding. This combination must be done carefully to balance the space of the sketch with the strength of the guarantee needed, which we do by conceptually breaking the problem into disjoint pieces of 1) reducing the problem using the linear regression guarantee, 2) solving the reduced problem with the affine embedding, and 3) checking if we have solved the overall problem with a JL-embedding guarantee. Achieving this decomposition relies on leveraging a less well-known ``guess-the-sketch'' approach."}, {"review_id": "eRV60Tx6Gy", "reviewer": "Reviewer_rhYv", "summary": "The paper considers the well studied $k$-means clustering problem and the $r$-sparse dictionary learning problem. The paper has multiple contributions:\n\n(1) It presents a new approach for obtaining a PTAS for $k$-means clustering which matches the time complexity of previous algorithms for the problems. This approach generalizes to give the first PTAS for the sparse dictionary problem.\n\n(2) Within turnstile streaming algorithms, they consider the setting where the algorithm has to output both the assignments to the clusters/dictionaries as well as the cluster centers or dictionary elements. Previous work, even in the case of the simpler $k$-means have either focused on one or the other so this is a more challenging setting. Omitting logarithmic factors, the paper provides an $O(nr/\\varepsilon^2+dk/\\varepsilon)$ space algorithm for the $r$-sparse dictionary learning problem with dictionaries of size $k$ and an $O(n/\\varepsilon^2+dk/\\varepsilon)$ space algorithm for the $k$-center problem. They also present an $O(n)$ space bounded algorithm when the points are inserted in a random order. On the lower bound side, they present an $\\Omega(n/\\varepsilon+dk/\\varepsilon)$ space bound for $k$-means clustering as well as an $\\Omega(n/\\varepsilon^2)$ bound for algorithms that can estimate the cost for a fixed set of candidate centers.\n\nTechnically most interesting seems to be the former lower bound for $k$-means clustering which is via a reduction from the multi-party set disjointness problem.", "questions": "l64: Should \"inefficient\" be \"efficient\"?\n\nl104-105: you should probably say \"after applying $G$\" somewhere.\n\nDefinition 2.3. This definition is strange. Saying that the algorithm outputs an $\\varepsilon$-approximation does not have anything to do with the rows arriving one at a time. It seems that it should be a definition of the model and not say anything about the approximation.\n\nl236: Appending $k$ rows of what?\n\nl238: \"but a $k$ rows\". Please check the writing.\n\nl263: What is an indicator matrix?\n\nl320: I am a bit confused why the dimensionality has been reduced to logarithmic in $n$. The new dimension seems to only depend on $k$ and $r$.\n\nl331: Has $b$ been introduced?\n\nLemma 3.1: Please check the statement. Are the order of quantifiers correct? Should the bound on $s$ be moved further back? \n\nl360: I think $S$ is $m\\times n$. Same for l380.\n", "limitations": "None as far as I can tell", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "I found the paper to be quite strong. It is indeed surprising that the setting where both the assignments and the centers/dictionaries must both be output have only received limited attention. I found the ideas for the lower bound via multi-party set disjointness interesting (they are sketched well in the first 9 pages) and I als think it is nice that they design a PTAS for dictionary learning. I went through a few of the proofs in the appendices but far from everything, so I cannot vouch for correctness. However, the paper is well written and the proofs seem clear. Given that both the $k$-center problem and sparse dictionary learning is of interest to a good chunk of the NeurIPS community, I think the paper should be accepted.", "weaknesses": "It seems that some of the algorithms proposed by the paper might be implementable and it would be nice to see some experiments on their performance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> It seems that some of the algorithms proposed by the paper might be implementable and it would be nice to see some experiments on their performance.\n\nWhile we agree that experimental inquiry on these streaming/sketching algorithms would be interesting, we believe they would be best situated in a work dedicated to the topic. Our results are focused on algorithmic techniques that will achieve the best worst-case complexity, which is related to, but not the same as optimizing for practical performance. Rather than directly apply our proposed algorithms, we believe our sketching methods to reduce the problem size could be paired with existing heuristic algorithms to efficiently solve the reduced problems in practice, at the cost of worst-case guarantees.\n\n> l64: Should \"inefficient\" be \"efficient\"?\n\nWe have clarified this as \"where even an inefficient algorithm will be tractable due to the smaller size of the instance\".\n\n> l104-105: you should probably say \"after applying $G$\" somewhere.\n\nDone. \n\n> Definition 2.3. This definition is strange. Saying that the algorithm outputs an $\\epsilon$-approximation does not have anything to do with the rows arriving one at a time. It seems that it should be a definition of the model and not say anything about the approximation.\n\nIndeed, this definition is intended to specify the model in which an input of $n$ vectors arrive one at a time. One could solve a variety of problems in this model, such as $\\epsilon$-approximate $k$ means clustering, exact $k$ means clustering, or any other problem whose inputs are $n$ vectors in $d$ dimensions. We have clarified this in our revision.\n\n> l236: Appending $k$ rows of what?\n\nWe have clarified this as follows: \"The result of Woodruff (2014) constructs a distribution over $O(k/\\epsilon)\\times d$ matrices such that one can recover an arbitrary random bit among $\\tilde\\Omega(dk/\\epsilon)$ random bits by appending a set of $k$ ``query'' rows and then computing a $(1+\\epsilon)$-approximately optimal low rank approximation to the resulting matrix.\"\n\n> l238: \"but a $k$ rows\". Please check the writing.\n\nWe have fixed this to be \"all but $k$ rows\".\n\n> l263: What is an indicator matrix?\n\nWe have clarified this as follows: \"let $\\mathcal X$ be the set of matrices $\\mathbf X\\in\\mathbb R^{n\\times k}$ with standard basis vectors as rows\".\n\n> l320: I am a bit confused why the dimensionality has been reduced to logarithmic in $n$. The new dimension seems to only depend on $k$ and $r$.\n\nWe were not precise in saying the size and dimensionality were at most logarithmic in $n$, as this is all we need for the intuition of the argument to hold. However, you are correct that, more specifically, the dimension is reduced to be independent of $n$ and the size of the input is reduced to be logarithmic in $n$. We will improve the clarity of this sentence by focusing only on the size reduction.\n\n> l331: Has $b$ been introduced?\n\nThank you for pointing this out. We write $b$ to denote the bit complexity of the input matrix $\\mathbf A$, that is, each entry of $\\mathbf A$ can be represented by $b$ bits. This is stated in Theorem D.1 of our initial draft, and we will move this definition to the main text in our revision.\n\n> Lemma 3.1: Please check the statement. Are the order of quantifiers correct? Should the bound on $s$ be moved further back?\n\nThanks for bringing this to our attention. The bound on $s$ does not need to be moved, since the set $\\mathcal{S}$ only depends on $n$, $k$, and $\\epsilon$. However, it should say: ``for every $\\mathbf{A}$ and $\\mathbf{B}$ there exists $\\mathbf{S} \\in \\mathcal{S}$...''. We will fix this.\n\n> I think $S$ is $m\\times n$. Same for l380.\n\nThank you for catching this, we have fixed this in our revision."}, {"review_id": "EFSO8NRvie", "reviewer": "Reviewer_MGS2", "summary": "This theoretical paper discusses algorithms and lower bounds regarding time and space complexity for two interesting machine learning problems:\n\n1) Euclidean k-means clustering\n\n2) Sparse dictionary learning\n\n\nI briefly summarize the results based on the order that they are presented in the main paper (which does not fully agree with the order that is presented in the introduction):\n\n1. Space complexity **lower bounds** for approximate k-means in the **(a)** turnstile streaming, **(b)** row-arrival streaming\n\n2. Upper bound for a special case of k-means, where the so-called sensitivities are bounded, which goes beyond the aforementioned lower bounds.\n\n3. PTAS for dictionary learning and k-means based on random dimension reduction.\n\n4. Space complexity **upper bounds** for the two problems in the turnstile streaming model.\n\nAll the results are supported with detailed proofs. Admittedly I only briefly checked very few of the proofs due to the limited time, but from the general impression of the paper I expect them to be robust.", "questions": "I have the following questions for the authors that could help me understand better the paper and potentially modify the score.\n\n**Questions**:\n\n1) Introduction, page 3: It is mentioned that a Gaussian JL sketch only need $O(ε^{-2}n)$ bits of space, could you explain a bit more? Maybe another JL sketch is required? (e.g. Rademacher,...)\n\n2) Theorems 2.3 and Theorem 2.4 mention \"a constant number of passes...\". Does the model support more than 1 passes over the stream? This is not mentioned in Definition 1.3 of a turnstile stream.\n\n3) Theorem 3.1: why is it needed that rank(A)=Ω(poly(k/ε))? How is it ensured later on? (an assumption of d=poly(k/ε) is made for d, not for rank(A))\n\n4) Theorem 3.2: $b$ is not defined. Also vec(A), which is first used in page 9, is not defined\n\n5) Abstract: I am not sure why the bounded sensitivity assumption is natural. Could you explain a bit more?\n\n6) Line 342: S seems to also depend on ε.\n\n7) Line 26: $r$-sparse is not defined. It might be confusing to someone who is not familiar with the term.\n\n8) I am not sure I understand the derivation of the PTAS (e.g. Section 3.4). The polysolver in the appendix seems to run in time exponential to the size of the input problem. From what I understood, this should not be a problem because we already reduce the matrix problem size with a sketch to something like $O(k log k)$, and if $k$ is fixed then $exp(k)$ is fine for a PTAS. Is this more or less correct? Could you provide a brief description that could help me understand the proofs of that section better?\n\n\n**Typos / Other suggestions**:\n\n1) Theorem 2.1: \"k-maens\"\n\n2) Line 64: Should it be \"efficient\" instead of \"inefficient\"?\n\n3) The title of Section 4 is a bit too generic, it took me a while to understand why it is any different from section 2, which also describes space complexity for turnstile.\n\n**Main recommendation**: I think that the structure of the paper can be significantly improved with not too much effort, and it would substantially improve the overall impression of the paper. I.e., there should be a clear summary of the new (and interesting) results that can guide the reader to locate them easier. I really think the best fit for this (large) paper is to submit a revised full-version to a ML or TCS journal, where the reviewers can take the appropriate amount of time to provide insightful feedback, and the suggestions could be incorporated in a revision. In any case, this is up to the authors.\n", "limitations": "I cannot see any potential negative societal impact.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "The major strengths that I can highlight are the following:\n\n1) The problems that are being studied are related to important machine learning problems that have drawn a lot of attention in the past\n\n2) The results that are presented reveal many interesting insights for these two problems, from an algorithmic perspective, and the algorithms communities can benefit from such a detailed analysis.\n\n3) Many results are presented and heavily supported with theoretical analysis (this is mostly a strength, but the amount of work makes it hard to thoroughly review in the limited time that is available)\n\n4) It is evident that there has been a lot of work preparing the paper and it seems that the majority the main claims are robust.", "weaknesses": "The major weakness of the paper that I can mention, unfortunately, is the way that it is written...!\n\n1) There is no clear-cut summary of the results in the introduction. There are many interesting results and improvements, but it takes significant time to identify them. E.g., the order in which the results are presented in the introduction does not agree with the order that the results are presented in the sections thereafter. The first mention of contributions is PTAS, but this only appears in Section 3. Section 2, which precedes PTAS, is about space complexity lower bounds. I spent a lot of time trying to locate results and connect them with each other, which I could have spent in verifying proofs.\n\n2) There are many results in the 20 pages of additional content seem to be new, non-trivial, and seem to be crucial parts of the paper, e.g. Algorithms 1 and 2, the polysolver, .... They should be part of the main paper, it is not ideal that they remain hidden in the Appendix. \n\n3) There are few things that I think need to be clarified / missing definitions, See \"Questions\".\n\n**Note**: Items 1. and 2. did not affect my score.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> There is no clear-cut summary of the results in the introduction. There are many interesting results and improvements, but it takes significant time to identify them. E.g., the order in which the results are presented in the introduction does not agree with the order that the results are presented in the sections thereafter. The first mention of contributions is PTAS, but this only appears in Section 3. Section 2, which precedes PTAS, is about space complexity lower bounds. I spent a lot of time trying to locate results and connect them with each other, which I could have spent in verifying proofs.\n\nThank you for pointing out that the order of sections makes our work harder to read, and we apologize for the inconveniences caused by this. We have reordered the sections of the main body of our work to follow the flow of the introduction.\n\n> Introduction, page 3: It is mentioned that a Gaussian JL sketch only need $O(\\varepsilon^{-2}n)$ bits of space, could you explain a bit more? Maybe another JL sketch is required? (e.g. Rademacher,...)\n\nYou are correct that exact instances of Gaussian random variables cannot be represented in finite space. However, Gaussian matrices truncated to finite bit complexity will suffice. We will avoid referring to $\\mathbf{G}$ as a Gaussian matrix and instead we can refer the reader (among other places) to Definition 1.2 in [Makarychev et. al., 2020].\n\n> Theorems 2.3 and Theorem 2.4 mention \"a constant number of passes...\". Does the model support more than 1 passes over the stream? This is not mentioned in Definition 1.3 of a turnstile stream.\n\nWhile turnstile streams can indeed be defined for more than one pass over the stream, our algorithms only need one pass, while our lower bounds work against a constant number of passes. We will clarify that our lower bounds work against this broader class of algorithms compared to our upper bounds in our revision.\n\n> Theorem 3.1: why is it needed that rank(A)=Ω(poly(k/ε))? How is it ensured later on? (an assumption of d=poly(k/ε) is made for d, not for rank(A))\n\nGood point. We do not need this assumption since, if $rank(\\mathbf A) < s$, then we can just directly reduce the dimension of the problem using SVD. We will change the theorem to remove this assumption. We do not need to change any later theorems, as we did not use this rank assumption anywhere else.\n\n> Theorem 3.2: $b$ is not defined. Also vec(A), which is first used in page 9, is not defined.\n\nThank you for pointing this out. We write $b$ to denote the bit complexity of the input matrix $\\mathbf A$, that is, each entry of $\\mathbf A$ can be represented by $b$ bits. This is stated in Theorem D.1 of our initial draft, and we will move this definition to the main text in our revision. We have also clarified that vec(A) refers to the $nd$-dimensional vector obtained by flattening $\\mathbf A$.\n\n> Abstract: I am not sure why the bounded sensitivity assumption is natural. Could you explain a bit more?\n\nThe sensitivity quantity captures how sensitive the objective function is with respect to a given point $i\\in[n]$, and is defined as the largest fraction of the objective function captured by the training example $i\\in[n]$, ranging over all centers $c^1, c^2, \\dots c^k\\in\\mathbb R^d$. The bounded sensitivity assumption states that there are no points that can take up a significant fraction of the objective function, and can also be interpreted as a way to formalize a ``well-clustered'' instance. In particular, this is one assumption which makes uniform sampling a good algorithm for sampling a small representative subset of examples. We have given a more in-depth discussion of this assumption in our revision.\n\n> Line 342: S seems to also depend on $\\epsilon$.\n\nThank you for catching this, we have fixed this in our revision.\n\n> Line 26: $r$-sparse is not defined. It might be confusing to someone who is not familiar with the term.\n\nWe have clarified that an $r$-sparse linear combination is a linear combination of at most $r$ vectors.\n\n> I am not sure I understand the derivation of the PTAS (e.g. Section 3.4). The polysolver in the appendix seems to run in time exponential in the size of the input problem. From what I understood, this should not be a problem because we already reduce the matrix problem size with a sketch to something like $O(k\\log k)$, and if is fixed $\\exp(k)$ then is fine for a PTAS. Is this more or less correct? Could you provide a brief description that could help me understand the proofs of that section better?\n\nYes, what you have described is indeed correct. Although the stated time complexity of PolySolver is $2^{O(nr + kd)}$ for input matrix $\\mathbf{A}$, we never call the PolySolver on the full matrix, but instead call it on $\\mathbf{W}\\mathbf{A}$, which has a smaller dimension that is only logarithmic in $n$. To briefly give the intuition behind the proof of our sparse dictionary learning PTAS, we first assume $d = \\operatorname{poly}(k/\\epsilon)$ (this is justified since we give a way to efficiently reduce to this case in Theorem 3.1). We then reduce the size of $\\mathbf{A}$ to be logarithmic in $n$ by applying a projective clustering coreset construction. We then show that using existing work on polynomial system solvers, we can solve this smaller problem in $\\operatorname{poly}(n)$ time. The technical difficulty comes from rigorously interfacing the projective clustering bounds, polynomial system solver complexity, and the specific constraints of the sparse dictionary learning problem, and this is what causes the technical complexity in the proof despite the intuitive simplicity of the approach."}, {"review_id": "tNlAruYwoX", "reviewer": "Reviewer_NUiP", "summary": "The paper studies the sparse dictionary learning and k-means clustering problems, using tools from sketching. Various results are obtained under different settings and assumptions.\n\nThe first part of the paper considers lower bounds in the streaming setting. Here, the main technical result, which is a lower bound for k-means, uses a reduction from the communication complexity of the multiparty set-intersection problem. This is a nice set of results that translate prior ideas to k-means clustering problems. A new upper bound is also established under certain input sensitivity assumptions in the random order model.\n\nThe second part of the paper gives approximation schemes for both problems. The key technical ingredient is the use of dimensionality reduction. Here, the use of dimensionality reduction follows essentially from prior work on projective clustering.\n\nThe final part of the paper considers space complexity in the turnstile model. At the high level, sketching tools are used to discretize the appropriate matrix optimization problem, followed by brute force.", "questions": "Can you provide any bounds on the exponent in the poly(n) term in Theorem 3.2?\n\nWhat's the running time of the algorithm in Theorem 4.3?\n\nCan you comment on possible applicability of your algorithms? Is there a bottleneck in performance?\n\nCan you briefly discuss whether your results on k-means imply anything for k-center or k-median? Your lower bound constructions seem general enough that perhaps other problems can be addressed too.\n", "limitations": "The authors have adequately addressed the limitations of their work.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper studies two fundamental important problems. The work introduces several ideas from sketching in this setting.\n\nThe authors appear to be very well versed in the related literature.\n\nThe paper is well-written and the presentation is quite accessible.\n", "weaknesses": "In the statements of several of the Theorems, the running time is not given (either at all, or not with enough precision). This makes me think that the algorithms are probably not very practical.\n\nThe section on the turnstile model is labeled as \"space complexity\". I find this confusing. Your algorithm has some space complexity and some time complexity, and it would be best to state both clearly.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">In the statements of several of the Theorems, the running time is not given (either at all, or not with enough precision). This makes me think that the algorithms are probably not very practical.\n\nWe will add more precise time complexity results to our upper bounds, so that our work is easier to compare to in future work. Regarding the practicality of our methods, please see our later response regarding the \"bottleneck\" of our methods.\n\n> The section on the turnstile model is labeled as \"space complexity\". I find this confusing. Your algorithm has some space complexity and some time complexity, and it would be best to state both clearly.\n\nWe will add time complexity bounds to the statements of Theorem 4.1 and 4.2 as well as rename the section to \"Turnstile Streaming Algorithms\".\n\n> Can you provide any bounds on the exponent in the $\\operatorname{poly}(n)$ term in Theorem 3.2?\n\nIgnoring lower order terms, the complexity of Theorem 3.2 will be $\\exp((8k^{3r}b \\log d)^{O(k^{r+1})}\\log n)$.\n\n> What's the running time of the algorithm in Theorem 4.3?\n\nThe dominant time complexity term for Algorithm 4.3 would be $n^{\\tilde{O}(k^2/\\epsilon)}$, since the cost with respect to $d$ is amortized over the turnstile updates.\n\n> Can you comment on possible applicability of your algorithms? Is there a bottleneck in performance?\n\nThe main bottleneck generally comes from the fact that, once we reduce the dimension of a problem, solving the reduced problem has a high computational complexity in terms of parameters such as $k$ and $r$. This likely cannot be avoided in the worst case, since both $k$-means and sparse dictionary learning are NP-Hard. However, there has been extensive work studying heuristic algorithms and algorithms leveraging additional statistical/structural assumptions for these problems. Our dimensionality reduction approaches could potentially be paired with these methods to achieve more practically efficient algorithms.\n\n> Can you briefly discuss whether your results on k-means imply anything for k-center or k-median? Your lower bound constructions seem general enough that perhaps other problems can be addressed too.\n\nThank you for pointing this out! Indeed, we expect our lower bound argument to hold for Euclidean $k$-median clustering, and more generally, $(k,p)$-clustering for $p \\leq 2$. For $p > 2$ (including $k$-center clustering), our lower bounds may also generalize to this setting, but we may also expect stronger lower bounds since $\\ell_p$ norm estimation in $d$ dimensions requires $\\operatorname{poly}(d)$ bits of space for $p>2$. In general, generalizing our results from Euclidean metrics to $\\ell_p$ metrics is an interesting question."}]

Author rebuttal:

Meta-review: The paper has general support from all reviewers.

On the plus side, the paper considers two important problems of k-means and sparse dictionary learning in a natural setting where the assignments of the input points are required in addition to the centers/dictionary. The paper has a lot of results, both upper and lower bounds drawing from a lot of techniques in sketching.

On the minus side, the reviewers find the techniques somewhat standard to the area and the work seems to be about finding the right combinations of existing techniques. That said, the literature in this area is vast and it is a nontrivial task to identify the right techniques. Several reviewers find the paper lacking a major result that stands out in terms of technique or statement but rather having a large number of good results. The reviewers recognized that the main contribution of the paper was theoretical and focused on the strength of the theory. In addition and to a lesser extent, the practicality of the algorithms is also questioned by several reviewers due to the lack of experiments and the very high (exponential in k with terms such as k^(k^r) or n^(k^2)) theoretical runtime.

The authors are strongly advised to improve the writing of the paper by highlighting the key contributions and adding the explanations from the discussion with the reviewers.
Decision: Accept (poster)