Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: This work considers the effect of sparsification, quantization and non-linear transormations on the spectrum of a random matrix with respect to performance in downstream applications like clustering. Eigen decomposition of large matrices is computationally very expensive and therefore methods like sparsification is used in order to reduce the computational complexity, while adding some amount of error. Therefore, theoretical bounds which quantize the amount of deviation because of such processing steps is essential to understand how much/little degraded the performance of machine learning applications are because of this step. This work considers the important case of spectral clustering with a 2 class mixture of subexponential models using 
the Grammian matrix X^{T}X under entry wise non-linear transformations (specifically thresholding, binarization and quantization).

The theoretical analysis derives asymptotic eigenvalue distribution f(X^{T}X/sqrt{p})/sqrt{p} for some entry wise non linear function f. The analysis heavily relies on entry wise central limit theorems for each entry and expansion of 
f using Gaussian orthogonal polynomials. It is shown that the limiting distribution depends only on the low order coefficients in the Gaussian polynomial expansion. Asymptotic accuracy rates for spectral clustering follows via Cauchy integral formula applied to the resolvent matrix, which is a standard technique in random matrix theory.
 
Proposition 1 is the most relevant contribution of the paper to machine learning - a parameter gamma is recognized based on the polynomial expansion of f which is a threshold for signal to noise ratio rho. if rho < gamma, asymptotically, 
spectral clustering doesn't work and when rho > gamma, precise asymptotic accuracy is derived for spectral clustering, depending only on rho and f. The analysis is largely independent on the specific mixture distribution considered because of the 
use of central limit theorems. 


The results are very nice and gives a firm theoretical understanding of a well studied practical problem in machine learning. The results are precise and look complete. I would like to see further research with non-asymptotic rates for misclassification. 
It could be possible to apply quantitative Berry-Esseen type local limit theorems to derive such results. This clearly deserves to be published in a venue such as ICLR
Some minor comments:

1.  it is called data dependent but notation f(M/sqrt{p})sqrt{p} doesn't suggest data-dependent quantization. How is this data dependent? the setting of parameter s in the definition of f? 
2. line 10, page 2 - corroborate instead of collabora
review_title: The paper derives precise asymptotic results for pre-processing steps used in machine learning problems to boost computational efficiency, resulting in a complete asymptotic characterization of tradeoffs.

final_score: rating: 6: Marginally above acceptance threshold
review_content: This is a nice paper that shows that one can perturb a kernel matrix (or pass it through a non-linear transformation) without necessarily modifying the underlying eigenspectrum significantly, and as such, without hurting the performance of spectral clustering applied on the matrix. The most important application I can immediately see is sparsifying the kernel matrix so it can be computationally used efficiently. Or similarly, apply quantization and binarization, as the authors mention.

First, a high level point: I wonder what the implication is of a non-linear transformation applied on X*X' instead of the design matrix itself X -- which is what seems more useful to me. You would want to apply the non-linear transformation on the actual vectors, not on the dot products between all of their pairs, isn't it? Though, I do see the value in "zeroing out", for example, or sparsifying the kernel matrix X*X', as working with kernel matrices can be problematic because of their size and density. I suppose, also, maybe a transformation on X can be translated into a transformation on X*X'? Not always.

I also wonder if the model presented here is not too simple to make the claim that spectral clustering is stable under perturbation to the kernel matrix. My understanding is that the author's model is rather toyish, consisting of only two clusters -- is that correct? How do your results generalize to more than two clusters? Is it a trivial step to make, or does it require significantly more thought?

Regarding Assumption 1, it is quite difficult to unpack it. Can you at least confidently state that Eq.3-5 satisfy this assumption? Can you give a few examples of other f's that satisfy that, or at least give an intuition what this assumption means? What properties of f is it related to? How is p coming into play?

Theorem 1 again needs some unpacking and intuition. Why is it important? The text that comes after the theorem makes it even more confusing -- what is the implication on the K matrix for that? For example, how would it be reduced for f which is just a sparsification, I would be curious? Is there a way to instantiate all the quantities in Theorem 1 as a corollary to get a better picture of how sparsification affects K and how it differs from previous results in the literature? Figure 1 helps do that, but it is far from being complete.

