Coresets for Kernel Clustering
Authors: Shaofeng H.-C. Jiang
Robert Krauthgamer
Jianing Lou
Yubo Zhang
Venue: ICLR 2022 Submitted (2022)
Keywords: coreset
clustering
kernel
PTAS
streaming
spectral clustering
k-means

Abstract: We devise the first coreset for kernel $k$-Means, and use it to obtain new, more efficient, algorithms. Kernel $k$-Means has superior clustering capability compared to classical $k$-Means particularly when clusters are separable non-linearly, but it also introduces significant computational challenges. We address this computational issue by constructing a coreset, which is a reduced dataset that accurately preserves the clustering costs.

Our main result is the first coreset for kernel $k$-Means, whose size is independent of the number of input points $n$, and moreover is constructed in time near-linear in $n$. This result immediately implies new algorithms for kernel $k$-Means, such as a $(1+\epsilon)$-approximation in time near-linear in $n$, and a streaming algorithm using space and update time $\mathrm{poly}(k \epsilon^{-1} \log n)$. 

We validate our coreset on various datasets with different kernels. Our coreset performs consistently well, achieving small errors while using very few points. We show that our coresets can speed up kernel $k$-Means++ (the kernelized version of the widely used $k$-Means++ algorithm), and we further use this faster kernel $k$-Means++ for spectral clustering. In both applications, we achieve up to 1000x speedup while the error is comparable to baselines that do not use coresets.

