Randomized Sketches for Clustering: Fast and Optimal Kernel $k$-Means
Authors: Rong Yin
Yong Liu
Weiping Wang
Dan Meng
Venue: NeurIPS 2022 Accept (2022)
Keywords: Kernel k-Means
Randomized Sketches
Statistical Analysis

Abstract: Kernel $k$-means is arguably one of the most common approaches to clustering. In this paper, we investigate the efficiency of kernel $k$-means combined with randomized sketches in terms of both statistical analysis and computational requirements. More precisely, we propose a unified randomized sketches framework to kernel $k$-means and investigate its excess risk bounds, obtaining the state-of-the-art risk bound with only a fraction of computations. Indeed, we prove that it suffices to choose the sketch dimension $\Omega(\sqrt{n})$ to obtain the same accuracy of exact kernel $k$-means with greatly reducing the computational costs, for sub-Gaussian sketches, the randomized orthogonal system (ROS) sketches, and Nystr\"{o}m kernel $k$-means, where $n$ is the number of samples. To the best of our knowledge, this is the first result of this kind for unsupervised learning. Finally, the numerical experiments on simulated data and real-world datasets validate our theoretical analysis.

Randomized Sketches for Clustering: Fast and Optimal Kernel k-Means
Rong Yin 1:2, Yong Liu 3A, Weiping Wang 1.2 Dan Meng
Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China
School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China
3 Gaoling School of Artificial Intelligence, Renmin University of China, Beijing, China Beijing Key Laboratory of Big Data Management and Analysis Methods, Beijing, China yinrongdiie ac. en, liuyonggsai cruug. edu. cn, (wangweiping, hengdan)-@iiee ac.
Abstract
Kernel k-means is arguably one of the most common approaches to clustering. In this paper, we investigate the efficiency of kernel k-means combined with random- ized sketches in terms of both statistical analysis and computational requirements. More precisely, we propose a unified randomized sketches framework to kernel k-means and investigate its excess risk bounds, obtaining the state-of-the-a risk bound with only a fraction computations. Indeed, we prove that suffices choose the sketch dimension (()n) to obtain the same accuracy of exact kernel k-means with greatly reducing the computational costs, for sub- uub-Gaussian sketches, the randomized orthogonal system (ROS) sketches, and Nyström kernel k-means, where n the number of samples. To the best of our knowledge, this is the first result of this kind for unsupervised learning. Finally, the numerical experiments simulated data and real-world datasets validate our theoretical analysis.
Introduction
Kernel learning is an important field of machine learning Yin al. (2020b 2021 2022). Kernel k-means is one of the fundamental approaches in unsupervised learning and has been widely used in numerous applications Zhang & Rudnicky (2002); Dhillon (Dillon
al. (000)); Chitta et al. (20TT):
Liu (02T). whose basic idea is to classify similar samples into the same cluster, and there is large difference between samples in different clusters.
The statistical properties of kernel k-means have been studied for decades, but they may appear to be not sufficient. Consistency of the empirical minimizer of the clustering risk was shown in Abaya &
Wise (984); PPollrd 1981 1982). Rates of convergence and nonasymptotic performance bounds
have been considered by Antos (2005): Antos et al. (2005); |Bartlett al. (1998); Linder (2000) 2002 The existing excess risk bounds are mostly dependent upon the dimension of the hypothesis space. For example, in Bartlett et al. (1998), the clustering risk upper bound O /k//n). where is the number of samples, & the number of clusters, and is the dimension of the hypothesis space. Note that the hypothesis space of kernel k-means is typically an siinite-dimensionall Hilbert space and the upper bound become useless when d very large. Subsequently, some researchers deduced inneension-inepeeddee upper bounds for kernel k-means Koltchinskii (2006): Biau et al.
(2008); Maurer Pontil (2010g Canas et (2012): Levrard al. (015); Fefferman et al. (2016);
Calandriello & Rosasco 2018); Liu (2021)
However, the existing excess clustering risk bounds
either have a slow convergence rate O (k/ vn) Biau al. (2008); Calandriello & Rosasco (2018) or
require pretty strong assumptions the underlying distribution or large approximate dimensions m
"Correspondnng author.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

