Refined Learning Bounds for Kernel and Approximate $k$-Means
Authors: Yong Liu
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Kernel $k$-means，Risk bound
Kernel methods
Learning theory

Abstract: Kernel $k$-means is one of the most popular approaches to clustering and its theoretical properties have been investigated for decades. However, the existing state-of-the-art risk bounds are of order $\mathcal{O}(k/\sqrt{n})$, which do not match with the stated lower bound $\Omega(\sqrt{k/n})$ in terms of $k$, where $k$ is the number of clusters and $n$ is the size of the training set. In this paper, we study the statistical properties of kernel $k$-means and Nystr\"{o}m-based kernel $k$-means, and obtain optimal clustering risk bounds, which improve the existing risk bounds. Particularly, based on a refined upper bound of Rademacher complexity [21], we first derive an optimal risk bound of rate $\mathcal{O}(\sqrt{k/n})$ for empirical risk minimizer (ERM), and further extend it to general cases beyond ERM. Then, we analyze the statistical effect of computational approximations of Nystr\"{o}m kernel $k$-means, and prove that it achieves the same statistical accuracy as the original kernel $k$-means considering only $\Omega(\sqrt{nk})$ Nystr\"{o}m landmark points. We further relax the restriction of landmark points from $\Omega(\sqrt{nk})$ to $\Omega(\sqrt{n})$ under a mild condition. Finally, we validate the theoretical findings via numerical experiments.