Proposition 1 is a bit easier to unpack (though "with the convention... etc" maybe add a footnote that there is some degree of freedom there, otherwise it is unclear). I am slightly concerned that under all these complex expressions there might be results that are not very strong, but it is hard to track, because tracing each quantity back to a concrete value would take a lot of time. Again, I strongly urge the authors to instantiate some of their results to simple cases, where many of the variables and traces of variables disappear, so that the strength of the results can be thought about.

I would expect for example a corollary in a simple form that roughly states: "Say x is drawn from the clustering model as above in Eq. 1. Say we use f as in Eq. 3 (and hence Assumption 1 is instantiated with the orthogonal polynomial framework). Then: (a) the eigenvector/eigenvalue of K stays such and such within the one of X; (b) spectral clustering will have this much or such increase in the error rate."

If you could do it for f's in Eq. 4-5 that's even better.

Minor comments:

1. "One approach to overcoming this limitation is simple subsampling: dividing X into subsamples of size εn, for some ε ∈ (0, 1), on which one performs parallel computation, and then recombining."

What type of computation?

2. In Eq. 1 -- are you saying you have a mixture model with two components C1 and C2? Might be a good idea to state that explicitly. Is there a specific prior probability to belong to C_1 or C_2?

3. Explain what are "isolated eigenvalues" or cite.


Full disclosure: given the time constraints and me being an emergency reviewer, I didn't look carefully at the supplementary materials.
review_title: Paper seems interesting and tackles a very important topic, a bit hard to unpack.

final_score: rating: 7: Good paper, accept
review_content: This paper studies algorithms for dropping entries from a dense Gram matrix constructed from a lower rank, p-by-n X matrix, with n much larger than p. It analyzes the preservation of eigenstructures, as well as the overall performance of clustering algorithms when the columns of X are random vectors, and the sparsity of the matrix is reduced by one of three methods: keeping only large magnitude entries, 0/1 based on whether magnitude exceeds a threshold, or a more continuous version between the 0 and 1 (in the small magnitude range). Some experimental comparisons with other sparsification methods such as uniform sampling are made.

Strengths:
+ The problem studied is an important one for analyzing large datasets.
+ The study of different  'filter' functions on the sampled entries is quite novel to the matrix sampling literature
+ The criteria used for measuring quality of output is holistic, and in my opinion significant step forward from simply measuring errors in the matrix sense.

Weaknesses:
- The randomness assumption of all columns of X being independent unit vectors is somewhat generous.
- Computing eigenvectors of a p-by-n X matrix can be done by solving p-by-p linear systems involving the matrix XX^T instead, and for many reasonable notions of errors, this matrix can be sketched. However, I do feel the analysis done is more broadly applicable.

Overall, I feel this paper takes an interesting step toward problem specific, and algorithmic specific sparsification. The set up is natural, and the mathematical depth is significant. Overall, the only main drawback I can think of is I had trouble extracting a higher level message from the formal statements, but I believe the results are more than sufficient for a paper.


review_title: analysis of an important case of a natural model

final_score: rating: 7: Good paper, accept
review_content: The paper rigorously studies the effect of sparsification and quantisation on the eigen-spectrum of kernel matrices, and subsequently on downstream tasks, such as spectral clustering. It is shown both theoretically and numerically that significant reduction in computation can be introducing entry wise non-linear operations (sparsification etc) on the kernel matrix with significant reduction in performance. 

The paper is of high technical quality, but the presentation is too technical, making the paper difficult to follow (particularly Section 3 and parts of Section 4). Moreover, there is hardly any discussion on the limitations of the analysis. The study makes few restrictions: the data is assumed to be sampled from two high-dimensional sub-gaussian mixtures and kernel function is assumed to a function of the dot product of the data. The latter assumption is somewhat restrictive since dot-product type kernels are not the popular choice, at least, not for spectral clustering. 
The authors may be interested in a work on high-dimensional clustering with dot-product kernels, which is based on concentration inequalities and hence can provide finite sample analysis [Vankadara and Ghoshdastidar, AISTATS 2020]. The work, however, does not focus on sparsification etc.
review_title: Good work, but presentation too technical 

Meta-review: The paper presents a nice analysis of the spectrum of a matrix that is obtained by applying non-linear functions to a random matrix. The paper is mostly well-written, the result is novel and interesting, and has clear implications for ML problems like spectral clustering. 
So I would enthusiastically recommend the paper for acceptance at ICLR. 
It would be important for authors to take into account reviewer comments. In particular, instantiating the theorems for simple ML-centric examples would be very useful.    
Decision: Accept (Spotlight)