to get the faster convergence rate. Specifically, in Calandriello & Rosasco (018). if the approximate dimension reaches 92( / / , the clustering risk upper bound is O vn), which proportional Based on its method, Liu Yong Liu (2021) further improves the convergence rate to O //n), but
the corresponding approximate dimension is increased to 2 2(vnk). Meanwhile, in order to reduce the approximate dimension to (2(zz) with the convergence rate unchanged, this paper Liu (2021)
requires stronger assumption of algebraically decreasing eigenvalues of the kernel matrix.
From the perspective of computational requirements, kernel k-means requires manipulating and storing an empirical kernel matrix, which unfeasible for large-scale problems. Exploring approxi- mate kernel k-means algorithms scale to large-scale application scenarios has become subject of recent works, see for example Nyström approximations Williams & Seeger (2001); Fowlkes et al.
al. (2018) 8): Calandriello & Rosasco (oosasco[2018)) (2018): Wang al. (2019); Liu (2021 randomized sketches Biau et al. (2008); Wang et (2019). random features Rahimi & Recht
(2004) Pourkamali-Anrak
(2008 ; Chitta et al.] (2012); Pham & Pagh| (2013); Atarashi et al. (2019), incremental clustering
Can [1993); BBadley et al.] (2000). and reference therein. This paper focuses on the excess risk bound and computational requirements for kernel k-means. Although there are many studies on the
approximate kernel k-means, these approximate works pay little attention to the excess risk of clusters with the exception of Biau et al.) (2008); (Cllandiill & Rosasco (2018) Liu (202T). For example, the works in Wang al. (211)) establish the + E relative-error bound for randomized sketches kernel k-means instead of excess risk bound. Therefore, in this paper, we mainly introduce the most related approximate kernel k-means with excess risk guarantees. In [Biau et al. (2008), they employ the randomized sketches method to project the data in Hilbert space so as to approximate kernel k k-means. However, the data in Hilbert space implicit and definit-ddimesiional and its sketch matrix is dense and unstructured. In Calandriello & Rosasco (2018), the excess risk upper bound is O(k/yn) when the approximate dimension reaches S2( (2())). The upper bound of clustering risk in Biau al. (2008) and Calandriello & Rosasco (2018) does reach the optimal O( k//)) Bartlett et al. (1998). In Liu (021)) the approximate Nyström kemel k-means obtains the risk upper bound P(vk/n) with the approximate dimension 52 (k))k).. Although this paper Liu 2021) further reduces the approximate dimension to S2( (2))n) by introducing a stronger assumption, this is not universal. In addition, the computational requirements in BBau et al. (2008): Calandriello & Rosasco (2018)
2222)) are still high.
Motivated by these issues, in this paper, we focus on improving the statistical analysis and computa- tional approximations of kernel k-mmans. We propose a randomized sketches framework to kernel k-means and construct three novel and specific examples: uub-Gaussian sketches, the randomized orthogonal system (ROS) sketches, and Nyström kernel k-means. Theoretical analysis shows that the proposed three randomized sketches methods obtain the optimal excess clustering risk upper bound O( ((vkk/)) with the sketch dimension (i.e. approximate dimension) of Ω (2(n) (see Theorem 2}. To the best of our knowledge, this is the first optimal excess risk bound with the least approximate dimension and no strong assumptions for general approximate kerne k-means. From a computational point of view, the proposed methods lead to massive improvements reducing the time complexity from O(nkkt) kt) to at least Onn/n n//kk) and the memory complexity from (nn)) to (nn)n). where is the number of iterations. Moreover, we further derive the similarity bound of approximate solutions in the general case, which can be effectively calculated by k-means++ (see Theorem 3)
Experimental results verify and illustrate our theoretical analysis.
The rest of the paper is organized as follows. Section 2 is the background of kernel k-means. Section 3 describes the proposed randomized sketches kernel h-means framework and provides three novel examples. In section 4 we mainly show excess risk bounds of the proposed randomized sketches kernel k-means and the further theoretical analysis in the general case of k-means+++. Sections 5 and 6 are the experiments and conclusions.
2 Background
2.1 Notation
Given a sampling distribution a on an arbitrary input space X' and n samples S = {x E X drawn i.i.d. from y4, we denote with (n, = 1 Ei_ T(x; E X) the empirical distribution, where I(-) is the indicator function. In this paper, we use the feature map sp.)) X + H. to map X
2

---

into a Reproducing Kernel Hilbert Space (RKHS) H. Schölkopf et al. (2002); Scholkopi & Smola (2018) and assume that is separable, such that for any x E X, we have Φx x(x). Let X X - R be mercer kernel. We denote the inner product of H by (:,)), the associated norm by || I|. the Cartesian product of H by Ht = I and with K the kernel matrix, where Kij- = x(x,, X2) = (I, 2j) = Φj. This paper assumes that || [xx - for any x E E
2.2 Kernel k-Means
Let C = [c1....,cc ca. be a collection of & centroids from H. We divide the given dataset into disjoint clusters, each characterized by its centroid cj. The Voronoi cell associated with centroid c defined as (Calandiiello & Rosasco (2018)
C = j = arg min | - c,
(1)
where [k] 1, ........ k. That is, the point 4; belongs to the j-th cluster if çj is its closest centroid. Now we formalize the criterion used to measure the clustering quality, The empirical squared norm criterion is defined
1 Σ = TI ==1
W pm)
min 21
c,ll?
(2)
and the expected squared norm criterion is defined
WCC, p4) == Eo
min . c,
(3)
j=(k]
The empirical risk minimizer (ERM) is defined as
C == arg min WCC, CEH
(4)
The sub-script n in C, indicates that it minimizes W(C, (un) for n samples in S. In this paper, we bound the excess clustering risk E(C.) of the empirical risk minimizer Rosasco (2018):
mininizer(Cllndrries Calandriello
E(CC,) == E.- [}] W"))),
(5)
where ("))= == inf W(C, μ4) is the optimal clustering risk. In the following, we will ignore subscript S ~ μ if the input dataset clear.
From a computational perspective, one cannot compute C, directly, since the points o in H cannot be explicitly represented. However, due the properties of the squared norm criterion and the kernel trick, one can reformulate the objective W(, (n) of kernel k-means.
Proposition 1 (Proposition 2 of Calandriello & Rosasco 2018)). Let Knn E Ruxn be the empir- ical kernel matrix, and k; its i-th columns. Then
min WCC, pm) min CEH
C
iEc,
SEC
(6)
min k; n V
k
CC
j=1iEC,
SEC,
This approach constructs an n-dimensional embedding k; each point i, namely the i-th columns of the kernel matrix Kanz which can be explicitly computed, and perfectly preserves ((: (b,) and its minimizer C, However, it requires Onn)) time and space to construct and store the kernel matrix K, which is not scalable to large-scale scenarios.
2.3 The Existing Excess Risk Bounds Kernel M-Means
Here provide the existing upper bound and lower bound of kernel k-means.

---

According to Bartlett et al. 1198), we know that there exists a collection of centroids C₁ E Ht and | S for any x X. such that
- W (p) = ( kl k//4//
where is the dimension of xx. In general, d is very large even infinite. Therefore, the lower The following is the upper bound of kernel k-means.
bound of kernel k-means is ?
At
Theorem (Theorem in Liu (2021)) ). If [x S for any x E X, then for any 8 E (0, 1), with
probability least 8, we have,
E(C.. E (C,, (C, 1i] 10000----0 (')))
- 1o =
(8)
Note that, p (u) means that there exists constant such that p cu. (()) means to hide the logarithmic terms. This upper bound matches the theoretical lower bound ? (V+) and therefore
shows that the ERM C, achieve an excess risk (nearly) optimal n.
The Proposed Algorithms
Kernel k-means is one of the most popular clustering methods Yin et al. (220c). However, it is non- scalable to large scenarios due to computing the exact embedding k, To reduce the computational requirements, we propose novel approximate embeddings by using randomized sketches. In this section, we propose a unified randomized sketches kernel k-means. In addition, three specific examples of randomized sketches algorithms and the corresponding complexity analysis are provided.
3.1 Framework of Randomized Sketches Kernel k-Meens
We consider an approximation based on reducing the original column k; E R" to mn-dimensional subspace of I2, where m & n is the sketch dimension. More precisely, the proposed approximation defined via a sketch matrix R E Rm such that the m-dimensional subspace generated by the span of R. Therefore, the proposed randomized sketches method can be described as:
K RK SQK E gT*X
where K = Kin and Q E RmXx is a sampling matrix. The rows of Q are composed of m rows sampled uniformly from the n identity matrix without replacement. The matrix S | is constructed in three ways, which will be introduced in detail in the following section.
Then the unified randomized sketches kernel k-means can be written as (similarly Proposition
Cn,m= arg min CERme
min b
k
c
(10)
min
k.
k
C2
j=1 KEC
SEC,
where k; is the column of the approximate kernel matrix K in Eq. 9 and Cn.m [2,,... .a.....,G, c.,] is the empirical clustering centers associated with the m-diimensional k k,, Each c2 is the mean of those k,' 's in the Voronoi cell č,
Define the clustering centers by
Σn 12
1= k K [k,EC)))
j I....,
(II)

---

where Cr.m = [či......ã .y..... čx] and [[) is the indicator function. [kredt)) = 1 if k, E C and Il [keE,, = otherwise.
The n--dimensional embeddings k; are replaced with the lower m-dimensional enbeddings k,. We can perform any k-means algorithms over (kl..... kn and compute the clustering centers in Eq. 11
Algorithm 1 Unified Randomized Sketches Kernel k- k-Means
Input: dataset S [x; J number clusters k, kernel parameter, and sketch dimension m.. centroids C.
Output:
1: Sample m data points from S according to the sampling matrix Q in Eq.
2: Compute the approximate kernel matrix K E Rm** between the m sampling data points and the all data points in S.
3: Construct the matrix S E mm (See Section 3.2 for specific construction methods).
4: Compute SK, namely SK = S(QK) = K is Eq.
5: Perform k-means algorithm over the columns of K.
6: Compute centroids Cn.m in Eq.
The detail of the proposed randomized sketches kernel k-means is shown in Algorithm [ The proposed algorithm is mainly divided into two parts. The first part is from step to step 4, which is mainly to construct the sketch matrix R = SQ and obtain the variant kernel matrix K = SQK. The second part is from step 5 to step 6, mainly performing k-means over the columns of K and obtaining centroids. step I, one samples m data points from S according to the sampling matrix Q. Then, computing the variant kernel matrix K E mx by m sampling data points and all n data points. From a mathematical point of view, this step can be expressed as = QK. In step 3, we construct a matrix S, whose specific expression will be given in Section 3.2 This paper provides three different examples S, which brings different effects in the approximate kernel k-mean algorithms. In step 5, take the columns k; of K SK generated in step 4 as the processing objects and execute k-means algorithm on them. Finally, compute the centroids Čn,m in Eq
3.2 Examples of Randomized Sketches Kernel k-Means
Here, we introduce three examples of randomized sketches kernel k-means, which are constructed by three different matrices in Eq. In addition, the detailed complexity analysis of the corresponding three approximate kernel k-means is provided.
Example 1: Sub-Gaussian Sketches Kernel k-Means The first example of approximate kernel k-means is called sub- Sab-Gaussian sketches kernel k-means, whose matrix S E mR in (q.(9) is described by hash function. Let be hash function and (i)) [+1, -13 is 2-wise independent hash function. The entries S.j ai)) /mm with a probability of 1 and S. with probability /n.
of 1 Vn.
Complexity analysis: In the terms of time, we first sample the data by Q then generate the variant kernel matrix K. Therefore, the time cost of computing SK should be Onmm²). However, due to the sparsity the aub-Gaussian matrix S, we only need to compute the non-zero elements instead of the total elements, which can further reduce the computational requirements of SK from Onn?? to O(Vrmm In the iteration operation of performing k k-means algorithm over the columns k, of K, one needs Onmmkt) time. Combining the above, the total time cost of sub-Gaussial sketches kernel k-means O( VTim² + nmkk).. In terms of space, due to the operation of sampling, the key of the space cost is changed to K and K instead of K. Therefore, the space complexity of the proposed Lub-Gaussian sketches kernel k- k-means is (nm)
Example 2: ROS Sketches Kernel M-Means The second example of the random sketches kernel k-means is based on the randomized orthogonal system (ROS) sketches. The corresponding matrix
5

---

S E Rmxm xm in Eq. (
can be defined as below:
=
(12)
where D E R is random diagonal matrix whose entries are i.i.d. Rademacher variables. A mm an orthogonal matrix with uniformly bounded entries, for example the Hadamard matrix Wallis (176) and the discrete Fourier transform matrix. We use the Hadamard matrix in
Am/2
Am/2
this paper. The Hadamard matrix is defined recursively as: Am
with
Am/2
-mm/2
1 1
1
A
and A Am
Due to the constructed property of the Hadamard matrix A, we can use FFT (Fast Fourier Transform algorithm) to compute the matrix-vector product, such as Au for any u E RT whose time complexity (m log m) instead of (mm²). Therefore, in step 4 of Algorithm| the computation of SK can be realized by the fast FFT, which is another way to further reduce the time cost, in addition to the sparsity mentioned above.
Complexity analysis: In terms of time cost, due to the use of the Hadamard matrix, we can compute SK by FFT, whose time cost is (nm logm). In the iteration operation of k-means algorithm over the columns k,, the time cost is Onnmkt). Therefore, the total time cost of ROS sketches kernel k-means is (nm log m + nmktt). In terms of space, the key to the space cost is to store the matrices K and K, whose space requirements is O(nm). Therefore, the space complexity of the proposed ROS sketches kernel k-means is (nn)).
Example 3: Nyström Kernel k-Means The third example of the approximate kernel k-means is Nyström kernel k-means, whose matrix S e R= in Eq. 9 can be defined as: = I, where I is an identify matrix. That is, we only use the sample matrix Q in (9. Therefore, the proposed Nyström kernel k-means can be converted into:
Čn,m = arg min ČERmik
min
k; Cj
1=1
(13)
arg mill mEg
min
c - č
where Φ; = TT č₁ $ Thc,, T.. = ( ..)............................. o (m)) T() E [1, and the dictionary (i.e.,
subset) (1) 1.m is m points Φ sampled from { through the sampling matrix Q.
Note that, the proposed Nyström kernel k-means also be understood the identity matrix as an orthonormal matrix and not using the Rademacher randomization.
variant ROS, based on
Complexity analysis: In terms of time cost, the matrix S is scaled identity matrix so that the computation of step 3 and step Algorithm is not needed. Therefore, the time complexity of Nyström kernel k-means is decided by the iteration operation of k-means algorithm over the columns k,, which is Omnkkl). In terms of space, the key is the matrix K. Therefore, the space complexity of the proposed Nyström kernel k-means is Onm)).
In algorithm, the function of Q is to reduce the scale of data. The function of S is to fuse data features. In complexity, the proposed randomized sketches can reduce the time and space complexity. We sample data points according to Q, then generate the variant kernel matrix, instead of generating and processing the kernel matrix directly, which can greatly reduce the time and space complexity. In addition, our matrices S are structured (in ROS) or sparse (in sub- Gabs-an and Nyström), which can speed up kernel k-means by FFT or sparsity. theoretical analysis, we obtain the optimal excess risk bound with small sketch dimension based on the proposed randomized sketches, which can further reduce the time and space complexity. Overall, the proposed randomized sketches can greatly reduce the time and space complexity with the optimal excess risk bound.

---

Theoretical Analysis
In this section, exploit the excess risk bound of the proposed randomized sketches kernel k-means. Theoretical analysis shows that we can improve the computational requirements of kernel k-means using sub-Gaussian, ROS, and Nyström, while maintaining optimal generalization guarantees.
Theorem 2. !f x x I for any x E X, & & (0, 1), E (0, 1), and, in either one of the three cases of Gau-Gaussian, ROS, and Nyström, the sketch dimension is m = S2 n ,thn, with e- e-log(1+ee)
probability least 6, we have
E[ - (w)) k
+ + 1 )
(14)
From a statistical point of view, let s = 1/ /n, Theorem shows that when the sketch dimension is m ((v/)) the proposed randomized sketches Mub--Gassian, ROS, and Nyström) kernel k-means achieve the same excess risk bound Ô (Vk/n) as the exact kernel k-means.
Remark 1.
From a computational point of view, we can construct the /n-ddmmnsion randomized sketches simply, which can greatly reduces the total required space from O to (nn//T) and the total required time from ( kt) to Onn + nn/Tikt) at least, with the optimal excess risk bound. Remark 3. In Calandriello & Rosasco (2088), when the approximate dimension m 5t VT), the excess risk bound can reach (k// vn), which linearly dependent on and fail reach the optimal bound. The corresponding space complexity and time complexity are O (nv/n) and O (nkl + n²²). respectively. Compared to it, our proposed methods obtain the better excess risk bound and reduce the time complexity from O /ill-/ii n²) O (nkly/n nV/D)) at least. Subsequently, Liu Yong Liu (2021) further improves the excess risk bound of the method in Calandriello & Rosasco (2018) to Ó Vk/m), but the corresponding approximate dimension m. is increused to S(Vnk)). Mean- while, its space complexity and time complexity increase to O (nvnk) and O (nktv/k nk + n²k)) Compared to it, the proposed methods reduce the time complexity from O (nkt l + +2kk) to O (nktv/n + n/nn) at least and reduce the space complexity from O (nv/k) to O (n//) while maintaining the optimal excess risk bound Ô (Vk/m) and the smaller m = I(vn). To the best of our knowledge, the proposed methods are the first time that they are always possible to maintain the optimal excess risk bound Ô (Vk/m) in unsupervised non-parametric problem with smaller m = Ω (Vn), while greatly reducing the time and space requirements. In Table | we show the detail space complexity, time complexity, excess risk bounds, and m of the approximate kernel k-means.
Remark 2.
4.1 Further Results: k-Means+
We adopt the improved kernel k-means++ sampling Lattanzi & Sohler (2019). which has a local search strategy, for the proposed randomized sketches kernel k-maan. Here is theoretical analysis.
Lemma (Ltttanzi & Sohler (2019)). If., is obtained by the improved k-means+ algorithm with a local search strategy Lattanzi & Sohler (2019), then E, [W pa)l S w W(C (a), where wo is constant and T is the randomness derived from the k-means++ initialization.
Note that, this is multiplicative error bound on the empirical risk.
Theorem 3. Let C++ n.m be obtained by the improved k-means++ algorithm with a local search strategy Lattanzi & Sohler 2019). If xx < for any x E X, E E (0, 8 E (0, 1), and, in either one of the three cases of sub- Gaussian, ROS, and Nyström, the sketch dimension is m Ω
8 (-1
then, with probability at least 1 8, we have
Es EE (C 10]l = -oV
(1-8) (
+o
(15)
where I is the randomness derived from the k-means++ initialization.
7

---

Table 1: Comparison of the approximate kemnl k-mmans. The second and third columns represent the space and time complexity. The fourth and fifth columns represent the excess risk bounds and
Approach
Space
Time
Bound
m
Kernel k-Means
O (n²)
o (nPkt)
CyttrnCCalandrieen & Rosasco (018
O (n
O (nkt + n²)
Vn
Vn
Nytröm 12021)
o nvvk)
0 (nktV/k nk + +22k
nk
Sub-Gaussian Sketches (This Paper)
O (n
Onktv - -ny
VT.
ROS Sketches (This Paper)
(nn/n)
O(nktyn nVn)
n
Nyström (This Paper)
O (1)T))
O (nktv/)
E
0.47
Kernel k-Means
Sub Gaussian
2
Nystrom (Liu)
0.46
Accuracy
Time log
Nystrom (Ours)
ROS
0.45
Kernel k-Mcans
-2
0.44
Sub-Gaussian Nystrom (Liu)
0.43
Nystrom (Ours)
4
ROS
-6
100
200
300
100
200
300
# dimensions
# dimensions
(a)
(b)
Figure 1: Test accuracy and training time (in seconds) with different dimensions m kernel k-means, Sub- Gaussian, ROS, Nystrom (Ours), and Nystrom (Liu) on simulated data.
Theorem 3 shows that, if the optimal clustering risk W*()) is smaller than Ö(vk/n), the risk of W(C (Ctmm))) ()) can reach ( /k/n). Note that e is small, i.c. E = 1/V7.
Experiments
In this section, we evaluate experimentally our theoretical analysis on both simulated data and real-world data for the proposed methods. The server is 32 cores (2.40GHz) and 32 GB of RAM. The compared methods are the exact kernel k-means, Gaussian Biau et al.) (2008), Nyström (Liu) Liu (2021), ROS, Sub-Gaussian and Nyström (Ours). For the sake of distinguishing, Nyström (Liu) is Nystrom Liu (202T) in this paper. Each experiment is repeated times.
5.1 Numerical Experiments on Simulated Data
We conduct the experiments to validate our theoretical analysis of the proposed randomized sketches kernel k-means on simulated data. Now we generate the simulated data. Let c R i [1, k). be the clustering centers. where the values of the dimensions are 1 or -1 with the probability of 1/2. The data ith clustering follows the normal distribution with mean cj and variance The number of data in each clustering is the same. We use the Gaussian kernel xs x') exp (-l|x x112²/8)
Generating 10,000 samples for training and 10,000 samples for testing. The number of training samples in each clustering is 10000/k. The accuracy of kernel k-means He & Zhang (018 on the v(j.map(z)) where is the solution returned by the (approximate)
test set can be written

---

Table 2: The datasets used in this paper. Test accuracy and training time (in seconds) of kernel k-means,
Gaussian, Nyström (Liu), Sub-Gaussian sketches, ROS sketches, and Nyström (Ours) real datasets.
Instance
Class
Kernel k-Means
Gaussian
Nyström (Liu)
Dataset
Time
Accuracy
Time
Accuracy
Time
Accuracy
dna
2000
3
0.16
0.50=#0.01
0.12
0.49 0.02
0.09
0.50=10.22
segment
2310
7
0.13
0.50=10.02
0.09
0.45+10.03
0.05
0.43=10.01
mushrooms
8124
2
0.56
0.64
0.32
0.63100.02
0.11
0.61
pendigits
10992
10
0.61
0.11 +0001
0.34
0.11+00.01
0.21
0,10 0.02
protein
17766
3
5.07
0.46++0.01
3.16
0.44+-0.03
1.09
0.45++0.02
a8a 32561
2
6.47
0.75+0.01
3.21
0.73+0.03
1.12
0.73
w7a
49749
2
29.7
0.97+0.02
15.3
0.95
1,36
0.96 0.01
connect-4
67557
3
0.28
0.61
0.22
0.60
0.11
0.59
covtype
581012
Instance
Class
Sub-Gaussian (Ours)
ROS (Ours)
Nyström (Ours)
Dataset
Time
Accuracy
Time
Accuracy
Time
Accuracy
dna
2000
3
0.06
0.49 0.01
0.07
0.50+0.001
0.04
0.50
segment
2310
0.03
0.47+0003
0.03
0.49+0001
0.02
0.42+00.01
mushrooms
8124
2
0.04
0.63+0.01
0.04
0.62+0002
0.03
0.60
pendigits
10992
10
0.14
0.11#0.01
0.16
0.11
0.03
0.11
protein
17766
3
0.16
0.45+:0.01
0.21
0.46+10.01
0.03
0.44
a8a 32561
0.11
0.74+10.01
0.12
0.74100.02
0.03
0.73
w7a 49749
2
0.30
0.94+00.0
0.36
0.95+ 0.01
0.03
0.97+00011
connect-4
67557
3
0.05
0.59
0.06
0.601:0.02
0.03
0.58
covtype
581012
7
1.02
0.32#0.02
1.36
0.33
0.66
0.32+00.33
kernel k--maas using Lloyd's algorithm [loyd (1982). y is the real label, and ñ is the number of data in the test set. If p q. v(p,)) 1, otherwise u(p,9) 0. map(-) represents the best mapping match ú and y. The higher the accuracy, the better the method. The test accuracy and training time of the approximate kernel k-means with different follows: (I) There exists lower bound of the approximate dimensions m vn 100. When this lower bound reached, the accuracy of the proposed methods tends be stable. This is consistent with our theoretical analysis in Theorem 2 (2) The accuracy of the proposed methods keeps the similar accuracy the exact kernel k-maas. (3) We take the logarithm of the running time (in seconds) in Figure Our methods (ROS, Sub-Gaussian, Nyström) have obvious advantages over other methods running time. This verifies our complexity analysis.
given in Figure [ which can be summarized as
5.2 Numerical Experiments on Real-World Scenarios
In this subsection, we perform the experiments on the real datasets: dna, segment, mushrooms, pendigits, protein, a8a, w7a, connect-4, and covtype, which are from LIBSVM website of the data in each dataset is used for training experiments, and the rest is used for testing. = 150.
70 percent
The Gaussian kernel exp (-||x /0²) where o / /Zi, =1 The detail of the datasets n
and experimental results are shown in Table 2 From the above results, can find that these methods give similar accuracy the exact kernel k- t-means. The proposed methods outperform Nytröm (Liu) and Gaussian in time cost, which matches our theoretical analysis. the training time exceeds 90 seconds or the memory is insufficient, the experiment will be stopped. In the large covtype dataset, kernel k-means, Gaussian, and Nytröm (Liu) cannot achieve the experimental results, our proposed methods can obtain small training time and good accuracy. Those verify the smaller computational requirements of the proposed methods.
Conclusions
We propose unified randomized sketches framework kernel k-meaas and provide three specific examples of sub-Gaussiaa sketches, the randomized orthogonal system (ROS) sketches, and Nyström
'htp://www.ssie.m wttp:/i...t.u..tt/ssssseo www.eddwwww//illiiiiisss..

---

kernel k-means. Theoretical analysis show that the proposed methods obtain the state- tfate-of-the-ar risk bound and greatly reduce the computational requirements with sketch dimension (z))). To the best of our knowledge, this is the first optimal excess risk bound with the least approximate dimension and no strong assumptions for general approximate kernel k-means. Moreover, we further derive the similarity optimal bound of approximate solutions in the general case, which can be effectively calculated by k-means++. The extensive experiments illustrate our theoretical analysis.
Acknowledgments and Disclosure of Funding
We appreciate all the anonymous reviewers, ACs, and PCs for their invaluable and constructive comments. This work is supported in part by the Special Research Assistant project of CAS E.EE0YY2112000000077
the National Natural Science Foundation of China (No.62106259, No.62076234), Beijing Outstanding Young Scientist Program (ABBI/WYYJH122111000000000 and Beijing Natural Science Foundation (No. 4222029). Thank Intelligent Social Governance Platform and Major Innovation & Planning Interdisciplinary Platform for the "Double-First Class" initiative.
References
Abaya, E. and Wise, G. L. Convergence vector quantizers with applications to optimal quantization. SIAM Journal on Applied Mathematics, 44(1):183-189, 1984.
Antos, A. Improved minimax bounds on the and training distortion of empirically designed
vector quantizers. IEEE Transactions on Information Theory, 51(11):4022-403 2005.
Antos, A., Gyorfi, L., and Gyorgy, A. Individual convergence rates in empirical vector quantizer design. IEEE Transactions on Information Theory, 31(11):40334022 2005.
Atarashi, K., Maji, S., and Oyama, S. Random feature maps for the itemset kernel. In The Thirty-Third AAAI Conference on Artificial Intelligence, pp. 3199-3206, 2019.
Bartlett, P. L., Linder, T., and Lugosi, G. The minimax distortion redundancy in empirical quantizer design. IEEE Transactions on Information theory, 44(5):1802-1813 1998.
Biau, G., Devroye, L.,, and Lugos, G. On the performance of clustering in hilbert spaces. IEEE Transactions Information Theory, 5402)7811-79, 2008
Bradley, P. S., Fayyad, U., and Reina, C. Clustering very large databases using em mixture models. In Proceedings 15th International Conference Pattern Recognition. ICPR-2000, volume 2, pp. 76-80. IEEE, 2000.
Calandriello, D. and Rosasco, L. Statistical and computational trade-offs in kernel k-means. In Advances in Neural Information Processing Systems, pp. 9379-9389, 2018
Can, F. Incremental clustering for dynamic information processing. Acm Transactions on Information Systems, 11(2):143-16 1993.
Canas, G. D., Poggio, T., and Rosasco, Learning manifolds with k-means and k-flats. In Proceedings of the 25th International Conference Neural Information Processing Systems- Volume 2, pp. 2465-2473, 2012.
Chitta. R., Jin, R., Havens, T. C., and Jain, A. K. Approximate kernel k-means: Solution to karge scale kernel clustering. In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 895-903, ACM, 2011.
Chitta, R., Jin, R., and Jain, A. K. Efficient kemel clustering using random fourier features. In 2012 IEEE 12th International Conference on Data Mining, pp. 161-170. IEEE, 2012.
Dhillon, S., Guan, Y., and Kulis, B. Kernel k-means: Spectral clustering and normalized cuts. In Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 551-556. ACM, 2004.
10

---

Fefferman, C., Mitter, S., and Narayanan, H. Testing the manifold hypothesis. Journal of the American Mathematical Sociery, 29(4)983-1049, 2016.
Fowlkes, C., Belongie, S., Chung, F., and Malik, J. Spectral grouping using the nystrom method.
IEEE Iransactions on patlern analysis and machine intelligence. 26(2):214-225, 2004.
He, L. and Zhang, H. Kernel k-means sampling for nyström approximation. IEEE Transactions on Image Processing, 2765):108-- 2018.
Koltchinskii, V. Local rademacher complexities and oracle inequalities in risk minimization. The Annals of Statistics, 34(6):2533-2566 2006.
Lattanzi, S. and Sohler, C. A better k-means++ algorithm via local search. In International Conference on Machine Learning, pp- 3662-3671. PMLR, 2019.
Levrard, C. et al. Nonasymptotic bounds for vector quantization in hilbert spaces. The Annals of Statistics, 43(():592-611) 619, 2015.
Li, and Liu, Y. Sharper generalization bounds for clustering. International Conference on Machine Learning, pp. 6392-6400 PMLR, 2021.
Linder, On the training distortion vector quantizers. IEEE Transactions on Information Theory, 46(4):1617-1623, 2000.
Linder, T. Learning-theorre theoretic methods in vector quantization. In Principles of nonparametric learning, pp. 163-210. Springer, 2002.
Liu, Y. Refined learning bounds for kernel and approximate k-means. Advances in Neural Information Processing Systems, 14:6142-6151 2021.
Lloyd, S. P. Least squares quantization in pem. IEEE Transacionss on Information theory, 28(2): 129 129-137, 137, 1982.
Maurer, A. and Pontil, M. k-dimensional coding schemes in hilbert spaces. IEEE Transactions on Information Theory, 56(1 (6(11))5539-5588 2010.
Pham, N. and Pagh, R. Fast and scalable polynomial kernels via explicit feature maps. In Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pp- 239-247, 2013.
Pollard, D. Strong consistency of k-means clustering. The Annals of Statistics, pp. 135-140, 1981.
Pollard, D. Quantization and the method of k-means. IEEE Transactions on Information theory, 28 (2):199-205, 1982.
Pourkamali-Anaraii, F., Becker, S., and Wakin, M. B. Randomized clustered nystrom for large-scale kernel machines. In Stcrry-Second AAAI Conference on Artificial Intelligence, pp. 1960-39677 2018.
Rahimi, A. and Recht, B. Random features for large-scale kernel machines. In Advances in neural information processing systems, pp. 1177-1184 2008.
Scholkopf, B. and Smola, A. J. Learning with kernels: support vector machines, regularization, optimization, and beyond. Adaptive Computation and Machine Learning series, 2018.
Schölkopf, B., Smola, A. J., Bach, F., et al. Learning with kernels: support vector machines, regularization, optimization, and beyond. MIT press, 2002.
Wallis, S. On the existence of hadamard matrices. Journal of Combinatorial Theory, Series A, 21 (2):188-195, 1976.
Wang, S., Gittens, A., and Mahoney, M. W. Scalable kernel k-means clustering with nyström approximation: relative-error bounds. The Journal of Machine Learning Research, 20(1):431-47) 2019.

---

Williams, C. K. and Seeger, M. Using the nyström method to speed up kernel machines. In Advances in neural information processing systems, pp. 682-688, 2001.
Yin. R., Liu, Y., Lu, L., Wang. W., and Meng, D. Divide-and con-urr learning with nyström: Optimal rate and algorithm. In The Thirty- Fourth AAAI Conference on Artificial Intelligence, pp. 2020a.
Yin, R., Liu, Y., Wang, W. and Meng, D. Sketch kernel ridge regression using circulant matrix: Algorithm and theory. IEEE transactions on neural networks and learning systems, 31(9):3512- 3524, 2020b.
Yin, R., Liu, Y., Wang, W., and Meng, D. Extremely sparse johnson-lindenstraus. transform: From theory to algorithm. In 20th IEEE International Conference on Data Mining, pp. 1376-1381. IEEE, 2020c.
Yin, R., Liu, Y., Wang, W., and Meng, D. Distributed nyström kernel learning with communications. In International Conference on Machine Learning, pp. 12019-12028, 2021.
Yin, R., Liu, Y., and Meng, D. Distributed randomized sketching kernel learning. In Proceedings of the AAAI Conference on Artificial Intelligence, pp. 8883-8891, 2022.
Zhang, R. and Rudnicky, A. A large scale clustering scheme for kernel k-means. In Object recognition supported by user interaction for service robots, volume 4, pp. 289-292. IEEE, 2002.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material as a URL)? [Yes] We provide Pseudo code, data, and instructions. Lucky to be accepted, the code will provided.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you eite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL.? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're
using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
12