Refined Learning Bounds for Kernel and Approximate k-Means
Yong Liu
!Gaoling School of Artificial Intelligence, Renmin University of China, Beijing, China Beijjng Key Laboratory of Big Data Management and Analysis Methods, Beijing, China liuyonggaai@ruc. edu.c.
Abstract
Kernel k-means is one of the most popular approaches clustering and its the- oretical properties have been investigated for decades. However, the existing state-of-the-art risk bounds are of order Ok/V/n) which do not match with the stated lower bound Q2 (k/n) in terms of k; where is the number of clusters and n is the size of the training set. In this paper, study the statistical properties of kernel k-means and Nyström-based kernel k-means, and obtain optimal clustering risk bounds, which improve the existing risk bounds. Particularly, based a refined upper bound of Rademacher complexity (21). we first derive an optimal risk bound of rate O(vk/n for empirical risk minimizer (ERM), and further extend it general cases beyond ERM. Then, analyze the statistical effect of computa- tional approximations of Nyström kernel k-means, and prove that it achieves the same statistical accuracy as the original kemeel k-means considering only Q (/k) Nyström landmark points. We further relax the restriction of landmark points from 92( Vnk) to (V))) under mild condition. Finally, we validate the theoretical findings via numerical experiments.
Introduction
Clustering, fundamental data mining task, is used in numerous applications including web search, medical imaging, gene expression analysis, social network analysis and recommendation systems k-means arguably one of the most popular approaches clustering, producing clusters with piece-wise linear boundaries. Its kernel version, which employs a nonlinear distance function, has the ability to find clusters of varying densities and distributions, greatly improving the
56
55
23
42
flexibility of the approach [18
53
38
37
39
60
29
36
35 61].
To understand (kernel) k-means and guide the development of new clustering algorithms, researchers have investigated its theoretical properties for decades. The consistency of the empirical minimizer was demonstrated by [45] 47 I]. Rates of convergence and non-asymptotic performance bounds 14 20). Most of the proposed risk bounds are dependent upon the dimension of the hypothesis space. For example, Bartlett et al. 7 provided, under certain mild assumptions, clustering risk bound of order O O(ykd//)), where d is the dimension of the hypothesis space and n is the size of the training set. However, the hypothesis space of kernel k-means is typically an infinit-ddimensional Hilbert space, such the reproducing kernel Hilbert space (RKHS) associated with Gaussian kernels [50]. Thus, the existing theoretical analysis of k-means are not extended
were considered by [46 13 33
usually suitable for explaining its kernel version. Recently, (20 16
TO
41
27
24 9
the previous results. and provided Limension-indepeee [16), the feature map associated with the kernel function satisfies || < then the clustering risk bounds are of order (k/v/)) These clustering risk bounds for kernel k-means are usually linearly
bounds for kernel k-means. As shown in
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

dependent on the number of clusters k. However, the number of clusters k may be very large in some domains, such as social networks and recommendation systems. Thus, from a theoretical perspective. these existing bounds of Okk/ Vn) do not match with the stated lower bound (2 k//) in k
Although kernel k-means is one of the most popular clustering methods, it requires the computation of a n X n kernel matrix. As for other kernel methods, this becomes unfeasible for large-scale problems, and thus deriving approximate computations, such as partial decompositions 6 28).
58 57], and random feature 34 31]. has become the subject of numerous recent works. However, few of these optimization- based methods focused on the underlying excess risk problem. To the best of our knowledge. the only two results providing excess risk guarantees for approximate kernel k-means are [16] and 9 In [6], Devroye and Lugosi considered the excess clustering risk when the approximate Hilbert space is obtained using Gaussian projections. In [9] Calandriello and Rosasco showed that, when sampling (2( (V) Nyström landmarks, the excess risk bound can reach Olk/ /n).. The excess risk bounds of [9] and [6] are both linearly dependent on k and thus do not match with the theoretical lower bound
random projection []6 15
Nyström approximations
[99 I 43 53
approximations [48] 12
In the recent work 21 the authors showed that the Rademacher complexity of the k-valued func- tion class of Lipschitz continuity with respect to the L norm can be bounded by the maximum Rademacher complexity of the restriction of the function class along each coordinate, times a factor of O(V)). Although it may be not very difficult to use the result of 21 for kernel k- k-means, the optimal bound of O( kk/n) for kernel k-mmans has never been given before. Moreover, we creatively extend the results of kernel k-means to the approximate one. Our major contributions include two parts:
1) A (nearly) optimal excess clustering risk bound of rate Ō(yk/ k/n proposed for empirical risk minimization (ERM) (see Theorem [T. To the best of our knowledge, this is the first (nearly) optimal excess risk bound for kernel k-means in terms of both & and n. Beyond ERM, we further extend the result of Theorem | to general cases (see Theorem and Theorem B)
2) A (nearly) optimal excess risk bound for Nyström kernel k-means is also obtained when sampling 2 (((nk) points (see Theorem 4 We further relax the restriction of landmark points from S2( //k) (Vvn) (see Theorem 5) and extend it to general cases (see Theorem 6 Theorem 77. This result shows that we can use the Nyström method to improve the effectiveness kernel k-means, while guaranteeing the optimal generalization performance.
The rest of the paper is organized as follows. In Section 2, we introduce some notations and provide an overview of kernel k-means. In Section 3, we provide nearly optimal excess risk bounds. In Section 4, we quantify the statistical effect of computational approximations of the Nyström-base kernel m-mmans. In Section 5, validate our theoretical findings by performing experiments both simulated and real data. We end in Section 6 with conclusion. All the detailed proofs are deferred to the Appendix.
2 Background
In this section, we will introduce some notations and provide a brief introduction of kernel k-means. Please refer to [8 9 for more details.
2.1 Notations
Assume P is (unknown) distribution on X, and S {x E X is a set of n samples drawn ii.d. from P. The empirical distribution IN is denoted as (,,()) (x) if E S, otherwise Let
R: X' x X + IR be mercer kernel [51], and 7 be its associated RKHS 522, which is the completion of the linear span of the set of functions:
H. span/k(x, -), XJ.
We denote the Cartesian product of H by H = 1 map X' into the Hilbert space H, and assume that H. is separable, such that for any X, we have
H. We use the feature map & : X + H to
'Ö hides logarithmic terms.

---

2x (x). Intuitively, in the rest of the paper, the reader can assume that 4x E R with d >> n or even infinite. From here on, we will denote the inner product of H. by (+-)), and the associated norm by || and assume that || I 1 for any x E X. We let
D { = (x.))
and denote []], =
= ( 2,) as the kernel matrix.
The notations μr (v) and μr Q(v) mean that there exist constants c1, such that S cv and CIV < S 02V, respectively. We use Ô and Ω to hide logarithmic terms.
2.2 Kernel M-Mans
In this paper, we aim at partitioning the given dataset into & disjoint clusters, each characterized by its centroid cj. The Voronoi cell associated with centroid cy is defined as [9]
Cj = 1==1:: arg min mig i:j
|1
c=
s=1...,k
Let C = [c....., Cs] be a collection of k centroids from H², this paper, we focus on the so-called kernel k-means clustering, by minimizing the empirical squared norm criterion
W(C,P,,) =
min
8 - cc,l²
(1)
over all possible choices of cluster centers C E H/. From written as
18 9..
we know that W(C, can be
k
min Σ P(C,P.):
Σ
4;
Dt
TI CER j=l j=l IEC,
Ccp
FEC
A ΣΣ
min n CEH 1=1 IEC,
n(x;, x;)
2
Σ
xx)
+
Σ x(xx)xx) L.eEC,
|Cg]
1c,1
DEC
The empirical risk minimizer (FRM) is defined as
C arg min W(C,P,). CEH*
The performance of a clustering scheme given by the collection C= [c cn. E Hº of cluster centers is usually measured by the expected squared norm criterion or expected clustering risk
W(C,P))
min 1=.....
1 Cy (x)
Given C H: let Sc (fo fee) be k-valued function of the collection C with fe, (x) || - 12 Let 4 R2 IR be minimum function. From the definition of ((fe(x)) min(Ja, (x), Sca (x)), one can see that the empirical and expected squared norm criteria can be respectively written as
W(C,P.) Σ x(fc(x))) and W(C,P) (lfc(x))dP(x))
In this paper, we consider bounding the excess clustering risk E(C,,) of the empirical risk mini- mizer [16]:
E(C,.) :-
where (P) = infce W(C, IP) the optimal clustering risk. the following, we will ignore the subscript D if the input dataset D is clear.

---

2.3 The Existing Excess Clustering Risk Bounds
According to [7], we know that there exists a collection of centroids Cy Ht, a constant c, and distribution I' with |x I 1 for any x E X, such that
4/-4/d B P)] W (P) 2 c
n
Note that the dimension of 4xx, which usually very large or even infinite. Thus, the lower bound of kernel k-means is 22( k/n).. However, most the existing risk bounds proposed for
kernel k-means are O(k/vT) [16 41 20 D] for example:
Lemma (11 Theorem 2.1). If 2x S for any x E X, then there exists a constant such that
k
C P) W Sc Vn'
where C, is the ERM of oF,(C, defined in
Note that the number of clusters may be very large for fine-grained analyses in social networks recommendation systems. This leaves us with the question: is it possible to prove a bound of rate V /k/n, which is (nearly) optimal in terms of both & and n?? In this paper, we attempt to answer this.
Main Results
In this section, we will provide nearly optimal excess risk bounds for kernel k-means. There are very few works focus on the underlying excess risk problem for kernel k-means. To the best of our knowledge, there are only two results [16] 9 providing excess risk bounds for kernel k-means or approximate kernel k-means. However, these bounds [6 9
are all linearly dependent on Based
on recently improvement of the upper bound of Rademacher complexity of L-Lipschitz with respect to the Lo norm (2I]. derive (nearly) optimal excess risk bound of linearly dependent on Vk. then for any 8 E (0,1). there exists constant c, and with
Theorem 1. If Vx E X, xx S probability at least - 8, we have,
CIW (P)) se (. log (Vn) +
log
n
From Theorem 1
we know that
E[W(C,,;)) (P) < Ô
which matches the theoretical lower bound Q k/m) when d is large 77]. Thus, our proposed bound (nearly) optimal.
Remark (Fast Rates). Some results suggest that the learning rate of kernel k-means can reach Okk/n) under certain assumptions on the distribution. Chou [13 pointed out that, if continuous densities of distribution satisfy certain regularity properties, the expected excess risk is of rate ((k/n) n)). An improved result was obtained by 3. who proved that the learning rate reach (kk/n) for any distribution supported on finite set. Levrard (7) further showed that, if the distribution satisfies a margin condition, the learning rate can also reach Ok/nn. Based on the notion of local Rademacher complexity, the expected excess risk has a rate faster than Okk /n) given in [24] 30). However, as pointed out, these conditions bounds are linearly dependent on k. In the future, we will consider studying whether it is possible to prove bound of O ((vk/)) under certain strict assumptions.
difficult verify in general. Moreover, these expected excess risk
3.1 Further Results: Beyond ERM
So far we have provided guarantees for C., that is, the optimal ERM in H/ Note that obtaining the optimal ERM C, a NP-hard problem in general (2] the following, we will consider the risk bound for general Č,, which only requires that its empirical squared norm criterion is not far from that of C...

