Sparse Quantized Spectral Clustering
Authors: Zhenyu Liao
Romain Couillet
Michael W. Mahoney
Venue: ICLR 2021 Spotlight (2021)
Keywords: Eigenspectrum
high-dimensional statistic
random matrix theory
spectral clustering

Abstract: Given a large data matrix, sparsifying, quantizing, and/or performing other entry-wise nonlinear operations can have numerous benefits, ranging from speeding up iterative algorithms for core numerical linear algebra problems to providing nonlinear filters to design state-of-the-art neural network models. Here, we exploit tools from random matrix theory to make precise statements about how the eigenspectrum of a matrix changes under such nonlinear transformations. In particular, we show that very little change occurs in the informative eigenstructure, even under drastic sparsification/quantization, and consequently that very little downstream performance loss occurs when working with very aggressively sparsified or quantized spectral clustering problems.
We illustrate how these results depend on the nonlinearity, we characterize a phase transition beyond which spectral clustering becomes possible, and we show when such nonlinear transformations can introduce spurious non-informative eigenvectors.

Published as a conference paper at ICLR 2021
SPARSE QUANTIZED SPECTRAL CLUSTERING
Zhenyu Liao
Romain Couillet
ICSI and Department of Statistics University of California, Berkeley, USA zhenyu. 1 tiao@berkeeey.co edu
G-STATS Data Science Chair, GIPSA-lab
University Grenobles-Alpes, France
roma couu @ psa- ab, wab..genoblle-inne... fr
Michael W. Mahoney
ICSI and Department of Statistics University of California, Berkeley, USA mmahoney@stat. wew.eter.eeeeeeeeeee
ABSTRACT
Given large data matrix, sparsifying, quantizing, and/or performing other entry- wise nonlinear operations can have numerous benefits, ranging from speeding up iterative algorithms for core numerical linear algebra problems providing non- linear filters to design state-of-the-art neural network models. Here, we exploit tools from random matrix theory to make precise statements about how the eigen- spectrum of a matrix changes under such nonlinear transformations. In particular, we show that very little change occurs the informative eigenstructure, even under drastic sparsification/uaniizza stream performance loss occurs when working with very aggressively sparsified quantized spectral clustering problems. We illustrate how these results depend on the nonlinearity, we characterize a phase transition beyond which spectral clus- tering becomes possible, and show when such nonlinear transformations introduce spurious non an-informative eigenvectors.
and consequently that very little down-
INTRODUCTION
Sparsifying, quantizing, and/or performing other entry-wise nonlinear operations on large matrices can have many benefits. Historically, this has been used to develop iterative algorithms for core numerical linear algebra problems (Achlioptas & McSherry) 2007 Drineas Zouzias, 2011 I). More recently, this has been used to design better neural network models (Srivastava et al. 2014: Dong jet al. 2019 Shen et al. 2020). A concrete example, amenable to theoretical analysis and ubiquitous practice, provided by spectral clustering, which can be solved by retrieving the dominant eigen- vectors of X XX for X [x],.... ... E Rpx* a large data matrix (Von Luxburg 2007). When the amount of data is large, the Gram "kernel" matrix X X can be enormous, impractical even form and leading to computationally unaffordable algorithms. For instance, Lanczos iteration that operates through repeated matrix-vects multiplication suffers from an On²²) complexity (Golub & Loan 2013) and quickly becomes burdensome.
One approach overcoming this limitation is simple subsampling: dividing X into subsamples of size En, for some E (0, 1), on which one performs parallel computation, and then recombining. This leads to computational gain, but the cost of degraded performance, since each data point x; looses the cumulative effect of comparing to the whole dataset. An alternative cost-reduction proce- dure consists in uniformly randomly "zeroing-out entries from the whole matrix X X, resulting in sparse matrix with only fraction of nonzero entries. For spectral clustering, by focusing the eigenspectrum of the "zeroed-out" matrix, Zarrouk et al. (2020) showed that the same computational gain can be achieved the cost of much less degraded performance: for n/ rather large, almost no degradation observed down to very small values (e.g., E N 2% for n/p pp Z 100).
Previous efforts showed that it often advantageous perform sparsification/quamiii uniform manner, rather than uniformly (Achlioptas & McSherry [007] Drineas & Zouzias 201T). The focus there, however, is often (non-asymptotic bounds of) the approximation error between
in non-

---

