Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile Streaming

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. The 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. The 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. The 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.

Strengths

The paper studies two fundamental important problems. The work introduces several ideas from sketching in this setting. The authors appear to be very well versed in the related literature. The paper is well-written and the presentation is quite accessible.

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

Questions

Can you provide any bounds on the exponent in the poly(n) term in Theorem 3.2? What's the running time of the algorithm in Theorem 4.3? Can you comment on possible applicability of your algorithms? Is there a bottleneck in performance? 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.

Rating

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

Confidence

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

Soundness

4 excellent

Presentation

3 good

Contribution

3 good

Limitations

The authors have adequately addressed the limitations of their work.

Summary

This theoretical paper discusses algorithms and lower bounds regarding time and space complexity for two interesting machine learning problems: 1) Euclidean k-means clustering 2) Sparse dictionary learning I 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): 1. Space complexity **lower bounds** for approximate k-means in the **(a)** turnstile streaming, **(b)** row-arrival streaming 2. Upper bound for a special case of k-means, where the so-called sensitivities are bounded, which goes beyond the aforementioned lower bounds. 3. PTAS for dictionary learning and k-means based on random dimension reduction. 4. Space complexity **upper bounds** for the two problems in the turnstile streaming model. All 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.

Strengths

The major strengths that I can highlight are the following: 1) The problems that are being studied are related to important machine learning problems that have drawn a lot of attention in the past 2) 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. 3) 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) 4) 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...! 1) 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. 2) 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. 3) There are few things that I think need to be clarified / missing definitions, See "Questions". **Note**: Items 1. and 2. did not affect my score.

Questions

I have the following questions for the authors that could help me understand better the paper and potentially modify the score. **Questions**: 1) 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,...) 2) 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. 3) 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)) 4) Theorem 3.2: $b$ is not defined. Also vec(A), which is first used in page 9, is not defined 5) Abstract: I am not sure why the bounded sensitivity assumption is natural. Could you explain a bit more? 6) Line 342: S seems to also depend on ε. 7) Line 26: $r$-sparse is not defined. It might be confusing to someone who is not familiar with the term. 8) 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? **Typos / Other suggestions**: 1) Theorem 2.1: "k-maens" 2) Line 64: Should it be "efficient" instead of "inefficient"? 3) 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. **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.

Rating

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

Confidence

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

Soundness

3 good

Presentation

2 fair

Contribution

4 excellent

Limitations

I cannot see any potential negative societal impact.

Summary

The paper considers the well studied $k$-means clustering problem and the $r$-sparse dictionary learning problem. The paper has multiple contributions: (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. (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. Technically 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.

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.

Questions

l64: Should "inefficient" be "efficient"? l104-105: you should probably say "after applying $G$" somewhere. Definition 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. l236: Appending $k$ rows of what? l238: "but a $k$ rows". Please check the writing. l263: What is an indicator matrix? 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$. l331: Has $b$ been introduced? Lemma 3.1: Please check the statement. Are the order of quantifiers correct? Should the bound on $s$ be moved further back? l360: I think $S$ is $m\times n$. Same for l380.

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

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

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

None as far as I can tell

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. Their lower bound results are: - 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. - An $\Omega(dk/\epsilon)$ lower bound which follows from earlier work by Woodruff. - They give some other lower bounds for restricted models. They 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.

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. - I like the fact that they give unified results for $k$-means and the sparse dictionary problems. - 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. - 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.

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? I would suggest that the writeup focus on one or two main results, and defer the other results for the expert reader.

Rating

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

Confidence

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

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

NA