CORESETS FOR KERNEL CLUSTERING
Anonymous authors Paper under double-blind review
ABSTRACT
We devise coresets for kernel k-MEANS with general kernel, and them obtain new, more efficient, algorithms. Kernel k-MEANS has superior clustering capability compared to classical k-MEANS, particularly when clusters are separa- ble non-linearly, but it also introduces significant computational challenges. We address this computational issue by constructing coreset, which reduced dataset that accurately preserves the clustering costs.
Our main result is the first coreset for kernel l- k-MEANS with general kerne,, that has size independent of n, the number of input points; moreover, our coreset can be constructed in time near-linear in This result immediately implies new algo- rithms for kernel k- E-MEANS, such as a (1 apapproximationn in time near-lineat in n, and a streaming algorithm using space and update time poly llg n))
We validate our coreset on various datasets with different kernels. Our coreset per- forms consistently well, achieving small errors while using very few points. We show that our coresets can speed up kernel k- 6-MEANS++ (the kernelized version of the widely used k- 6-MEANS++ algorithm),, and we further use this faster kernel k- t-MEANS++ for spectral clustering. In both applications, we achieve up to 1000x speedup while the error is comparable to baselines that do not coresets.
INTRODUCTION
We design the first coresets, and consequently new efficient algorithms, for kernel k-MEANS and related problems. like its generalization kernel (k, -)LLSSTERIN under general kernels. The k- MEANS problem has proved to be fundamental for unsupervised learning in numerous application domains. Vanilla k-MEANS fails capture sophisticated cluster structures, e.g., when the clusters are separable non-linearly, but this can be tackled by applying kernel methods (Schölkopf et al., 1998: Girolami, 2002). This has led kernel k- ME-MENS, where data points are first mapped high-dimensional feature space (possibly implicitly via kernel function), and then clustered in this richer space using a classical k:MMENSS.
Formally, kernel for a dataset X is a function K X x X + R, (intended to measure similarity between elements in X) that can be realized by inner products, i.e., there exist Hilbert space H and map xp: X + H (called feature space and feature map) such that
Vx, y E X, (p(x), p(v)) = K(r,y).
In kernel i-- 6-MEANS, the input is dataset with weight function wx X + R4 and kernel function K : X X + R, as above, and the goal is to find k-point center set C' C H. that minimizes the objective
cost 9 (0,,((X))))))
Σ wx(x) min [1)(()) - cll2. ZEX
dEC
(An equivalent formulation asks for a d-partitioning of X. keeping C' implicit.)
This kernel version has superior clustering capability compared to classical k-MEANS (Zhang & Rudnicky, 2002; Kim et al., 2005), and has proved useful in different application domains, such as pattern recognition (Shawe- Taylor Cristianini, 2004), natural language processing (Andrews & Fox, 2007), biology (Gönen & Margolin, 2014) and social networks (van Laarhoven & Marchiori, 2016). In fact, kernel k-MEANS is useful also for solving other clustering problems, such as nor- malized cut and spectral clustering (Dhillon et al., 2004; Ding et al., 2005).

---

Computational challenges. As observed in previous work (Girolami, 2002; Dhillon et al., 2004), the kernel trick can be applied to rewrite kemel k M-MAS using access only to the kernel (:.)) and without computing the very high- high-dimensional map y explicitly. However, this approach has out- standing computational challenges (compared to classical k-MRANS), essentially because of the ker- nel trick. Consider the special case where k 1 and the input is n unweighted points (i.e., 1-MRAN clustering). It is well known that the optimal center c* has a closed form c* ;= #Z f(r). But the kernel trick requires Q(n²)) accesses to K to evaluate cost (xx (X)" while in the classical setting such evaluation needs only (()) distance computations.
This ((n²) barrier can be bypassed by allowing (1 + >>approximation, In particular, let S be uniform sample of poly(c-1 points from X, and let == [ST Ezes (f(x) be its 1-MEAN; then with high probability, cost* S (1 + e) cost (Xs, c*)) and evaluating cost*(X, ê) takes only poly(e-)) n time. However, this uniform-sampling approach does not generally work for k 2 2, because if the optimal clustering is highly imbalanced, a uniform sample is unlikely to include any point from a small cluster. Alternative approaches, such as dimension reduction, were also proposed to obtain efficient algorithms for kernel k-MEANS, but they too do not fully resolve the computational issue. We elaborate on these approaches in Section 1.2.
Our approach. To tackle this computational challenge, we adapt the notion of coreset (Har- Peled & Mazumdar, 2004) to kernel k-MEANS. Informally, a coreset is tiny reweighted subset of the original dataset on which the clustering cost is preserved within (1 + e) factor for all candidate centers C' C H. This notion has proved very successful for classical k-MEANS, e.g., to design efficient near-linear algorithms. In our context of kernel k-MEANS, a coreset of size s for an input of size |X] has a huge advantage that its is optimal center points can all be represented as linear combinations of only s points in the feature space. Given these optimal centers (as linear combinations), evaluating the distance between point s0(x) and such center takes merely (ss2) time, instead of O(n²), ), and consequently the objective can be -approxiiaitt in time Osskkm) Moreover, suffices to use & centers (again as linear combinations) that are (1 + e>aapproximately optimal for the coreset S.
In addition, coresets are very useful in dealing with massive datasets, since an offline construc- tion of coresets usually generalizes to the streaming setting (Har-Peled & Mazumdar, 2004), dis- tributed computing (Balcan et al., 2013) and dynamic algorithms (Henzinger & Kale, 2020) via the merge-and red-uuc method (Har-Peled & Mazumdar, 2004), and existing (offline) algorithms can be efficiently applied to the coreset, instead of to the original dataset, with minor or no modifications.
1.1
OUR RESULTS
Our main result is the first coreset for kernel k-MEANS with a general kernel, that has size inde- pendent of the input size n = |X|: moreover, our coreset can be constructed in near-linear time for small k. (In fact, generalizes to kernel (k, E)CLLSSTERING see Section 2 for definitions.) Formally, an e-coreset for kernel k- K-MEANS with respect to weighted dataset X and kernel function K : X x X + 2 is a weighted subset S C X, such that for every feature space and feature map yp that realize K, as defined in (1),
AC H. CI = k,
cO, E (1 cost (X,
Previously, only weak coreset was known for kernel k-MEANS (Feldman et al., 2007). meaning that the objective preserved only for certain candidate centers (whereas (3) guarantees this for all centers), and that coreset works only for certain kernels (fnite-dimensionaa), While employ similar approach, the technical differences make our bottom- result much stronger.
Throughout, we assume an oracle access to K takes unit time, and therefore stated running times also bound the number of accesses to K. We denote Ö(J) = O( polylog J) to suppress logarithmic factors.
Theorem 1.1 (Informal version of Theorem 3.1). Given n-point weighted dataset X, oructe access to a kernel K X x X - R4, integer 2 and 0 < 6 < 1, one can construct in time Ö(nk),
IIn fact, evaluating ||e* (2m)]] for single point X already requires ((n?) accesses, since ||c* ((())l (u,,u) 2 =Σ Exex K( u) + Ezvex K(2,
2

---

reweighted subset S S X of size |S| = poly(ke")). that with high probability is c-coreset for kernel K-MEANS with respect to and K.
We can employ our coreset to devise a (1 + e) approximation algorithm for kernel k-MEANS, that runs in time that is near-linear in n and parameterized by k. This is stated in Corollary 1.2, whose proof follows by solving k-MEANS on S optimally, using straightforward enumeration over all k- partitions of S. To the best of our knowledge, such fast (1 + ( aapproximatioo for kernel k- k-MEANS was not known even for k = 2; for example, uniform sampling would fail in cases where the optimal clustering is very imbalanced, as mentioned earlier.
Corollary 1.2 (FPT-PTAS). Given n-point weighted dataset X, oracle access to kernel K X x X + R2, integer k 2 1 and 0 < < 1, one can compute in time O(nk + kpoly(ke""), center set C. of k points, each represented as a linear combination of at most poly(ke points from (X)), such that with high probability C is a (1 e)-approximation for kernel k- K-MEANS on X and K. In particular, given such C, one can find for each x E X its closest center in C in time poly(kc-1)
In fact, for the purpose of finding near-optimal solutions, it already suffices to preserve the cost for centers coming from span()(()) (see Fact 2.1) which an n-dimensional subspace. However, our definition of coreset in (3) is much stronger, in that the objective is preserved even for centers coming from a possibly anfinttedimmensionall feature space. This stronger guarantee ensures that the coreset is composable, and thus the standard merge-and songe-and-reduce method can be applied. In particular, our coreset implies the first streaming algorithm for kernel k- k-MEANS.
Corollary 1.3 (Streaming kernel k-MEANS). There a streaming algorithm that given a dataset X presented as a sireum of n points, and oracle access to a kernel K X x X - R4,, constructs reweighted subset C X of poly(ke (k) points using poly(ke (k log n) words of space and update time, such that with high probability S is e-coreset for k-MEANS with respect X and K.
Experiments and other applications. We validate the efficiency and accuracy of our coresets on various data sets with polynomial and Gaussian kernels, which frequently-used kernels. For every dataset, kernel, and coreset-size that we test, our coreset performs consistently better than uniform sampling which serves as baseline. In fact, our coreset achieves less than 10% error using only about 1000 points for every dataset.
We also showease significant speedup to several applications that can be obtained using our coresets, Specifically, we adapt the widely used k-MEANS++ (Arthur & Vassilvitskii, 2007) to the kernel setting, and we compare the running time and accuracy of this kernelized k-MEANS++ with and without coresets. On dataset of size 10S, we observe more than 1000z speedup of k-MEANS++ when using coresets, while achieving a very similar error. Furthermore, this new efficient version of kemelized k- t-MEANS++ (based on coresets) is applied to solve spectral clustering, using the connection discoverd by Dhillon et al. (2004). Compared to the implementation provided by Scikit- learn (Pedregosa et al., 2011), our algorithm often achieves better result and uses significantly less time. Hence, our coreset-based approach can potentially become the leading method for solving spectral clustering in practice.
1.2 COMPARISON PREVIOUS APPROACHES
The computational issue of kernel k- B-MEANS is an important research topic and has attracted signif- icant attention. In the following, we compare our result with previous work that is representative of different possible approaches for the problem.
Uniform sampling of data points is commonly used technique, which fits well in kernel clustering. because samples can be drawn without any access to the kernel. While the coresets that we use rely on sampling, we employ importance sampling, which is non-uniform by definition. Chitta et al. (2011) employs uniform sampling for kernel k-MEANS, but instead of solving kernel k-MEANS on a sample of data points directly (as we do), their method works in iterations, similarly to Lloyd's algorithm, that find a center set that is linear combination of the sample. However, it has no worst-case guarantees on the error or the running time, which could be much larger than Ó(kk). Lastly, this method does not generalize easily to other sublinear settings, such as streaming (as our Corollary 1.3). Ren & Du (2020) analyze uniform sampling for M-MAANS in Fuclidean space,
3

---

which could be the kernel's feature space. In their analysis, the number of samples (and thus running time) crucially depends on the diameter of the dataset and on the optimal objective value, and is thus not bounded in the worse-case. This analysis builds several carlier papers, for example Czumaj & Sohler (2007) achieve bounds of similar flavor for k-MEANS in general metric spaces.
Another common approach to speed up kernel K- M-MEANS is to approximate the kernel K using dimdntion-reduccton techniques. In a seminal paper, Rahimi & Recht (2007) proposed a method that efficiently computes a low (namely, Olog r)) dimensional feature map ş that approximates yp (without computing y explicitly), and this O can be used in downstream applications. Their method based on designing random Fourier features, and works for a family of kemels that includes the Gaussian one, but not general kernels. This method was subsequently tailored to kernel k- M-MEANS by Chitta et al. (2012), and another followup work by Chen & Phillips (2017) established worst-case bounds for kernel k-MEANS with Gaussian kernels. Despite these promising advances, we are not aware of any work based on dimension reduction that can handle general kernel function (as in our approach). In sense, these cennensioo-reducttin techniques are "orthogonal" to our data-reduction approach, and the two techniques can possibly be combined to yield even better results.
An alternative dimension-reduction approach is low-rank approximation of the kernel matrix K. Recent work by Musco & Musco (2017) and by Wang et al. (2019) presents algorithms based on Nyström approximation to compute a low-rank (namely, Okk/e)) approximation K to the kernel matrix K in time near-linear in such that the optimal kernel k-MEANS on K achieves (1 + e)- approximation that on the original kernel K. However, the low-rank K does not immediately imply efficient algorithms for kernel k-MEANS (for instance, Lloyd's algorithm still requires O(n²) queries to K per iteration), while coreset can be readily combined with off-the-sher clustering algorithms.
2 PRELIMINARIES
Notation. A weighted set U is a finite set U associated with a weight function wy : U + R4. For such U, let ||U'|l be the number of distinct elements in it. For weight function as above and a subset S C U. define (5) := Eues wy (u). For any other map f : U + V (not a weight function), we follow the standard definition S(S) == {f(x) : x E S}. For an integer I. 2 1, let [t] == (1. .t). For a real number x and an integer i 2 1, let log( x be the i-th iterated log of x, i.e., log (1) x = log x and for i 2 2 let log( x log(log((-1) (f-1) xt).
Kernel functions. Let X be a set of n points, A function K : X x X + R. is a kernel function if the Since M is positive semi-definite, there exists map from X to some Hilbert space H. such that all xr y E X satisfy K(x, v) = (f(x)), (oy)). This above (existence of map yp of into H) can be extended to infinite X, e.g., X = Rdd by Mercer's Theorem. The distance hetween x', y/ E H is
matrix M such that My K(,,, 2g) (where 2,, 2y E X) is positive semi-definite.
defined as dist(z', .v)' := || - v'll = V(x' V' x - v²). Hence, the distance dist(pp(x), (v)) for xr y E X can be represented using K as
dist(p(()) ((v)) = lxx(x) - x(y)l = v K(xx x) + K(y.y) (K(x y).
We refer to survey by Ghojogh et al. (2021) for more comprehensive introduction to kernel functions.
Kernel (k. -CLUSTERUNGGG.. In the the kernel 2k (5,2))CCUUSE -LLUSTERING problem, the input is weighted data set X of n objects, a kernel function K X x X - R4, an integer & 2 1, and 0. The goal is to find k-point center set C. C H that minimizes the objective
cost of (X, () = Σ (xx(=)(dis(((()))))))
(4)
ZEX
where H. is an induced Hilbert space of K and yp x + is is its feature map. and dist((p(x). C) == mincen dist(p(z),c) c) min.en [1xp(z)) cl|- The case 2 2 clearly coincides with kernel k- MEANS whose objective is (2). The (non-kernel) (k, -)LLLSETER problem may be viewed as kernel (k, CT.USSRRNG with kernel K(x,)) y) (x, y) and identity feature map (px)) = x.
4

---

While the feature map ip might not be unique, show below that this kernel (k, 2) CLUSTERING well defined, in the sense that the optimal value is independent of sp The following two facts are standard and easy to prove.
Fact 2.1. For every map yp into H. there is an optimal solution C in which every center point C C lies inside span()(X))), and is thus a linear combination of (X)).
Corollary 2.2. The optimal value of (4) can be represented as a finction of kernel values K ((, y). and is thus invariant of q.
c-Coresets for kernel -)-CCLSTTRIING.. For CLUSTERING on weighted dataset X and a kernel function K is a reweighted subset S C X, such that for every Hilbert space H. and map @ H satisfying (I), we have AC S M,,CII k, The case clearly coincides with (3).
<
e-coreset for kernel (k, z)-
cost (S, C)) (1 + cost (xo,t((Xeer (X,C).
CORESETS FOR KERNEL (T,:))-CUUSTERINN
Theorem 3.1. Given n-point weighted dataset X, oracle access to a kernel K X x X R4, 2 =21 1, integer k 2 1, and 0 < E << 1, one can construct in time Ö(nk), reweighted subset S S X of size ||S||o 20(x) poly (ke-1), that with high constant probability is an e-coreset for kernel 2k, CLUSTTRING with respect X and K.
At high level, our prove this theorem by employing recent constructions of coresets for (k, z)- CLUSTERING in Fuclidean spaces, in which the coreset size is independent of the Fuclidean dimen- sion (Sohler& & Woodruff, 2018; Feldman et al., 2020; Huang & Vishnoi, 2020; Braverman et al., 2021). However, these coresets are designed for finte-dimensional Euclidean spaces, and are thus not directly applicable to our feature space H. which might have infinite dimension.
To employ these coreset constructions, we show in Lemma 3.2 that the data points in the feature space H. embed into an (n + 1)-dimensional (Euclidean) space, without any distortion to distances between data points and centers. This observation similar to one previously made by Sohler & Woodruff (201 8) for a different purpose. Due to this embedding, it suffices to construct coreset for (n + 1) 1)-dimensional space (Corollary 3.3).
the limited setting where centers come only from an
Lemma 3.2. Let H be Hilbert space and let X C H. be subset of n points. Then there exists map f g such that
Vr E E.CEPA H,
|| ||-- el = [f(x) f(cll.-
Proof. Let S (X). Then every point H can be written (uniquely) as c cll c where ell S and c² is orthogonal to S. Thus, ||d]]2 = ||c|||| 2 + ||"" Note that for all x E X, we have
x- = 0. Now, for every e H. let f(c (cll ||c--1 where interpret æll n-dimensional
vector. Then for all x E X and c E H.
| c|| ||=||| ||| || et || cll 1| = 11 s(o)11
The claim follows.
Corollary 3.3. Consider n-point weighted dataset X, kernel function K X X
R4,
integer h 2 1, and O < c < 1. Suppose that reweighted subset S S X satisfies that for every p X Ra+1 such that for all x, y X, (p())))(())) = [(x, y), the following holds
VC 12a+1 .[C
k, cost (1 cost (X,C).
Then S is an for kernel 2 CLLUSTERIN with respect to X and kernel K.
Proof. To verify that S is coreset with respect to X and K, consider some feature space H' and feature map sp' be induced by K. Apply Lemma 3.2 to obtain f: H' - R=+1, then for all C C H'. [C| k. have VQ S X, cost (Q, C) costfor (Q,f(C)) and using the promise about S with x = for',
cost (S, C) = costi( f(C) E (1 c) cost (x, = -11 + c) cost (X,C).
Thus, 8 is indeed coreset with respect X and K.
5

---

Algorithm 1 Constructing e-coreset for kernel (k, 2) CLUSTERING on data set X with kernel K
1: let Xo X, X
2: repeat
3: let i f i + 1 and G, + <log |
|
4: X; < IMPORTANCE-SO LANAANNCE-SAMLLINGXIIIIII
5: until ||x; la does not decrease compared with |X llo
6: return X;
Another issue is that some of the existing algorithms, such as Sohler Woodruff (2018); Feldman et al. (2020), require the imput to be an explicit representations of points in p(X), which is very expensive to compute. Fortunately, the samplling- hased algorithms of Huang Vishnoi (2020) and Braverman et al. (2021) are oblivious to the representation of y, and only rely on
distance oracle that evaluates l|<((z) (())ll = VK(r, (x) + K y) 2K(x,)) 2) for data points y,y E X. Now, by Corollary 3.3, executing these algorithms without any modifications (except for plugging in the distance oracle defined by kernel K) yields the desired coreset for kernel (k, z)- CLUSTERING. We choose to use the coresct construction of Braverman et al. (2021), which is arguably simpler. We now recall its statement for completeness.
Theorem 3.4 (Braverman et al. (2021)). Given n-point weighted dataset X C. I for some integer m, together with z 1, integer k 2 1, and 0 < < 1, one can construct in time Ö(nk). reweighted subset S S X of size ||S||o (((=-422x33) that with high constant probability is e-coresel for (ki, -L-USSSTER with respect to X.
Proof of Theorem 3.1. It follows immediately by combining Corollary 3.3 and Theorem 3.4.
3.1 DESCRIPTION OF CORESET CONSTRUCTION ALGORITHMS
Next, we present our full algorithm in Algorithm 1 (which depends on the subroutines defined in Algorithm 2 and 3). While it essentially tailors previous work to our kernel clustering setting, we provide full details for completeness. The following notation is needed. For a subset C S H and data point X, define NNc(x) == arg (dist(((())) x C with respect to the distances in the feature space (breaking ties arbitrarily). Thus NNc(.) defines a [CI-partition of X, and the cluster that x belongs to (with respect to C)) is denoted C(x) {æ' E EX: (Nc((') (z))
C} as the nearest neighbor of
Algorithm 1 is the main procedure for constructing the coreset, and its loop iteratively executes coreset construction (Algorithm 2). Informally, each invocation
another sawprrannn----ppiingg--- of IMPORTANCE- SAMPLING constructs coreset X, from the current coreset X;-1, to reduce the number of distinct elements in X;-I to roughly log | | loo The procedure ends when such size reduction cannot be done any more, at which point the size of the coreset reaches the bound in Theorem 3.4, which is independent of n.
In fact, subroutine IMPORTANCE-SAMEN size that depends on log ||X||o This subroutine is based on the well-known importance sampling approach that was proposed and improved in series of works (cf. Langberg & Schulman (2010); Feldman & Langberg (201 1); Feldman et al. (2020)). Its first step is to compute an importance score ar for every data point x E X (lines 1-2), and then draw independent samples from X with probability proportional to ar (lines 3-4). The final coreset is formed by reweighting the sampled points (lines 5-6). Roughly speaking, the importance score a₂ measures the relative contribution of æ to the objective function in the worst-case, which here means the maximum over all choices of the center set. It can be computed from an Olog k) approximatee solution for kernel (k, 2)- CLUSTERING on X, which is generated by the Da-sampiing subroutine (Algorithm 3), natural generalization of the D2 D2-sampling introduced by Arthur & Vassilvitskii (2007).
already constructs coreset, albeit it is of worse
We stress that our algorithm description the feature vectors (o(x) for clarity of exposition. These vectors do not have to be provided explicitly, because only distances between them are required, and thus all steps can be easily implemented using the kernel trick, and the total time (and number of accesses to the kernel function ) is only Ö(nk).

---

Algorithm 2 IMPORRTACE-SAMMPPIGGCC,
1: let C* < DDD-SAMPLINGG(A
(c cost)((,,C.) + =x((
2: for each x E X, let t wx (x)
3: for each x E X, let Pe + E
oz
4: draw N = (0-0((1200 (G--222=2k2 log" k log ||X i.idd. samples from X, using probabilities (F>) wx wx(#))
5: let D be the sampled set, and for each D let wp(a)
P.N
6: return weighted set D
Algorithm 3 D* SAMPLING(X)
> the feature vectors (o() mentioned for clarity and not needed for implementation 1: let x be a uniform random point from X, and initialize C' < {{{()}}
2: for = 1.....k k do
3: draw one sample a E X, using probabilities wx (x)) cost, (X,C)
(dist(p()),C)))
(X,C)
4: let C' + C {xpx))
5: end for
6: return C
4 EXPERIMENTS
We validate the empirical performance our coreset for kernel k- k-MEANS against various datasets, and show that our coresets can significantly speedup kernelized version of the widely used k-MEANS++ (Arthur Vassilvitskii, 2007). addition, we apply this new coreset-based kernel- ized K-MEANS+ to spectral clustering (via reduction devised by Dhillon et al. (2004)), showing that it outperforms the well-known Scikit-learn solver in both running time and objective value.
Experimental setup. Our experiments are conducted on standard clustering datasets that con- sist of vectors in Rd and use the RBF kernel (radial basis function kernel, also known as Gaussian kernel) and polynomial kernels as kernel functions. An RBF kernel KG is of the form
KG(2, v) = exp ||z-y] where o > 0 is a parameter, and polynomial kernel Kp is of the 20
form () == ((x,, y) +c)" where e and d are parameters. Table summarizes the specifications of datasets and choice of the parameters for the kernel function. We note that the parameters are dataset-dependent, and that for Twitter and Census 1990 dataset we subsample to 100 points since otherwise it takes too long to run for some of our inefficient baselines. Unless otherwise specified, we use typical value & 5 for the number of clusters. All experiments are conducted on PC with Intel Core 17 CPU and 16 GB memory, and algorithms are implemented using C++.
4.1 SIZE AND EMPIRICAL ERROR TRADFOFF
Our first experiment evaluates the empirical error versus coreset size. In our coreset implementation, we simplify the construction in Algorithm by running the importance sampling step only once in- stead of running it iteratively, and it turns out this simplification still achieves excellent performance. As in many previous implementations, instead of setting c and solving for the number of samples N in the IMPORTANCE-S CAAAANCEE-SMPPPAP SAMPLING procedure (Algorithm 2), we simply set N parameter to di- rectly control the coreset size. We construct the coreset with this and evaluate its error by drawing 500 random center sets C (each consisting of k points) from the data set, and evaluate the maximum empirical error, defined as
(S, cost (X, (o,
== max CEC
(5)
cxs C*)
This empirical error is measured similarly the definition of coreset, except that it is performed on a sample of center sets. To make the measurement stable, the empirical error is evaluated indepen- dently 100 times and the average is reported.
7

---

Table 1: Specifications of datasets
dataset
size
RBF kernel param.
poly. kernel param.
Twitter (Chan et al., 2018)
21040936
50
0, d = 4
Census 1990 (Meek et al., 1990)
2458284
100
d
Adult (Dua & Graff, 2017)
48842
a
200000
c
Bank (Moro et al., 2014)
41188
a 500
c 0, d =
kard
kemol Cura cobromal hersl
2:26
Dura, polynoted card
C20
pibremio
50-
60
20
6-30
100
272
500
Size
1000
2030
5000
10000
23020
200
550
LE36
2000
5380
19800 20000
Adult dataset
Bank dataset
Uniiom shmpling RGF karne
76-
Unifern camoiing ser same
fnclomm dumpling pobyooris komel
Lndeer damoling pilyioiial kame.
5.0
250
303
1000
2305 Size coreset
3000
10000 20000 33000
500
1026
2003
5003
10300 20302 50002
Size
coneset
Twitter dataset
Census! 1990 dataset
1998
Figure 1: Tradeoffss between coreset size and empirical error.
The tradeoff of the coreset size versus empirical error is shown in Figure 1, where also compare with baseline that constructs the coresct using uniform sampling. These experiments show that our coreset performs consistently well on all the datasets and kernels. Furthermore, our coreset admits similar error curve regardless dataset and kernel function - for example, one can get within 10% error using coreset of only 1000 points, which is perfectly justified by theory that the size of e-coreset only depends on and k. Comparing with the uniform-sampling baseline, our coreset generally has superior performance, especially when the coreset size is small. We also observe that the uniform sampling suffers a larger variance compared with our coreset.
4.2 SPEEDING UP KERNELIZED M-MEANS++
A-MEANS+ (Arthur Vassilvitskii, 2007) is a widely-used algorithm for k-MEANS, and could easily be adopted to solve kernel M-MMANS by using the kernel trick, however mentioned earlier this would take ((n²) time. We use our coreset to speedup this kernelized k d-MEANS++ algorithm, by first computing the coreset and then rumning kernelized k- M-MANNS+ on the coreest; this yields an implementation of kernelized k- A-MEANS++ whose running time near-linear (in n))
In Figure 2, demonstrate the running time and the error achieved by kernelized M-MEANS++ with and without coresets, experimented with varying coreset sizes. We measure the relative error of our coreset-based kernelized M-MEANS+ by comparing the objective value achieves with that of vanilla (i.e., without coreset) kernelized k-MEANS++. These experiments show that the error decreases significantly as the coreset size increases, and stabilizes around size N 100, achieving merely < 5% error. Naturally, the running time of our coreset- coreset-based approach increases with the coreset size, but even the slowest one still several orders of magnitude faster than vanilla kernelized k: A-MMANS+++
4.3 SPEEDING UP SPECTRAL CLUSTERING
In the spectral clustering problem, the input is a set n objects X and an n x n similarity matrix A that measures the similarity between every pair of elements in X, and the goal is find k-
8

---

-haante commstravning
Bollative amor
Reladive
Bare
0004
58783 3M 88888888
099 (MV)
Size coresse
Size coreset
RBF kernel
Polynomial kernel
Figure 2: Speedup of kemelized K-MEANS++ using coreset. This experiment is conducted the Twitter dataset with RBF and polynomial kernels. We run each algorithm 10 times, report the average running time and the minimum objective value (in relative-error evaluation).
Base- regenttmiic 2. X. 2 [mml
-R out CEACUE sot gering lire Dats nieing trie
SCGET AESSUN
340
-COET
Objective
330
203 10100
.310
2023
2000 dalsset
23030
2500
40000
3000
10303
1500
2000
2010 datasel
25:00
30302
4002
Size
Size
RBF kernel
Polynomial kernel
Figure 3: Speedup of spectral clustering using coreset-based kernelized k-MEANS++ with coreset size N 2000. Similarly Figure 2, we run each algorithm 10 times, report the average running time and the minimum objective value.
partition of X such that a certain objective function with respect to A is minimized. Dhillon et al. (2004) shows way to write spectral clustering as a (weighted) kernel k-MEANS problem, which is eventually used to produce a spectral clustering. Specifically, let D be an n x n diagonal matrix such that D Eje(n Atj- Then according Dhillon et al. (2004), spectral clustering can be written as weighted kernel k-MEANS problem with weights w; == D;, and kernel function D-IAD- provided that A is positive semidefinite (which could be viewed as a kernel). We use this reduction, and plug in the abovementioned coreset-based kernelized k-MEANS++ as the solver for kernel M-MEANS. We experiment the subsampled Twitter dataset with varying number of points, and we use the polynomial and RBF kernels as the similarity matrix A.
However, would need (nn²) time if we evaluate Dú naively. To resolve this issue, draw uniform sample S from [n]]. and use D :- [sT EjesAu, an estimate for Da. The accuracy of D is justified by previous work kernel density estimation (Joshi al., 2011, Theorem 5.2), and for our application we simply set |S] = 1000, which achieves good accuracy.
We compare our implementation with the spectral clustering solver from the well-known Scikit- learn library (Pedregosa et al., 2011) as baseline. The experimental results, reported in Figure 3, show that our approach has more than 1000x of speedup already for moderately large datasets (n 40000). This difference might be partially caused by efficiency issues of the Python language used for the Scikit-learn implementation (recall that our implementation that the asymptotic growth of our algorithm's 's running time is also much better than that of the Scikit- learn baseline. This suggests that our improvement in rumning time is fundamental, and not only due to the programming language. We also observe that approach yields better objective values than Scikit-learn. One possible reason is that Scikit-leam might be conservative in using more iterations gain better accuracy, because of the expensive computational cost that do not suffer.
C++), but we actually see

---

REFERENCES
Nicholas O Andrews and Edward A Fox. Recent developments in document clustering. Techni- Report TR-07-35, Department of Computer Science, Virginia Polytechnic Institute State University, 2007.
David Arthur and Sergei Vassilvitskii. k-means++: the advantages of careful seeding. In SODA, pp- 1027-1035. SIAM, 2007.
Maria-Florina Balcan, Steven Ehrlich, and Yingyu Liang. Distributed k-means and k-median clus- tering on general communication topologies. In NIPS, pp. 1995-2003, 2013.
Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Xuan Wu, Coresets for clus- tering in excluded-ming minor graphs and beyond. In SODA, pp. 2679-2696. SIAM, 2021.
T-H. Hubert Chan, Arnaud Guerquin, and Mauro Sozio. Twitter data set, 2018. URL https: / diigthubb.. com/ fe
Di Chen and Jeff M. Phillips. Relative error embeddings of the gaussian kernel distance. In ALT, volume 76 of Proceedings of Machine Learning Research, pp. 560-576. PMLR, 2017.
Radha Chitta, Rong Jin, Timothy C. Havens, and Anil K. Jain. Approximate kernel k-means: Solu- tion to large scale kernel clustering, In KDD, pp. 895-903, ACM, 2011.
Radha Chitta, Rong Jin, and Anil K. Jain. Efficient kernel clustering using random Fourier features.
In ICDM, pp. 161-170. IEEE Computer Society, 2012.
Artur Czumaj and Christian Sohler. Sublincar time approximation algorithms for clustering via random sampling. Random Struct. Algorithms, 30(1-2):226-256, 2007. doi: 10.1002/rsa.20157.
Inderjit S. Dhillon, Yuqiang Guan, and Brian Kulis. Kernel k-means: spectral clustering and nor-
malized cuts. In KDD, pp. 551-556. ACM, 2004.
Chris H. Q. Ding, Xiaofeng He, and Horst Simon. Nonnegative lagrangian relaxation of K- means and spectral clustering. In ECML,, volume 3720 of Lecture Notes in Computer Science, pp- 530-538. Springer, 2005.
Dheeru Dua and Casey Graff. UCI machine learning repository, adult dataset, 2017. URL https: / //archi ve. ics .ui feci.eedu/mi //taaaatttt//aaullllllaa
Dan Feldman and Michael Langberg. unified framework for approximating and clustering data. In STOC, pp. 569-578. ACM, 2011.
Dan Feldman, Morteza Monemizadeh, and Christian Sohler. PTAS for k-means clustering based on weak coresets. In SoCG, pp. 11-18. ACM, 2007.
Dan Feldman, Melanie Schmidt, and Christian Sohler. Turning big data into tiny data: Constant-size coresets for k-means, PCA, and projective clustering. SIAM J. Comput., 69(3)6601-677, 2020.
Benyamin Ghojogh, Ali Ghodsi, Fakhri Karray, and Mark Crowley. Reproducing kernel Hilbert space, Mercer's theorem, eigenfunctions, Nyström method, and use kernels in machine learn- ing: Tutorial and survey. CoRR, 0et/220060044433 2021.
Mark A. Girolami. Mercer kernel-based clustering in feature space. IEEE Trans. Neural Networks, 13(3):780-784, 2002.
Mchmet Gönen and Adam A. Margolin. Localized data fusion for kernel k-means clustering with application to cancer biology. In NIPS, pp. 1305-1313, 2014.
Sariel Har-Peled and Soham Mazumdar. On coresets for k-means and k-median clustering. In STOC, pp. 291-300. ACM, 2004.
Monika Henzinger and Sagar Kale. Fully-dynami coresets. ESA, volume 173 LIPIcs, pp- 57:1-57:21. Schloss Maasstull-Leibnii-Zeeree für Informatik, 2020.
10

---

Lingxiao Huang and Nisheeth K. Vishnoi. Coresets for clustering in Euclidean spaces: Importance sampling is nearly optimal. In STOC, pp. 1416-1429, ACM, 2020.
Sarang C. Joshi, Raj Varma Kommaraju, Jeff M. Phillips, and Suresh Venkatasubramanian. Com- paring distributions and shapes using the kernel distance. In SoCG, pp. 47-56. ACM, 2011.
Dae-Won Kim, Ki Young Lee, Doheon Lee, and Kwang Hyung Lee. Evaluation of the performance of clustering algorithms in kernel-induced feature space. Pattern Recognit. 38(4):6077-) 2005.
Michael Langberg and Leonard J. Schulman. Universal epsilon-aprroximator for integrals. In SODA, pp. 598-607. SIAM, 2010.
Chris Meek, Bo Thiesson, and David Heckerman. UCI machine learning repository, census 1990 dataset, 1990. URL http:://rchhi ics httediedmmmmmaaaat/////////// Data+ (1990).
S. Moro, P. Cortez, and P. Rita. UCI machine learning repository, bank dataset, 2014. URL https: //archive. ics. uci wwweee/mmm/eeeeeeeeeeeeeeeeeeeee http://mmdaaaats//////as Bank MaankMaateeing
Cameron Musco and Christopher Musco. Recursive sampling for the Nystrom method. NIPS, 2017.
pp.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830, 2011.
Ali Rahimi and Benjamin Recht. Random features for large-scale kemee machines. In NIPS, pp- 1177-1184. Curran Associates, Inc., 2007.
Yuanhang Ren and Ye Du. Uniform and non-uniform sampling methods for sub-linear time k-means clustering. In ICPR, pp. 7775-7781. IEEE, 2020.
Bernhard Schölkopf, Alexander J. Smola, and Klaus-Rober Müller. Nonlinear component analysis as a kernel eigenvalue problem. Neural Comput., 10(5): 1299-1319, 1998.
John Shawe- Shawe-Taylor and Nello Cristianini. Kernel Methods for Pattern Analysis. Cambridge Univer- sity Press, 2004.
Christian Sohler and David P. Woodruff. Strong coresets for k-median and subspace approximation: Goodbye dimension. In FOCS, pp. 802 813. IEEE Computer Society, 2018.
Twan van Laarhoven and Elena Marchiori. Local network community detection with continuous optimization of conductance and weighted kernel k-means. J. Mach. Learn. Res., 17:147:1- 147:28, 2016.
Shusen Wang, Alex Gittens, and Michael W. Mahoney. Scalable kernel k-means clustering with Nyström approximation: Relative-error bounds. J. Mach. Learn. Res., 10:12:1-12:49 2019, URL http: / jmmr..mir...//..m orw.orgg..o.......oooo.....o.. wttp://pprss////////
html.
Rong Zhang and Alexander Rudnicky. A large scale clustering scheme for kernel k-means. In ICPR (4), pp. 289-292, IEEE Computer Society, 2002.
11


Reviews:
[{"review_id": "quPSdfEpFYU", "reviewer": "Reviewer_AgHC", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "Strengths:\n1)Kernel k-means is an important problem in machine learning and since it is computationally expensive, the use of coresets to speed up the algorithm is an interesting and important problem.\n2) Theoretically the paper uses a couple of nice small results (lemma 3.2 and corollary 3.3) to apply the coreset frame work in the kernelized setting. Overall the paper is not difficult to read.\n3) Experimental results over large real datasets show significant speed ups for the kernelized k-means problem while preserving the accuracy. Code is also provided.\n\nWeaknesses:\n1)Less Novelty:  The algorithm for construction of coresets itself is not novel. Existing coreset frameworks for classical k-means and (k,z) clusterings  are  extended to the kernelized setting. \n2)Clarity:  Since the coreset construction algorithm is built up on previous works, a reader without the background in literature on coresets would find it hard to understand why the particular  sampling probabilities are chosen and why they give particular guarantees. It would be useful rewrite the algorithm preview and to give at least a bit of intuition on how the importance sampling scores are chosen and how they can give the coreset guarantees\n\nSuggestions:\n1) In the experiment section, other than uniform sampling, it would be interesting to use some other classical k-means coreset as baselines for comparison. \n2) Please highlight the technical challenges and contributions clearly when compared to coresets for classical k-means.", "summary_of_the_paper": "The paper claims to present the first coreset for kernel k-means and other (k,z) kernel clusterings given oracle access to the kernel. The size of coreset is independent of the number of points and construction time is near linear in k. The authors use the coreset to get a (1+\\epsilon) approximation for the kernel k-means. The theory is supported with experimental results.", "summary_of_the_review": "Overall the paper discusses an important and interesting problem and the experiments performed on real datasets show the utitility of the method in practice. However the theory results are heavily based on existing coreset techniques for classical k-means and  I am not very sure if the paper has enough technical novelty for ICLR. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "VoPs0nVOfTv", "reviewer": "Reviewer_w9ag", "summary": "", "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 provides a coreset construction using the $D^z$ sampling technique to bound the probability of sampling any input point $p \\in X$. The technique can be thought of as a generalization to the well-known technique $D^2$ sampling technique of David Arthur et al. due to the incorporation of the feature map.\nWhile the paper is theoretical in nature and admits strong plausible results, I have some concerns:\n1. The paper claims the first coreset for the problem of kernelized k-means problem. This claim is not true in my opinion due to the following. Even though the problem was not the main contribution of \"A PTAS for k-Means Clustering Based on Weak Coresets\" by Feldman et al., it was still mentioned in this paper. Another coreset paper mentions a coreset for kernelized k-means (for some type of kernels) where the coreset's size is exponential in k (see \"Turning Big data into tiny data:\nConstant-size coresets for $k$-means, PCA and projective clustering\" by Feldman et al.). \nHowever, the best feature associated with your paper is the generation of coresets of smaller size with respect to any kernel function. A more proper claim would be the first coreset for $(k,z)$-kernelized clustering for any kernel function. \n2. Throughout the experiments, there was no need for the feature map itself as it is not commonly explicitly defined. However, Algorithm 3 requires its explicit existence which forms a bit of a problem. Can you please justify this? As far as I understood, Algorithm 3 uses the explicit feature map. How did you obtain this map? \nPractically speaking, I don't see why you need the explicit map, since the distance function can be slightly altered to apply the kernel trick also on points from $C^*$ (using $K$). This is due to the fact that $C^*$ is generated using points from $X$. Correct me if I am wrong.", "summary_of_the_paper": "The paper suggests a coreset construction technique to the kernelized $(k,z)$-clustering, whose size is independent of $n$ (the number of points in the input data), in time that is near-linear in $n$.", "summary_of_the_review": "The paper is novel, well written, and admits theoretically and practically great results. I recommend acceptence. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "JmcU80pwzdw", "reviewer": "Reviewer_BBxb", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "Coresets allow geometric problems to be reduced to small size, and then an expensive algorithm run on the coreset instead of the full input. Here the authors consider the problem of k-means where the distance function is given as a kernel. They show that coresets exist for this formulation, and so a brute-force algorithm can be used to solve this problem.\n\nThe technical framework is as follows: The authors present a known embedding from Hilbert to Euclidean space, and then the coreset of Braverman et al. satisfies the required approximation bounds. \n\nThe theoretical contributions here seem very slight, more like observations, and I don't see the paper having the type of underlying innovation I would expect from ICLR. Also, I wasn't so impressed by an error of 10% using a coreset of 1000 points (although this application is somewhat outside my area of expertise).\n\ntypo on page 6: \"importane-sampling\"", "summary_of_the_paper": "The paper suggests a small coreset for the problem of clustering under kernel distances.", "summary_of_the_review": "Nice result, but in my opinion not innovative enough for ICLR.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Overall it was decided to reject this paper mainly because it seemed to be a minor extension of known constructions. The reviewers agreed that it certainly is valuable that the paper presents the best known results for kernel k-means, but the paper was viewed by the reviewers as more of an observation and primarily an off-the-shelf application of techniques in the coreset literature. Because of this, the novelty was thought to be a bit below the bar. 

One suggestion for improving the presentation is that in the thesis of Melanie Schmidt, there seems to be such a construction for kernel k-means which is exponential in 1/eps, and so much worse than what is in this submission. While that's great and certainly something to add and discuss in the paper, the reviewers still felt the technical novelty here was not quite enough to merit acceptance.
Decision: Reject