Published as a conference paper at ICLR 2021
the original and the sparsified//uantizee matrices. This, however, does provide direct access to the actual performance for spectral clustering or other downstream tasks of interest, e.g., since the
top eigenvectors are known to exhibit phase transition phenomenon (Baik al. 2005 Saade al.) 2014). That is, they can behave very differently from those of the original matrix, even the matrix after treatment is close in operator Frobenius norm the original matrix.
Here, we focus on a precise characterization of the eigenstructure of X after entry-wise non- linear transformation such sparsification or quantization, in the large n, n,p regime, by performing simultaneously non-uniform sparsification and/or quantization (down to binarization). We consider a simple mixture data model with MV+u, Ip) and let = //X"X/VV /PP//P, vp, where f is an entry-wise threshollinggquaniizaiio operator (thereby crooing-ou/quaaniiing entries of XTX); and we prove that this leads to significantly improved performances, with the same computational cost, in spectral clustering as uniform sparsification, but for much reduced cost in storage induced by quantization. The only (non- nog-negllg additional cost arises from the extra need for evaluating each entry of X Our main technical contribution (of independent interest, e.g., for those inter- ested in entry-wise nonlinear transformations of feature matrices) consists in using random matrix theory (RMT) to derive the large n. p asymptotics of the eigenspectrum of K = /(X"X// /D)/ /PP for a wide range of functions f' and then comparing to mreviossly-sstablishee results for uniform subsampling and sparsification in (Zarrouk et al. 2020). Experiments on real-world data further corroborate our findings.
Our main contributions are the following.
1. We derive the limiting eigenvalue distribution of K as n, oo (Theorem D.. and we identify:
(a) the existence of non-informative and isolated eigenvectors of K for some f (Corollary D
(b) in the absence of such eigenvectors, a phase transition in the dominant eigenvalue-eigenvee
(Å, v) pair (Corollary 2 if the signal-to-noise ratio (SNR) ||a]|² of the data exceeds a certain
threshold % then Å becomes isolated from the main bulk (Von Luxburg 2007: Joseph & Yu, 2016 Baik et al. 2005) and contains data class-structure information exploitable for cluster- ing; if not, then v contains only noise and is asymptotically orthogonal to the class-label vector.
2. Letting f be a sparsification, quantization, or binarization operator, we show:
(a) selective non-uniform sparsification operator, such that X can be drastically sparsified with very little degradation in clustering performance (Proposition [ and Section 4.2) which
significantly outperforms the random uniform sparsification scheme (Zarrouk et al. 2020);
(b) for a given matrix storage budget (i.e., fixed number of bits store K), an optimal design of the quantization/ nuunizzation/inarizatioo operators (Proposition] and Section 4.3) the performances of which are compared against the original X X and its sparsified but not quantized version.
For spectral clustering, the surprisingly small performance drop, accompanied by huge reduction in computational cost, contributes to improved algorithms for large-scale problems. More generally, our proposed analysis sheds light on the effect of entry-wise nonlinear transformations on the eigen- spectra of data/feature matrices. Thus, looking forward (and perhaps more importantly, given the use of nonlinear transformations in designing modern neural network models as well as the recent interest in applying RMT to neural network analyses (Dobriban et al. 2018 Li & Nguyen| 2018 Seddik et al. 2018, Jacot et al., 2019 Liu & Dobriban (2019)), we expect that our analysis opens the door to improved analysis computationally efficient methods for large dimensional machine learning and neural network models more generally.
2 SYSTEM MODEL AND PRELIMINARIES
Basic setup. Let ,I,...,X.. Xn, E Rp be independently drawn (not necessarily uniformly) from a two-class mixture of C1 and C2 with
C = - 2; C2 x; = +u
(1)
with z, 128 having i.i.d. zero-mean, unit-variance k-kuutosis, sub-exponential entries, μ E RP
such that |a||2 + P 2 0 as p b 0o, and v {+1}" with [v], = -1 for x; E C1 and +1 for
x; E C2 The data matrix X Ky..... x,1 E Rox" can be compactly written as X Z + pvd
'The norm ||- || the Fuclidean norm for vectors and the operator for matrices.
2

---

Published as a conference paper at ICLR 2021
for Z [2,...., ,2,...,,,,...... Zn] so that ||v]| = vvn and both Z, μuV have operator norm of order O(yP) in the p regime. In this setting, the Gram (or linear kernel) matrix X X achieves optimal clustering performance on the mixture model ( see Remark [amnark[bblor below. However, it consists of a dense x n matrix, which becomes quickly expensive store or to perform computation on, as n increases.
Thus, we consider instead the following entry-wise nonlinear transformation of X x
K
VP)
for f:B. R + IR satisfying some regularity conditions (see Assumption I beloow, where ووæ equals 1 for i * j and equals 0 otherwise. The diagonal elements f(x] x, vp) (i) bring no additional information for clustering and (ii) do not scale properly for large (x. x:/ vP O(vp) instead of O(1)). Thus, following (El Karoui 2010 Cheng & Singer, 2013). they are discarded.
Most of our technical results hold for rather generic functions f. e.g., those of interest beyond sparse quantized spectral clustering. but we are particularly interested in with nontrivial numerical properties (c.g.. promoting quantization and sparsity):
Sparsification:
ft( 1112
(3)
Quantization:
f2(t) 2
(Lt- 2M 22-2222//2 /V2ss + 1/2) Insv2. sign(t) 1//>
(4)
Binarization:
fa(t) = sign(t) (t) 1113
(5)
Here, 2 0 is some truncation threshold, and M 2 2 is a number of information bits The visual representations of these ss are given in Figure F (left). For f3, taking - O leads to the sign function sign((). In terms of storage, the quantization J2 consumes 2 + 1 bits per nonzero entry, while the binarization fa takes values in {+1,0) 0} and thus consumes 1 bit per nonzero entry.
Random matrix theory. To provide precise description of the eigenspectrum of K for the non- linear f of interest, to be used in the context of spectral clustering, we will provide a large dimen- sional characterization for the resolvent of K, defined for E C R as
(6) This matrix, which plays central role in RMT analysis (Bai & Silverstein 2010), will be used in
Q()) = (K - =I,,
two primary ways. First, the normalized trace tr Q(=) is the so-called Stieliess transform of the eigenvalue distribution of K, from which the eigenvalue distribution can be recovered, and be further used to characterize the phase transition beyond which spectral clustering becomes theoretically possible (Corollary 2 Second, for (), v), an "isolated" eigenvalue-eigenveed
pair of K, and a e R", a deterministic vector, by Cauchy's 's integral formula, the "angle" between v and a is given by [Taal" 2mi fr(3) a Q(z)a where (²)) is a positively oriented contour surrounding only. Letting a = v, this will be exploited to characterize the spectral clustering error rate (Proposition) I
From technical perspective, unlike linear random matrix models, K (and thus Q(z)) involves non- linear dependence between its entries. To break this difficulty, following the ideas of (Cheng & Singer 2013 we exploit the fact that, by the central limit theorem, z! 23/ vp NO, 1) distri- bution as p > Do. As such, up to Jvv which is treated separately with a perturbation argument, the entries of K asymptotically behave like family of dependent standard Gaussian variables to which f is applicd. Expanding f in a series of orthogonal polynomials with respect to the Gaus- sian measure allows for "unwrapping" this dependence. A few words on the theory of orthogonal polynomials (Andrews et al. 1999) are thus convenient to pursue our analysis.
Orthogonal polynomial framework. For a probability measure μe, let (P((z), 2 0} be the orthonormal polynomials with respect to (f.g) = fgdu obtained by the Schn-Schmidtt procedure on the monomials (1, xr. xx? .............. such that Po(x) = 1, Pt is of degree and (Pi, , Pt.) = o1, -1- By the Riesz-Fischer theorem (Rudin) 1964] Theorem I 11.43), for any function f E L (w), the set of
square-integrable functions with respect to (:,)). one can formally expand f as
f(x) Σ (1), a = 1
00
f(x))(()))((d))
1=
? Also, here, L.] denotes the floor function, while erf(x) 3/ So - and erfe(x) = 1 1-er((x) denotes the error function and complementary error function, respectively.
3

---

Published as a conference paper at ICLR 2021
f1
f
d1
f2
fi
erfo(s) + 2se 5" 1/TT
erfc(s) + +2E 1VT
f2
V² .21- MM (1 c-
1 -ー1 or cr((s)
1
k==1_ 22 2p. a2r-2)
12,2
22- & kerl(ks.
k=1
22
-v2s
22
28
fs
e 12/T
crfe ()
Figure| I: Visual representations of different functions f defined in 33 (left) and their corre-
sponding parameters ai and (right) (a2 = 0 for each of these fss defined Assumption [
where "f ~ Ei Pt" indicates that |If Et = Pill - 0 as L + co with = (f.
To investigate the asymptotic behavior of K, n + co, we make the following assumption on f. Assumption
inntare-ttegrable in Gauss space). Let = 2, 23/ /pand Pt,(()) be the orthonor- mal polynomials with respect to the measure Up of E.. For f E L2 (p()). f(x) ~ L. with at in ( such that (i) 5
converges T,² (1p))) to f(x) uniformly over large p. and (ii) as p - 0C, Di= ot.p + and, for 0.1 01.p + at converges with ag O.
= (t.pPt.p())ee
Since E, + (O, 1) in distribution, the parameters ag, a1, ag and v are simply moments of the standard Gaussian measure involving f. More precisely, for & ~ NN 1).
a1 = [E)) V2ag = ElE2 ao. == (() agt 2 a + az. (8) a0 = [E](
Imposing the condition ag = simply discards the non-informative rank-one matrix ,, /P from K. The three parameters (0)) of crucial significance in determining the spectral below).The sparse fi, quantized f2, and binary fa of our primary interest all satisfy Assumption I (counterexample exists though, for example f(xx) = c(() for polynomial P(z) of degree greater than two), with their corresponding dg 0 (as we shall see in Corollary [ellow, this is important for the spectral clustering use case) and d1 V given in Figure (right). With these preliminary comments, are in position to present our main technical results.
behavior of K (see Theorem [
3 MAIN TECHNICAL RESULTS
Our main technical result, from which our performance-complente trade-off analysis will follow, provides an asymptotic deterministic equivalent Q(=) for the random resolvent Q, defined in (6). (A deterministic equivalent is a deterministic matrix (z) such that, for any deterministic sequence of matrices A, E _g*x and vectors an, b, E Rn' of bounded (spectral and Euclidean) norms, tr A.. (Q.(()) - Q()) + 0 and a (Q()) - Qb + 0 almost surely n. P OC. We denote this relation Q(2) + Q(2.) This is given in the following theorem. The proof is in Appendix A.II Theorem (Deterministic equivalent). Let n. p + oo with p/n - c E (0, oo), let Q(2) be defined in (6. and let 3/|] denote the imaginary part of a complex number. Then, under Assumption !
((=)m²(2) v 0(=)0()) m(2)
x(1,,(=))(E)) m(()
Q(2) + Q(2) m())I. VA(2)VT A(2)
(v (vTT,)
[(=)]
22
23 (z)
with VRV = [v, 1m,, [(=)
2c 2z--oz(n-1))mn (2) ((z) oto)m(=K1+ m| lie 1..
for i. the kurtosis of the entries of Z, and m(2) the unique solution, such that 3(m(=)) 332] 2 0, to
1
afm((=) c a1m(2)
-- af m()).
(9)
m
The major implication of Theorem I is that, the spectral behavior of the matrix K (e.g., its eigenvalue distribution and the isolated eigenpairs as discussed after (6) depends on the nonlinear f only via the three parameters 01, a2, v defined in (8). More concretely, the empirical spectral measure wn. = 4 D.11 6x, of K has deterministic limit w as n, + co, uniquely defined through its Stieltjes transform m(2) = f 2) - w((t) (t)) the solution to g This limiting measure does not
'For m=( the Stieltjes transform of measure w. w can be obtained via w([a, b]) = lim a f 3[m(a+ ry)]dr for all b continuity points of w.
4

---

Published as a conference paper at ICLR 2021
0.02
0
-0.02
0.02
0
10
5
5
10 15
-0.02
Figure 2: (Left) Histogram of eigenvalues of K (blue) versus the limiting spectrum and spikes
(red). (Right) Eigenvectors of the largest (top) and second largest (bottom) eigenvalues of K (blue), versus the rescaled class label av vv/vi (red, from Corollary 2 f(t) sin(t) 3 cos(() +
3/ve,p 800, n = 6 400, P = 1.1 1p /P, [-1a//2 1n/2| on Student-t data with K = 5.
depend on the law of the independent entries of Z, so long that they are sub-exponential. with zero
mean and unit variance. In particular, taking d1 0 in (9) gives the (rescaled) Wigner semi-cirele law w (Wigner 1955). and taking V = of (i.e., at = 0 for I 2 2) gives the Marëenko- Pastur law (Marcenko Pastur 1967). See Remark in Appendix A.2 for more discussions.
Spurious non-informative spikes. Going beyond just the limiting spectral measure of K. Theo- rem [ also shows that isolated eigenvalues (often referred to as spikes) may be found in the eigen- spectrum of K at very specific locations. Such spikes and their associated eigenvectors are typically thought to provide information on the data class-structure (and they do when f is linear). However, when f is nonlinear, this is not always the case: it is possible that not all these spikes are "useful" in the sense of being informative about the class structure. This is made precise in the following, where we assume μ 0, i.c., that there is no class structure. The proof is in Appendix AA.2
Corollary iooon-nnfommttvee spikes). Assume μ 0. K * and 02 * so that the notations of Theorem /
(2) O and Q(z) = m(2) + (2) for Q22) defined in Theorem ! Then,
of
x+
02 satisfies a a1 + +1 and (v = (I+0121)
1/c, two eigenvalues
a7z+
of converge to z= cz
(v - am}== away from the support of w. If instead Itals
x+ = =1/1 a1 + then a single eigenvalue of K isolates with limit 2
(2(2)c)
2c
Corollary [ (combined with Theorem TD says that, while the limiting spectrum is universal with re- spect to the distribution of the entries of Z, the existence and position of the spurious non-informative spikes are not universal and depend on the kurtosis λ of the distribution. (See Figure [2] in Ap- pendix A.2 for an example.) This is far from a mathematical curiosity. Given how nonlinear transformations are used in machine learning practice, being aware of the existence of spurious non-informative spikes in the eigenspectrum of K (well separated from the bulk of eigenvalues, but that correspond to random noise instead of signal), as a function properties of the nonlinear f. is of fundamental importance for downstream tasks. For example, for spectral clustering, their associ- ated eigenvectors may be mistaken as informative ones by spectral clustering algorithms, even the complete absence of classes. This is confirmed by Figure 2 where two isolated eigenvalues (on the right side of the bulk) are observed, with only the second largest one corresponding to an eigenvector that contains class-label information. For further discussions, see Appendix A.2 and A.3
Informative spikes. From Theorem ! we see that the eigenspectrum of K depends on f only via a1, 02 and v. particular, a1 and v determine the limiting spectral measure w. From Corollary [] we see that 02 contributes by (i) introducing (at most two) non-informative spikes and (ii) reducing the ratio a l/v (since v Σiz1 a?), thereby necessarily enlarging the support w (see Remark 2 for Appendix(A.22oorr more details). Taking d2 thus reduces the length of the support of and, as such, maximizes the "chance" of the appearance of an informative spike (the eigenvector of which positively correlated with the label vector v). See Remark [Tmark[[below for a more precise statement.
in Appendix
In particular, by taking 0 and an F O. we obtain only informative spikes, and we can charac- terize a phase transition depending on the SNR p. The proof of the following is Appendix A.3
Corollary (Informative spike and a phase transition). For an > and a2 = 0, let
F(x) = x² + 2r +
+1--
CV -
2cr - G(x) = 01 (1 +++)
a1 v 0
(10)
a
1 xx
5

---

Published as a conference paper at ICLR 2021
and let y be the largest real solution to F(r) = 0. Then, under Assumption /cv/as, and the largest eigenpair (A, v) of K satisfies
we have V0S
-=
G(P) GG())
p >> 7
v v
aa=
F(e) p(L+ojs
p>? 7
(11)
p ps
0
p PS 7;
almost surely as p, + 0c, p/n - E (0, oo), where we recall p lim ||el and ||v|| = vn.
Without loss of generality, we discuss only the case an > 0 For > 0, both F(x:) and (xx) are increasing functions on x E (?, x)). Then, as expected, both À and a increase with the SNR p. Morcover, the phase transition point is an increasing function of and of v/aa.. As such, the optimal f in the sense of the smallest phase transition point is the linear function f(t) = t with
d1 V = 1 and y Vc. This recovers the classical random matrix result in (Baik et al. 2005
4 CLUSTERING PERFORMANCE OF SPARSE AND QUANTIZED OPERATORS
We start, in Section 4.1 by providing sharp asymptotic characterization of the clustering error rate and demonstrating the optimality of the linear function under (T). Then, in Section 4.2 we discuss the advantageous performance of the proposed selective sparsification approach (with f1) versus the uniform or subsampling approach studied previously in (Zarrouk et al. 2020). Finally, in Section|..3 derive the optimal truncation threshold Sopt. for both quantized /2 and binary f3, so as to achieve an optimal performance-omplexity trade-off for a given storage budget.
4.1 PERFORMANCE OF SPECTRAL CLUSTERING
The technical results in Section 3 provide conditions under which K admits an informative eigen- vector & that is non-trivially correlated with the class label vector (and thus that is exploitable for spectral clustering)
the n, - oc limit. Since the exact (limiting) alignment /v TV is known, along with an additional argument on the normal fluctuations of v, we have the following result for the performance of the spectral clustering method. The proof is in Appendix AA.4.
Proposition 1 (Performance of spectral clustering). Let Assumption hoold, let 0, and let C, sign((v}:) be the estimate of the underlying class C, of x4, with the convention v v 2 for v the top eigenvector of K. Then, the (average) misclassification rate satisfies 1 Ei= &c, +
(2 - 2a)), almost surely, as n. + for a E [0, 1) defined in IIp.
Recall from Corollary 2 that, for 02 O, the nonlinear function f (e.g., f2, fa) acts on the (statistical behavior of the) isolated eigenvector v, and thus on the spectral clustering performance per Proposition| [ only through the ratio v/ v/of. It thus suffices to evaluate the ratio v of different f and compare, for instance to that of the linear f(t) = t corresponding to the original X X matrix.
Despite being asymptotic results valid in the n,p + oo limit, the results of Proposition [ and Corollary [ closely match empirical results for moderately large n, p only in the hundreds. This illustrated in Figure 3 Proposition [ further confirms that the misclassification rate, being a decreasing function of a, increases with w/af (for and p fixed). This leads to the following remark.
Remark (Optimality of linear function). Since both the phase transition point and the misclas- sification rate grow with v/aî, the linear function f(t) in the sense of (i) achieving the smallest SNR or the largest ratio e lim p/n (i.e., the fewest samples n) necessary to observe an informative (isolated) eigenvector, and (ii) upon existence of such an isolated eigenvector, reaching the lowest classification error rate.
with the minimal v/at 1 is optimal
According to Remark 1. any I with v/af > induces performance degeneration (compared to the optimal linear functionn. However, by choosing / to be one of the functions f1, /2, S's defined in 33-5). one may trade clustering performance optimality for reduced storage size and computa- tional time. Figure size of the sparse fi. quantized f2, and binary f3. when compared to the optimal but "dense" linear function. As s + 0. both performance and storage size under f1 naturally approach those of the
the theoretical decay in clustering performance and the gain in storage
Otterwiise we could consider K instead of K and the largest eigenvalue becomes the smallest one.

---

and our proposed selective sparsification thus leads to strictly sparser matrices. Moreover, their ratio r(s) erfc(s)/(erf((s) + =se /VT) is decreasing function of and approximates as Published as a conference paper at ICLR 2021
100
Misclassif rale
M VV
0.8
0N
0.4
0.1
0.6
000000 Pocoo g 8d
0.4
0.2
0.08
00
0.2
0.06
2
5
0.5
SNR P
Truncation threshold
Figure 3: (Left) Empirical alignment V v/ //2/n (green crosses) and misclassification rate (purple
circles) in markers versus their limiting behaviors in lines, for f(t) = sign(t), as a function of SNR p. (Right) Misclassification rate as function of the truncation thresholds 8 of sparse fi (blue crosses) and binary /a (red circles) with p 4. Here, = 512, 256, l (0, Ip),
v = [-1n/2i 1// on Gaussian data. The results are obtained by averaging over 250 runs.
Misclassif, rate
0.2
10
Storage size
0.18
0.14
0.16
0.13
10"
0.14
0.12
0.12
10-1
0
0.5
1.5
0.43 0.69
0.5
Truncation threshold
Truncation threshold
Truncation threshold
Figure 4: Clustering performance (left, zoom-in in middle) and storage size (MB) (right) of (blue). f2 with M = (green), fa (red), and linear f() = f (black), versus the truncation threshold for SNR p 2, 1/2 and n 103, with 64 bits per entry for non-quantized matrices.
linear function. This unlike f2 or fa, which approach the sign function. For 8 > 1, the perfor- mance under sparse fi becomes comparable to that of binary fs (which significantly worse than quantized but non-sparse fa) but for larger storage cost. In particular, using f2 or fa in the setting of Figure one can reduce the storage size by factor of 32 64 (in the case of IEEE standard single- or double-precision foating-poinn format), at the price of a performance drop less than 1%.
4.2 COMPARISON TO UNIFORM SPARSIFIIATION AND SUBSAMPLING
From Figure we see that the classification error and storage gain of the sparse fi increase mono- tonically, the truncation threshold grows. For fi. the number of nonzero entries of K is approx- imately erfc(s) n with truncation threshold 8. Thus, the sparsity level Eseloe = erfc(s) E [0, 1] can be defined and compared to uniform sparsification subsampling approaches.
Recall (from the introduction) that the cost of spectral clustering may be reduced by subsampling the whole dataset in 1/Esut, chunks of nésub data vectors each. Alternatively, as investigated recently in (Zarrouk et al. 2020), the cost can be reduced by uniformly zeroing-out X X with a symmetric
random mask matrix B, with B, Bern(Euntt) for < j S and B 0. On average, proportion 1 unif of the entries of X sparsity level (and thus the storage size as well as computational time). Similar to our Corollary the associated eigenvector alignment a (and thus the clustering accuracy per Proposition I both cases can be derived. Specifically, taking Euuif af/v in (Zarrouk et al. 2020 Theorem 3.2). we obtain the same F(x:) as our Corollary and therefore the same phase transition point y and eigenvector alignment As for subsampling, its performance can be obtained by letting oj and changing e into c/ésub in the formulas F(x) and G(x)) our Corollary Consequently, the same clustering performance is achieved by either uniform selective sparsification (using fi with
to zero, so that Eunif [0. 1] controls the
Eunif dî/v erfc(s) + 2se -62
288 / erfc(s) Eselecs
(12)

---

Published as a conference paper at ICLR 2021
10
Proportion /aaio
Uniform
50%
0.8
Selective
10%
SNR p
0.6
Ratio r(s)
6
1%
0.4
(()) for >>
4
0.2
3
0.2
0.4
0.6
0.8
Truncation threshold 8
Level of sparsity
Figure 5: (Leff) Proportion of nonzero entries with uniform versus selective sparsification f1 and their ratio r(s), function of the truncation threshold s. (Right) Comparison of 1%, 10% clas- sification error and phase transition (i.e., 50% error) curves between subsampling (green), uniform (blue) and selective sparsification fi (red), as a function of sparsity level ε and SNR p. for
r(s) (1+ for 1 meaning that the gain in storage size and computational time is more significant as the matrix becomes sparser. This is depicted in Figure (left)...
Fixing a in Corollary to achieve given clustering performance level (via Proposition Dp. one may then retrieve "equi-performant tive sparsification, and subsampling. This is displayed in Figure (right), showing that dramatic performance gain is achieved by the proposed selective sparsification fi. Besides, here for c = 2, as much as 80% sparsity could be obtained with selective sparsification at constant SNR p, with virtu- ally no performance loss (red curves are almost flat on & E [0.2, 1)). This fails hold for uniform sparsification (Zarruuk et al. (2020) obtain such result only when S 0.1) subsampling.
curves the ()-p)),lane, for uniform sparsification, selec-
4.3 OPTIMALLY QUANTIZED AND BINARIZED MATRICES
From Figure we see that the classification errors of the quantized f2(M; s; t) and binarized fa(s; do not increase monotonically with the truncation threshold 8. It be shown (and also visually confirmed in Figure(4) that, for a given M 2 2, the ratio v/aî of both fz and fa is convex in s and has unique minimum. This leads the following optimal design result for f2 and fs, respectively, the proof of which is straightforward.
Proposition 2 (Optimal design of quantized and binarized functions). Under the assumptions and notations of Proposition ! the classification error rate is minimized at = Sopt with
1. Sopt the unique solution to a1 (Sopt)) (Sopt)
2a (Sopt) ((spp)) for quantized fz. with (s) and v/(s) the corresponding derivatives with respect to in Figure ( (right); and
2. Supt exp(-ssppt/(CC crfc(s.o))) = 0.43 for binary fa. with level of sparsity = 0.54.
Therefore, the optimal threshold Sopt for quantized f2 or binary fa under ① pisoobeen-indeeeeneet as it depends neither on nor on In particular, note that (i) the binary fa(Sopti is consistently better than f(1) = sign(() for which v/aţ = T/2 R 1.57 >> 1.24; and (ii) the performance of quantized S2 can be worse, though very slightly, than that of binary Sa for small s, but significantly better for not-too-small These are visually confirmed in the left and middle displays of Figure 4
As already observed in Figure (right), a significant gain storage size can be achieved by using f2 or fa. versus the performance-opiimal but dense linear function, with virtually no performance loss. Figure 6 compares the performance of the optimally designed fz and fa, sparse fi that has approximately the same storage size A significant drop in classification error is observed by using quantization f2 or binarization fa rather than sparsification f1. Also, performances of ʃ2 and /3 are extremely close to the theoretical optimal (met by f(t) = 1). This is further confirmed by Figure (right) where, for the optimal f2. the ratio v/af gets close to 1, for all M 2 5.
Figure 7 next evaluates the clustering performance, the proportion of nonzero entries in K, and the computational time of the top eigenvector, for sparse fi and binary fa. versus linear f(t) = t,
*ee use here the asymptotic expansion erfo(s) = - [1
ΣE_ (-1) 1.t--.22--1
(2+
"We set the truncation threshold of f1 such that erfc(s) = 3/64, so that the storage size of the sparse fi (64 bits per nonzero entry) is the same as the quantized fa with M = 3 (with 3 bits per nonzero entry), which three times that of the hinary fa-
8

---

Published as a conference paper at ICLR 2021
Misclassif. rate
8
1.2
0.4
Sopt
10
1.1
0.2
(v
2
8
10 10
10
10
2
4
6
SNR p
M
Figure 6: Performance of f1 (blue), f2 with M 3 (green) and (red) of the same storage size, versus SNR for c 4 (Ieft) and versus for SNR p = (middle). (Right) Optimal threshold sept (green) and (v/of)mis (purple) of f2 versus M. Curves for linear f(t) are displayed in black.
Misclassif, rate
Nonzero prop.
Compute. time
0.4
Sparse
0.4
0.8
0.6
Nonzero Timé
0.1
0.2
Binary
0.2
0.4
0.2
0
5
10
15
20
0
10
15
20
5
10
15
20
Truncation threshold
Truncation threshold
Truncation threshold
Clustering performance of sparse Ji and binary Sa (left and middle), proportion of nonzero entries and computational time of the top eigenvector for fa (right), as a function of the truncation threshold on the MNIST dataset: digits (0, 1) (left) and (5, 6) (middle and right) with n 248 and performance of the linear function in black. Results averaged over 100 runs.
Figure 7:
as a function of the truncation threshold s, on the popular MNIST datasets (LeCun et al. 1998 Depending on (the SNR p of) the task, up 90% of the entries can be discarded almost "for free". Moreover, the curves of the binary fa appear strikingly close to those of the sparse f1, showing the additional advantage of using the former to further reduce the storage size of K. More empirical results various datasets are provided in Appendix Bo confirm our observations in Figure 7
5 CONCLUDING REMARKS
We have evaluated performance-complextt trade-offs when sparsifying, quantizing, and binarizing linear kernel matrix via thresholding operator. Our main technical result characterizes the change in the eigenspectrum under these operations; and we have shown that, under an information informmation-luu- plus- noise model, sparsification and quantization, when carefully employed, maintain the informative eigenstructure and incur almost negligible performance loss in spectral clustering. Empirical results real data demonstrate that these conclusions hold far beyond the present statistical model.
The proposed analysis can be extended in many ways, for instance by considering a multi-cluster and more involved model than (1) as in (Liao & Couillet, (019) (i.e., "generic" K-class Gaussian mixture (( C.) for E {l....,
...,,K K}. which may help better interpret the empirical observations in Figure and Appendix B by focusing on more general kernels beyond the current inner-product type in (2), or by deriving non-asympiotic guarantees as in Vankadara & Ghoshdastidar 2020).
Our results open the door to theoretical investigation
broad range of cost-efficient linear alge- bra methods in machine learning, including subsampling techniques (Mensch et al.) [2017) Roosta-
Khorasani Mahoney| 2019), distributed optimization (Wang et al., 2018), randomized linear alge- bra algorithms [Mahoney] [201] Drineas & Mahoney (016), and quantization for improved training
and/or inference (Dong et al. [019)] Shen et al. 2020). Also, given recent interest in viewing neural networks from the perspective of RMT (Li & Nguyen 2018 Seddik et al. 2018 Jacot et al. 2019 2019 Martin Mahoney 2019 2020), our results open the door to understand- offe-offs far beyond kernel methods (Rahimi & Recht 2008 Jacot et al. 2018 Liu et al. 2020), e.g., to sparse, quantized, or even binary neural networks
Liu & Dobriban
ing and improving pertormance-complexii
(Hubara et al. 2016 Lin 2017).

---

Published as a conference paper at ICLR 2021
ACKNOWLEDGMENTS
We would like acknowledge DARPA, IARPA (contract W91 INF22CC00))) NSF, and ONR via its BRC on RandNLA for providing partial support of this work. Our conclusions do not necessarily reflect the position or the policy of our sponsors, and no official endorsement should be inferred. Couillet's 's work is partially supported by MIAI at University Grenoble-Alper (ANR-19) LANR-19-P31 19---19---003) and the HUAWEI LarDist project.
REFERENCES
Dimitris Achlioptas and Frank McSherry. Fast computation of low-rank matrix approximations. Journal of the ACM 54(2:9-s,, 2007.
George E. Andrews, Richard Askey, and Ranjan Roy. Special Functions, volume 71. Cambridge University Press, 1999.
Zhidong Bai and Jack W Silverstein. Spectral analysis of large dimensional random matrices, volume 20. Springer, 2010.
Jinho Baik, Gérard Ben Arous, and Sandrine Péché. Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices. The Annals of Probability, 33(5):1643-169) 2005.
Xiuyuan Cheng and Amit Singer. The spectrum of random inner-product kernel matrices. Random Matrices: Theory and Applications, 2(04):1350010, 2013.
Tarin Clanuwat, Mikel Bober-Irizar, Asanobu Kitamoto, Alex Lamb, Kazuaki Yamamoto, and David Ha. Deep learning for classical japanese literature, 2018.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. ImageNet: A large-scale hi- erarchical image database. In 2009 JEEE conference on computer vision and pattern recognition, pp. 248-255. leee, 2009.
Yen Do and Van Vu. The spectrum of random kernel matrices: universality results for rough and varying kernels. Random Matrices: Theory and Applications, 2350000 2013.
Edgar Dobriban, Stefan Wager, et al. High-dimensional asymptotics of prediction: Ridge regression and classification. The Annals of Statistics, 46(1):247-22) 2018.
Zhen Dong, Zhewei Yao, Amir Gholami, Michael W Mahoney, and Kurt Keutzer. HAWQ: Hes- sian aware quantization of neural networks with mixed preeedppeeiiion. In Proceedings of the IEEE International Conference Computer Vision, pp. 293 993-302,,20 2019.
Petros Drineas and Michael W Mahoney. RandNLA: randomized numerical linear algebra. Com-
munications of the ACM, 59(6):80-90 2016.
Petros Drineas and Anastasios Zouzias. A note on element-wise matrix sparsification via a matrix- valued Bernstein inequality. Information Processing Letters, 118(8))355-88,, 2011.
Noureddine El Karoui. On information plus noise kernel random matrices. The Annals of Statistics. 38(5):3111-3216 2010.
Zhou Fan and Andrea Montanari. The spectral norm of random inner-product kernel matrices. Probability Theory and Related Fields, 173(1-2):27-88 85, 2019.
Gene H. Golub and Charles Van Loan. Matrix Computations. The Johns Hopkins University Press, third edition, 2013.
Itay Hubara, Matthieu Courbariaux, Daniel Soudry, Ran El-yan,, and Yoshua Bengio. Binarized Neural Networks, In Advances Neural Information Processing Systems, volume 29, pp. 4107- 4115, 2016.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural Tangent Kernel: Convergence and generalization in neural networks. In Advances in neural information processing systems, pp- 8571-8580, 2018.
10

---

Published as a conference paper at ICLR 2021
Arthur Jacot, Franck Gabriel, and Clement Hongler. The asymptotic spectrum of the Hessian of DNN throughout training. In International Conference on Learning Representations, 2019.
Antony Joseph and Bin Yu. Impact of regularization on spectral clustering. The Annals of Statistics, 44(4):1755-1791, 2016.
Arun Kadavankandy and Romain Couillet. Asymptotic gaussian fluctuations of spectral clustering cigenvectors. In 2019 IEEE 8th International Workshop on Computational Advances in Multi- Sensor Adaptive Processing (CAMSAP). pp. 694 698. IEEE, 2019.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278-2322 1998.
Ping Li and Phan-Minh Nguyen. On random deep weight-tied autoencoders: Exact asymptotic analysis, phase transitions, and implications to training. In International Conference on Learning Representations, 2018
Zhenyu Liao and Romain Couillet. Inner-product kernels asymptotically equivalent to binary discrete kernels. arXiv preprint arXiv:1909.0677 06788, 2019.
Xiaofan Lin, Cong Zhao, and Wei Pan. Towards accurate binary convolutional neural network. In Advances in Neural Information Processing Systems, pp. 345-353, 2017.
Fanghui Liu, Xiaolin Huang, Yudong Chen, and Johan AK Suykens. Random features for kernel approximation: A survey in algorithms, theory, and beyond. arXiv preprint arXiv:2004. 1/154 2020.
Sifan Liu and Edgar Dobriban. Ridge Regression:
Structure, Cross- Validation, and Sketching. In International Conference Learning Representations, 2019.
Anna Lytova and Leonid Pastur. Central limit theorem for linear eigenvalue statisties of random matrices with independent entries. The Annals of Probability, 3775):178--1840, 2009.
Michael W Mahoney. Randomized Algorithms for Matrices and Data. Foundations and Trends@ in Machine Learning, 3(2):123-224, 2011.
Vladimir A Marcenko and Leonid Andreevich Pastur. Distribution of eigenvalues for some sets of random matrices. Mathematics of the USSR-Sbornik, 1(4):457, 1967.
Charles H Martin and Michael W Mahoney, Traditional and heavy tailed self regularization in neural network models. International Conference on Machine Learning, pp. 4284 4293, 2019.
Charles Martin and Michael Mahoney. Heavy-tailed universality predicts trends in test aceu- racies for very large pre-trained deep neural networks. In Proceedings of the 2020 SIAM Interna- tional Conference on Data Mining, pp. 505-513. SIAM, 2020.
Arthur Mensch, Julien Mairal, Bertrand Thirion, and Gaäl Varoquaux. Stochastic subsampling for factorizing huge matrices. IEEE Transactions on Signal Processing, 66(1):113-128, 2017.
Vinay Uday Prabhu. Kannada-MNIST A new handwritten digits dataset for the Kannada language. arXiv preprint arXiv: 012242,, 2019.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Advances in neural information processing systems, pp. 1177-1184, 2008
Farbod Roosta- Khorasani and Michael W Mahoney. Sub-sampled Newton methods. Mathematical Programming, 174(1-2):293-3) 2019.
Walter Rudin. Principles of mathematical analysis, volume 3. McGraw-hill New York, 1964.
Alaa Saade, Florent Krzakala, and Lenka Zdeborová. Spectral clustering of graphs with the Bethe Hessian. In Advances in Neural Information Processing Systems, pp. 406-414, 2014.
Mohamed El Amine Seddik, Mohamed Tamaazousti, and Romain Couillet. A kernel random matrix- based approach for sparse PCA. In International Conference on Learning Representations, 2018

---

Published as a conference paper at ICLR 2021
Mohamed El Amine Seddik, Cosme Louart, Mohamed Tamaazousti, and Romain Couillet. Random matrix theory proves that deep learning representations of GAN-date behave as gaussian mixtures. arXiv preprint 20Xx::2001108370, 2020.
Sheng Shen, Zhen Dong, Jiayu Ye, Linjian Ma, Zhewei Yao, Amir Gholami, Michael W Mahoney, and Kurt Keutzer. Q-BERT: Hessian Based Ultra Low Precision Quantization of BERT. In AAAI, pp. 8815-888 88111 2020.
Jack W Silverstein and ZD Bai. On the empirical distribution of eigenvalues of a class of large dimensional random matrices. Journal of Multivariate analysis, 54(2):175-192 1995.
Jack W Silverstein and Sang-ll Choi. Analysis of the limiting spectral distribution of large dimen- sional random matrices. Journal of Multivariate Analysis, 54(2):295 309, 1995.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: simple way prevent neural networks from overfitting. The journal of machine learning research, 15(1):1929-1958 2014.
Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Du- mitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich. Going deeper with convolutions. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 1-9, 2015,
Terence Tao, Van Vu, and Manjunath Krishnapur. Random matrices: Universality of ESDs and the circular law. The Annals of Probability, 3865))20233 2010..
Leena C Vankadara and Debarghya Ghoshdastidar. On the optimality of kernels for high- dimensional clustering. In International Conference on Artificial Intelligence and Statistics, pp- 2185-2195, PMLR, 2020.
Dan Voiculescu. Addition of certain non-commuting random variables. Journal functional anal- ysis, 66(3):323-346, 1986.
Ulrike Von Luxburg. A tutorial on spectral clustering. Statistics and computing, (7(4):395-416, 2007.
Shusen Wang, Fred Roosta, Peng Xu, and Michael W Mahoney, GIANT: Globally improved approx- imate Newton method for distributed optimization. In Advances in Neural Information Processing Systems, pp. 233222342,22 2018.
Eugene P. Wigner. Characteristic vectors of bordered matrices with infinite dimensions. Annals of Mathematics, 62(3):548--3) 1955.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-MNIST Novel Image Dataset for Bench- marking Machine Learning Algorithms, 2017.
Tayeb Zarrouk, Romain Couillet, Florent Chatelain, and Nicolas Le Bihan. ciltomancc-compleexe trade-off in large dimensional statistics. In 2020 JEEE International Workshop Machine Learn- ing for Signal Processing (MLSP). IEEE, 2020.
12

---

Published as a conference paper at ICLR 2021
A PROOFS AND RELATED DISCUSSIONS
Under the mixture model T.. the data matrix E Rpx* can be compactly written as
X = Z uv',
(13)
for Z E Rex= having i..d. zero-mean, unit-variance, с- x-kurtosis, sub-exponential entries and v
{=1}" so that |v| = vn. Recall also the following notations:
K ( /DD)
Q(z) =(K=- -K=I,,]
2I,)'
(14)
A.1 PROOF OF THEOREM 1
The proof of Theorem comes in the following two steps:
1. show that the random quantities ir A, Q(=) and (z)bb, of interest concentrate around their expectations the sense that
1
tr (Q(=) -(Q()))((()))
(Q(((()) - (=))),,,, + 0,
(15)
71
almost surely as n. p - oo; and
2. show that the sought-for deterministic equivalent ((=) given Theorem is asymptotic approximation for the expectation of the resolvent Q(z) defined in (6) in the sense that
E Q Ql| + 0,
(16)
- 30.
The concentration of trace forms in the first item has been established in (Cheng Singer 2013 Do & Vu 2013). and the bilinear forms follow similarly. Here we focus on the second item to show that [EQ Ql - the large n, limit.
In the sequel, we use o(1) and 0 (1) for scalars or matrices of (almost surely if being random) vanishing absolute values or operator norms as n. -> oc.
To establish E Q
QlI
- 0, we need to show subsequently that:
1. under
13). the random matrix K defined in (2) admits spiked-model model approximation, that
K= Ko + UAU + (1),,
(17)
for some full rank random (noise) matrix Ko and low rank (information) matrix UAUT to be specified; and
2. the matrix inverse (Ko -Ko-UUU - -2I,) can be decomposed with the Woodbury identity, so that
Q = (Ko UAU -AUU-=I,p, - +01 Q. - - - + (18)
with Q0(2) (Ko -1; :';
3. the expectation of the right-hand side of 18 is close to Q in the large limit, allowing us to conclude the proof of Theorem [
To establish
17 we denote the "noise-only" null model with || = b writing K Ko such that
Kolys = 8,45 (zz 2,/ h//////
(19)
With combinatorial argument, it has been shown in (Fan & Montanari 2019) that
02 1
Ko Ko
[1 T + 1, 0,
(20)
V2p
almost surely as n. p- + oe, for Ko such that (Ko -1 =Qa(=) m())I, and the random vector tp E R2n with its i-th entries given by
1
[xb],
(1|2, [[[12111]]
vp (122112 -p)-
/p
13

---

Published as a conference paper at ICLR 2021
Consider the informative-plus model K for X ||v|| = vn. It follows from (Liao & Couillet 2019 that
Z +
as in 13 with [v]; +1 and
K Ko
@1 [v
Z'
P
|
v
+ 0.
(21)
0
1 Z
almost surely as n. p. + 00.
Combining 20 with 21). we obtain |
K-Ko-
--KO-UAUI
+ 0 almost surely as n, p + co, with
0
0
V2
U
In v, v, Zd [4] E TR
A
0
a1
1
01
(22)
vp
d2
0
0
V2
0
a1
and (Kn - =I,) -1 = Q0(2) ++ mI= By the Woodbury identity, we write
Q (K - =I, = (Ko + UAU =I,))= + 01-1 (1)
Qu Q0 -'Q + 11
U
(23)
with
m(=)
m(z) v 1n m(=)
0
0
m(=) I
A- + A-+U'QU QoU=
0
+ + +1))((1)
(n - 1) m((=
0
0
0
0
where we use the fact that
E
[ = 0,
Blbbab 1 (n - 1)I..
We need to evaluate the expectation P
This is given in the following lemma.
Lemma 1. Under the assumptions and notations of Thhoore 7 we have
vn(z)
ElZ((Ko
=II,)= c a)m(2) I + (1))
(24)
p
Proof of Lemma 7 For Qo = - we aim to approximate the expectation "//2QzZ1/1/ Consider first the case where the entries of Z are i.i.d. Gaussian, we can write the (i, entry of
E[ZQ,Z with Stein's lemma (i.e., [f(x((()) [=] for N/(0 1))
a QQ00 TT 1s
E Ja
E Zig
Qo Liel =
OZ.j
==1
j=1
2 Ooolli jk Z
Σ
E
Qolisow
OZij
A 82.g
We first focus the term
by writing
a[Qolsk
OKo
[ Im
20
Q0
Σ
Qul5t
[Qu] mm
oZij
Oz:z
Oziz
jk
1.=1
where we recall [Kolij = d:psl (i 5/ /P//s////
vD so that for 1 + m we have
a[Kolim 1 s' 7/ vp)
az Z 1m
fzT /D) Zim + 2T55gmo)
aZ,j
p
oZg
0[K oZ:5
and
= 0 for 1 = m. We get
0 @(Quljk
Σ
Σ
/D) Zim [Q0) mk kg
Iioos /D)e (
Zku
OZij
j.k
j.k.m
j.k.
(Z
Q
Q. -
1 の S 2/ (T) Qo
14

---

Published as a conference paper at ICLR 2021
where f'(z'z/ /P) indeed represents f' -diag()) 1 in both cases.
For the first term, since /Z diag(+) 1, 1, 01-11 (P)), we have
1 Z/ "1 1.0,, 1, + Opp = amm(()
1n + +(p-1112)
(25)
p
where Olp 11/)) is understood entry-wise. As a result,
! Z diag
= (1m(() -Z0Z " + (1)
For the second term, since f' 2/ vP) has O(1) entries and A, B E Raxn, we deduce that
| O B & A for
! Iz ZZ Qa O(VD)
p
As consequence, we conclude that
1 EEZOOZZ -
1
tr Qo I aim(z) -BIZQoZ + (1)
P
that is
m(z)
ElZ P
El
c+ m1m(2) I + o1--1 (1)
where we recall that ir Qo/p= m(=)/c /c and thus the conclusion of Lemma for the Gaussian case.
The interpolation trick (Lytova & Pastur (2099 Corollaray 3.1) can then applied extend the result beyond Gaussian distribution. This concludes the proof of Lemma
Denote A (A-1 + UTQ it follows from Lemma that
EUAU
AA [A 1 A A2 A22 A33(1 - 1)I, + I
p
[A + A A2iv1
) + (1)
since |||||| 01) and |||| = o(v We thus deduce from 23 that
A
A12
(x) <> Q(=) m(=)I, (m2
VT
A21
Az2
with VVV [v, 1,]. Rearranging the expression we conclude the proof of Theorem
A.2 PROOF OF COROLLARY I AND RELATED DISCUSSIONS
Consider the noise-only model by taking (=)) so that
0 in Theorem
Then, we have K K and
a3(nn - ())
(() = m22)+ + 0((z)
- 2(2) 2 - a3 1)m
(26)
where we recall m(2) the solution
m(=) -(+ afm(z)
v at
-1
(2+ + a1m(2) +
m(z)
(27)
Since the resolvent Q(2) is undefined for IR within the eigensupport of K that consists of (i) the main bulk characterized by the Stieltjes transform m(z) defined in (27) and (fi) the possible spikes, need find the poles of (=)) but not those of m(2) to determine the asymptotic locations of
the spikes that are away from the main bulk. Direct calculations show that the Stieltjes transforms of the possible non-informative spikes satisfy
2
m +1
(28)
a2
15

---

Published as a conference paper at ICLR 2021
that are in fact the poles of (22), for d2 # 0 and # 1. For or 0g 0, S((2) has no (additional) poles, so that there is (almost surely) no spike outside the limiting spectrum.
It is however not guaranteed that & E R corresponding to (28) isolates from the main bulk. To this end, we introduce the following characterization of the limiting spectral measure in (27). the proof of which follows from previous work.
Corollary (Limiting spectrum). Under the notations and conditions of Theorem | with proba- bility one, the empirical spectral measure wi. = = (Ko) of the noise-only model Ko (and therefore that of K as a low rank additive perturbation of Kg via (2I)) converges weakly to a prob- ability measure of compact support n.p + 50, with uniquely defined through its Stieltjes transform m(z) solution to (27) Moreover,
1. if we let supp(w) be the support of then supp(w) U (0) = R\ (z(m) m EERR MER ((\/////ai) {0}) and a' (m) > 0}
(29)
for x(m) the functional inverse of (2 explicitly given by
a,m
a m,
x(m)
(30)
m
+ aim
c
2. the measure has density and its support may have up to four edges, with the associated Stieltjes transforms given by the roots of x' (m) = 0, i.e.
1 m²
afe amm)
of =0
x' ('))
(31)
The limiting spectral measure w of the null model K₂ was first derived in (Cheng Singer 2013)
for Gaussian distribution and then extended to sub-exponential distribution in (Do & VuI The fact that a finite rank perturbation does not affect the limiting spectrum follows from (Silverstein &
Bai 1995
Lemma 2.6).
The characterization in (29) above follows the same idea as in (Silverstein & Choi 1995 Theo-
rem 1.1), which arises from the crucial fact that the Stieltjes transform m(x) [ (t x) w (dt)
of a measure w is an increasing function on its domain of definition and so must be its functional
inverse xm)) given explicitly in (30). In plain words, Corollary 3 tells us that (i) depending on the number of real solutions to (31). the support of w may contain two disjoint regions with four edges, and (ii) R. is outside the support of if and only if its associated Stieltjes transform m satisfies r' (m) > 0, i.c. belonging to the increasing region of the functional inverse r(m) in (30). This
is depicted in Figure 8 where for the same function ftt = max(t, 0) 1/ with @₁ = 1/2.
ag = 1T22 and v ( (2 we observe in the top display a single region of for c and in the bottom display two disjoint regions (with thus four edges) for c 1 1/10. The correspond- ing (empirical) eigenvalue histograms and limiting laws are given in Figure 9 Note, in particular, that the local extrema of the functional inverse z (m) in Figure 8 characterize the (possibly up to four) edges of the support of w in Figure 9
According to the discussion above, it remains to check the sign of (mmm) for m + if they correspond to isolated eigenvalues away from the support of w. This, after some algebraic manipulations, concludes the proof of Corollary [
x- to see
2
Discussions. The limiting spectral measure in Corollary 3 is indeed a "mix" between the popular Marčenko-Pastee Pastur and the Wigner's semicircle law.
semicircle law). As already pointed out in (aan & Montanari 2019 here the limiting spectral measure w is the so-called free additive convolution (Voiculescu 1986 of the semicirele and Parrennko-asttur laws, weighted respectively by a1 and vv - a i.e.
Remark 2 (From Martenko-Pastie
w = an aawwMPe- 1) E V( ag)/c wsc
(32)
where we denote a1 (WMP,c 1 - 1) the law of a (1 for x ~ WMP. and V(v- /(v-at)/ wsc the law of V(v at)/c- for x wse Figure 10 compares the eigenvalue distributions of Ko
16

---

Published as a conference paper at ICLR 2021
x(m) supp(w)
(mm))
4
c/a1 01
15
x(m)
10
supp(w)
2 (m))
c//01
17
Figure 8: Functional inverse x(m) for m R RR\ff-c/on
{0}}. with f(t) max(t, 0) 10011/ 1/ 1/T, for = 2 (above, with two edges) and 1/10 (bottom, with four edges). The support of w can be read on the vertical axes and the values of æ such that x' cm(m) = 0 are marked in green.
5
Figure 9:
Eigenvalues of K with μ (blue) versus the limiting laws in Theorem and
Corollary 3 (red) for 200, n 600 (left) and p 400, 400 (right). with
f(() max () - 1/V2n and Gaussian data. The values of x such that x' (m) = 0 in Figure are marked in green.
for f(t)= az 12 (so that v- v- oî a²) with different pairs of (a1, az). We observe transition from the Marčenko- Pastur law (in the left display, with * and 02 0) to the semicircle law (in the right display, with 01 and a2 + 0).
0
2
0
2 2
0
2
Figure 10:
Figenvalues of K with la 0 (blue) versus the limiting laws in Theorem and Corollary (red) for Gaussian data, = 1 024, n 512 and f(t) axt + az(t² 1)/v2 with
a1 1, (left), a1 1, 42 1/2 (middle), and a1 O, a2 1 (right).
17

---

Published as a conference paper at ICLR 2021
Remark 2 tells us that, depending the ratio v/aj. the eigenspectrum of K exhibits transition from the Marčenko- fi. the ratio v/af is increasing function of the truncation threshold and therefore, as the matrix K become sparser, it eigenspectrum changes from a Marčenko- Pastuur--pp (at = 0) to be more semicircle-like. This is depicted in Figure 11 and similar conclusions hold for quantized f2 and binary f3 in the 2 Sopt regime.
to semicircle-lice shape. Note from Figure | (right) that, for the sparse
2
2
0.5
0.5
Figure 11:
Eigenvalues of K with μ (blue) versus the limiting laws in Theorem and Corollary (red) for Gaussian data, p = 1 024, n = 512 and f(t) = -t 112 with s = 0.1 (left), = .75 (middle), and 1.5 (right).
As discussed after Theorem and in the proof above, while the limiting eigenvalue distribution w universal and independent of the law of the entries of Z, long they independent, sub- exponential, zero mean and unit variance, as commonly observed in RMT (Tao et al.) 2010), this no longer the case for the isolated eigenvalues. In particular, according to Corollary the possible non-informative spikes do depend on the kurtosis к of the distribution. In Figure 12 we observe farther (left) spike for Student-t (with k and is thus nor sub cub-exponential than Gaussian distri- bution (with バ 3), while no spike can be observed for the symmetric Bernoulli distribution (that takes values #1 with probability 1/2 that 1). with the same limiting eigenvalue distribution
for f(t = max (f, 0) 1/ 1/v2x.
mm
2
0
4
0
2
2
0
2
Eigenvalues of K with fe 0 (blue) versus the limiting laws and spikes in Theo- rem I and Corollary [ (red) for Student-t (with 7 degrees of freedom, left), Gaussian (middle) and Rademacher distribution (right), p 512, n 2 048, f(t) max(t, 0) 1/v2π. Emphasis on the non-informative spikes at different locations: at 2. for Student-t and - 1.77 for Gaussian.
Figure 12:
Remark 3 (Non-informative spike in-between). When the support of consists of two disjoint regions (e.g., in the right plot of Figure 9. non-informative spike may appear between these two regions, with the associated Stieltjes transform < -c/aa in the setting of Figure 8 (boltom). This
only possibly when as
02. An example is provided in Figure 13
A.3 PROOF OF COROLLARY AND RELATED DISCUSSIONS
Similar to our discussions in Section A.2 we need to find the zeros of det A(2), that are real solu- tions to H (x) = 0 with
IvT) (vv
((x) = -
- - n²
mz(x)) (e((x)aaefe azo(n (xfhh-1))m(=))))20)))))) (p+1m))((
0
(33)
18

---

Published as a conference paper at ICLR 2021
Gettinnnneee 5
10
Figure 13:
Eigenvalues K with μ = (blue) versus the limiting laws and spikes Corol- lary and (red) for = 400, n = 6000, with ((t) = max((, 0) 1/v22 and Gaussian data.
for (2) the unique solution 9 and
limp ||l. Note that
1. for ai si (K 1)( (v'1.. p p) * there can be up to three spikes;
2. with 01 and 02 * 0, get m (z)
2c* ar(x-1] and there at most two spikes: this is equivalent to the case of Corollary with p = 0; in fact, taking a we discard the information in the signal μe, has been pointed out in (Liao & Couillet 2019);
3. with 02 = 0 and 01 A 0 we obtain m(x)
(i(+i] this is the case of Corollary
For a given isolated nigenvalue-eigenvector pair (), v) (assumed to be of multiplicity one), the projection iv v22 onto the label vector v can be evaluated via the Cauchy's s integral formula and our Theorem | More precisely, consider positively oriented contour I that circles around only the isolated X, we write
-v (K -I== -Iv)-'v dz
2n Jr n2
11
1 of (m(())) - dz dz
2
n
I Tv
1
f
A(z) dz dz)
VTv + n
- (ResA(z)) V o(1)
2m
n
I.
(im 2)
((=)((=) vIaa m()) ( (s)) (م) (1(z)
((=)m²(s)
+ o(1)
v'
where we use Theorem for the second line and recall that the asymptotic location of Ž is away from the support of limiting spectral measure that 2m fr m(=) dz in the third line.
Interestingly. note this point that taking v vI, or 02 (so that ((2) 0) leads to the same simplification
Σ 1 v 0/2 lim (z (=)
01 pm (2)
lim A)
+ o(1)
(34)
ニ-t c (aam((()(
pp)
aip (1 (1- afam?()) aip m² m + + 1+p (c amm()))2 1+ (A)
V- at
m²(2)) c
+ o(1) (35)
with I'Hospital's rule and the fact that m (z) (=)))
M-a
by differenti-
(c+))
ating (9p. The particularly means that, in the absence of the (noisy) non-informative spikes due to 42 * Oor in the case of balanced class v1, 0 (in fact "almost" balanced class v V1, = o(n)), we obtain the same asymptotic alignment (with respect to v) for the informative eigenvector. However, there may appear spurious non-informative and isolated eigenvectors in the latter case.
In the setting of Corollary 2 with #1 > and d2 = 0, with the substitution m(A) = mp ax (p+1) into Corollary 2 The phase transition condition can be similarly obtained, discussed in Section A.2 by checking the sign of the derivative the functional inverse x' (m) as Corollary This concludes the proof of Corollary
35 and then the change-of-variable
a: 1+x obtain the expression of F(x) in
19

---

Published as a conference paper at ICLR 2021
Discussions. Note that, while with either d2 0 vr,, 0 we obtain the same expression for the projection vv the possible spike of interest À (and its asymptotic location A) in these two scenarios can be rather different. More precisely,
1. with d2 0, there is a single possible spike Ā with m(A) mp as(p+I)
2. with v 1, 0, there can be up to three spikes that correspond to m, a11p+1] and m =
This observation leads to the following remark.
Remark 4 (Noisy top eigenvector with 02 * 0). For vI,, = and 02 * O, one may have ailptI] mp for instance with large 02 and small 01. Since m(x) is increasing function, the top of the SNR p. and totally useless for clustering purposes. An example is provided in Figure Figure@wherr where one observes that (i) the largest spike (on the right-hand side) corresponds to noisy eigenvector while the second largest spike has its eigenvector positively aligned with the label vector v; and (üi) the theoretical prediction of the eigen-alignment in Corollary 2 still holds here due to v v'1, 1n O.
m_ - -
pair of K can be non-informative, independent
This extends our Corollary to the signal-plus-nont scenario and confirms the advantage and necessity of taking 02 O.
where we observe that the non-informative spike can be lying between the two disjoint regions of the limiting measure w, in the case of a₁ > O, the informative spike mp a1(o+1) can only appear on the right-hand side of the support of w, since
As side remark, in contrast to Remark 3 and Figure 13
(I()t)) < 0 for p p= lim, || 2 O. See Figure & (bottom) for an illustration.
A.4 PROOF OF PROPOSITION 1
Note that, for V the top isolated eigenvector of K, with Corollary
2 we can write
v= Vovov/VR ow
(36)
for some o E R. evaluate the asymptotic clustering performance in the setting of Proposition (i.e., with the estimate
I a zero-mean random vector, orthogonal to v, and of unit norm. To
Č, = sign( [+)) for vvv v 2 0), we need to assess the probability Pr(sign((*) ( < 0) for x; E C1 and
Pr(sign((V) [v], (1) > 0) for x; E C2 (recall that the class-label [v]: 1 for x; E C1 and [v]; = +1 for
x; C2), and it thus remains to derive a. Note that
1 v a 20 v / 0² =a a 0² + o(1)
(37)
where we recall |v| /n. which, together with an argument on the normal fluctuations of Kadavankandy & Couillet 2019). concludes the proof.
B ADDITIONAL EMPIRICAL RESULTS ON REAL-WORLD DATASETS
In Figure 14 we compare the clustering performance, the level of sparsity, and the computational time of the top eigenvector, of the sparse function f1 and quantized f2 with M (so 2 bits per nonzero entry), on the MNIST dataset. We see that, different from the binary fs with which small entries of K are set to zero, the quantized function f2, by letting the small entries of K take certain nonzero values, yields surprisingly good performance on the MNIST dataset. This performance gain comes, however, at the price of somewhat heavy computational burden that approximately the same as the original dense matrix X X, since we lose the sparsity with f2, see Figure (left). This may be interpreted as a trade-off between storage size and computational time.
Also, from the left and middle displays of Figure and Figure 14. see that for MNIST data, while the classification error rates on the pair of digits (0. 1) can be as low as 1%. the performances on the pair (5.6) are far from satisfactory. with the linear f(t) t and the proposed fi. fz fs. This is the limitation of the proposed statistical model in (L. which only takes into account the first-order discriminative statistics. Indeed, it has been shown in (Liao & Couillet] 2019) that, taking d2 0 (as
20

---

Published as conference paper at ICLR 2021
Misclassif, rate
Prop of nonzero
0.4
Sparse Quant.
0.4
0.1
Compute. time
0.5
0.2
0.2
5
10
15
20
10
15
20
5
10
15
20
Truncation threshold
Truncation threshold
Truncation threshold
Figure 14: Clustering performance (left), proportion of nonzero entries, and computational time of the top eigenvector (right, in markers) sparse fi and quantized f2 with M 2, as function of the truncation threshold the MNIST dataset: digits (0, 1) (left) and (5,6) (middle and right) with n = 2048 and performance of the linear function in black. Results averaged over 100 runs.
in the of the proposed /1, J2 and fa) asymptotically discards the second-order discriminative statistics in the covariance structure, and may thus result in suboptimal performance in the case of non-identity covariance, would of future interest to extend the current analysis the "generic" Gaussian mixture classification: NW1 Ci) versus M C2) by considering the impact of (i) asymmetric means μr and μ4 * =M and (ii) statistical information in the covariance structure C₁ versus C2 and (iii) possibly multi-class mixture model with number of classes K 2 3.
Misclassif, rate
Sparse
0.4
Quant.
0.2
0.2
Binary
0.2
10
15
20
10
15
20
10
15
20
Truncation threshold
Truncation threshold
Truncation threshold
Clustering performance of sparse f1, quantized fz (with M 2) and binary fs as function of the truncation threshold on: (left) Kuzushij--MNIST class versus 4, (middle) Bushion-MNIST class versus 9, and (right) MNIST class 4 versus 8, for 048 and performance of the linear function in black. Results averaged over 100 runs.
Figure 15:
Figure compares the clustering performances of the proposed fi, f2. and fa on other MNIST- like datasets including the Fashion-MNIST (Xiao et al. 2017). Kuzushiji-MNIST (Clanuwat et al.) 2018), and MannA (Prabhu 2019) datasets. Then, Figure 16 compares the performances on the representations of the ImageNet dataset (Deng et al. 2009) from the popular Geet (Szegedy et al. 2015) of feature dimension = 2 248. On various real-world data or features, we made similar observations as in the case of MNIST data in Figure Figure [4] the performances of sparse fi and binary fa are very similar and generally degrade as the threshold becomes large, while the quantized fa yields consistently good performances that are extremely close to that of the linear function. This is in line with the (theoretically sustained) observation in (Seddik et al.) (020)) that the "deep" representations of real-world datasets behave, in the large n, p regime, very similar simple Gaussian mixtures, thereby conveying a strong practical motivation for the present analysis.
Misclassif. rate
Sparse
Sparse
0.4
0.4
Quant.
Quant.
0.2
Binary
0.2
Binary
20
40
20
40
Truncation threshold
Truncation threshold
Clustering performance of sparse f1, quantized fe (with M 2) and binary fa as function of the truncation threshold s on GoogLeNer features of the ImageNet datasets: (left) class "pizza" versus "daisy" and (right) class "hamburger" versus "coffee". for n = 1 024 and performance of the linear function black. Results averaged over 10 runs.
Figure 16:
21


Reviews:
[{"review_id": "e2e03rjvj5", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nStrengths:\n+ The problem studied is an important one for analyzing large datasets.\n+ The study of different  'filter' functions on the sampled entries is quite novel to the matrix sampling literature\n+ 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.\n\nWeaknesses:\n- The randomness assumption of all columns of X being independent unit vectors is somewhat generous.\n- 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.\n\nOverall, 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.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "Yr5hvZ6XxSj", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\nThe 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. \nThe 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.", "extra_scores": {}, "extra_text": {}}, {"review_id": "CFPZqN_psRn", "reviewer": "AnonReviewer6", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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 \nthe Grammian matrix X^{T}X under entry wise non-linear transformations (specifically thresholding, binarization and quantization).\n\nThe 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 \nf 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.\n \nProposition 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, \nspectral 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 \nuse of central limit theorems. \n\n\nThe 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. \nIt 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\nSome minor comments:\n\n1.  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? \n2. line 10, page 2 - corroborate instead of collabora", "extra_scores": {}, "extra_text": {}}, {"review_id": "5tufK-HfTKX", "reviewer": "AnonReviewer7", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nFirst, 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.\n\nI 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?\n\nRegarding 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?\n\nTheorem 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.\n\nProposition 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.\n\nI 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.\"\n\nIf you could do it for f's in Eq. 4-5 that's even better.\n\nMinor comments:\n\n1. \"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.\"\n\nWhat type of computation?\n\n2. 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?\n\n3. Explain what are \"isolated eigenvalues\" or cite.\n\n\nFull disclosure: given the time constraints and me being an emergency reviewer, I didn't look carefully at the supplementary materials.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

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)