---

(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "rBP7mIQc1mJ", "reviewer": "Reviewer_b1Eg", "summary": "This paper proposes a new sketching method for vectors, which allows one to retain the guarantees associated with k-means but with dimension bounded by sqrt{n}, which can be much less than d. The framework can be applied using three standard random matrices (sub-Gaussian, ROS or Nystrom), and of course the reduced dimension allows for better algorithmic runtime. \n\nThe core contribution is the creation of a sketch of the form SQK, where S is the full random matrix, Q is a sampling matrix (a random submatrix of the identity matrix), and the multiplication of Q by K yields the approximate kernel matrix between the sampled data points and the point set.", "questions": "Please address the above concerns.", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: The overall result is a non-trivial improvement for an important problem.\n\nWeaknesses: I felt the presentation could be greatly improved. There are multiple choices made regarding the construction of the sketch (basically, the SQK format used by the authors), without sufficient explanation, overview or discussion of the import of these choices. The steps of the algorithm should be discussed and explained in depth and they are introduced. A similar issue is that the current technique isn't placed in context - what is its relation to earlier used techniques, and in what way is it different. The overall presentation is poor, and also doesn't allow one to judge the novelty of the paper.\n\n--------------------\n\nIn response to the authors' rebuttal, I have raised my overall score.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "hpIr4wyY1LT", "reviewer": "Reviewer_ZBXn", "summary": "This paper studies statistical properties and computational efficiency of randomized sketching for kernel k-means clustering. Compared to most existing works, this paper focuses on characterizing the optimal excess clustering risk upper bounds for three types of randomized sketching. In this paper, randomized sketching involves multiplying the kernel matrix by a \"random\" matrix (also called a sketch matrix). Overall, the paper provides a detailed overview of background materials (i.e., kernel k-means and randomized sketching). ", "questions": "Can you please explain how Section 4.1 relates to the other sections? It looks like the main contribution of this subsection is to include some results from (Lattanzi & Sohler 2019). However, the significance of this new result has not been discussed in other places, such as experimental results. ", "limitations": "There should be some more discussion on the significance of the statistical analysis for practitioners. Although this work provides an interesting upper bound, how does this result translate for analyzing large data sets? Can this approach be used for clustering a data set with a few hundreds of thousands of samples? ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n+ The main strength of this work is related to the provided statistical analysis and upper bounds for the the optimal excess clustering risk. Based on the provided table, this work shows that sketch dimension can be substantially reduced without compromising accuracy. \n+ Another strength of this work is providing a nice overview of kernel k-means clustering and randomized sketching. Although these materials are very standard, it is nice to provide them for general readers. \n+ This work also presents a \"unified\" algorithm with time/space complexity analysis, which is beneficial. \n\nWeaknesses:\n- From a computational standpoint, the contribution of this work is limited. The three randomized sketching methods have been used for various kernel-based methods, including more sophisticated clustering techniques such as spectral clustering. \n- Although the improved upper bound is interesting, experimental results do not directly show the benefits of this statistical analysis. In other words, it is shown that the proposed randomized methods are more efficient compared to the exact kernel k-means, but no comparison with the other cited works. ", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "NyygCou_50g", "reviewer": "Reviewer_sN6c", "summary": "The paper investigates the statistical analysis and computational requirements of kernel k-means based on randomized sketches.\nThe authors proposed a randomized sketches framework for kernel k-means and construct three specific examples of sub-Gaussian sketches, ROS sketches, and Nystrom to kernel k-means.\nThe proposed methods obtain the optimal excess risk upper bound $\\mathcal{O}(\\sqrt{k/n})$ with the least sketch dimension $\\Omega(\\sqrt{n})$ in the theoretical analysis.\nMeanwhile, they reduce the time cost to $\\mathcal{O}(n\\sqrt{n}+n\\sqrt{n}kt)$\nand the space complexity to $\\mathcal{O}(n\\sqrt{n})$, which make a good improvement in computational requirements.\nFinally, this work adopts the improved kernel k-means++ for the proposed randomized sketches kernel k-mean and derives the similar bound.\nThe experimental results on both simulated data and real-world data\nverified the theoretical results of the proposed methods (sub-Gaussian sketches kernel k-means, ROS sketches kernel k-means, and Nystrom kernel k-means).", "questions": "A solid theoretical analysis is provided. A clear comparison with the results of recent works is given in Table 1. The experiment results on synthetic and real data show the effectiveness of the proposed methods. Nevertheless, there are some minor issues.\n\n1) The experiments in this paper are convincing. It would be much better if the figures are more beautiful.\n\n2) The author should double check the text. There are few typos. For example, in Table 1, the citations are connected with the text. \"real-word\" should be \"real-world\".\n\n3) In line 200, it is a little bit confusing that the authors present $K$ followed by $\\hat{K}$\n\n4) The conclusion section of this paper is missing.", "limitations": "This paper describes the scope of application of the proposed methods in detail, and does not involve negative social impact.", "rating": 9, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper has the following contributions: \n1) proposed a unified randomized sketches framework to kernel k-means;\n2) proposed three novel and specific examples (sub-Gaussian sketches, the randomized orthogonal system (ROS) sketches, and Nystrom kernel k-means);\n3) obtained the state-of-the-art risk bounds of the proposed methods in theoretical analysis;\n4) made significant improvement in reducing computational requirements,\n5) derived the similarity optimal bound of approximate solutions in k-means++.\n\nThose contributions are novel and significant. The experimental evaluations in simulated and real case settings illustrate the theoretical analysis of the proposed methods. The paper is well organized, well written, and technically sound. The exposed materials can be followed up fairly. All the relevant papers are properly cited. Overall I enjoyed reading this paper, which nicely generalizes randomized sketches to the kernel k-means.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept