Refined Learning Bounds for Kernel and Approximate k-Means
Year: 2022

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 O(k/ √ n), which do not match with the stated lower bound Ω( √ 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ö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 O( √ 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öm kernel k-means, and prove that it achieves the same statistical accuracy as the original kernel k-means considering only Ω( √ nk) Nyström landmark points. We further relax the restriction of landmark points from Ω( √ nk) to Ω( √ n) under a mild condition. Finally, we validate the theoretical findings via numerical experiments.

text: √ n), which do not match with the stated lower bound Ω( √ 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ö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 O( √ 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öm kernel k-means, and prove that it achieves the same statistical accuracy as the original kernel k-means considering only Ω( √ nk) Nyström landmark points. We further relax the restriction of landmark points from Ω( √ nk) to Ω( √ n) under a mild condition. Finally, we validate the theoretical findings via numerical experiments.

heading: 1 Introduction
text: Clustering, a fundamental data mining task, is used in numerous applications including web search, medical imaging, gene expression analysis, social network analysis and recommendation systems [56, 55, 23, 42]. k-means is arguably one of the most popular approaches to 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 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, 1]. Rates of convergence and non-asymptotic performance bounds were considered by [46, 13, 33, 7, 32, 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, a clustering risk bound of orderO( √ kd/n), 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 infinite-dimensional Hilbert space, such as the reproducing kernel Hilbert space (RKHS) associated with Gaussian kernels [50]. Thus, the existing theoretical analysis of k-means are not usually suitable for explaining its kernel version. Recently, [20, 16, 10, 41, 3, 27, 24, 9] extended the previous results, and provided dimension-independent bounds for kernel k-means. As shown in [16], if the feature map associated with the kernel function satisfies ‖Φ‖ ≤ 1, then the clustering risk bounds are of order O(k/ √ n). These clustering risk bounds for kernel k-means are usually linearly
35th Conference on Neural Information Processing Systems (NeurIPS 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 O(k/ √ n) do not match with the stated lower bound Ω( √ k/n) in k [7].
Although kernel k-means is one of the most popular clustering methods, it requires the computation of a n × 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], random projection [16, 15], Nyström approximations [19, 11, 9, 43, 53, 58, 57], and random feature approximations [48, 12, 5, 49, 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 [16], 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 Ω( √ n) Nyström landmarks, the excess risk bound can reach O(k/ √ n). The excess risk bounds of [9] and [16] are both linearly dependent on k and thus do not match with the theoretical lower bound [7].
In the recent work [21], the authors showed that the Rademacher complexity of the k-valued function 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( √ k). Although it may be not very difficult to use the result of [21] for kernel k-means, the optimal
bound of O( √ k/n) for kernel k-means 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 Õ( √ k/n)1 is proposed for empirical
risk minimization (ERM) (see Theorem 1). To the best of our knowledge, this is the first (nearly) optimal excess risk bound for kernel k-means in terms of both k and n. Beyond ERM, we further extend the result of Theorem 1 to general cases (see Theorem 2 and Theorem 3).
2) A (nearly) optimal excess risk bound for Nyström kernel k-means is also obtained when sampling Ω( √ nk) points (see Theorem 4). We further relax the restriction of landmark
points from Ω( √ nk) to Ω( √ n) (see Theorem 5) and extend it to general cases (see Theorem 6 and Theorem 7). This result shows that we can use the Nyström method to improve the effectiveness of 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-based kernel k-means. In Section 5, we validate our theoretical findings by performing experiments on both simulated and real data. We end in Section 6 with conclusion. All the detailed proofs are deferred to the Appendix.

heading: 2 Background
text: In this section, we will introduce some notations and provide a brief introduction of kernel k-means. Please refer to [18, 9] for more details.

heading: 2.1 Notations
text: Assume P is a (unknown) distribution on X , and S = {xi}ni=1 ∈ X is a set of n samples drawn i.i.d. from P. The empirical distribution Pn is denoted as Pn(x) = 1n if x ∈ S, otherwise 0. Let κ : X ×X → R be a mercer kernel [51], andH be its associated RKHS [52], which is the completion of the linear span of the set of functions:
H = span{κ(x, ·),x ∈ X}. We denote the Cartesian product of H by Hk = ⊗ki=1H. We use the feature map ψ : X → H to map X into the Hilbert spaceH, and assume thatH is separable, such that for any x ∈ X , we have
1Õ hides logarithmic terms.
Φx = ψ(x). Intuitively, in the rest of the paper, the reader can assume that Φx ∈ Rd with d n or even infinite. From here on, we will denote the inner product ofH by 〈·, ·〉, and the associated norm by ‖ · ‖, and assume that ‖Φx‖ ≤ 1 for any x ∈ X . We let
D = {Φi = ψ(xi)}ni=1 ,
and denote [K]i,j = κ(xi,xj) = 〈Φi,Φj〉 as the kernel matrix. The notations µ = O(ν) and µ = Ω(ν) mean that there exist constants c, c1, c2 such that µ ≤ cν and c1ν ≤ µ ≤ c2ν, respectively. We use Õ and Ω̃ to hide logarithmic terms.
2.2 Kernel k-Means
In this paper, we aim at partitioning the given dataset into k disjoint clusters, each characterized by its centroid cj . The Voronoi cell associated with a centroid cj is defined as [9]
Cj := { i : j = arg min
s=1,...,k ‖Φi − cs‖2
} .
Let C = [c1, . . . , ck] be a collection of k centroids fromHk. In this paper, we focus on the so-called kernel k-means clustering, by minimizing the empirical squared norm criterion
W(C,Pn) := 1
n n∑ i=1 min j=1,...,k ‖Φi − cj‖2 (1)
over all possible choices of cluster centers C ∈ Hk. From [18, 9], we know thatW(C,Pn) can be written as
W(C,Pn) : = 1
n min C∈Hk k∑ j=1 ∑ i∈Cj ∥∥∥∥∥∥Φi − 1|Cj | ∑ t∈Cj Φt ∥∥∥∥∥∥ 2
= 1
n min C∈Hk k∑ j=1 ∑ i∈Cj κ(xi,xi)− 2|Cj |∑ t∈Cj κ(xi,xt) + 1 |Cj |2 ∑ t,t′∈Cj κ(xt,xt′)  . The empirical risk minimizer (ERM) is defined as
Cn := arg min C∈Hk
W(C,Pn). (2)
The performance of a clustering scheme given by the collection C = [c1, . . . , ck] ∈ Hk of cluster centers is usually measured by the expected squared norm criterion or expected clustering risk
W(C,P) := ∫
min j=1,...,k
‖Φx − cj‖2dP(x).
Given a C ∈ Hk, let fC = (fc1 , . . . , fck) be a k-valued function of the collection C with fcj (x) = ‖Φx − cj‖2. Let ϕ : Rk → R be a minimum function. From the definition of ϕ(fC(x)) = min(fc1(x), . . . , fck(x)), one can see that the empirical and expected squared norm criteria can be respectively written as
W(C,Pn) := 1
n n∑ i=1 ϕ(fC(xi)) andW(C,P) := ∫ ϕ(fC(x))dP(x).
In this paper, we consider bounding the excess clustering risk E(Cn) of the empirical risk minimizer [16]:
E(Cn) := ED[W(Cn,P)]−W∗(P),
whereW∗(P) = infC∈HkW(C,P) is the optimal clustering risk. In the following, we will ignore the subscript D if the input dataset D is clear.

heading: 2.3 The Existing Excess Clustering Risk Bounds
text: According to [7], we know that there exists a collection of centroids Clb ∈ Hk, a constant c, and a distribution P with ‖Φx‖ ≤ 1 for any x ∈ X , such that
E[W(Clb,P)]−W∗(P) ≥ c √ k1−4/d
n .
Note that d is the dimension of Φx, which is usually very large or even infinite. Thus, the lower bound of kernel k-means is Ω (√ k/n ) . However, most of the existing risk bounds proposed for kernel k-means are O(k/ √ n) [16, 10, 41, 20, 9], for example:
Lemma 1 ([16], Theorem 2.1). If ‖Φx‖ ≤ 1 for any x ∈ X , then there exists a constant c such that
E[W(Cn,P)]−W∗(P) ≤ c k√ n ,
where Cn is the ERM ofW(C,Pn) defined in (2).
Note that the number of clusters k may be very large for fine-grained analyses in social networks or recommendation systems. This leaves us with the question: is it possible to prove a bound of rate√ k/n, which is (nearly) optimal in terms of both k and n? In this paper, we attempt to answer this.

heading: 3 Main Results
text: 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 of [16, 9] are all linearly dependent on k. Based on a recently improvement of the upper bound of Rademacher complexity of L-Lipschitz with respect to the L∞ norm [21], we derive a (nearly) optimal excess risk bound of linearly dependent on √ k. Theorem 1. If ∀x ∈ X , ‖Φx‖ ≤ 1, then for any δ ∈ (0, 1), there exists a constant c, and with probability at least 1− δ, we have,
E[W(Cn,P)]−W∗(P) ≤ c √k n log2 (√ n ) + √ log 1δ n  . From Theorem 1, we know that
E[W(Cn,P)]−W∗(P) ≤ Õ
(√ k
n
) ,
which matches the theoretical lower bound Ω (√ k/n )
when d is large [7]. Thus, our proposed bound is (nearly) optimal.
Remark (Fast Rates). Some results suggest that the learning rate of kernel k-means can reach O(k/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 rateO(k/n). An improved result was obtained by [3], who proved that the learning rate can reach O(k/n) for any distribution supported on a finite set. Levrard [27] further showed that, if the distribution satisfies a margin condition, the learning rate can also reach O(k/n). Based on the notion of local Rademacher complexity, the expected excess risk has a rate faster than O(k/ √ n) given in [24, 30]. However, as pointed out, these conditions are difficult to verify in general. Moreover, these expected excess risk bounds are linearly dependent on k. In the future, we will consider studying whether it is possible to prove a bound of O( √ k/n) under certain strict assumptions.

heading: 3.1 Further Results: Beyond ERM
text: So far we have provided guarantees for Cn, that is, the optimal ERM inHk. Note that obtaining the optimal ERM Cn is a NP-hard problem in general [2]. In the following, we will consider the risk bound for a general C̃n, which only requires that its empirical squared norm criterion is not far from that of Cn.
Theorem 2. If ∀x ∈ X , ‖Φx‖ ≤ 1 and E [ W(C̃n,Pn)−W(Cn,Pn) ] ≤ ζ,
then for any δ ∈ (0, 1), there exists a constant c and, with probability at least 1− δ, we have
E[W(C̃n,P)]−W∗(P) ≤ c √ k
n log2
(√ n ) + c √ log 1δ n + ζ.
From the above theorem, one can see that if the discrepancy between the empirical squared norm criterion of C̃n and Cn is small, that is ζ ≤ O( √ k/n), the risk bound of C̃n is (nearly) optimal.
3.2 Further Results: k-means++
Lloyd’s algorithm [40] is the most popular k-means algorithm and when coupled with a careful k-means++ seeding [4], a good approximate solution C̃n can be obtained. Recently, based on a simple combination of k-means++ sampling and a local search strategy, an improved k-means++ algorithm was proposed [25]. It was shown that the empirical squared norm criterion of C̃n can be up to a constant factor from the optimal empirical solution. For the completeness, we briefly describe the improved k-means++ in the following, please refer to [25] for more details.
1: If |C| < k, add a sampled point x ∈ S with probability
cost({ψ(x)}, C)∑ x∈S cost({ψ(x)}, C) , where cost(P, C) = ∑ xi∈P min c∈C ‖Φi − c‖,
and add ψ(x) to C.
2: If |C| ≥ k, sample x ∈ S with probability cost({ψ(x)},C)∑ x∈S cost({ψ(x)},C)
, check whether there exists a point c ∈ C such that
cost(S, C\{c} ∪ {ψ(x)}) < cost(S, C).
If this is the case, we replace c 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-means by replacing the Euclidean distance ‖xi − xj‖2 with ‖Φi − Φj‖2H = κ(xi,xi)− 2κ(xi,xj) + κ(xj ,xj). Lemma 2 ([25]). If CAn is returned by the improved k-means++ algorithm with a local search strategy [25], then
EA[W(CAn ,Pn)] ≤ β · W(Cn,Pn),
where β is a constant and A is the randomness derived from the k-means++ initialization.
In the following, we derive a risk bound for CAn . Theorem 3. If ∀x ∈ X , ‖Φx‖ ≤ 1, and CAn is returned by the improved k-means++ algorithm with a local search strategy [25], then for any δ ∈ (0, 1), with a probability at least 1− δ, we have
ED [ EA[W(CAn ,P)] ] ≤ Õ
(√ k
n +W∗(P)
) .
The above result implies that if the optimal clustering riskW∗(P) is small, the risk ofW(CAn ,P) can reach Õ( √ k/n).
4 Risk Analysis of Nyström Kernel k-Means
Kernel k-means is one of the most popular clustering methods. However, it requires the computation of a n× n kernel matrix. This renders it non-scalable to large datasets that contain more than a few
tens of thousands of points. In particular, simply constructing and storing the kernel matrix K takes O(n2) time and space.
The Nyström method [19] is a 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, 9, 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 [9]. However, its excess risk bound is linearly dependent on k. In the following, we will improve it from k to √ k.
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 a dataset D = {Φi}ni=1, we use
I = {Φi}mi=1 ⊆ D
as a collection of landmark points to replace D. LetHm be a linear span of I = {Φi}mi=1,
Hm = span { m∑ i=1 αiΦi, αi ∈ R,Φi ∈ I } ,
and Hkm = ⊗ki=1Hm be its Cartesian product. The Nyström kernel k-means, i.e., the approximate kernel k-means overHkm, can be written as [9]:
Cn,m = arg min C∈Hkm
1
n n∑ i=1 min j=1,...,k ‖Φi − cj‖2 . (3)
The centroids Cn,m are still point inHm ⊂ H. Let Km,m ∈ Rm×m be the empirical kernel matrix between all points in I, and its eigen-decomposition is Km,m = UΛU. From [9], we can search over C̃n,m ∈ Rm×k instead of searching over C ∈ Hkm, that is,
C̃n,m = arg min C̃∈Rm×k
1
n n∑ i=1 min j=1,...,n ‖Φ̃i − c̃j‖2, (4)
where Φ̃i := Λ−1/2UTΦTmΦi, c̃j := Λ −1/2UTΦTmcj , Φm = [Φπ(1), . . . ,Φπ(m)], π(i) ∈ [1,m]. We can use any k-means algorithms to solve Eq.4, and then use the reverse of the relationship c̃j := Λ
−1/2UTΦTmcj to bring back the solution toHm, i.e., Cn,m = ΦmUΛ−1/2C̃n,m. This can be done in O(nm) space and O(nmkt+ nm2) time using t steps of Lloyd’s algorithm for k clusters [40]. Please refer to [9] for more details.
4.2 Excess Risk Bound of Nyström Kernel k-Means
Denote with Ξ = Tr(KT(K + I)−1) the so-called effective dimension of K [49, 9]. Note that
Tr ( KT(K + I)−1 ) ≤ Tr ( KT(K)+ ) ,
so we can obtain that Ξ ≤ Rank(K). Thus, the effective dimension Ξ can be seen as a soft version of the rank.
Theorem 4. If ∀x ∈ X , ‖Φx‖ ≤ 1, and the size of a uniform sampling is m ≥ Ω (√
n log(1/δ) min(k,Ξ)√ k
) ,
then, with probability at least 1− δ, we have
E[W(Cn,m,P)]−W∗(P) ≤ O
(√ k
n log (n δ )) .
Note that √ nmin(k,Ξ)√
k ≤ √ nk.
Thus, from a statistical point, Theorem 4 shows that when sampling Ω̃( √ nk) 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 [9] have reported that if m ≥ Ω̃( √ n), an excess risk bound of rate Õ(k/ √ n) for Nyström kernel k-means can be obtained, which seems to be better than our Ω̃( √ nk). However, it should be noted that the risk bound in [9] is linearly dependent on k, while ours is linearly dependent on √ k. From the proof of Lemma 10, if we want to obtain a risk of linear dependence on k, we only need
m ≥ Ω (√ n log(1/δ) min(k,Ξ)
k
) = Ω̃( √ n),
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.

heading: 4.3 Further Results: Reducing the Sampling Points
text: From Theorem 4, we know that we 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 Ω̃( √ nk) to Ω̃( √ n) under a basic assumption on the eigenvalues of the kernel matrix.
Theorem 5. Let λi be the i-th eigenvalue of the kernel matrix K, i = 1, . . . , n, and λi+1 ≤ λi. If ∀x ∈ X , ‖Φx‖ ≤ 1, the eigenvalues satisfy the assumption
∃α > 1, c > 0 : λi ≤ ci−α, and the size of an uniform sampling is
m ≥ Ω (√ n log(1/δ) ) .
then, with probability at least 1− δ, we have
E[W(Cn,m,P)]−W∗(P) ≤ O
(√ k
n log (n δ )) .
The assumption of algebraically decreasing eigenvalues of the kernel matrix is a 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 Ω̃( √ n) points, which is much better than Ω̃( √ nk) when k is large.

heading: 4.4 Further Results: Beyond ERM
text: In the following, we show that our result can be extended to general cases beyond ERM. Theorem 6. Under the same assumptions as Theorem 5, if
E [ W(C̃n,m,Pn)−W(Cn,m,Pn) ] ≤ ζ,
and the size of an uniform sampling is m ≥ Ω (√ n log(1/δ) ) ,
then, with probability at least 1− δ, we have
E[W(C̃n,m,P)]−W∗(P) ≤ Õ
(√ k
n + ζ
) .
The above result demonstrates that the risk bound of C̃n,m is optimal when E [ W(C̃n,m,Pn) −
W(Cn,m,Pn) ] is small.
4.5 Further Results: k-means ++
If adopting the improved k-kernel means++ sampling with a 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, CAn,m is returned by the improved kmeans++ algorithm with a local search strategy [25], if the size of an uniform sampling is
m ≥ Ω (√ n log(1/δ) ) ,
then with probability at least 1− δ, we have
ED [ EA[W(CAn,m,P)] ] ≤ Õ
(√ k
n +W∗(P)
) ,
where A is the randomness derived from the k-means++ initialization. The above result implies that if the optimal clustering riskW∗(P) is small, i.e. W∗(P) ≤ Õ( √ k/n),
the risk ofW(CAn,m,P) can reach Õ( √ k/n).

heading: 5 Experiments
text: In this section, we will validate our theoretical findings by performing experiments on both simulated data and real data for kernel k-means and approximate k-means.

heading: 5.1 Numerical Experiments
text: In this subsection, we will validate our theoretical findings by performing experiments on simulated data for kernel k-means and approximate k-means.
Let c∗i ∈ R10, i = 1, . . . , 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 Ci from the normal distribution with mean c∗i and variance 2, |C1| = . . . = |Ck|. In the experiments, we consider the popular Gaussian kernel
κ(x,x′) = exp ( −‖x− x ′‖2
10
) .
Based on the above construction method, it is easy to verify that the optimal clustering risk is W∗(P) = ∫
min j=1,...,k
‖Φx − Φc∗j ‖ 2dP(x) =
∫ min
j=1,...,k 2(1− κ(x, c∗j ))dP(x).
Kernel k-Means In the first experiment, we validate our theoretical findings of kernel k-means. We generate ∑k i=1 |Ci| 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∑
xi∈Dt minj=1,...,k ‖Φxi − Φcj‖ 2 −minj=1,...,k ‖Φxi − Φc∗j ‖ 2
|Dt| ,
where Cn = [c1, . . . , ck] is the solution returned by the kernel k-means using Lloyd’s algorithm [40], and Dt 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 k are given in Figure 1. We can see that the line of best fit for empirical excess risks is k0.48
n0.53 for k = 20, k0.52 n0.49 for k = 40, k0.49 n0.51 for k = 80, and k0.50
n0.51 for k = 160, achieving the predicted rate k 0.5
n0.5 (from Theorem 1), which verifies our theoretical findings.
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 (|Ci| = 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 m are given in Figure 2, which can be summarized as follows:
1) There exists a lower bound of the sampling landmarks l which does not decrease the error when increase its value. This verifies the theoretical statement in Theorem 4.
2) The lower bound of l increases with the number of the clusters k. This result confirms Theorem 4 once again.

heading: 5.2 Real-World Scenarios
text: To reflect real-world scenarios, we add more experiments on the real data sets. We use 6 publicly avaiable datasets, dna, segment, mushrooms, mnist, skin-nonskin and covtype, from the LIBSVM Data 2. The empirical evaluations with Gaussian kernel
exp ( −‖x− x ′‖2
σ2
) , σ = √∑ ij ‖xi − xj‖2
d ,
are given in the following table 1, where d is the dimension of x ∈ X .
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.

heading: 6 Conclusion
text: 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 a 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/n) for the basic case. In the future, we will consider studying whether it is possible to prove a bound of O( √ k/n) under certain strict assumptions.

heading: Acknowledgment
text: 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 NO.BJJWZYJH012019100020098, Intelligent Social Governance Platform, Major Innovation & Planning Interdisciplinary Platform for the "Double-First Class" initiative, Renmin University of China, China Unicom Innovation Ecological Cooperation Plan, Public Computing Cloud of Renmin University of China.
2http://www.csie.ntu.edu.tw/ cjlin/libsvm

Review summaries:
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. 

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.