---

Theorem 2. Vf E 2, #x11 I and
P.) w(C,, s.
then for any ò (0, there exists a constant and, with probability at least - 8, we have
k B[W(C.. P)] (T)) S sa log (Vn)
log
+ Ç.
From the above theorem, one can see that if the discrepancy between the empirical squared norm criterion of C₂ and C, small, that is ((ykkn)) the risk bound Cn is (nearly) optimal.
3.2 Further Results: k-means++
Lloyd's algorithm [40] is the most popular k-means algorithm and when coupled with careful k-means++ seeding a good approximate solution Cn can be obtained. Recently, based on a simple combination of k-means++ sampling and local search strategy, an improved k-means++ algorithm was proposed [25]. was shown that the empirical squared norm criterion of C, can be up to constant factor from the optimal empirical solution. For the completeness, we briefly describe
the improved k in the following, please refer to 25 for more details.
1: If [C] < k, add sampled point x E S with probability cost(()((x)),C)
ExEs cost( ()) where cost (Ost(P,C) -= Σ min D - c/l-
eEC
X.EP
and add (x) C.
2: If [C] 2 k, sample x E S with probability Exes cost ((V())) point E C such that
cost(fsb(x)) check whether there exists
cost(S, ( < cost(S,C).
If this is the case, we replace e by the point in C that reduces the cost function by the largest amount.
Note that we use the algorithm from 25 for kernel k-meaas by replacing the Euclidean distance ||x: 12 with | 2 s(x., x;) 2x(x;, x,) + x(x,: x,).
Lemma 2 (5)).. If C is returned by the improved k-means++ algorithm with local search strategy 25 then
EA(W(CA ((IW(CAAP,)) S 3. W(C,,,
where 3 is constant and A is the randomness derived from the k-means++ initialization.
In the following, we derive a risk bound for C,A.
Theorem 3. If'x E X, 1 xl S 1, and C is returned by the improved k-means++ algorithm with
local search strategy 255, then for any ó (0, 1), with probability at least 1 5, we have
Ep EA P)] Sō (V=+
The above result implies that if the optimal clustering risk W* is small, the risk of W(CA IP) can reach Ö (k/k))).
4 Risk Analysis of Nyström Kernel k-Means
Kernel k-means one of the most popular clustering methods. However, it requires the computation of n x kernel matrix. This renders it non-scalable large datasets that contain more than few

---

tens of thousands of points. In particular, simply constructing and storing the kernel matrix K takes O(n²) time and space.
The Nyström method 19 is popular method for approximating the kernel matrix. The properties of Nyström approximations for kernel k-means have recently been studied in [11
15 43
53 59
However, most of these works focus on the computation area. To the best of our knowledge, the only
study providing excess risk guarantees for the Nyström kernel k-means is (2] However, its excess risk bound is linearly dependent k. In the following, will improve it from & to vk.
4.1 Nyström Kernel k-Means
To derive the excess risk bound of Nyström kernel k means, we first briefly introduce some notations. Given dataset D = { J we use
I= ( mm C
as collection of landmark points to replace D. Let Hm be linear span of I {
Hm span Σ
o oj ER, B. EI
and Hith - Hm be its Cartesian product. The Nyström kernel k-means, i.c.. the approximate kernel k-means over H can be written as 1
C n.m. = arg min
Σ
min | -cyll cyll²
(3)
CE
The centroids Cn.m are still point in Hm C H. Let Km, E mmmm be the empirical kernel matrix between all points in I, and its eigen-decompositton is K Km, UAU. From (9) can search over Cr,, mac instead of searching over C E Hm, that is,
Čn,m arg min
min 1 - 2,11²
(4)
CERmxi n2
where d; := A -
= A 1 TT cj. 4 = ((())...... 4 (m(m)). x() E [L. m].
We can use any k-means algorithms solve Eq and then use the reverse of the relationship Cj == A U" m ey bring back the solution Hm, i.e. Cn,m. pm UA -1/2 This can be done in (nn)) space and Onmkk nm?) time using steps of Lloyd's algorithm for & clusters Please refer to for more details.
40
4.2
Excess Risk Bound of Nyström Kernel k-Means
Denote with E Tr(K (K + +)= the so-called effective dimension of K 49 Note that
Tr [K"TKK I)-1) S (K"(K)))
can obtain that = (Rank(K). Thus, the effective dimension E can be seen soft version of the rank.
Theorem 4. 1f E X, xx < 1, and the size of uniform sampling is
m Ω (118) min (k, E)
VT:
then, with probability at least 1 - 5, we have
B PJ] 21]-Wa (P) ( log 11
)7)

---

Note that
vn miink((,3)) S Vnk.
Thus, from statistical point, Theorem shows that when sampling (((vk)) points, the Nyström kernel k-means achieves the same excess risk as the exact one does. This result demonstrates that we can improve the computational aspect of kernel k-means using Nyström embedding, while maintaining optimal generalization guarantees.
Remark. Calandriello and Rosasco [ have reported that if m 2 [(vn), an excess risk bound of rate (kk for Nyström kernel k-means can be obtained, which seems to be better than our (Vnk). However, it should be noted that the risk bound in 9 is linearly dependent on k; while ours is linearly dependent on Vī. From the proof of Lemma 10 if we want to obtain risk of linear dependence on k, we only need
VTilog(1/0) min (k. E)
= (((v)),
k
which is the same as (9]. In the following, we will show that we can relax the restriction of landmark points under a mild condition.
4.3 Further Results: Reducing the Sampling Points
From Theorem 4 we know that need (((nk) sampling points to guarantee the nearly optimal rate for approximating kernel k-means. In the following, we show how to reduce the sampling points from (Vvnk) to ()(T)) under a basic assumption on the eigenvalues of the kernel matrix.
Theorem 5. Let X; be the i-th eigenvalue of the kernel matrix K, I,... n. and A411 S As.
Vx E X, xx S 1, the eigenvalues satisfy the assumption
3a 1, 0: 2 Sc
and the size of an uniform sampling
m 2 Ω (V
then, with probability at least 1 - 8. we have
(V
B[W(CC ( 50
k
log
n T
The assumption of algebraically decreasing eigenvalues of the kernel matrix is common assumption, and met by the popular finite rank kernels and shift invariant kernel [54), for example. The above results show that we can guarantee the optimal generalization performance when only sampling ((Vn) points, which is much better than Q2 ((vvk)) when k is large.
4.4 Further Results: Beyond ERM
In the following, show that result can be extended to general cases beyond ERM. Theorem 6. Under the same assumptions as Theorem 5 if
T [WCCC.,, Pn) - W(Cn,,, P.)] Sc
and the size of an uniform sampling
m 2 Ω (VVllg((1/8))
then, with probability at least 1 - 8, we have
EDW(Cn,m (P) - (vits).
The above result demonstrates that the risk bound of C..m is optimal when E WCC W(Cn.,, IP)) is small.
Pn)

---

k=20
k=40
empreci mncens
0.35
emprtiaa rorees fiec
opt mal tiee
optimal line
ft: Inc:
0.30
fitline:
0.00
0:25
0.06
0.04
0.10
2000
4000
5000
7000
5000
1000
2000
3000
5000
6000
7000
8000
K-80
Ic-1 1660
empir excess
ampliical excess fox
0.25
opt mal lie
0.35
optimall Inc: *
fitline
0.20
0.20
0.15
0.05
Figure 1: The empirical excess error of kernel k-means on the test set with different sizes of training data n and the number of clustering k. The blue line means the empirical excess error on the test with different sizes of training data. The dotted orange line means the optimal rate of theoretical findings. The dotted green line means the fit curve of the empirical excess error.
4.5 Further Results: k-means ++
adopting the improved k-kernel means++ sampling with local search strategy (25 for Nyström kernel k-means, we can obtain the following results:
Theorem 7. Under the same assumptions as Theorem 5 n.m. is returned by the improved k-
means++ + algorithm with local search strategy 125), the size of an uniform sampling is
m 2 Ω (Vnlog(1/6)).
then with probability least 1 8, we have
Ep EAMICA D.mm P)]] S Ô 50 ( (W===()):
where A is the randomness derived the k-means++ initialization.
The above result implies that if the optimal clustering risk W*(P) is small, i.e. (T(P) Ö(vk/m) the risk of W(CA W,, P) can reach ((vkkn)
5 Experiments
In this section, we will validate our theoretical findings by performing experiments on both simulated data and real data for kerne & k-means and approximate k-means.
5.1 Numerical Experiments
In this subsection, we will validate our theoretical findings by performing experiments on simulated data for kernel k-means and approximate k-means.

---

k=20
k=40
pmpical ecceus
ampitial Poress fhc
8.175
0.25
A.155
0.23
0.075
0.10
3.025
50
150
200
300
K-80
k-166
empii excess ASC
0.30
ampliical excass fox
angl 0000022
0.20
0.20
0.15
0.10
6.06
Figure The empirical excess enror of the approximate kernel k-means on the test with different uniform samplings m. The red star is the lower bound of the sampling landmarks, which, when increased, does not decrease the error.
Let c E R i I.....k, be the clustering centers, where the values of the 10 dimensions are 1 or -1 with equal probability. We generate the ith clustering samples C, from the normal distribution with mean oj and variance 2, |C1 =.. [Cxl In the experiments, we consider the popular Gaussian kernel
<(x, x') = exp (-
x
10
Based on the above construction method, it is easy verify that the optimal clustering risk is
W (P) -
min | 1c;1)xPP(x) = min j= 2(1 - <(x, d(P)).
Kernel k-Means
In the first experiment, we validate our theoretical findings of kernel k-means. We generate Σ C, samples of k clustering centers for training and 10,000 samples for testing. The empirical excess risk of kernel k-means on the test set can be written as
Σx minj==......
1xx
Dey 1| min.. Px - Peg 1|
[D.
where C, = [C1,.... cx] is the solution returned by the kernel k-means using Lloyd's ' algorithm 40]. and D; is the test set.
The empirical excess errors of kernel k-means on the test set with different sizes of training data and numbers of & are given in Figure We can see that the line of best fit for empirical excess risks is g0.32
R0.3T for k 160, achieving the predicted rate n0.55 (from Theorem which verifies our theoretical findings.
no.sy for k 20, m for t: = 40, अर for k 80, and g
g0448
20.49
ko.5
Approximate Kernel k-Means
In the second experiment, we validate our theoretical findings of approximate kernel k-means on simulated data.

---

The data generation rule is the same as that in the kernel k-means. We generate 10,000 samples (IC, 10000/k) for training and 10,000 samples for testing. The empirical excess errors of the approximate kernel k-means on the test set with different uniform samplings are given in Figure 2 which can be summarized as follows:
1) There exists lower bound of the sampling landmarks which does decrease the emror when increase its value. This verifies the theoretical statement in Theorem 4
2)
The lower bound of / increases with the number of the clusters k. This result confirms Theorem once again.
5.2 Real-World Scenarios
To reflect real-world scenarios, we add more experiments the real data sets. We use 6 publicly avaiable datasets, dna, segment, mushrooms, mnist, skin-nonskin and covtype, from the LIBSVM Data The empirical evaluations with Gaussian kernel
-
|x
x'1
Eig I|. xn
exp
,0
d
are given in the following table
where d is the dimension of x E X'
Table I: Experiments on the real data sets with kernel k-means and Nystöm kernel k-means (m = 100).
Dataset dna
Datasize
Kernel k-means
Nyström Kernel k-Means
2000
0.53
0.52
segment
2310
0.55
0.55
mushrooms
8124
0.66
0.65
mnist
60000
0.43
skin-nonskin 245057
0.63
covtype
581012
0.32
From the above results on real data sets, we can find that Nyström kernel k-means give the similar results as the original one, which also match the theoretical findings.
Conclusion
In this paper, we derive nearly optimal risk bounds for both kernel k-means and Nyström kernel k-means of learning rate of O(/k/n), which fills the gap ignoring the optimal risk bounds for (approximate) kernel k-means. Furthermore, we extend these results to general cases beyond ERM and k-means++. Our result may provide new perspective to study the optimal statistical properties of unsupervised learning.
In this paper we only derived the risk bounds of learning rate O( k(Vk/)) for the basic case. In the future, will consider studying whether it is possible to prove bound of O O(Vee/n) under certain strict assumptions.
Acknowledgment
This work is supported in part by the National Natural Science Foundation of China (No. 62076234, No.61703396. No.62106257). Beijing Outstanding Young Scientist Program Intelligent Social Governance Platform, Major Innovation & Planning Interdisciplinary Platform for the "Double-Firs Class" initiative, Renmin University of China, China Unicom Innovation Ecological Cooperation Plan, Public Computing Cloud of Renmin University of China.
"ttt://wwww.csc.atu.edde cjlin/libssm
10

---

References
[1] E. Abaya and G. Wise. Convergence of vector quantizers with applications to optimal quantiza- tion. SIAM Journal on Applied Mathematics, 44(1):183-189, 1984.
[2] D. Aloise, A. Deshpande, P. Hansen, and P. Popat. NP-hardness of Euclidean sum-of-squares clustering. Machine learning, 75(2):245-248, 2009.
[3] A. Antos, L. Gyorfi, and A. Gyorgy. Individual convergence rates in empirical vector quantizer design. IEEE Transactions Information Theory, (1(11):40134402 2005.
[4] D. Arthur and S. Vassilvitskii. K-means++: The advantages of careful seeding, In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1027-1035, 2007.
[5] F. Bach. On the equivalence between quadrature rules and random features. arXiv preprint 10X.v0050..06800 2015.
[6] Bach and M. Jordan. Predictive low-rank decomposition for kernel methods. Proceedings of the 22nd International Conference on Machine Learning (ICML), pages 33-40, 2005.
[7] P. Bartlett, T. Linder, and G. Lugosi. The minimax distortion redundancy in empirical quantizer design. IEEE Transactions Information Theory, 44(5):1802-188 1998.
[8] P. Bartlett and S. Mendelson. Rademacher and Gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3:463 482, 2002.
[9] D. Calandriello and L. Rosasco. Statistical and computational trade-offs in kernel k-means. In Advances in Neural Information Processing Systems (NeurIPS), pages 9357-9367, 2018.
[10] G. Canas, T. Poggio, and I.. Rosasco. Learning manifolds with k-means and k-flats. In Advances in Neural Information Processing Systems (NeurIPS), pages 2465-2473 2012.
[11] R. Chitta, R. Jin, Havens, and A. Jain. Approximate kernel k-means: Solution large scale kernel clustering. In Proceedings of the 17th ACM SIGKDD International Conference Knowledge Discovery and Data Mining (KDD), pages 895-903, 2011.
[12] R. Chitta, R. Jin, and A. Jain. Efficient kernel clustering using random fourier features. In Proceeding of 12th International Conference on Data Mining (ICDM), pages 161-170, 2012.
[13] P. Chou. The distortion of vector quantizers trained on n vectors decreases to the optimum as (1/n). In Proceedings of 1994 IEEE International Symposium on Information Theory, page 457, 1994.
[14] S. Clémençcon. On u-processes and clustering performance. Advances in Neural Information Processing Systems (NeurIPS), 24:37-45, 2011.
[15] M. Cohen, S. Elder, C. Musco, C. Musco, and M. Persu. Dimensionality reduction for k-means clustering and low rank approximation. In Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, pages 163-172, 2015.
[16] G. B. L. Devroye and G. Lugosi. On the performance of clustering in hilbert spaces. IEEE Transactions on Information Theory, 34(2):781-790) 2008.
[17] L. Devroye, L. Györfi, and G.Lugosi. Probabilistic Theory of Pattern Recognition. New York: Springer-Verlag. 1996.
[18] I. Dhillon, Y. Guan, and B. Kulis. Kernel k-means: spectral clustering and normalized cuts. In Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pages 551-556, 2004.
[19] P. Drineas and M. W. Mahoney. On the Nyström method for approximating a Gram matrix for improved kernel-based learning. Journal of Machine Learning Research, 6:2153-2175, 2005.
[20] C. Fefferman, S. Mitter, and H. Narayanan. Testing the manifold hypothesis. Journal of the American Mathematical Society, -994)99831 2016.

---

[21] D. Foster and A. Rakhlin. Eoo vector contraction for Rademacher complexity, arXiv preprint arXiv:1911.06468, 2019.
[22] U. Haagerup. The best constants in the khintchine inequality. Studia Mathematica, 70(3):231- 283, 1981.
[23] A. Jain. Data clustering: 50 years beyond k-means. Pattern Recognition Letters, (1()))6511666 2010.
[24] V. Koltchinskii. Local Rademacher complexities and oracle incqualities in risk minimization. The Annals of Statistics, 34(6):2593-2656 2006.
[25] S. Lattanzi and C. Sohler. A better k-means++ algorithm via local search. In Proceedings of 36th International Conference on Machine Learning (ICML), pages 3662-3671, 2019.
[26] Y. Lei, Ürün Dogan, D.-X. Zhou, and M. Kloft. Data-dependent generalization bounds for multi-class classification. IEEE Transactions Information Theory, 65(5):2995-3021, 2019.
[27] C. Levrard. Nonasymptotic bounds for vector quantization in Hilbert spaces. The Annals of Statistics, 43(2):592-619, 2015.
[28] J. Li, Y. Liu, and W. Wang. Distributed learning with random features. arXiv preprint 19Xiv=9906003155 2019.
[29] J. Li, Y. Liu, R. Yin, and W. Wang. Multi-class learning: From theory to algorithm. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
[30] S. Li and Y. Liu. Sharper generalization bounds for clustering, In Proceedings of 38th International Conference on Machine Learning (ICML), pages 6392-6402, 2021.
[3]] Z. Li, J.-F. Ton, D. Oglic, and D. Sejdinovic. Towards unified analysis of random fourier features. In Proceedings of the 36th International Conference Machine Learning (ICML), pages 3905-3914, 2019.
[32] Linder. On the training distortion of vector quantizers. IEEE Transactions on Information Theory, 1617):16 2000.
[33] T. Linder, G. Lugosi, and K. Zeger. Rates of convergence in the source coding theorem, empirical quantizer design, and in universal lossy source coding. IEEE Trunsactions on Information Theory, (0(6):1728-17444
1994.
[34] F. Liu, X. Huang. Y. Chen, and J. A. Suykens. Random features for kernel approximation: A survey in algorithms, theory, and beyond. arXiv preprint 1rXiv:2004.11154 2020.
[35] X. Liu. Incomplete multiple kernel alignment maximization for clustering, IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), 2021.
[36] X. Liu, M. Li, C. Tang, Xia, Xiong, L. Liu, M. Kloft, and E. Zhu. Efficient and effective regularized incomplete multi-view clustering. IEEE Transactions on Patlern Analysis and Machine Intelligence (TPAMI), 4308):2634-26466 2021.
[37] Y. Liu, Jiang, and S. Liao. Efficient approximation of cross-validation for kernel methods using bouligand influence function. In Proceedings of the 31st International Conference on Machine Learning (ICML), pages 324 332, 2014.
[38] Y. Liu, S. Liao, S. Jiang, L. Ding, H. Lin, and W. Wang. Fast cross-validation for kernel-based algorithms. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1083)-0083 2020.
[39] Y. Liu, Liu, and S. Wang. Effective distributed learning with random features: Improved bounds and algorithms. In Proceedings of the 9th International Conference on Learning Representations (ICLR), 2021.
[40] S. -loyd. Least squares quantization in pem. IEEE Transactions on Information Theory, (292):199-133 1982.
12

---

[41] A. Maurer and M. Pontil. k-dimensional coding schemes in hilbert spaces, IEEE Transactions on Information Theory, 56(11):5839-544 2010.
[42] B. Mirkin, Mathematical classification and clustering, volume 11. Springer Science & Business Media, 2013.
[43] D. Oglic and T. Gärtner. Nyström method with kernel k-means++ samples as landmarks. In Proceedings of the 34th International Conference on Machine Learning (ICML), pages JMLR. org, 2017.
[44] L. Oneto, A. Ghio, S. Ridella, and D. Anguita. Local Rademacher complexity: Sharper risk bounds with and without unlabeled samples. Neural Networks, 65:115-125, 2015.
[45] D. Pollard. Strong consistency of k-means clustering. The Annals of Statistics, pages 135-140. 1981.
[46] D. Pollard. A central limit theorem for k-means clustering. The Annals of Probability, 10(4):919- 926, 1982.
[47] D. Pollard. Quantization and the method of k-means. IEEE Transactions on Information Theory, 28(2):199-205, 1982.
[48] A. Rahimi and B. Recht. Random features for large-scale kemnel machines. In Advances in Neural Information Processing Systems (NeurIPS), pages 1177-1184, 2007.
[49] A. Rudi and L. Rosasco. Generalization properties of learning with random features. In Advances in Neural Information Processing Systems (NeurIPS), pages 3215-3225, 2017.
[50] B. Schölkopf and Smola. Learning with kernels: Support vector machines, regularization, optimization, and beyond. MIT Press, Cambridge, MA, USA, 2002.
[51] I. Steinwart and A. Christmann. Support Vector Machines. Springer Verlag, New York, 2008.
[52] V. Vapnik. The Nature of Statistical Learning Theory. Springer Verlag, 2000.
[53] S. Wang, A. Gittens, and M. W. Mahoney. Scalable kernel k-means clustering with nyström approximation: relative-error bounds. The Journal of Machine Learning Research, 20(1):43) 1::31- 2019.
[54] R. Williamson, A. Smola, and B. Scholkopf. Generalization performance of regularization networks and support vector machines via entropy numbers of compact operators. IEEE transactions on Information Theory, 47(6):2516-2532 2001.
[55] R. and Wunsch. Survey of clustering algorithms. IEEE Transactions on Neural Networks, 16(3):645667) 2005.
[56] R. Xu and D. Wunsch. Clustering, volume 10. John Wiley & Sons, 2008
[57] T. Yang, Y.-F. Li, M. Mahdavi, Jin, and Z.-H. Zhou. Nyström method random Fourier features: A theoretical and empirical comparison. In Advances in Neural Information Processing Systems (NeurIPS), pages 476 476,484,22 2012.
[58] R. Yin, Y. Liu, L. Lu, W. Wang, and D. Meng. Divide-and learning with Nyström: Op- timal rate and algorithm. In Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI), pages 6696-6703 2020.
[59] R. Yin, Y. Liu, W. Wang, and D. Meng. Distributed Nyström kernel learning with commu- nications. In Proceedings of 28th International Conference on Machine Learning (ICML), 2021.
[60] X. Zhang and S. Liao. Incremental randomized sketching for online kernel learning. In Proceedings of the 36th International Conference on Machine Learning (ICML), pages 7394- 7403, 2019.
[61] Y. Zhang, Zhang, Y. Wang, Z. Zhang, L. Zhang, S. Yan, and M. Wang. Dual-constrained deep semi-supervised coupled factorization network with enriched prior. International Journal of Computer Vision (ICCV), 2021.
13


Reviews:
[{"review_id": "wjSHN5LD_LI", "reviewer": "Reviewer_uDpd", "summary": "This manuscript derived nearly optimal risk bounds for both kernel k-means and Nystrom kernel k-means of learning rate of O(sqrt(k/n)), which is interesting and attractive.", "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": "Pros:\n1. Well-organized and clearly written, full and accurate understanding of related works.\n2. A (nearly) optimal excess clustering risk bound is proposed in this paper, which is the main contribution of it.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Cons: \n1. Weak innovation, all contributions and most of the results of this manuscript can also be found in the journal: Nearly Optimal Clustering Risk Bounds for Kernel K-Means, Machine Learning, arXiv:2003.03888.\n2. The Lemma3 mentioned in the main result and the Lemma10 mentioned in section 4.2 are not found in the script, making the result of this article unreliable.\n3. Weak experiments. The employed datasets are synthetic , clearly unable to reflect real-world scenarios.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "tw0"}, "extra_text": {}}, {"review_id": "nnRCZdXgPsQ", "reviewer": "Reviewer_Cavx", "summary": "The paper provides a nearly optimal bound for consistency of kernel $k$-means clustering and gives an approximation scheme based on the Nystrom method that allows one to perform scalable data quantization. More specifically, a new upper bound in $\\sqrt{\\frac{k}{n}}$ is obtained for the excess risk in kernel $k$-means, which improves the state-of-the-art excess risk bound in $\\frac{k}{\\sqrt{n}}$. The same bound for the Nystrom approximation of the algorithm are also provided.", "questions": "", "limitations": "", "rating": 8, "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": "The paper proposes a nearly optimal excess clustering risk bound is proposed for ERM, which is the first (nearly) optimal excess risk bound for kernel $k$-means in terms of both $k$ and $n$. It improves the bound from $\\frac{k}{\\sqrt{n}}$ to $\\sqrt{\\frac{k}{n}}$, which is a significant advancement. Moreover, the general cases beyond ERM are also considered. The paper also considers the computational aspects, i.e., the paper states the same bound for Nystrom approximation of the algorithm. These results are important for kernel $k$-means and are very interesting. The paper also provides some numerical experiments to demonstrate the theoretical results. In summary, I think this is a good and well-written theoretical paper which is helpful to who are interested in kernel methods or kernel $k$-means.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Here are some comments:\n1. It would be better to provide more intuition and clear descriptions of the proofs and the relations among them can help the reader better understand the content.\n2. In Line 207, the paper mentions \"improved $k$-kernel means++\". What's this? Is this improved $k$-means++ ? The paper should provide a brief introduction about this.\n3. It would be better to introduce the experimental results in more detail.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 days."}, "extra_text": {}}, {"review_id": "lyCCuh6OD-S", "reviewer": "Reviewer_vjeN", "summary": "The authors proposed optimal risk bound for clustering using kernel kmeans and Nystrom based kernel k-means. They improve the risk bound from k/sqrt(n) to sqrt(k/n).", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "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": "1. The paper is well organized and well written. \n2. The theoretical results are significant as the author shows near-optimal risk bounds. \n\n\n----\nI appreciate for the response and increase my final score. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "1. An overview of the algorithm in the main paper or supplementary would be beneficial.\n2. Some more experiments on larger real data set would have been better.\n3. Regrading the sample size in theorem-4 & 5: The notion of statistical dimension is also used to show importance sampling-based spectral property approximation \"Avron H, Clarkson KL, Woodruff DP. Sharper Bounds for Regularized Data Fitting. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. 2017 Aug\". Do you think a similar sampling technique can be used here to get a better sample size?\n4. Although the authors acknowledge about \"discussing limitations\" however, I did not find any discussion. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5-6"}, "extra_text": {}}, {"review_id": "QqOESn7jTku", "reviewer": "Reviewer_SaBc", "summary": "In this paper, the authors provide a near-optimal risk bound for kernel $k$-means, namely $\\tilde{O}(\\sqrt{k/n})$, which improves upon the existing risk bound $O(k/\\sqrt{n})$, and nearly matches the lower bound $\\Omega(\\sqrt{k/n})$, where $k$ is the number of clusters and $n$ is the size of the training set. They first derive a near-optimal risk bound for the empirical risk minimizer (ERM) and then extend it to general cases beyond ERM and $k$-means++. For efficiency, the authors also provide near-optimal risk bounds for Nyström kernel $k$-means for the case of using $\\tilde{\\Omega}(\\sqrt{n})$ sampling points. The authors have performed numerical experiments to validate their theoretical findings. ", "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": "My impression is that this is an interesting work with solid theoretical contributions, so overall I am inclined to accept. Some minor comments are listed as follows:\n\n1. Mentioning that $k$ is the number of clusters and $n$ is the size of the training set in the abstract.\n\n2. The authors should check all the notations used in the main document carefully. For example, in Section 2.1, the definition of the empirical distribution $\\mathbb{P}_n(\\mathcal{S})$ at Line 73 is problematic because it always equals $1$. Line 82, $\\mu = \\Omega(\\nu)$ does not mean $c_1 \\nu \\le \\mu \\le c_2 \\nu$. \n\n3. For brevity, some notations/equations that are never used in the main body can be omitted or be placed in the supplementary material. For example, \\mathcal{W}(\\mathbf{C}, \\mathbb{P}_n)  does not need to be expanded as the equation between Eqs. (1) and (2). The definitions of f_{\\mathbf{C}} and \\mathcal{F}_{\\mathbf{C}} (Eq. (3)) are never used in the main document. In fact, I think the content between Lines 92 and 98 can all be removed (or move to the supplementary material). The notation $\\mathcal{E}(\\mathbf{C}_n)$ (excess clustering risk) has never been used in the statements of the theorems. \n\n4. Line 103, the authors should not use $\\mathbf{C}$ to represent the collection of centroids corresponding to the lower bound. Perhaps renaming it as $\\mathbf{C}_{lb}$. The authors should add \"for example\" before presenting Lemma 1. \n\n5. Between Lines 170 and 171, removing  \"span\" in the definition of $\\mathcal{H}_m$. \n\n6. Checking the format of all the references in the References section. For example, in [2], it should be \"NP-hardness of Euclidean\". In [8], \"risk\" should be \"Risk\". ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "As mentioned in the Checklist, the limitations have been addressed and potential negative societal impact is not applicable.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The work presents nearly optimal bounds for the excess clustering risk of kernel k-means, improving the rate of convergence from k/sqrt(n) to sqrt(k/n), and also shows that approximate (Nystrom with uniform sampling of sqrt(nk) landmark points) has the same order of excess clustering risk. This theoretical result is a strong contribution and of great relevance to the community.
Decision: Accept (Spotlight)