Simple, Scalable and Effective Clustering via One-Dimensional Projections
Authors: Moses Charikar
Monika Henzinger
Lunjia Hu
Maximilian Vötsch
Erik Waingarten
Venue: NeurIPS 2023 poster (2023)
Keywords: clustering
k-means
random projection
massive datasets
TL;DR: Running k-means++ on high dimensional data projected to a random line gives a simple, practical algorithm for k-means with provable guarantees and good empirical performance.

Abstract: Clustering is a fundamental problem in unsupervised machine learning with many applications in data analysis. Popular clustering algorithms such as Lloyd's algorithm and $k$-means++ can take $\Omega(ndk)$ time when clustering $n$ points in a $d$-dimensional space (represented by an $n\times d$ matrix $X$) into $k$ clusters. On massive datasets with moderate to large $k$, the multiplicative $k$ factor can become very expensive. We introduce a simple randomized clustering algorithm that provably runs in expected time $O(\mathsf{nnz}(X) + n\log n)$ for arbitrary $k$. Here $\mathsf{nnz}(X)$ is the total number of non-zero entries in the input dataset $X$, which is upper bounded by $nd$ and can be significantly smaller for sparse datasets. We prove that our algorithm achieves approximation ratio $\widetilde{O}(k^4)$ on any input dataset for the $k$-means objective, and our experiments show that the quality of the clusters found by our algorithm is usually much better than this worst-case bound. We use our algorithm for $k$-means clustering and for coreset construction; our experiments show that it gives a new tradeoff between running time and cluster quality compared to previous state-of-the-art methods for these tasks. Our theoretical analysis is based on novel results of independent interest. We show that the approximation ratio achieved after a random one-dimensional projection can be lifted to the original points and that $k$-means++ seeding can be implemented in expected time $O(n\log n)$ in one dimension.

Simple, Scalable and Effective Clustering via One-Dimensional Projections
Moses Charikar Stanford University Stanford, CA mosesêcs. stanford.
Monika Henzinger
Institute of Science and Technology Austria (ISTA)
Klosternuuurg,, Austria
monika www.whnnnniiinttccc.om ac
Lunjia Hu Stanford University Stanford, CA aunjaa@ttan taaossttafrdrd edu
Maximilian Vötsch
Faculty of Computer Science
Doctoral School of Computer Science DoCS Vienna University of Vienna Vienna, Austria
maximiliam www..ovwwtsseiiiiie..ooo.om.. ac. at
Erik Waingarten
Department of Computer and Information Sciences
University of Pennsylvania Philadelphia, PA ewaingar upenn edu
Abstract
Clustering is a fundamental problem in unsupervised machine learning with many applications in data analysis. Popular clustering algorithms such Lloyd's al- gorithm and k-means++ can take ((ndk) time when clustering n points in a d-dimensional space (represented by an d matrix X) into k clusters. In ap- plications with moderate to large k, the multiplicative factor can become very expensive. We introduce simple randomized clustering algorithm that provably runs in expected time (nnz((X + n log n1) for arbitrary k. Here nnz(X) is the total number of non-zero entries in the input dataset X, which is upper bounded by nd and can be significantly smaller for sparse datasets. We prove that our algorithm achieves approximation ratio ((k4) on any input dataset for the k-means objective. We also believe that our theoretical analysis is of independent interest, as we show that the approximation ratio of k-means algorithm is approximately preserved under a class of projections and that k-means++ seeding can be implemented in expected (n log n) time in one dimension. Finally, we show experimentally that our clustering algorithm gives new tradeoff between running time and cluster quality compared previous state-of-the-art methods for these tasks.
Introduction
Clustering is essential and powerful tool for data analysis with broad applications in computer vision and computational biology, and it is one of the fundamental problems in unsupervised machine learning. In large-scale applications, datasets often contain billions of high-dimensional points. Grouping similar data points into clusters is crucial for understanding and organizing datasets. Because of its practical importance, the problem of designing efficient and effective clustering algorithms has attracted the attention of numerous researchers for many decades.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

One of the most popular algorithms for the k-means clustering problem is Lloyd's algorithm [52]. which seeks locate k centers in the space that minimize the sum of squared distances from the points of the dataset to their closest center (we call this the "k-means cost"). While finding the centers minimizing the objective is NP-hard [ in practice we can find high-quality sets of centers using Lloyd's iterative algorithm. Lloyd's s algorithm maintains a set of & centers. It iteratively updates them by assigning points to one of k clusters (according to their closest center), then redefining the center as the points' center of mass. It needs good initial set of centers to obtain a high-quality clustering and fast convergence. In practice, the k-means++ algorithm [6, a randomized seeding procedure, is used to choose the initial & centers. k-means++ achieves an (log kc) -appoxximatoon ratio in expectation, upon which each iteration of Lloyd's ' algorithm improves Beyond their effectiveness, these algorithms are simple to describe and implement, contributing to their popularity.
The downside of these algorithms that they do not scale well to massive datasets. A standard implementation of an iteration of Lloyd's algorithm needs to calculate the distance to each center for each point in the dataset, leading to (nddk) running time. Similarly, the standard implementation of the k-means++ seeding procedure produces k samples from the so-called D distribution (see Appendix A for details). Maintaining the distribution requires making a pass over the entire dataset after choosing each sample. Generating & centers leads to ((ndk) running time. Even for moderate values of k making k passes over the entire dataset can be prohibitively expensive.
One particularly relevant application of large-scale k-means clustering is in approximate nearest neighbor search [66] (for example, in product quantization 44 and building inverted file indices [T)].. There, k-means clustering is used to compress entire datasets by mapping vectors to their nearest centers, leading to billion-scale clustering problems with large (on the order of hundreds or thousands). Other applications on large datasets requiring a large number of centers may be spam filtering [6] (65, near-duplicate detection 42], and compression or reconciliation tasks [62]. New algorithmic ideas are needed for these massive scales, and this motivates the following challenge:
Can we design simple, practical algorithm for k-means that runs in time roughly (nd)), independent of k and produces high-quality clusters?
Given its importance in theory and practice, a significant amount of effort has been devoted to algorithms for fast k-means clustering. We summarize a few of the approaches below with the pros and cons of each so that we may highlight our work's position within the literature:
A. Standard k-means++: This is our standard benchmark. Plus:
Guaranteed be an Ollog k)- approximation [6;; outputs centers, as well as the assignments of dataset points to centers. Minus: The running time is O(ddk),, which is prohibitively expensive in large-scale applications.
B. Using Approximate Nearest Neighbor Search:
One may implement k-means++ faster using techniques from approximate nearest neighbor search (instead of a brute force search each iteration). Plus: The algorithms with provable guarantees, like [26). obtain an O₂ (log k)- approximation. Minus: The running time is O(nd + (n log( A)) > depending
dataset dependent parameter A, the ratio between the maximum and minimum distances between input points. The techniques are algorithmically sophisticated and incur extra poly-logari factors (hidden in O())) making the implementation significantly more complicated.
C. Approximating the D'-Distribution: Algorithms that speed up the seeding procedure for Lloyd's algorithm or generate fast coresets (we expand on this below) have been proposed in 8 7 10] Plus: These algorithms are fast, making only one pass over the dataset in time O(nd). (For [ 77) there is an additional additive O(k2d) d) term in the running time). Minus: The approximation guarantees are qualitatively weaker than the approximation of k-means clustering. They incur an additional additive approximation error that grows with the entire dataset's variance (which can lead to arbitrarily large error; see Section 3p. These algorithms output set of k centers but not the cluster assignments, Naively producing the assignments would take time ((ndk)
'Aprooximation is with respect to the k- m-mes cost. A c-approximation has m-mna cost, which is at most e times larger than the optimal k-means cost.
*One may use approximate nearest neighbor search techniques to improve on the ((ddk) running time. However, as discussed above, approximate nearest neighbor search adds significant layer of complexity (and approximation).

---

Coresets. At high level, coresets are retaset-reduction mechanism. A large dataset X of points in R is distilled into significantly smaller (weighted) dataset of m points in R called "coreset" which serves as good proxy for X, i.e., the clustering cost of any k centers on Y is approximately the cost of the same centers on X. We point the reader to p 351 for recent survey on coresets. Importantly, coreset constructions (with provable multiplicaaveeaappoimmaaii require an initial approximate clustering of the original dataset X. Therefore, any fast algorithm for k-means clustering automatically speeds up any algorithmic pipeline that uses coresets for clustering - -looking forward, we will show how our algorithm can significantly speed up coreset constructions without sacrificing approximation.
guarantees)
Beyond those mentioned above, many works seek to speed up k-means++ + or Lloyd iterations by
maintaining some nearest neighbor search data structures [58] [4]]
46
45 33 60 40, [5
71
30 22
13 55
18 or by running some first-order methods (4] These techniques do not give provable
guarantees on the quality of the k-means clustering on the running time of their algorithms.
Theoretical Results. We give a simple randomized clustering algorithm with provable guarantees on its running time and approximation ratio without making any assumptions about the data. It has the benefit of being fast (like the algorithms in Category C above) while achieving a multiplicative error guarantee without additional additive eπror (like the algorithms in Category B above).
The algorithm runs in time O(nd + n log n) irrespective of k. It passes over the dataset once to perform data reduction, which gives the nd factor plus an additive On log n) term to solve k-means the reduced data, producing & centers and cluster assignments. On sparse input datasets, the nd term becomes nnz(X). ). where nnz(X) is the number of non-zero entries in the dataset. Thus, our algorithm runs in (nnz((X) + n log n) time on sparse matrices.
The algorithm is as simple as the k-means++ algorithm while significantly more efficient. The approximation ratio we prove is poly(k), which is worse than the Olog k) -ppaprooxintaoon achieved by k-means++ but it is purely multiplicative (see the remark below improving this to Olog k)). It does not incur the additional additive errors from the fast algorithms in (0).
Our algorithm projects the input points to random one-dimensional space and runs an efficient k-means++ seeding after the projection. For the approximation guarantee, we analyze how the approximation ratio achieved after the projection can be transferred to the original points (Lemma (25) We bound the running time of our algorithm by efficiently implementing the k-means++ seeding in one dimension and analyzing the rumning time via potential function argument (24mma2.44.... Our algorithm applies beyond k-mmeans to other clustering objectives that sum up the z-th power of the distances for general = 2 1, and our guarantees on its running time and approximation ratio extend smoothly to these settings.
Improving the Approximation from poly(k) to O(log k). The approximation ratio of poly(k) may seem significantly worse than the O(log k) approximations achievable with k-means++. How- ever, we can improve this to Ollog k) with an additional, additive (polyy(kd) (ldd))loggo n) term in the running time. Using previous results discussed in Appendix A.2 (specifically Theorem (A.2). a multi- plicative (oly())aaprooiimatinn suffices to construct a coreset of size poly(kd) and run k-means++ on the coreset. Constructing the coreset is simple and takes time poly (kd) -log n (by sampling from an appropriate distribution); rumning + + on the coreset takes poly(kd) time (with no dependence on n). Combining our algorithm with coresets, we get a O k) a)-approxiimation in O (nnz(X)) + O(n l) + poly (kdy log time. Notably, these guarantees cannot be achieved with the additive approximations of g
Experimental Results. We implemented our algorithm, well as the lightweight coreset of [T0 and k-means++ with sensitivity sampling [15]. We ran two types of experiments, highlighting various aspects of our algorithm. We provide our code in the supplementary material. The two types of experiments are:
Coreset Construction Comparison: First, we evaluate the performance of our clustering algorithm when we use to construct coresets. We compare the performance of our algorithm to k-means++ with sensitivity sampling g and lightweight coresets (10). In real-world, high-dimensional data, the cost of the resulting clusters from the three algorithms is roughly the same. However, ours and the lightweight coresets can be significantly faster (ours is up to 190x faster than k-mens++.,
3

---

see Figure and T. The lightweight coresets can be faster than our algorithm (between 3-5x); however, our algorithm is "robust" (achieving multiplicative approximation guarantees) Additionally, we show that the clustering from lightweight coresets can have an arbitrarily high cost for a synthetic dataset. On the other hand, our algorithm achieves provable (multiplicative) approximation guarantees irrespective of the dataset (this is demonstrated in the right-most column of Figure 2)
Direct k-means++ comparison: Second, we compare the speed and cost of our algorithm to k-means++ as a stand-alone clustering algorithm (we also compare two other natural variants of our algorithm). Our algorithm can be up to 800x faster than k-means++ for k = 5000 and our slowest variant up to 100x faster (Table Dp. The cost the cluster assignments can significantly worse than that of k-means++ (see Figure 3). Such result is expected since our theoretical results show a poly(A) (aaappoxxiimiainnn The other (similarly) fast algorithms (based on approximating the D2 DP-distribution) which run in time ((dd) 8 7 do not produce the cluster assignments (they only output & centers). These algorithms would take (nddk) time to find the cluster assignments this is precisely the computational cost our algorithm avoids.
We do not compare our algorithm with [26] nor implement approximate nearest neighbor search to speed up k-means++ for the following reasons. The algorithm in (26) is significantly more compli- cated, and there is no publicly available implementation. In addition, both [26] and approximate nearest neighbor search incur additional poly-logarithnic (or even n) for nearest neighbor search over &g [)] which add significant layers of complexity to the implementation and make thor- ough evaluation of the algorithm significantly more complicated. Instead, our current implementation demonstrates that simple, miedimmeniionll projection and k-means++ on the line enables dramatic speedups to coreset constructions without sacrificing approximation quality.
Related Work. Efficient algorithms for clustering problems with provable approximation guar- antees have been studied extensively, with a few approaches in the literature. 'here are polynomial-time (constant) approximation algorithms (an exponential dependence l is not allowed) (see (50 17
39] for some of the most recent and strongest results), nearly lin- ear time (1 + approximmtaio with running time exponential in k which proceed via core- 27 25 and references therein, as well as the surveys I 35 and
2
sets (see [4 36
37
15
9
mearly-linear time (1 EE) apprrxxmmaaoo in fixed diwdenesiional spaces [5] 48 68 38 24 23).
Our (n log n.) -expected time implementation of k-means++ seeding achieves an Ollo k) expected
approximation ratio for k-median and k-means in one dimension. We are unaware of previous work on clustering algorithms running in time On log n).
Another line of research has been dimensionality reduction techniques for k-means clustering. Dimensionality reduction can be achieved via PCA based methods B1 37
21 67 or random projection 11 533 For random projection methods, it has been shown that the k-means objective is preserved up to small multiplicative factors when projecting onto O₂ (log(A) (k)) dimensional space. Additional work has shown that dimensionality reduction can be performed in O O(nnz (A)) time (5T)
To the best of our knowledge, we are the first to show that clustering objectives such as k-median and k-means are preserved up to poly(k) factor by one-dimensional projections.
Some works show that the Ollog k) expected approximation ratio for k-means++ can be improved by adding local search steps after the seeding procedure 44 20 In particular, Choo et al. [20] showed that adding ek local search steps achieves an (1/ea3 approximation ratio with high probability.
Several other algorithmic approaches exist for fast clustering of points in metric spaces. These include density-based methods like DBSCAN (4 and DBSCAN++ [43] and the line of heuristics based on the Partitioning Around Medoids (PAM) approach, such as FastPAM (63) Clarans [56). and BanditPAM [69]. While these algorithms can produce high-quality clustering, their running time is at least linear in the number of clusters (DBSCAN++ and BanditPAM) or superlinear in the number of points (DBSCAN, FastPAM, Clarans).
Recall that the lightweight coresets incur an additional additive error which can be arbitrarily large.

---

2 Overview of Our Algorithm and Proof Techniques
Our algorithm, which we call PRONE (PRojected ONE-dimensional clustering), takes random projection onto a one-dimensional space, sorts the projected (scalar) numbers, and runs the k- means++ seeding strategy on the projected numbers. By virtue of its simplicity, the algorithm is scalable and effective at clustering massive datasets. More formally, PRONE receives as input a dataset of n points in R. a parameter & E N (the number of desired clusters), and proceeds as follows:
1. Sample a random vector E R from the standard Gaussian distribution and project the data points to one dimension along the direction of v. That is, we compute x' (azz v) E R in time ((nzz(X) (X) by making a single pass over the data, effectively reducing our dataset to the collection of one-dimensional points z'...... 2yy R.
2. Run k-means++ seeding on .'....,, zn to obtain & indices f1.... fe E [ya] indicating the chosen centers ,/....,, 2'y, and an assignment a [n] - [k] assigning point z² to center " Even though k-means++ seeding generally takes (nk) time in one dimension, implementation, leveraging the fact that points are one-dimensional, which runs in O( logn) expected time, independent of k. A detailed algorithm description is in the appendix.
give an efficient
3. The one one-dimensional k-means++ algorithm produces a collection of k centers T'....., as well as the assignment a mapping each point z; to the center T) For each E [k]. we update the cluster center for cluster E be the center of mass of all points assigned to Ije
While the algorithm is straightforward, the main technical difficulty lies in the analysis. In particular, analysis (1) bounds the approximation loss incurred from the mie-dimensional projection in Step and (2) shows that we can implement Step 2 in On log n) expected time, as opposed to ((nk) time. We summarize the theoretical contributions the following theorems.
Theorem 2.1. The algorithm PRONE has expected running time (nnz((X) + log n)) any dataset X {Ii,... ........ ,, ] C Rdd. Moreover, for any 8 E (0, 1/2) and any dataset X, with probability at least 1 - 8, the algorithm runs in time (nnz(XX + n log(n/5)).
Theorem 2.2. The algorithum PRONE achieves an (k*)) approximation ratio for the k-means objective with probability at least 0.9.
To our knowledge, PRONE is the first algorithm for k-means running in time O(nd + n log n1) for arbitrary k. As mentioned in the paragraph on improving the competitive ratio we obtain the following corollary of the previous two theorems using a two-stage approach with coreset:
Corollary 2.3. By using PRONE as the a-approximatton algorithm in Theorem A.2 and running k-means++ on the resulting coreset, we obtain an algorithm with an approximation ratio of Ollog) that runs in time ((nzz(X) + log + poly (kd) log n),, with constunt success probability.
Due to space constraints, all proofs of our theoretical results are deferred the appendix, where we also generalize them beyond k k-means to clustering objectives that sum up the 2-th power of Euclidean distances for general 1. The following subsections give a high-level overview of the main techniques we develop to prove our main theorems above.
2.1 Efficient Seeding in One Dimension
The k-means++ seeding procedure has & iterations, where new center is sampled in each iteration. Since a new center may need to update 2(n) distances to maintain the D2 distribution, which samples each point with probability proportional to a running time of (nk)). A key ingredient in the proof of Theorem 2.1 is showing that, for one-dimensional datasets, k-means++ only needs to make Onn log n) updates, irrespective of
its distance its closest center, naive analysis leads
Lemma 2.4. The k-means++ seeding procedure can be implemented in expected time Onn log n) in one dimension. Moreover, for any â E (0, 1/2), with probability least 8, the implementation runs in time On log(n/ ()).
The intuition of the proof is as follows: Since points are one-dimensional, we always maintain them in sorted order. In addition, each data point v; will maintain its center assignment and distance p; the closest center. By building binary tree over the sorted points (where internal nodes maintain sums of p ss, it is easy to sample new center from the D2 distribution in Oloog n) time. The difficulty is
5

---

that adding new center may result in changes to Ps of multiple points 2i, so the challenge is to bound the number of times these values are updated (see Figure Tellow).
Figure 1:
From the top the bottom, new center (black circle) is chosen. Every point has an arrow pointing to its closest center. The points in the dashed box are the ones that require updates.
To bound the total running time, we leverage the one-dimensional structure. Observe that, for new center, the updated points lie in a contiguous interval around the newly chosen center. Once a center is chosen, the algorithm scans the points (to the left and the right) until we reach point that does not need to be updated. This point identifies that points to the other side of need be updated, so we can get away without necessarily checking all n points (see Figure I Somewhat surprisingly, when sampling centers from the D2 D--distribution, the expected number times that each point will be updated is only (log nt), which implies bound of On log n.) on the total number of updates in expectation. The analysis of the fact that each point is updated Oloog n) times non-trivial and uses carefully designed potential function (Lemma C.5
2.2 Approximation Guarantees from One-Dimensional Projections
Our proof of Theorem 2.2 builds on line of work studying randomized dimension reduction for clustering problems [4]
53]. Prior work studied randomized dimension reduction for accurate (1 [1=0) e) approxxximtssss.. Our perspective is slightly different; restrict ourselves to dieeenmnsional projections and give an upper bound on the distortion.
For any dataset Ti,..., In Rd projection to a random lower-dimensional space affects the pairwise distance between the projected points a predictable manner the Jahnson-LLindestrenn lemma which projects to Ollog n) dimensions being prime example of this fact. When projecting to just one dimension, however, pairwise distances will be significantly affected (by up to poly(n) (n)- factors). Thus, naive analysis will give (ol((r))approximmai) c-approximation to a Olog k) --aappoxxiaation, one needs a coreset of size roughly poly (c/ log k). This bound becomes vacuous when c is polynomial in since there are at most n dataset points.
for k-means. To improve
However, although many pairwise distances are significantly distorted, we show that the k-means cost is only affected by poly(k)-facte) At a high level, this occurs because the k-means cost optimizes a sum of pairwise distances (according to a chosen clustering). The individual summands, given by pairwise distances, will change significantly, but the overall sum does not. Our proof follows the approach of (21), which showed that (roughly speaking) pairwise distortion of the optimal centers suffices to argue about the k- k-means cost. The & optimal centers will incur maximal pairwise distortion poly(k) when projected to one dimension (because there are only O(k²) pairwise distances among the l centers). This allows to lift an r-approximate solution after the projection to an -(prr)-appooximate solution for the original points.
Lemma 2.5 (Informal). For any X of points in Rd. the following occurs with probability least 0.9 over the choice of a standard Gaussian vector u E Rd.. Letting X' C R be the -ineeimenia projection of X onto v, any r-approximate k-means clustering of X' gives an O(k2r) -aprr))aaproxiimate clustering of X with the same clustering partition.
Experimental Results
In this section, we outline the experimental evaluation of our algorithm. The experiments evaluate the algorithms in two different ways. For each, we measure the running time and the k-means cost the resulting solution (the sum of squares of point-to-center assigned distances). (1) First, we evaluate our algorithm as part of a pipeline incorporating a coreset construction the expected use case for our algorithm. (2) Second, we evaluate our algorithm by itself for approximate k-means clustering and compare to k-means++ [6]. As per Theorems and
we expect our algorithm be much faster but output assignment of higher cost. Our goal is to quantify these differences empirically.
[nn

---

All experiments were run on Linux using notebook with 3.9 GHz 12th generation Intel Core i7 six-core processor and 32 GiB of RAM. All algorithms were implemented in C++, using the blaze library for matrix and vector operations performed on the dataset unless specified differently below. We provide our code in the supplementary material for this submission.
Datasets. For our experiments, we use the following four datasets:
KDD 47 Training data for the 2004 KDD challenge protein homology. The dataset consists of 145751 observations with 77 real-valued features.
Song 12: Timbre information for 515345 songs with 90 features each, used for year prediction.
Census 32
1990 US census data with 2458285 observations, each with 68 categorical features.
Gaussian: A synthetic dataset consisting of 240005 points of dimension 4. The points are generated by placing a standard normal distribution at large positive distance from the origin on each axis and sampling 30000 points. The points are then mirrored so the center mass remains at the origin. Finally, points are placed on the origin. This is an adversarial example for lightweight coresets [10] which are unlikely to sample points close to the mean the dataset.
3.1 Coreset Construction Comparison
Experimental Setup. Coreset constructions (with multiplicative approximation guarantees) always proceed by first finding an approximate clustering, which constitutes the bulk of the work. The approximate clustering defines a "sensitivity sampling distribution" (we expand on this in the appendix, see also [)), and a coreset constructed by repeatedly sampling from the sensitivity sampling distribution. In our first experiment, we evaluate the choice of initial approximation algorithm used to define the sensitivity sampling distribution. We compare the use of k-means++ and PRONE. In addition, we also compare the lightweight coresets of [10), which uses the distance to the center of mass as an approximation of the sensitivity sampling distribution. For the remainder refer to sensitivity sampling using k-means++
of this section, coresets as Lightweight. All three algorithms produce a coreset, and the experiment will measure the running time of the three algorithms (Table and the quality of the resulting coresets (Figure We implemented all algorithms in C++.
Sensitivity and lightweight
Once a coreset is constructed for each of the algorithms, we evaluate the quality of the coreset by computing the cost of the centers found when clustering the coreset (see Definition state-of-the-art implementation of Lloyd's k-means algorithm from the scikit- with the default configuration (repeating 15 times and reporting the mean cost to reduce the variance). The resulting quality of the coresets is compared to (computationally expensive) buseline, which runs k t-menns++ ++ from the frikit-leary library, followed by Lloyd's algorithm with the default configuration on the entire dataset (repeated 5 times to reduce variance).
A. I.Ipp We run library [57]
We evaluate various choices of Is ([10, 100, 1000}) as well as coresets various relative sizes, (0.001, 0.0025, 0.005, 0.01, 0.025, 0.05, 0.1} times the size of the dataset. We use as performance metrics (1) relative cost, which measures the average cost of the k-means solutions returned by Lloyd's 'ss algorithm on each coreset divided by the baseline, and (2) the running time of the coreset construction algorithm.
Results on Coreset Constructions. Relative cost. Figure 2 shows the coreset size (x-axis) versus the relative cost (y-axis). Each "row" of Figure 2 corresponds a different value for 1 E (10, 100, 1000). and each "column" corresponds to different dataset. Recall that the first three datasets (i.e., the first three columns) are real-world datasets, and the fourth column is the synthetic Gaussian dataset. We note our observations below:
As expected, on all real-world data sets and all settings of ks the relative cost decreases as the coreset size increases.
In real-world datasets, the specific relative cost of each coreset construction (Senstivity, Lightweight, and ours) depends on the datase [1 but roughly speaking, all three share a similar trend. Ours and Sensitivity are very close and never more than twice the baseline (usually much better).
'The spike in relative cost for algorithm Sensitivity on the KDD data set for relative size 5 10-3 3 is due to outliers.
7

---

Datauer: 130
Cotnert Seng
Dacanee CAntL
Conmet Gaurtan
Le
1.05
2300
1.05
1050
1.00
20
1845
1.01
1.
3000
10"
10
1377
14"
10
22
12
100
3.50
PM61 ve
1.05
k-moanee Secctiity
Agar then
1.40
3.00
1554
101
10-1
151
10.19
33.4
33*1
35-1
30rl
1.5
15
1.8
1.4
10
OUSC
1-4
10
Baterive San
Retstiva
An Anadio Size
Figure 2: Plot of relative cost versus coreset size on our four datasets. The shaded region indicates standard error. There no data for relative size values where the coreset size less than
The big difference, distinguishing ours and Sensitivity from Lightweight, is the fourth column, the synthetic Gaussian dataset. For all settings of k the coreset size increases, Lightweight exhibits a minimal cost decrease and is factor 2.7-17x times worse than ours and Sensitivity (as well as the baseline). This is expected, we constructed the synthetic Gaussian dataset to have arbitrarily high cost with Lightweight. Due to its multiplicative approximation guarantee, our algorithm does not suffer this degradation. In that sense, our algorithm is more "robust," and achieves worst-case multiplicative approximation guarantees for all datasets.
Running time. In (the first table in) Table T we show the running time of the coreset construction algorithms as k increases. Notice that as k increases, the relative speedup of our algorithm and Lightweight increases in comparison to Sensitivity. This is because our algorithm and Lightweight have running time which does not grow with kt. In contrast, the running time of Sensitivity grows linearly in k. In summary, our coreset construction is between 33-192x faster than Sensitivity for large k. In addition, Our analysis also shows this; both algorithms make an initial pass over the dataset, using ((nd) time, but ours uses additional O(n log n) time to process.
algorithm runs about 3-5x slower than Lightweight, depending the dataset.
3.2 Direct k-Means++ Comparison
Experimental Setup. This experiment compares our algorithm and k-means++ as a stand-alone clustering algorithm, as opposed to as part of coreset pipeline. We implemented three variants of our algorithm. Each differs in how we sample the random -i-dimensional projection. The first is one-dimensional projection onto standard Gaussian vector (zero mean and identity covariance). This approach risks collapsing an "important" feature, i.e. feature with high variance. To mitigate this, we implemented two data-dependent variants that use the variance, resp. covariance of the data. Specifically, in the "variance" variant, we use a diagonal covariance matrix, where each entry in the diagonal is set to the empirical variance of the dataset along the corresponding feature. In the "covariance" variant, we use the empirical covariance matrix of the dataset. These variants aim to project along vectors that capture more of the variance of the data than when sampling vector uniformly at random. Intuitively, the vectors sampled by the biased variants are more correlated with the first principal component of the dataset. For each of our algorithms, cost of the output set C' of centers when assigning points to the closest center (cost> C) in Definition A.I and when using
evaluate the k- k-means
algorithm's 's assignment (cost2 C, defined in Equation (I). We evaluated the algorithms for every l in (10, 25, 50, 100, 250, 500, 1000, 2500, 5000) and = = 2, for sol solving k-means with the lg- metri.... When evaluating the assignment cost, we ran each of our
8

---

Dananet XTD
Docanet Song
Datenet Census
Dacanet GeuedAn
201
2011
Algerith
3
(cevarance))
100
101
Dataset - 42D
Datase:- - Song
Datase: - Cersus
102
Dutaset Caussion
Vie to!
Alperthm
88
1004
10
MORE (nntaree
104
24300
301
307
124
133
124 103
16"
107
101
101
Figure 3: Clustering cost of all our variants compared to k-means++. The top row shows the k-means cost, and the bottom row shows the cost of the assignment produced by our algorithm.
k
500
5000
Dataset
Algorithm
100
1000
Census
7.5
73.2
662.5
Dataset
Algorithm
PROXE (variance)
2.2
22.2
214.7
Census
Lightweight
7.3
69.4
670.2
(covariance)
117.4
PRONE coreset
1.5
14.1
136.3
I-mcans++
1.0
1.0
1.0
Sensitivity
1.0
1.0
1.0
Song
PROXE
9.7
95.5
837.5
Song
Lightweight
8.9
87.2
875.3
PROVE (variance)
2.3
23.1
217.2
PRONE coreset
2.1
19.9
187.9
PROVE (covariance)
0.8
8.2
82.4
Sensitivity
1.0
1.0
1.0
k m-mmuu+++
1.0
1.0
1.0
KDD
Lightweight
6.4
63.0
642.8
KDD
PROVE
6.9
68.3
727.5
PROME coreset
2.1
192.6
PROVE (variance)
3.1
32.0
312.4
Sensitivity
1.0
1.0
1.0
PROXE (cnvariance)
1.3
12.9
128.4
Lightweight
m-mmen+++
PROME cnneset
0.5
3.8
33.7
Gaussian
PROME
1.9
18.3
165.9
Sensitivity
(variance)
PRONE (covariance)
1.7
16.1
152.6
1.0
Table 1: Average speedup over sensitivity sampling across all relative sizes for constructing coresets (in the first table) and average speedup over k-means++ as stand-alone clustering algorithm (in the second table). The tables with the full range of parameters can be found in the appendix.
algorithms 100 times for each i and five times when computing the nearest neighbor assignment, and we report the average cost of the solutions and the average running time. Due to lower variance and much higher runtime, k-means++ was run five times.
Results on Direct A-Means++ Comparison. Cost. Figure 3 (on top) shows the cost of the centers found by our algorithm compared to those found by the k-means++ algorithm after computing the optimal assignment of points to the centers computed by the algorithm (computing this takes time (ndk))) That is, we compare the values of cost (X, C') in Definition A. In summary, the k-means cost of all three variants of our algorithm are roughly the same and closely match that of m-means++ On the Gaussian data set, one run of the biased algorithm failed to pick center from the cluster at the origin, leading to a high "outlier" cost and a corresponding spike in the plot.
We also compared the k-means cost for the assignment computed by our algorithm (so that our algorithm only takes time O(nd n log n)) and not O(ndk)) with the cost of k-means++ (bottom row of Figure 3. That is, we compare the values of costz X, C, o)) defined in Equation ( The clustering cost of our algorithms is higher than that of k-means++. This is the predicted outcome from our theoretical results; recall Theorem 2.2 gives poly(k)-approxiin) approximation, as opposed to Olog k) from k-means++. On the real- world data sets, is between one order of magnitude (for 10) and two orders of magnitude (for A: = 5000) worse than k-means++ for our unbiased variant and between a factor 2 (for 10) and one order of magnitude (for k = 5000) worse than k-means++ for our biased and covariance variants.

---

Running time. Table [ shows the relative running time of our algorithm compared to k-means++, assuming that no nearest-center assignment is computed. Our algorithms are designed have running time independent of k, so we can see, from the second table in Figure] [ all of our variants offer significant speedups.
The running time of our algorithm stays almost constant as i increases while the running time of k- k-means++ scales linearly with k. Specifically for k 25, even slowest variants have about the same running time as k-means++, while for k = 5000, is at least 82x faster, and our fastest version is up 837x faster over k-means++.
The two variants can affect the quality of the chosen centers by up an order of magnitude, but they are also significantly slower. The "variance" and "covariance" variants are slower (between 2-4x slower and up 10x slower, respectively) than the standard variant, and they also become slower as the dimensionality d increases. We believe these methods could be further sped up, as the blaze library's 's variance computation routine appears inefficient for our use case.
4 Conclusion and Limitations
To summarize, we present simple algorithm that provides new tradeoff between running time and approximation ratio. Our algorithm runs in expected time ((nzz(X) ) + n log n) to produce a (kly(k) aaproxxiappooiii with additional poly(kd) log time, we improve the approximation to Ollog k). This latter bound matches that of k-means++ but offers a significant speedup.
Within a pipeline for constructing coresets, our experiments show that the quality of the coreset produced (when using our algorithm as the initial approximation) outperforms the sensitivity sampling algorithm. It is slower than the lightweight coreset algorithm, but it more "robust" independent of the diameter of the data set. It does not suffer from the drawback of having an additive error linear in the diameter of the dataset, which can arbitrarily increase the cost of the lightweight coreset algorithm. When computing an optimal assignment for the centers returned by our algorithm, its cost roughly matches the cost for k-means+++. When directly using the assignment produced by one variant of our algorithm, its cost is between a factor and 10 worse while being up to 300 times faster.
it is
Our experiments and rumning time analysis show that our algorithm is very efficient. However, the clustering quality achieved by our algorithm is sometimes not good as other, slower algorithms. We show that this limitation is insignificant when we use our algorithm to construct coresets. remains an interesting open problem to understand the best clustering quality (e.g., terms of approximation ratio) an algorithm can achieve while being as efficient as ours, i.e., running in time Onnd + n log n).
Another interesting problem is whether other means of projecting the dataset into (11) dimensional space exist, which lead to algorithms with improved approximation guarantees and running time faster than (ndk)..
Acknowledgments and Disclosure of Funding
Moses Charikar was supported Simons Investigator award.
Lunjia Hu was supported by Moses Charikar's and Omer Reingold's Simons Investigators awards, Oner Reingold's NSF Award IIS- 190774,774, and the Simons Foundation Collaboration on the Theory of Algorithmic Fairness. Part of this work was done while Erik Waingarten was a postdoc at Stanford University, supported by an NSF postdoctoral fellowship and by Moses Charikar's Simons Investigator Award.
This project has received funding from the European Research Council (ERC) under the European Union's 's Horizon 2020 research and innovation programme (Grant agreement No. 101019564 "The Design of Modern Fully Dynamic Data Structures (MoDynStruuct" and the Austrian Science Fund (FWF) project Z 422-N, project "Static and Dynamic Hierarchical Graph Decompositions", I 5982-N, and project "Fast Algorithms for Reactive Network Layer (ReactNet)",, 33775-N, with additional funding from the netidee SCIENCE Stiftung, 2020-2024.
10

---

References
[1] Pankaj K Agarwal, Sariel Har-Peled, Kasturi R Varadarajan, et al. Geometric approximation via coresets. Combinatorial and computational geometry, 52(1):1-30, 2005.
[2] Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, and Justin Ward. Better guarantees for k-means and Euclidean k-median by primal-dual algorithms. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 61-72, 2017.
[3] Daniel Aloise, Amit Deshpande, Pierre Hansen, and Preyas Popat. NP-hardness of Euclidean sum-of-squares clustering. Machine Learning, 75(2):245-244 2009.
[4] Alexandr Andoni, Piotr Indyk, and Ilya Razenshteyn. Approximate nearest neighbor search in high dimensions. In Proceedings of the International Congress of Mathematicians: Rio de Janeiro 2018, pages 3287-3318. World Scientific, 2018.
[5] Sanjeev Arora, Prabhakar Raghavan, and Satish Rao. Approximation schemes for Euclidean k-medians and related problems. In Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing. STOC '98, page 106-113, New York, NY, USA, 1998. Association for Computing Machinery.
[6] David Arthur and Sergei Vassilvitskii. k-means++: the advantages of careful seeding. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium Discrete Algorithms, pages 1027-1035. ACM, New York, 2007.
[7] Olivier Bachem, Mario Lucic, Hamed Hassani, and Andreas Krause. Fast and provably good seedings for k-means. In Lee, M. Sugiyama, U. Luxburg, Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 29. Curran Associates, Inc., 2016.
[8] Olivier Bachem, Mario Lucic, S. Hamed Hassani, and Andreas Krause. Approximate k-means++ in sublinear time. Proceedings of the AAAI Conference on Artificial Intelligence, 30(1), Feb. 2016.
[9] Olivier Bachem, Mario Lucic, and Andreas Krause. Practical coreset constructions for machine learning. arXiv preprint arXiv:1703.066 2017.
[10] Olivier Bachem, Mario Lucic, and Andreas Krause. Scalable k -means clustering via lightweight coresets. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. KDD '18, page 1119-1127, New York. NY, USA, 2018. Association for Computing Machinery.
[11] Luca Becchetti, Marc Bury, Vincent Cohen-Addad, Fabrizio Grandoni, and Chris Schwiegelshohn. Oblivious dimension reduction for k-means: Beyond subspaces and the johnson-lindenstraus. lemma. In Proceedings of the 5 Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, page 1039-1050, New York, NY, USA, 2019. Association for Computing Machinery.
[12] Thierry Bertin-Mahieux, Daniel P.W. Ellis, Brian Whitman, and Paul Lamere. The million song dataset. In Proceedings of the 12th International Conference on Music Information Retrieval (ISMIR 2011), 2011.
[13] Thomas Bottesch, Thomas Bühler, and Markus Kächele. Speeding up k-means by approximating Euclidean distances via block vectors. Maria Florina Balcan and Kilian Q. Weinberger, editors, Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 2578 2586, New York, New York, USA, 20-22 Jun 2016. PMLR.
[14] Christos Boutsidis, Anastasios Zouzias, Michael W Mahoney, and Petros Drineas. Randomized dimensionality reduction for k-means clustering. IEEE Transactions on Information Theory, 1062 2014.
[15] Vladimir Braverman, Dan Feldman, and Harry Lang. New frameworks for offline and streaming coreset constructions. CoRR, abs/1612.00889, 2016.

---

[16] James Briggs, Faiss: The missing manual.
10 www.lo/r//aaaass...a///oo//
[17] Jarostaw Byrka, Thomas Pensyl, Bartosz Rybicki, Aravind Srinivasan, and Khoa Trinh. An improved approximation for k-median, and positive correlation in budgeted optimization. In Proceedings of the Twenty-Sixe Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '15, page 737-756, USA, 2015. Society for Industrial and Applied Mathematics.
[18] Marco Cap6, Aritz Pérez, and Jose A Lozano. An efficient k-means clustering algorithm for massive data. arXiv preprint arXiv: eete::801...90 2018.
[19] Ke Chen. On coresets for k-median and k-means clustering in metric and Euclidean spaces and their applications. SIAM Journal on Compuling, 39(3):92-9947, 2009.
[20] Davin Choo, Christoph Grunau, Julian Portmann, and Vaclav Rozhon. k-means++: few more steps yield constant approximation. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 1909-1917. PMLR, 13-18 Jul 2020.
[21] Michael B. Cohen, Sam Elder, Cameron Musco, Christopher Musco, and Madalina Persu. Dimensionality reduction for k-means clustering and low rank approximation. In Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, STOC '15, page 163-172, New York, NY, USA, 2015. Association for Computing Machinery.
[22] Vincent Cohen-Addad. A fast approximation scheme for low-dimensional k-means. In Pro- ceedings of the Twenty-Ninth Annual ACM-SIAM Symposiun Discrete Algorithms, SODA '18, page 440, USA, 2018. Society for Industrial and Applied Mathematics.
[23] Vincent Cohen-Addad, Andreas Emil Feldmann, and David Saulpic. mation schemes for clustering in doubling metrics. J. ACM, 68(6), oct 2021.
time approxi-
[24] Vincent Cohen-Addad, Philip N. Klein, and Claire Mathieu. Local search yields approximation schemes for k-means and k-median in Euclidean and minor-free metrics. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 353-364, 2016
[25] Vincent Cohen-Addad Kasper Green Larsen, David Saulpic, and Chris Schwiegelshohn. To- wards optimal lower bounds for k-median and k-means coresets. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 1038-1051, 2022.
[26] Vincent Cohen-Addad Silvio Lattanzi, Ashkan Norouzi-Fard, Christian Sohler, and Ola Svens- son. Fast and accurate k-means++ via rejection sampling. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances Neural Information Processing Systems, volume 33, pages 16235-16245. Curran Associates, Inc., 2020.
[27] Vincent Cohen-Addad David Saulpic, and Chris Schwiegelshohn. A new coreset framework for clustering. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 169-182, 2021.
[28] Ryan R Curtin. A dual-tree algorithm for fast k-means clustering with large k. In Proceedings of the 2017 SIAM International Conference on Data Mining, pages 300-308. SIAM, 2017.
[29] Yufei Ding, Yue Zhao, Xipeng Shen, Madanlal Musuvathi, and Todd Mytkowicz. Yinyang k-means: A drop-in replacement of the classic k-means with consistent speedup. Francis Bach and David Blei, editors, Proceedings of the 32nd International Conference Machine Learning, volume of Proceedings of Machine Learning Research, pages 579-587, Lille, France, 07-09 Jul 2015. PMLR.
[30] Jonathan Drake. Faster k-means clustering. PhD thesis, Baylor University, 2013.
[31] Petros Drineas, Alan Frieze, Ravi Kannan, Santosh Vempala, and Vishwanathan Vinay. Cluster- ing large graphs via the singular value decomposition. Machine learning, 56:9-33, 2004.
[32] Dheeru Dua and Casey Graff. UCI machine learning repository, 2017.
12

---

[33] Charles Elkan. Using the triangle inequality to accelerate k-means. In Proceedings of the Twen- tieth International Conference on International Conference on Machine Learning, ICML'03. page 147-153. AAAI Press, 2003.
[34] Martin Ester, Hans-Peter Kriegel, Jörg Sander, and Xiaowei Xu. A density-based algorithm for discovering clusters in large spatial databases with noise. In Proceedings of the Second International Conference on Knowledge Discovery and Data Mining, KDD'96, page 231.
AAAI Press, 1996.
[35] Dan Feldman. Introduction to core-sets: updated survey, arXiv preprint 1eXiv:0011009385 2020.
[36] Dan Feldman and Michael Langberg. A unified framework for approximating and clustering data. In Proceedings of the forty-thire terty-thirddd annual ACM symposium on Theory of computing, pages 569-578, 2011.
[37] Dan Feldman, Melanie Schmidt, and Christian Sohler. Turning big data into tiny data: Constant- size coresets for k-means, pea, and projective clustering. SIAM Journal on Computing, 49(3):601-657, 2020.
[38] Zachary Friggstad, Mohsen Rezapour, and Mohammad R. Salavatipour. Local search yields a plas for k-means in doubling metrics. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 365-374, 2016.
[39] Fabrizio Grandoni, Rafail Ostrovsky, Yuval Rabani, Leonard J. Schulman, and Rakesh Venkat. refined approximation for Euclidean k-means. Inf. Process. Lett., 176(C), jun 2022.
[40] Greg Hamerly. Making k-means even faster. In Proceedings of the 2010 SIAM international conference data mining, pages 130-140. SIAM, 2010.
[41] Sariel Har-Peled and Soham Mazumdar. On coresets for k-means and k-median clustering. In Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, STOC '04, page 291-300, New York, NY, USA, 2004. Association for Computing Machinery.
[42] Oktie Hassanzadeh, Fei Chiang, Hyun Chul Lee, and Renée J. Miller. Framework for evaluating clustering algorithms in duplicate detection. Proc. VLDB Endow, 2(1): 1282-1233,, aug 2009.
[43] Jennifer Jang and Heinrich Jiang. Dbscan++: Towards fast and scalable density clustering. In International conference machine learning, pages 3019-3029. PMLR, 2019.
[44] Herve Jegou, Matthijs Douze, and Cordelia Schmid. Product quantization for nearest neighbor search. IEEE transactions on pattern analysis and machine intelligence, 33(1):117-128, 2010.
[45] T. Kanungo, D.M. Mount, N.S. Netanyahu, C.D. Piatko, R. Silverman, and A.Y. Wu. An efficient k-means clustering algorithm: analysis and implementation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 24(7):881 1-28892, 2002.
[46] Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine Piatko, Ruth Silverman, and Angela Y. Wu. The analysis of a simple k-means clustering algorithm. In Proceedings of the Sixteenth Annual Symposium on Computational Geometry, SCG '00, page 100-109, New York, NY, USA, 2000, Association for Computing Machinery.
[47] 2004 KDD Cup.
Protein homology dataset.
available at
httpss//osmot.csccomeel/ www.ee/wwwcwwccccdaasste.....e 2004.
[48] Stavros G. Kolliopoulos and Satish Rao. A nearly linear-time approximation scheme for the Euclidean k-median problem. In Jaroslav Nešetřil, editor, Algorithms ESA' 99, pages 378-389, Berlin, Heidelberg, 1999. Springer Berlin Heidelberg.
[49] Silvio Lattanzi and Christian Sohler. better k-means++ algorithm via local search. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine I Learning Research, pages 3662-3671. 1.0.7.....LLL.. PMLR, 19-15 Jun 2019.
13

---

[50] Shi Li and Ola Svensson. Approximating k-median via of the Forty-Fifthl Annual ACM Symposium on Theory of Compuring, STOC '13, page 901-910, New York, NY, USA, 2013. 3. Association for Computing Machinery.
In Proceedings
[51] Weiwei Liu, Xiaobo Shen, and Ivor Tsang. Sparse embedded k-means clustering. Advances in neural information processing systems, 30, 2017.
[52] Stuart P. Lloyd. Least squares quantization in PCM. IEEE Transactions on Information Theory, 28(2):129-131) 1982.
[53] Konstantin Makarychev, Yury Makarychev, and Ilya Razenshteyn. Performance of johnson- lindenstrauss transform for k-means and k-medians clustering. In Proceedings of the s1 Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, page 1027-1038, New York, NY, USA, 2019. Association for Computing Machinery.
[54] Andrew W. Moore. The anchors hierarchy: Using the triangle inequality to survive high dimensional data. In Proceedings of the Sixteenth Conference Uncertainty in Artificial Intelligence, UAT00,, page 397-405, San Francisco, CA, USA, 2000. Morgan Kaufmann Publishers Inc.
[55] James Newling and Francois Fleuret. Fast k-means with accurate bounds. In Maria Florina Balean and Kilian Q. Weinberger, editors, Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 936-944, New York, New York, USA, 20 22 Jun 2016. PMLR.
[56] Raymond T. Ng and Jiawei Han. Clarans: A method for clustering objects for spatial data mining. IEEE transactions on knowledge and data engineering, 14(5):1003-1016, 2002.
[57] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, 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-2888 2011.
[58] Dan Pelleg and Andrew Moore. Accelerating exact k-means algorithms with geometric rea- soning. In Proceedings of the Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 199, page 277-281, New York, NY, USA, 1999. Association for Computing Machinery.
[59] James Philbin. Scalable object retrieval in very large image collections. PhD thesis, Oxford University, 2010.
[60] James Philbin, Ondrej Chum, Michael Isard, Josef Sivic, and Andrew Zisserman. Object retrieval with large vocabularies and fast spatial matching. In 2007 IEEE Conference Computer Vision and Pattern Recognition, pages 1-8, 2007.
[61] Feng Qian, Abhinav Pathak, Yu Charlie Hu, Zhuoqing Morley Mao, and Yinglian Xie. A case for seaiperrisse--lamiin--bbe jun 2010.
spam filtering, SIGMETRICS Perform. Eval. Rev,, 38(1):367-368,
[62] M Ali Rostami, Alieh Saeedi, Eric Peukert, and Erhard Rahm. Interactive visualization of large similarity graphs and entity resolution clusters. In EDBT, pages 690-693, 2018.
[63] Erich Schubert and Peter J Rousseeuw. Faster k-medoids clustering: improving the pam, clara, and clarans algorithms. In Similarity Search and Applications: 12th International Conference, SISAP 2019, Newark, NJ, USA, October 2-4, 2019, Proceedings 12, pages 171-187. Springer, 2019.
[64] D. Sculley. Web-scale k-means clustering. In Proceedings of the 19th International Conference on World Wide Web, WWW '10, page 1177-1178, New York, NY, USA, 2010. Association for Computing Machinery.
[65] Mina Sheikhalishahi, Andrea Saracino, Mohamed Mejri, Nadia Tawbi, and Fabio Martinelli. Fast and effective clustering of spam emails based on structural similarity. In Joaquin Garcia- Alfaro, Evangelos Kranakis, and Guillaume Bonfante, editors, Foundations and Pructice of Security, pages 195-211, Cham, 2016. Springer International Publishing.
14

---

[66] Harsha Vardhan Simhadri, George Williams, Martin Aumüller, Matthijs Douze, Artem Babenko, Dmitry Baranchuk, Qi Chen, Lucas Hosseini. Ravishankar Krishnaswamny, Gopal Srinivasa, et al. Results of the neurips 21 challenge on billion-scale approximate nearest neighbor search. In NeurlPS 2021 Competitiins and Demonstrations Track, pages 177-189. PMIR, 2022.
[67] Christian Sohler and David P Woodruff. Strong coresets for k-median and subspace approxima- tion: Goodbye dimension. In 2018 IEEE 59th Annual Symposium Foundations of Computer Science (FOCS), pages 802-813. IEEE, 2018.
[68] Kunal Talwar. Bypassing the embedding: Algorithms for low dimensional metrics. In Proceed- ings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing. STOC '04, page 281-290, New York, NY, USA, 2004. Association for Computing Machinery.
[69] Mo Tiwari, Martin Zhang. James Mayclin, Sebastian Thrun, Chris Piech, and Ilan Shomorony. Banditpam: Almost linear time k-medoids clustering via multi-armed bandits. Advances in Neural Information Processing Systems, 111111111222211 2020.
[70] Erik Waingarten. Notes for algorithms for big data: Clustering, https://drive. google
[71] Jing Wang, Jingdong Wang, Qifa Ke, Gang Zeng, and Shipeng Li. Fast approximate k-means via cluster closures. In 20/2 IEEE Conference Computer Vision and Pattern Recognition, pages 3037-3044, 2012.
15

---

A Problem Setup and Background
In this work, we always consider datasets X f In C R of high-dimensional vectors, and we will measure their distance using the Euclidean (f2) distance. Below, we define (k, -lccusstri, This problem introduces parameter 2 1, which measures the sensivity outliers (as grows, the clusterings become more sensitive to points furthest from the cluster center). The case of k-means corresponds
2, but other values of capture other well-known clustering objectives, like k-median (the case of 2 = 1).
Definition A.1 ((k -luustrrri, Consider a dataset X = (21....,, C IRd, desired number of clusters k E N, and a parameter z 2 1. For a set of k centers C = (ci,..., c C Rd, let cost, (X, C)) denote the cost of using the center set C to cluster X, i.e.
cost (X,C)
E min | - cgl22-
1
jE(M]
We let = denote the optimal cost over all choices of = .k) C CR²:
o (X) inf cost, (X,
CC
1clsk
A (k: z)-cuuttering algorithm has the following specifications. The algorithm receives as input dataset X = [IT } C. Rd, as well as two parameters is E N and 2 2 1. After it executes, the algorithm should output a set of k centers C = te.,..., Ck C Rd as well as an assignment [m] k] mapping each point x; a center Co(()-
We measure the quality of the solution (C, using the ratio between its (k, =llusterii cost cost, a) and the optimal cost , (X), where
cost (X,
Σ | Co(w.)
For any D 1, an algorithm that produces a D-approximation to (A: zllcttrtering should guarantee that cost. (X, C, or) is at most D opt,, (X)) For randomized algorithm, the guarantee should hold with large probability (referred to as the success probability) for any input dataset.
A.1 k-Means++ Seeding
The k-means++ seeding algorithm a well-studied algorithm introduced in 66. and it an important component of our algorithm. Below, we describe it for general 1, not necessarily
2. Definition A.2 (k-means++ seeding, for arbitrary z 2 1). Given n data points & $1...., Inp E Rdd the k-means+ + seeding algorithm produces set of k centers, I with the following procedure:
1. Choose & uniformly at random from [n].
2. For i = .....,k. sample l, as follows. For every i E [n]. let denote the Euclidean distance from I; its closest point among Ftis... Iit Sample &, from [n] so that the probability Pr(e, = i] is proportional to př for every i [n). That is,
P
Pr[ee = Evei P.
the context of k-means (iee, when = 2), the distribution known as the D)2 distribution.
3. Output Th.
In the above description, Step 2 of k-means++ needs maintain, for each dataset point V;, the Euclidean distance p; to its closest center among the centers selected before the current iteration. This step is implemented by making entire pass over the dataset for each of the k iterations of Step 2 leading to an ((ndk) running time.
Theorem A.1 (6), Theorem in (70). For Z1...., In h Rdd let X (z xn be the input to the k-means++ + seeding algorithm. For the output ot,...., Tt, of the k-means++ + seeding algorithm, define C ( Jt. Then
Elcost, (x, C*] O(22 log k) opt,, (X).
16

---

A.2 Coresets via Sensitivity Sampling
One of our algorithm's 's applications constructing coresets for (k: 2) clusserrng. We give a formal definition and describe the primary technique for building coresets.
Definition A.3. Given a dataset X (xi...., Fn C RR, as well as parameters N, 2 2 1 and & > O, a (strong) e-coreset for (ki, z)-clstteingg specified by a set of points C IR4 and a weight function w: Y R20, such that, for every set C {c1, ........ Ck 12d,
(1 =) cost, (x, (X, -
((y) min lly cy 2 s (1 +) cost, cost, C). JE(R
yEY
Coresets are constructed via "sensitivity sampling." a technique that, given approximate clustering of a dataset X, produces a probability distribution such that sampling enough points from this distribution results in coreset.
Definition A.4 (Sensitivity Sampling). Consider dataset X (ai,..., Fnn C RR, well as parameters E N. 2 2 1. For centet set C = (ci...., Cb C. R2 and assignment a: [n] + [k], let
X, {2y j}. We let DD be distribution supported on X where
|x, Ca(i)
[xr = 04) X æ>D
2==1
[0z
Coc
[Xae)l
The main theorem that we will use is given below, which shows that given a center set and an assignment that gives an a-approximation to (k, :)-clustering, one may sample from the distribution D defined about in order to generate a coreset with high probability.
Theorem A.2 (15)). For any dataset X (I1,.... , In Rd and any parameters and 1. suppose that C CC Rd and a: [n] + [k] a a-approximation (k, z)-clustering, iee,
Σ | - co l1 S opt,,
Letting D denote the distribution specified in Definition the following occurs with high probability.
We let y1.---. ys denote independent samples from DD and w(y be the inverse of the probability that y; is sampled according to 'D. We set 2 poly(kd: a 2 2e)e).
The set = f........ with weights w is an E-coreset for (k, =llusseeriin
A.3 Simple Lemma
We will repeatedly use the following simple lemma.
Lemma A.3. Let o, b E R2 be any two numbers and = 2 1. Then, (a + b)2 S 2 + 22-113
Proof. The function d(t) 1a is convex for 1, Jensen's inequality implies Φ((a + b)/2) < (1/2)ø(a) + (1/2)ø(b).
B Approximation Guarantees from One-Dimensional Projections
In this section, we prove Theorem 2.2 (rather, the generalization of Theorem 2.2 to any 2 2 1) by analyzing the random one-dimensional projection step in our algorithm. In order to introduce some notation,
= (xI,..., In} Rd be set of points, and for partition of X into sets, (Y,,..., Ye), we let the (k, =.clusteriii cost of X with the partition (Y,,..., Yx) be
cost, (Y Yk)
Σ min Σ
|1 cll
CER
YEY
and call the & points e selected as minima a set of centers realizing the (k, =l-custtriing cost of .Y,...,Yo Yx). We note that (2) is cost function for (k, 2)-clusterin but it is different from
17

---

Definition A.1 In Definition A. the emphasis is on the set of & centers C = fci...., )+), and the induced of clustering of X, i.e., the partition (Yi...., Yx) given by assigning points to the closest center, is only implicitly specified by the set of centers. On the other hand, 2 emphasizes the clustering V& (Y,.... and the set of centers implicitly specified by (Y,,..., Vt). The optimal set of centers and the optimal clustering will achieve the same cost; however, our proof will mostly consider the clustering [Y,..... Yk) as the object to optimize. Shortly, we will sample (random) dimensionality reduction map II: R" I'' and seek bounds for t 1. We will write cost, (II(Y1):.. II)) for the cost of clustering the points after applying the dimensionality reduction map II the partition ...... Yı. Namely, write
cost, (II())) II)) - E
Σ [II cl
min
OER E=1
ZEY:
Definition B.1. For set of points X (xI,.... InJ C Rd, we use Xi...., X2 of X to denote the
partition of X with minimum (k, 2) -clusterin cost and we use C = set of k centers which realizes the (k, cluustrrn cost of .i...., X i.e. the set of centers which satisfies
3 C R to denote
cost (Xi, X
E --- i=1zEx;
By slight abuse of notation, we also lel c X O be the map which sends every point of X its corresponding center (i.e., i & Xi, then e² (x) is the point c.).
prove the following lemma, which generalizes Lemma 2.5 from k-means to (k, =)clusterii (recall that k-means corresponds to the case of = 2).
Lemma B.1 (Effect of One- Dimeesionnl Projection on (k, 2) Clusterrig)) For n, d, k E N and
2 2 1, let X = (x1...., 3 C IR be an arbitrary dataset. We consider the (random) linear map
II Rd > given by sampling g ~ (0, Ia) and setting
IT (T)) = (xr, g)-
With probability at least 0.9 over g, the following occurs:
We consider the projected dataset X' (a' I',, IR be given by x II(x,) and
For any 1, we let (Y1,...Ye) Yi.) denote any partition of X satisfying
cost. (II()),...... IIxY))) Sr.
min
Σ min | cy1².
Cpenn ER
jE(K]
Then,
cost,(Yi,.... Y2) < 20()) 22= T optp,,
We can immediately that, from Lemma B.1 and the approximation guarantees of k-means+ (or rather, its generalization to 2 2 1) in Theorem A.I we obtain desired approximation guarantees. Below, state the generalization to all 2 and, assuming Lemma B.I its proof.
By setting = 2, obtain the desired bound from Lemma 2.5
of Theorem 2.2
Theorem B.2 (Generalization of Theorem 2.2 to 2 1). For n, n,,,k E and 2 2 1, let X =
(x1...., Fn IRd be arbitrary dataset. We consider the following generalization our algorithm PRONE:
1. Sample a random Gaussian vector g -N La) and consider the projection X' "e', given by x -I(x;, for II(x) = (x. E R.
2. Execute the (generalization of the) k-means++ seeding stralegy for 2 of Definition A.2 with the dataset X' C RR and ...,...., , denote the centers and (Y 11,..., denote the partition of X specifying the ko clusters found.
18

---

3. Output the clustering (YI.... Yd), and the set of centers C1. E R' where
Cj E x>>Y( E
Then, with probability at least 0.8 over the execution of the algorithm,
cost. (Y Y
1 - ce cellã = 20() k2= log k (X).
nYY
Proof of T'heorem B.2 assuming Lemma B.J cution of the algorithm) that:
We consider the case (over the randomness the exe-
1. The conclusions of Lemma B.1 hold for the projected dataset X' (which happens with probability at least 0.9) by Lemma B.I
2. The execution of the generalization k-means++ seeding strategy on X' (from Defini tion A.2 produces a set of centers ( 2/1,} C R which cluster X' with cost most ( log k)) (X'),=(X') (which also happens with probability 0.9 by Markov's inequality).
By union bound, both hold with probability at least 0.8. We now use Lemma B. to upper bound the The first inequality is trivial; suppose we let ......, 2s Rd be the centers which minimize each E [k]
cost of the clustering (Y i..... x)).
min Σ ARERd YeY:
11--
cell:
Σ YEY
1 c
Then, trivially have
cost. (Y, Ys)
Σ f=1xEY,
Σ
| -
Ef S
Σ (=1xEY,
Σ || - callē-
Furthermore, also show corresponding upper bound. For each & E [k]. recall that Cg Rd is the center of mass of Y k. so we can apply the triangle inequality and Lemma A.3
Σ zeYr
cell 22-1
Σ
1
0 +
2 YYel
E m>y
[x]
Y
2
Σ
2
2 Y
E
- 231
=>Y;
xEY;
where the second inequality is Jensen's 's inequality, since Φ(x) = || - æ is convex for 2 2 1. Thus, we have upper-bounded
Σ xEY,
| coll5 2 Σ | -
DEY,
and therefore
k
Σ
Σ
| - c 2 2 cost. 1,,..., Yt).
(3)
8=1 D
The final step involves relating cost. (YI..... i..... Y k) using the conclusions of Lemma B. Notice that
our algorithm produces the clustering (Y) Y...., Yx) of X' which is specified by letting
Y = (a. x : E [k), |ob =z/,1 I |ay x,,1=).
and by the event
have cost. (II 1) ... II v)) < 0 log k) opt (X'). By event
Lemma B.1 implies that cost, Y,,.... 1,.... Yx) < 20(x). 2 0(222 log k) opt (X). Combined
with 33) we obtain our desired bound.
D
19

---

B.1 Proof of Lemma B.1
We now turn to the proof of Lemma where our analysis will proceed in two steps. First, we assume fixed dimensionality reduction map II: R - R², which satisfies two geometrical conditions on II. Under these conditions, we show how to "lift" an approximate clustering of the mapped points in IR. to an approximate clustering of the original dataset in IR at the cost of weakening the approximation ratio. Then, we show that a simple one-dimensional projection II: Rd - IR. given by [ = (x) g). for being sampled from d-dimensional standard Gaussian, satisfies the geometrical conditions of our lemma.
Lemma B.3. Let X (z1....,,ān) C Rdd and II: Rd + Re be linear map. Let C J C. Rd denote the set of centers minimizing cost, (X, and (Xi,..., xx)) denote the optimal (ki, z)-clssteri and suppose that for the parameters D1, D2, D3 2 1, the following conditions hold:
,ci....,c,)
Centers Don't Contract: Every i, E [k]] satisfies
|c; - D1 [ II(c))
Cost of does not Increase: We have that
Σ
[m)x) - IG)) < D2 (Xi, Xz)-
== DEX;
Approximately Optimal
The partition (Yi..... Yk) of X is D3-
approximately optimal for II(X), i.e.
cost. (IIX)). IIY))) s D3
min q ERC
min jE(K]
II(x) cy lb..
Then,
cost:(Yi,.... Vi. S (22-1 + 20==2D::D2( + Dz)) cost, (Xi, Xg)-
Before starting the proof of Lemma B.3 we show that projecting points onto a random Gaussian vector gives the first two desired guarantees of the above lemma with D (A-2 and D2 == 2=)) /8 with probability at least 1 8. The first lemma that state below shows that the first condition of Lemma [.3 is satisfied with high probability, and the second lemma that the second condition of Lemma B.3 satisfied with high probability.
Lemma B.4 (Centers Don't Contract). Let C (cI,..., C Rd denote any collection of k points and let II: Rd + R be a random map given by
IIxx) (x, g)
for a randomly chosen vector ~ N(0, Ia). Then, with probability at least 1 - over g, every i.j [k] satisfies
|c cill (T)) [[(2))
1:2
Lemma B.5 (Cost of (Xi...., does not Increase). Let X (II,..., In, C Bd and let Xi...., Xú be the partition of X, and .t. ch IRd be the centers which minimize the (k, 2)- clustering cost of X. Then, with probability a least 1 -
k
Σ
Σ
[T(x)
- (20(z)
16)
Σ Jml
Σ ZEX;
-r-
-EX;
Proof of Lemma B.1 assuming Lemma B.3 Lemma B. and Lemma B.3 We will apply Lemma B.3
by letting be a small enough constant (say, 0.01) to take a union bound. Lemma B. implies
the first condition with D, O(k2)) and Lemma B.5
implies the second condition with D = (x))
Finally, the second assumption of Lemma B. sets
Dz. from which derive the conclusion. D
20

---

We now prove Lemma B.4 Lemma
B.5
Lemma
B.3 is proved in Subsection B.2
Proof of Lemma B.4 The proof relies on the 2-stability property of the Gaussian distribution. Namely, if we let 2 E R be an arbitrary vector and we sample standard Gaussian vector
g P~NV (0, Ia). the (scalar) random variable (z, distributed like || where g NO 1). Us-
ing the 2-stability of the Gaussian distribution for every i.j E [k), we have that [[I[(c) II 112 2 is
distributed as (lc)) cyll2. where g' is distributed as a (one-dimensional) Gaussian (0 1).
Thus, by a union bound, the probability that there exists a pair i. E 1k]. which satisfies
[I((c)) ( < a² l|e, cyll2 is at most ka2 times the probability that Gaussian ran- dom variable lies in a-a, a). and this probability easily seen to be less than a. Setting a = 6/k²
gives the desired lemma.
Proof of Lemma B.5 distributed as g x of where g' is distributed as (one-dimensional) Gaussian // 1). By linearity of expectation,
Similarly to the proof of Lemma B.4 we have that []]()) ( is
EnIJJa
ΣΣ
E = xEX; (0,1
[|]
|| c
i=
To conclude, note that for = 2 1, there is some a > 1 such that az is an even integer and a S 2. Thus, by Jensen's inequality and the fact that (x) = x 1/a is concave we can write
lgg
[+] < ((g')=0)2//0
Now note that all odd moments of the Gaussian distribution are zero by symmetry. Thus, for the moment generating function E[cx"] it holds that
E
(2k)
As Ejex' S 1//2 it follows that
(B((g))==)) $ ((22))
1/a
s {((a))ee!1)
1/a
S 20(z)
Applying Markov's inequality now completes the proof.
B.2 Proof of Lemma B.3
Let (aheej be an optimal set of centers for the partition (Yi,..., Yx) for the (k, 2)-clusterin problem on (IX), where à E Y, Specifically, the points , E R are those which minimize
cost( ..., IT().)) def
è 1
To quantize the cost difference between the centers e" and the centers we analyze the following value. We assume we mapped every point X to IXc and we then compute the cost of the partition Yi,..., Yx on this set. Formally, we let
val c², V. ..... Yk) ΣΣ MOXII--II - -61
=1
First, we prove the following simple claim.
Claim B.6. There exists a set of centers ey...., .. (with possible repetitions) which are chosen among the points {c],.... C.) such that
X (I()))) - 11(())l 2 - YI....
21

---

Proof. We will prove the claim using the probabilistic method. For every i E [k], consider the distribution over center {ci..... of which samples a center c/ as
Pr
-
E n
Then, we upper bound the expected cost of using the centers c/. Using Lemma A.3.
A
E
Y Xj1 ([)))) 1
k
<
Y n Ny1 E [([ all2 + (TT()) - Gill2)]
1=1 j=l
2
M ((T()))((())))>>>))))))))))))))) allē 2 Σ
Σ
(axxi B(][T(e)) - -115
= val e², Yi...., Yk) + + --
Σ |xnxil
[xnx EE= Minyl
[I(c]) -él
= 2" val(Il, c², .y..... Yu).
We now upper bound cost, (Yi...., Yk. in terms of (Xi X.). We do this by going through the centers chosen according Claim B.6 This will allow us to upper bound the cost of clustering with .Y,...., Yx) ) in terms of the (Xi ...., Xx) only pairwise distances from [c) Then, we relate to distances after applying the map II. Specifically, first notice that if we consider the set of centers c/,,..., c chosen from Claim B.6
as well as clustering cost involving
cY,,,(Y,,.... Yn) <
- 2
i=1
zEY;
Σ
- (11--ج9l22 + |lej - ccll2)²
i= j= =
2 cost, (X1 (Xi....,. X1) + 2 ΣΣ Y Mnxjilllle 411..
(4)
where the third inequality uses Lemma A.3 once more. Note that the right- most summation of 44) involves distances which are only among ci ......, ch so by the first assumption of the map and Claim B.6 we may upper bound
Xnn 11c, 111111c-411 -411 - D Σ
MnnaI -xn(c)-11l(() m(()))
i=1 j=1
< D 2 val(ll, c², ,,,,,,,,,................. ,,,...,,
(5)
Combining 4 and we may upper bound
(Y,... Yn)= 2=-1 cost, (Xi (Xi.....
X Dj 223-1 val c² Yi...., Y.)
k
2--1 cost, (Xi (Xi X + Dj 225-1
Y, n [I((]) -
2.1..
(6)
We continue upper bounding the mish expression in 6 by applying the triangle inequality:
Xnx3I [I((c]) - -
22

---

S 2
[I((2)) - -1()) 2n-1
ΣΣ
[[((2)) - -
me Y
:= ==1 aE =EYin
2 2 D2 cost. X 2 cost. (II(Y)) I))
By the third assumption of the lemma, we note that cost (oszz)),)),,....... II(Y))) S D3-
min
Σ
min [[(()) - - JE(
FEX
S D3
Σ
Σ
[1(())
1B D3D2 cost, (Xi,..., Xx). (8)
f=1 2
Summarizing by plugging and
8 into 6 can upper bound
cost, (YI..... Yn)
(2 23 DfD2(1+ + Da)) cost, (Xi Xx).
C Efficient Seeding in One Dimension
In this section, we prove Theorem 2.1
which shows upper bound for the running time of our
algorithm PRONE. As in Theorem B.2 we consider a generalized version of PRONE where we run
k-means++ seeding for general
(Definition A.2 in Step 2. We prove the following generalized
version of Theorem 2.1
C Rd be a dataset consisting of points in d dimensions. Assume that nnz(X), which can be ensured after removing redundant dimensions j E [d] where the j-th coordinate of every x4 is zero. For any 2 2 1, the algorithm PRONE (for general z as in Theorem (.2) has expected running time O(nnz (X) ))+2** + log n) on X. For any E (0, 1/2), with probability at least 1 6, the algorithm runs in time (nnz((X) + 2=/2 log(n/8)). Moreover, the algorithm always runs in time (nnz(XX) + n log + nk).
xn Theorem C.1 (Theorem 2.1 for general 2 2 1). Let X (
To prove Theorem 2.1
we show an efficient implementation (Algorithm T of the k-means++ seeding procedure that runs in expected time 0(2=/2n log n) for one-dimensional points (Lemma C.3). A naive implementation of the seeding procedure would take (mk)) time in one dimension because need (n) time to update ps and sample from the D distribution to add each of the k centers. To obtain an improved and provable running time, we use basic binary tree data structure to sample from the 22 distribution more efficiently, and we use a potential argument to bound the number of updates to Pt-
The data structure we use in Algorithm can be implemented as a basic binary tree, as described in more detail in Appendix[D] The data structure S keeps track of nonnegative numbers $1, .... Sn corresponding to pi,... P and it supports the following operations:
1. Initialize(a). Given an array a (a1..... an) E R the operation Initialize(d creates a data structure S that keeps track of the numbers $I...., initialized so that ($1,..., 8n.) = (0), (#1,..., a,)). This operation runs in O(n) time.
2. Sum(S). The operation SSm(S) returns the sum 81 + ..... time, as the value will be maintained as the data structure is updated.
on. This operation runs in O(1)
3. Find(S, r). Given number E [0, Di s:), the operation Find(S, returns the unique index (1....,73 n such that
[-1
Σ
s S
i=1
This operation runs in Ologn) time.
4. Update(S, a, é,, 62). Given an array = (a) (a......0 an) E By and indices i in satisfying S in S is S n, the operation Update(S, (S, a, in, i2) performs the updates 8; +- a; for every i i + 1, 1,...,2 i2. This operation runs in O(ii i + + log time.
23

---

Algorithm 1: Elficient k-means++ seeding in one dimension
Input:
Points - E IR; k E Z satisfying 1 S k Σ real number 1.
Output: Centers F......, 2t, E R: assignment a [mx] + [k].
Sort and re-order the points so that #1 S S Zni
2 Choose & uniformly at random from {I....,,2] n);
Initialize (Az,..., an) by setting a; | F4i for every ,,,
S <- Initializa(1):
for t = 2....,k' do
Choose uniformly at random from Sum S));
+ Find(S, r): ag, < 0; & 1; j x 4 + 1;
while i 2 andd [r; zee 8 < 02 do
04 + [i Ft. 1:
10
i iti-l;
11
end
12
while
j < n and [
-E, Fe, < a, do
13
aj + 23 1
14
j +1;
end
16
Update (S, i + 1.j 1);
17
end
Sort and re-order 4,, ................................ la that l S ... S :;:
19
i x-1, 1; j 1- 1;
while S do
/* Assign Vi to the closest center Veay among -hr Fta.
21
jf < k and
an Fzg laq Ftzz1 then
22
j+ 1:
else
24
(11) j; iti i+1;
25
26
end
27
end
return ; Dt, and a (converted to the old ordering of æ1,..., Fn before Line 1
The following claim shows that Algorithm I correctly implements the k-means++ seeding procedure in one dimension.
Claim C.2. Consider the values of t, a1....... On and the data structure S at the beginning of each iteration of the for-loop (i.e., right before Li. Let Si,...,3 the numbers the data structure
keeps track of. For every 1,...,n, define p; == min.==1.....- 1-1 lr, It, Then s; a; pt for every 1,...,n. n. Consequently, the distribution of & at Line history far satisfies Pr(e,
- P. for every 7 conditioned on the execution pt /
,
The claim follows immediately by induction over the iterations of the for-loop based on the description of the data structure and its operations above. The following lemma bounds the running time of Algorithm!!
Lemma C.3 (Lemma 2.4 for general 2 1). The expected rumning time of Algorithm [ is (2 log n). For any 5 E (0, 1/2), with probability at least 1 d, Algorithm 1 runs in time ( log(n/6)). Moreover, Algorithm Algorithmaaalway runs in time O log n. + nk).
Before proving Lemma C.3 we first use it to prove Theorem C.1
C.1 Lemma C.3 bounds the running time of Step 2 of our algorithm PRONE defined in Section 2 Now we show that Step (random one-dimensional projection) can be performed in time O(nnz X) + n). Indeed, x can be computed as x¹ Σ, Ui where the sum is over all the non-zero coordinates Tij of xj, and each " is drawn independently from the one- one-dimensional standard Gaussian (the value of Uy should be shared for all i). The time needed to compute z',.... 2 in this way is O(nn((X) + n2). In Step 3 of PRONE, we compute the center of mass for every cluster.
Proof of Theorem
24

---

This can be done in time (nnzz(X) + +n) by summing up the points in each cluster and dividing each sum by the number of points in that cluster.
The key step towards proving Lemma C.3 is to bound the number of updates to a at Lines 9 and 13 As the algorithm starts by sorting the n input points, which can be done in time On log n),, we can assume that the points are sorted such that
S ... S In- For i = ....., n and t = 2, .....hk k, we define E(i, t) = 1 if a, is updated at Line 9 in iteration t and define E(i,t) denote each iteration of the for-loop beginning at Line by the value of the iterate t. We define U, := Eizy {(i, t) to be the number of times a, gets updated at Line 9 The following lemma gives upper bounds on Us both in expectation and with high probability:
otherwise. Here, we
Lemma C.4. For every i = L..... n, it holds that
Elu,] S O log
Moreover, for some absolute constant B > 0 and for every E (0, 1/2), it holds that
Pr[u: v /2 log(n/5) 2 1 5.
Before proving Lemma C.4 we first use it to prove Lemma C.3
Proof of Lemma updated at Line in iteration t and define E(i, t) = 0 otherwise. Similarly, for j = 1,.... n and t= 2..... k, we define t) 1 if aj is updated Line 13 in iteration t and define (' t) 0 otherwise.
Recall that for i I,..., and t == ...... k.
define E(i,t) 1 if a, is
,.,,,
The computation at Lines 1 takes O(n n) time. The computation at Lines 18 28 takes
Ok log k + n) O log n time. For = 2.... k. iteration t of the for-loop takes time Ollog + E E(i,2) Ei= ii=1 E'(i, ()).
Summing them up, the total running time of Algorithm
o n llg +
t(i,t) +
(((.t))
(9)
t=
By Lemma C.4
n
E
E(i, t) = E
= 0 log n.)
(10)
(=1 1=2
i=1
Also, for any 8' E (0, setting 5 = 8 in Lemma
C.4
by the union bound we have
h
Pr
E(i,1) < 2
2 Pr
E(i, () < (ogn/))
1=1 t=2
2 no
8'.
(11)
Similarly to
10
and
11
we have
ΣΣ 11
=2(222nnog
and
(12)
&
Pr
(( S 2B2 2 log(n/8))
2 21-8 8'
(13)
Plugging
1T and
into 9 proves that the expected running time of Algorithm is
0 n). Choosing 8' 8/2 for the d in Lemma C.3 and plugging (I and [13 into
we can use the union bound to conclude that with probability at least 1 ô Algorithm runs
time 0 n log(n/ (n))..)). Finally, plugging t(i,t) S and t' < into (9) we get that Algorithm always runs in time O log + nk).
To prove Lemma C.4 for O,..., and I E (1...., k} such that [ú, (') = u. That is, a, gets updated at Line for the u-th time in iteration ((i, u). Our definition implies that ((i, 0) = 1 and ((i,u) E {,.... k for u 1, 1,..., Mi. We define a nonnegative potential function v/(,, u) as follows and show that it decreases exponentially in expectation increases (Lemma C.5
O,..., us we define t(i, u) to be the smallest
25

---

Potential Function nid, u). Fort = 2.....k we consider the value of & after Line 7 in iteration For L..... ................................ uy we define n(i, u) to be (1(i..)) - which is guaranteed to be a positive integer by the definition of t(i, u). Indeed, in the while-loop containing Line [ starts from & 1 and keeps decreasing, so whenever Line Dis executed, i is smaller than 4, In particular, a, is updated Line 9 in iteration t(i, u) of the for-loop, so we have i < le(t,,). We define 17(2, 0) = n, and for U. u4 + .,..., define nii, u) O. See F example illustrating the definition of (t, w).
3 1
2i+4
In
(((1.2) = i 1
(((1.)) = + 4
7ii,)) ((i,2)=1 =1
r 1 =4
Figure 4:
An example illustrating the definition of the potential function 17. Here, is updated at
Line for the first time in iteration (ii, 1) when (2((.1) = + Then a; gets updated at Line for the second time in iteration (i, 2) when (1(1.2) - 1. We always have & i whenever a, is updated Line 9 and 1) is the difference between and i. Thus in this example ( 1) 4 and ()( 2) 1. If a; is never updated at Line 9 after iteration f(2, 2), we define n)(,, u) = 0 for u = 3, 4,...
Lemma C.5 (Potential function decrease). For any E {I,.... n and u E Zzo.
Eln(i, u + ()) O). ...., n(i, u)] max {
2
2z/2 (i,
we first use to prove Lemma that 1i,i, u) decreases exponentially (in expectation)
Before proving Lemma C.5
Intuitively, Lemma C55 says
function of u. Since 17 u) is always nonnegative integer, we should expect 171,, u) to become zero as soon as u exceeds a small threshold. Moreover, our definition ensures 17(2, u4) > 0, so u; must be smaller than the threshold. This allows us to show upper bounds for u, and prove Lemma C.4
Proof of Lemma
C.4
Our definition of 1 ensures (1,, u4) 2 1. By Lemma C.5 and Lemma C.7
In n
E ua
1] S
0(2=/2lnm) + 2=/2 + 1.
In 2c/2 2-72
2+/2
2=/44I
This implics B[u,] = 0(2:/2 log nt. Moreover, by Lemma C.5
2²/2
24/2
E Eln(i, 5(, 22/2
22/2
and thus, by Markov's 's inequality,
2²/2
Pr[u, 2 u] Pr(n(i, u) 2 1]
2=/2 +
For any d E (0, choosing In(n/6)/ In( 11) ( (00sl(/))))))) in the inequality above gives Pr[u: u] < 8.
We need the following helper lemma to prove Lemma Lemma C.6. The following holds at the beginning of each iteration of the for-loop in Algorithm i.e. right before Line 6 is executed. Choose an arbitrary = 1,..., n and define
7
== Ui E Then for e, E T. satisfying El < <t, it holds that ag S 2 az.
S n, |z, xel² < a.).
(14)
Proof. For 2...., at the beginning of iteration t, the values ly,..., 4--1 have been determined. For every E IR, let p(x) denote the value among It,..... It,-, closest to x. By Claim C.2 a; = It; - p(x;))² for every
[n]. Now for a fixed E [n], define L as in (14) and consider e, E L satisfying E < f'. It is easy to see that x; < p(zz) & dr cannot hold because otherwise
a; S lx - -(xx)) S [x; - xgl 1 < 0z a contradiction. For the same reason, the inequality o; S p(zr) S øe cannot hold. Thus there are only three possible orderings of 24, Zt, Ze, p(xe), p(zz))
26

---

1. p(zz) p(ae) < < S 21 S 20;
2. p(zz) < 2i S xt S or < p(xr);
3. 2, S 22 S dr < p(xx)= = p(zx):
In scenario 3, it is clear that age 10 p(xxe)) )F S lze p(xx))² 20 = dg. In the first two scenarios,
for any 1' 0 0
c - st, 2 Ire - F2,l - I0e - 2i1 2 l - p(zz)) - Ie - 15|= -
1z p(zz))-
This implies that p(zz) is the closest point to r; among 2t,,, ..... -te--- Therefore, 1-:---ppp p(x))) Jensen's is inequality ensures ((9 + 12) S (g² //²//2 for any g, h 2 0, which implies (g h1) S + 2²
1-2-11²² Therefore,
Dg p(xe))² < 2 p. x..² 2 20 p(are)) 2²ai,
ae
whereas
ag b p(ax))² 2 bz, p(xx)l= a,.
Thus, we have ag 2 in three scenarios.
Proof of Lemmn C.S Throughout the proof, we fix i E {l....,ii ,n) and u E Zzo that they are deterministic numbers. Algorithm iss randomized algorithm, and when we run it, exactly one of the following four events happens, and we define a random variable t* accordingly:
1. Event Ej: u, < u. That is, a gets updated Line for less than times. In this case we have m7(é, + 1) = 0 by our definition of and we define t* = +o0.
2. Event Ez: Ug
and is never chosen as le at Line 7 In this case we also have n(1 1) 0. and we also define t" +cc.
3. Event Ey: u, and there exists E 32.3...... k} such that is chosen as &, at Line 7 in
iteration f. This must satisfy > t(i, u), as all updates to a in Line must happen before is chosen as center. We define to = t in this case. Again, have r7(i, + 1) 0 in this case.
4. Event Eq: us > u. We define t* := t(i, u + 1) > t(ē, u) in this case.
Define Ea = E' U E4. Since nii, + 1) = 0 under Ei and Es, it suffices to prove that
2=/2
Eln(i, a + ())m((, .),...,,. (7,,, u), F²)
2=/2 + ni, u)
(15)
2
By our definition, the random variable t* takes its value in {2, (2.3.... t" to0 if and only if E* does happen. Therefore, to prove [15. following for every to = k:
......k)
k} U (+00). Moreover, it suffices prove the
2-/2
El u + 1))m(i, 0), ((, = = - 2=/2 + (1, u)
(16)
Consider a fixed to E 3.. .......... Aj. For t" = to to happen, the following must hold during the execution of Algorithm C [before iteration to: a; has been updated Line for for exactly times, and i has not been chosen as & at Line Thus, the rest of the proof assumes that the execution history of Algorithm I before iteration satisfies this property. Now we know that the values 17(1, .)......l (i, u) are determined by the execution history H. Lines guarantee that the distribution of lg, satisfies
Pr(ke
{|H] Σ/=1a aj
for every f= l
where we use the values a...... an right before iteration to is executed. Moreover, conditioned on H, we have = to if and only lo E L. where
L = (i) e <iiiiesnn xz1² < ai).
'We have ni(i, + 1) 0 also for E's so one can also simply choose E" Es. Choosing E" = -Bg U Es helps get improved constants in our bound.
27

---

Therefore, if we further condition on t" = tv. we have lo E L and
Pr(le, =|Hit = Ejena aj
ag
for every 8 L.
(17)
When t" = to, we have n1,, + Loo i. Therefore, to prove 16 it suffices to show that
2²/2
1 2
Bieg, i|H, tol - 2²/2 + M7. u)
(18)
It is clear that implies a; I [2 Flees.a) 1", and thus f" < ((i.w) and e" is (z((. -i -i= 71, u). If u = 0, we
write L as L i 1,...,," ) for some integer e² 1. If 0, Claim C.2
have v7(i, u) = n,, so it also holds that l - < 111, u). By and Lemma C.6 we can set 7 = 2
C.6
in Lemma C.8 to get
22/2
(6" - -i) 2 < 22/2
Bi6e, - iH = tol -
2 (1 u)
2²/2 +
2
This proves 18 and thus proves the lemma.
C.1 Helper Lemmas
Lemma C.7. Let M 2 and X (0,1) be parameters. Let 00,01 E [0, +00) be random variables satisfying Ogg M and E|a | ail S for every = 0, l,.... Let 2 0 be the
smallest integer salisfying at < Then
In I Im(1/A) + 1-
1
Eit S
Proof. For every j = 0, 1...., we define a random variable 1 = min((,j.. By the monotone convergence theorem, suffices to show that
In M In(1/A)
1 T-X
E[G]
for every 0,1,....
(19)
We prove [19] by induction on j. When
we have tj and the inequality above holds trivially. We assume that (I9) holds for an arbitrary j E Ezu and show that it also holds with replaced by j + 1. We have
1]= = B 1)]oa]]. E[ts+1]=11 + 1 1]
(20)
By our definition of li+1, we have 1,+1 - 1, Applying our induction hypothesis on the sequence (11, .2,,..,, we have
1,5) B[( 1)(ai] = - f(a)),
(21)
where
if [0, 1);
f(a)
--X:
if 2
[/( T=
It is easy to check that f is an increasing concave function of a E +0,+ and 1 + f(Aa) s f(a) holds for every 2 1. Plugging (2T) into 20). we have
In M E[t 1 E[f(a)) s 11+ f(Boa)) < + f(AM) & f(M) In(1/A) 1-X
1
Lemma C.8. Let be real number. Let Bo...., "0,...,,m-11. be non-negative real numbers such that for every i.j E (O...., 1) satisfying S j. it holds that B3 S 7B,. Then,
m
//
m
18
Σ
3
7 +1
2
1=0
1=0
28

---

Proof. The lemma holds trivially if Bu = 0 because in this case B, S 7 = 0 for every =
O..... 1. We thus assume w.l.o.g. that Bo 0. Define T to be the unique real number satisfying
m
m-1
Σ
8. Σ 13,=00 O.
is clear that T [0, m 1). Our goal is to prove that
T
(22)
V +
Define B. minosisr 3, For every = 0, ..... m 1, have 2 3. if T, and B, 7:3. if
i > т. Therefore, defining == [T], we have
m-1 1
m-1
0
D
i8
20
t=0
Σ (T i)B3
1=0
- -1.3++ + Σ(r
(T- - -1
(23)
15T
(s + 1)
3. (m 1) 5) 7.2..
(24)
2
Now, we show that 3. 0. For the sake of contradiction, assume B. We already assumed
that 30 > O, so B. * So. By the definition of B., this means that r > and inequality (23) is strict, leading to the false claim of
0 (T - 10-- + Σ(r
i)78. = O.
EST
15T
Therefore, B. > 0 must hold. Now we know that 24 implies
(s + 1)(2T s) + (m
() m s\y 50 0.
Treating s as real-valued variable, the left-hand side minimized when = T - 1/2, giving us
(T + 1/2)2 - (m - - 1/2)) < 0.
The inequality above implies
(7 + 1/2) S (m 112)33
Taking square root for both sides and solving for gives (22)
D Data Structure for Fast Sampling in Seeding
In Appendix C our Algorithm I uses binary tree data structure S that keeps track of n nonnegative this
numbers $1..... Sy and supports several operations. Here, we describe the implementation data structure. We assume that n = 2 for some nonnegative integer q. This is without loss of generality because we can choose ní to be the number that satisfy n' < and n' 29 for some 8n' = 0. Under this assumption, the data structure S is a complete binary tree with g + layers indexed by O...., q. In each layer O...., there are 2 nodes each corresponding to set of indices from {1. (1...., n.. The root,
q E Zzo and consider $1...., 8n, 1n.1..... .,, with Su+1
denoted by (0) is the unique node in layer 0 and it corresponds to the entire set 1/(0) = (1,...,n) n). ((+1) ((+1) in the (S+ 1)-th For <= 0,..., 4 1, each node (() in the Ç-th layer has two children u2 122
(({+1) respectively, where (({11) is the smaller half of layer corresponding to the sets V15+1) V2j
2j-1
v-( and V22 (1+ is the larger half. Thus,
v( (i Z: (j 1)25-6 < <is 53
(4) in the tree stores sum $ Eievço 8i.
Each node /
The data structure supports the four types of operations needed in Appendix C as follows:
29

---

11
(0)
Layer
22
(1)
Layer 1
(2)
(2)
(2)
Layer 2
1
P2
3
13
3/
2
6
Us
Layer 3
$2
Figure 5: An example of a basic binary tree data structure with q = 3.
1. Initialize(a). Recursively Initialize the first half (a1.-... 0n/2) and the second half (An/2-1:-.... On) to obtain the two subtrees rooted at uf" and oz) Then add (0)
root that stores $i + s1 + 52
(1)
2. (Sm( Simply output s
3. Find(S,r) If < si recursively call Find on the left subtree rooted at 0j Otherwise, recursively call Find on the right subtree rooted 2/2 we reach a leaf ui return L.
(1) with replaced by r s Once
4. Update(S, (1, 12). If in S n//2, recursively call Update on the left subtree rooted at e If 1 n/2, recursively call Update on the right subtree rooted at m2 Otherwise, we have i S n/2 < i2 and we call Update the left subtree with indices 81, n/2 and call Update
on the right subtree with indices n1/2 1, 12. all cases, we update a1 <- b1 + ( as the final step. The running time is proportional to the number of nodes we update. We need to update s(5) stored at (( only if ((()) fiz,..., d2) # 0. For each Ç, the number of such j is at most (ig i + 1)/24 < + 2. Summing up over Ç = ....., q. the total number of nodes we need to update O(ii é1 1) q) O in + log
,
E Additional Experiments and Data
In this section, provide the tables for speedups and absolute running times of the experiments performed in Section Additionally, we provide some experimental data for the algorithmic approach described in Theorem 2.3
E.1 Improved Approximation Ratio
Experimental Setup. This experiment aims to compare the algorithmic approach outlined in Theorem 2.3 the direct use of PRONE clustering algorithm as was done in Section 3.2 For this, we use PRONE as the approximation algorithm for sensitivity sampling and then cluster the coreset using a weighted variant of the k-means++ algorithm. This approach termed PRONE (boosted) in the rest of this section. This pipeline requires parameters the number of centers k and a hyperparameter a indicating the size of coreset produced by sensitivity sampling. We aim to compare the clustering cost (see Definition A.1) and running time of our approach to that of k-means++.
We run both algorithms on the datasets described in Section 3 and choose k E {10, 25, 50, 100, 250, 500, 1000, 2500, 5000) and {0.001, 0.01,0.1), Each algorithm is run 5 times.
Results on Improved Approximation Ratio Costs. Figure 6 shows the costs of centers produced by this algorithm relative to the cost of centers produced by k-meanst+. It also contains the (k, 2)-
30

---

Dusssct Sony
3.3
2.00
2.5
PACHE iteetted e 0.6231
Algortim
2.00
1.10
1.5
125
PACINE [seattdd 0.31
crrea16-e MACE, spedte
1.00
3.2
Figure 6: Clustering cost of the boosted variants compared to k-means++. Lines in the plot show the cost of centers produced by the boosted algorithm relative to k-means++ for centers ranging from 10 to 5000. Dark blue indicates the non-boosted version.
clustering costs of PRONE relative k-means++. We that all real datasets, PRONE (boosted) produces solutions of the same or better quality than k-means++, as long as on < k. This shows that although PRONE by itself produces centers of worse quality, the PRONE (boosted) variant produces centers the same quality as vanilla k-means++. When on s k, we observe an uptick in cost before the end of the lines corresponding to {0.1, 0.01} the plots for KDD, Song, and Gaussian. The boosted approach outperforms PRONE, which is usually worse by constant faccorr compared the other algorithms, and it helps reduce significantly the amount of variance in the quality of solutions. On the Gaussian dataset, we observed failure to sample a point from the central cluster, 0.1.
which explains the spike at k 2500 for the line corresponding
Rumning time. Table shows the speedup of the boosted approach versus using plain k-means++, for the time taken compute the centers. The running time of algorithms scales with k, but at slower rate compared to k-means+++, as we have to run it on much smaller dataset. Once again, we observe significant speedups, especially k grows large.
As expected, the speedup depends on the choice of the hyperparameter We observe diminishing returns for larger a as scales, with the speedup remaining mostly constant for k: 2 100 across datasets, except for Gaussian. This is due the algorithm's 's running time being dominated by the time it takes to execute k-means++ on the coreset, which has ((ddk) asymptotic running time. The speedups can achieve using this method are significant, up to 118x faster than k-means++. We expect that on massive datasets, even greater speedups can be achieved.
Interestingly. the speedup come very close to Song datasets. The final stage the boosted approach exccutes k-means++ on a coreset of size on, the running time of this step should be (andk)). The observed additional speedup may be due to better cache and memory utilization in the k-means++ step of the algorithm.
out scale observed on the KDD and
Centers
10
50
100
250
500
1000
2500
5000
Dataset
Algorithm
Census
PRONE (boosted, 0.001)
1.6
4.0
7.9
15.6
36.8
69.5
118.5
PRONE (boosted, 0.01)
1.5
3.7
6.7
11.7
20.8
28.5
30.1
36.2
41.9
PRONE (boosted, 0.1)
1.0
1.8
2.3
2.7
3.0
3.2
3.0
3.0
3.2
k k-means++
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
Song
PRONE (boosted,
0.001)
2.1
5.3
10.7
21.3
51.7
97.5
PRONE (boosted, 0.01)
2.1
5.0
9.8
18.5
38.0
59.1
81.5
108.3
117.0
PRONE (boosted, a
0.1)
1.3
2.2
2.8
3.4
3.8
4.0
4,0
4.0
3.9
k-means++
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
KDD
PRONE (boosted, 0.001)
1.8
5.0
9.6
20.6
PRONE (boosted, 0.01)
1.9
4.8
9.0
17.5
37.1
59.2
92.5
PRONE (boosted, 0.1)
1.4
2.7
3.6
4.9
5.7
6.2
7.1
6.6
6.4
k- k-means++
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
Gaussian
PRONE (boosted, 0.001)
0.5
0.9
1.9
3.6
PRONE (boosted, 0.01)
0.5
1.0
2.0
3.4
8.2
14.8
25.6
PRONE (boosted, 0.1)
0.4
0.8
1.4
2.2
4.0
5.0
6.1
6.8
7.2
k-meanst+
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
Table 2: Average speedup when computing a clustering and assignment for different datasets relative k-means++. In other words, each cell contains me-mennst+//// of on > k.
/mmeunst//Tpronee /TPrOn Missing entries denote the case
31

---

E.2
Additional Data
In this section, we provide the running time data for the full range of parameters for the experiments performed in Section 3.2 Table 3 shows the speedups over k-means++, analogous to the right-hand hand-
side table in Table Additionally, Table provides absolute running times in milliseconds.
Centers
10
25
50
100
250
500
1000
2500
5000
Dataset
Algorithm
Census
PRONE
1.5
3.8
7.5
15.1
36.2
73.2
142.2
351.9
662.5
PRONE (variance)
0.5
1.1
2.2
4.6
11.0
22.2
43.7
109.5
214.7
PRONE (covariance)
0.2
0.5
2.2
5.2
10.7
21.0
54.7
117.4
k-means++
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
Song
PRONE
2.0
5.0
9.7
46.1
95.5
188.2
443.0
837.5
PRONE (variance)
0.5
1.1
2.3
4.5
11.4
23.1
44.2
110.9
217.2
PRONE (covariance)
0.2
0.4
0.8
4.0
15.5
40.0
82.4
k-means++
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
KDD
PRONE
1.5
3.7
6.9
16.3
39.5
68.3
158.5
414.7
727.5
PRONE (variance)
0.7
1.7
3.1
6.3
16.1
32.0
63.4
159.6
312.4
PRONE (covariance)
0.3
0.7
1.3
2.6
6.8
12.9
25.8
58.5
128.4
+-means++
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
Gaussian
PRONE
0.5
1.0
1.9
3.8
9.2
18.3
35.7
85.3
165.9
PRONE (variance)
0.5
1.0
2.0
3.8
9.1
17.7
34.5
83.6
162.9
PRONE (covariance)
0.4
1.0
1.7
3.6
8.2
16.1
31.8
79.9
152.6
k-means++
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
1.0
Table Average speedup when computing a clustering and assignment for different datasets relative to k-means++. In other words, each cell contains Th memmsst++ TPRONE-
Daau
Alascvv
175 15.1
705
11926-271-1
17013 230
11514 360
1111 1
1770 233
17915 = 180
6-754-00 714
1N06 156
2ec 1- 75.
790 915
1910- 1176
1387 6- GES
J9SI WeT
7519
ScaE
1
FAZSE
4413 2:50
-4.3 2.50
4011
4833
4883
PAZSR
11644 1621
1365 1956
1850=
INA 1T1A
126.0- 115
K3D
FACCE
111.5:2
132 2-
SAL
201 11
534 S.
FEOEK (coualine)
1983 2.2
8.55
151
186142212
1867
485-1.13
115.3
2034
45541111
48761
1111
129865
2203
243855
2438
FRERE OVEERAN
211-2.30
25.0
203
21:206
252-2:13
24204
502 012-03
905 02
301 00
137222
3:0
30
11
2
5253
10433
20753
$2205 155.0
Table 4: Average running time and standard deviation in milliseconds when computing a clustering
and assignment for different datasets relative to k-means++.
32


Reviews:
[{"review_id": "ougdRwVbZn", "reviewer": "Reviewer_7JVT", "summary": "This paper introduces a randomized clustering algorithm that provably runs in expected time O(nnz(X) + n log n) for arbitrary k. In theoretical analysis, the proposed algorithm achieves approximation ratio O(k^4 ) on any input dataset for the k-means objective. In the experiments, the quality of the clusters found by the proposed algorithm is usually much better than this worst-case bound. They use the algorithm for k-means clustering and coreset construction. This work shows that the approximation ratio achieved after a random one-dimensional projection can be lifted to the original points and that k-means++ seeding can be implemented in expected time O(n log n) in one dimension. ", "questions": "See “Weaknesses”.", "limitations": "N/A", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "This paper has the following contributions: \nIt designs a simple, practical algorithm for k-means that runs in time roughly O(nd), independent of k, and produces high-quality clusters. In theoretical analysis, they give a randomized clustering algorithm with provable guarantees on its running time and approximation ratio without making any assumptions about the data. In experiments, they run two types of experiments, highlighting various aspects of the algorithm: Coreset Construction Comparison and Direct k-means++ comparison.", "weaknesses": "1.Insufficient research on related work. \nThere are many methods for accelerating clustering. This paper did not conduct comprehensive research. In the most relevant random projection clustering, this work is not the first random projection clustering work, such as paper [1]. It is not cited in this paper. The superiority of this work cannot be verified. Please compare it from the theoretical analysis, experimental results, algorithm complexity, etc.\n\n[1]Liu W, Shen X, Tsang I. Sparse Embedded $ k $-Means Clustering[J]. Advances in neural information processing systems, 2017.\n\n2.The organization and presentation of this paper can be further improved. The second half of the abstract is logically chaotic.\n\n3.The experiment is insufficient to verify the superiority of this work. The experimental results show that the performance of the proposed algorithm is not excellent, such as in Figure 2,3.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the helpful feedback! Here is our response to the individual comments in your review:\n\n**Research on related work.** In our submission we extensively discussed prior results on fast algorithms for clustering with a focus on results with provable guarantees. We discussed algorithms in three major categories (Lines 55-72) and other related results (Line 83). We also mentioned previous work on dimension reduction at Line 215. In our final version, we will make sure to cite the paper you suggest [Liu-Shen-Tsang,17] and include a refined discussion about dimension reduction methods for k-means clustering.\n\nWhile dimension reduction is a major component of our algorithm, our goal is making the *entire* clustering algorithm run fast, rather than *just* the dimension reduction step. For example, while the dimension reduction in [Liu-Shen-Tsang,17] runs very fast in $O(\\mathsf{nnz}(X))$ time and reduces the dimension to $d’ = O(k/\\\\varepsilon^2 + 1 / \\\\varepsilon^2\\\\delta)$, running a clustering algorithm such as k-means++ after the dimension reduction would require $O(nd’k) = O(nk^2/\\\\varepsilon^2 + nk /\\\\varepsilon^2\\\\delta)$ time. Our algorithm achieves a running time $O(\\\\mathsf{nnz}(X) + n\\\\log n)$ independent of k for the entire clustering algorithm (dimension reduction plus k-means++ seeding afterwards).\n\n**Paper presentation.** Thank you for the feedback! Below is a revised version of our abstract based on your feedback. We welcome any additional suggestions on the presentation of our paper.\n\nAbstract: Clustering is a fundamental problem in unsupervised machine learning with many applications in data analysis. Popular clustering algorithms such as Lloyd's algorithm and $k$-means++ can take $\\\\Omega(ndk)$ time when clustering $n$ points in a $d$-dimensional space (represented by an $n\\times d$ matrix $X$) into $k$ clusters. In applications with moderate to large $k$, the multiplicative $k$ factor can become very expensive. We introduce a simple randomized clustering algorithm that provably runs in expected time $O(\\\\mathsf{nnz}(X) + n\\\\log n)$ for arbitrary $k$ and achieves an approximation ratio of $\\\\smash{\\\\widetilde{O}(k^4)}$ on any input dataset for the $k$-means objective. Here $\\\\mathsf{nnz}(X)$ is the total number of non-zero entries in the input dataset $X$, which is upper bounded by $nd$ and can be significantly smaller for sparse datasets. We believe that our theoretical analysis is also of independent interest, as we show that the approximation ratio achieved by a $k$-means algorithm is approximately preserved under random one-dimensional projections and that $k$-means++ seeding can be implemented in expected $O(n \\\\log n)$ time in one dimension. Finally, we show empirically that our clustering algorithm gives a new tradeoff between running time and cluster quality compared to previous state-of-the-art methods for these tasks.\n\n\n**Experiments.** Figures 2 and 3 show that the clustering cost of the centers produced by our algorithm is comparable to that of k-means++ and that it produces strong coresets of similar quality when used for the initial seeding in state of the art coreset constructions. The main improvement of our algorithm is made in the running time, where we observe large speedups (see Table 1)."}, {"review_id": "IYo0D6Fla0", "reviewer": "Reviewer_sFfD", "summary": "The paper presents a new technique for clustering data such that the running time of the method is independent of the number of clusters, and the approximation error is polynomial only in the number of clusters and not the number of data points. \n\nThe paper experimentally tests the method and finds that it is a good balance of speed and quality of the result. ", "questions": "What is the time complexity for the third step?\n\n", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "There are many strengths.\n\n\n1) The runtime being independent of $k$ is a significant speed up. Further, the constants seem to be better as well. Since the method is not iterative and only makes a single pass over the data \n2) The experimental results on corsets are compelling. \n3) The presentation of the method is easy to follow. ", "weaknesses": "The approximation of ratio of $O(k^4)$ is significantly worse than $O(\\log k)$. I was hoping this was only theoretical and that we would see better results experimentally, but the experimental results are not clear. \n\nSpecifically for Figure 3, I have no idea what the difference between the bottom and the top row is. This is partly due to the fact that the paper never actually writes down formally the problem or the metrics used. From my understanding, we have $n$ data points $x_1, \\ldots, x_n$ in high dimensional space. We want to find $k$ clusters $C_1, \\ldots, C_k$ where each $C_i$ is a subset of the $n$ data points such that if $c_i$ is the center of the mass of those points, then \n\n$$ \\sum_{i=1}^k \\sum_{j \\in C_i} \\|c_i - x_j\\|^2 $$\n\nis minimized. This is what I interpret to be the cost. Hence it is very unclear to me what Figure 3 is showing. \n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thoughtful review! Here is our response to the individual comments and questions in your review:\n\n**Experimental results.**\nThe experiments in the paper are mainly meant to demonstrate that we achieve significant speedups over the baseline algorithms (see Table 1 in the submission), while achieving results of similar quality. While the centers together with the assignment output by our algorithm do not yield clusterings that are competitive with vanilla k-means++, it provides an extremely fast way of seeding coresets. In additional experiments (see Figure 1 in rebuttal PDF) we found that running k-means++ on this coreset can produce a set of centers with clustering cost very close to running k-means++ on the full dataset. Using it in this configuration still lets us achieve speedups over plain k-means++, especially on large datasets, if many centers have to be chosen.\n\n**Two rows in Figure 3.** Thanks for the feedback! We explain the difference between the bottom and top row below. We will add a formal description of our evaluation metrics to the final version.\n\nOur algorithm computes k cluster centers $c_1,\\\\ldots,c_k$ as well as an assignment $\\sigma:[n]\\to [k]$ mapping each input point $x_i$ to a center $c_{\\\\sigma(i)}$. The bottom row of Figure 3 computes the cost $\\\\sum_{i=1}^n \\\\|x_i - c_{\\\\sigma(i)}\\\\|_2^2$. \n\nNote that $c_{\\\\sigma(i)}$ may not be the center closest to $x_i$, and computing the closest center to each $x_i$ requires $O(ndk)$ time in total. The top row of Figure 3 computes the cost where every point $x_i$ is assigned to its closest center: $\\\\sum_{i=1}^n \\\\min_{j=1}^k \\\\|x_i - c_j\\\\|_2^2$.\n\n**Time complexity of the third step.** The third step which updates each cluster center to the center of mass of the cluster takes O(nnz(X)) time. It can be implemented by summing up all the points in each cluster and then dividing the sum by the size of each cluster. This analysis appears in our proof of Theorem C.1 (Line 801)."}, {"review_id": "Gg01HlfHX6", "reviewer": "Reviewer_t2Mh", "summary": "The submitted paper focuses on the problem of unsupervised clustering and aims at improving the $\\Omega(ndk)$ runtime of the ```kmeans++``` algorithm in the clustering of $n$ $d$-dimensional datapoints in $k$ clusters. The proposed algorithm relies on the intuition of running ```kmeans++``` on a one-dimensional projection of the dataset along a random direction $\\boldsymbol v$: the authors prove that such strategy leads to a clustering in $O(nd+n\\ln n)$ steps with an approximation ratio scaling as $\\tilde O(k^4)$ (to be compared with the $O(\\ln k)$ of ```kmeans++```). Numerical experiments compare the performance of the algorithm both with ```kmeans++``` and with other strategies for the production of coresets.", "questions": "* If I understand correctly, the algorithm relies on a single low-dimensional projection along a random vector $\\boldsymbol v\\in\\mathbb R^d$. I was wondering if the algorithm would benefit from the sampling of $m=O(1)$ vectors, or if instead, such strategy would lead to irrelevant benefits.\n* It is not very clear in which units the elements of Table 1 are given (from what I understand the table reports speed-up ratios). Please clarify the caption. Also, do the authors have an estimate of the error on the reported values?\n* Do the authors have an intuition about the fact that the biased and covariance version of the algorithm suffers a remarkable slowdown with respect to the unbiased version?\n* In section 3.2 it is commented that, when working on the Gaussian dataset, the algorithm *did not pick up one of the points close to the origin* so its output is associated with a particularly high cost. Could the author clarify what they mean with this sentence?\n\nMinor typos\n* Line 45: *in approximate* in place of *an approximate*.\n* Line 244: *measn* in place of *means*.\n* What does *with a few approaches in the literature*  refer to in line 147?\n* Line 293: *Senstivity* in place of *Sensitivity*.", "limitations": "Limitations of the contribution have been addressed, see also the *Weakness* section.", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The proposed algorithm is very simple to implement (reminiscent of sliced optimal transportation strategies, in which a low-dimensional projection is adopted to solve a high-dimensional problem with a subsequent polynomial gain in speed). The approach proposed by the authors is indeed compatible with a remarkable speed-up and, given its price in quality, suitable for adoption in a pipeline. One of the strengths of the paper is that the authors can provide theoretical guarantees on the performance obtained by this simple trick.", "weaknesses": "The proposed algorithm pays the price of better performances producing clusterings of lower quality, as the authors themselves point out. This drawback can be mitigated by adopting the algorithm for the construction of coresets within a pipeline (as discussed in the paper). In the case in which the algorithm is adopted as a stand-alone solution, the (possibly deteriorating) effect of structure in the dataset is only partially investigated and addressed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your comprehensive review! Here are our answers to your questions:\n\n**Sampling more than one vector.** Thanks for the great question! An obvious way to obtain improved performance by sampling more than one projection vector would be independently running our algorithm multiple times and taking the clustering with the smallest cost. We observed experimentally that using this approach, while taking the minimum of 10 runs with uniformly sampled vectors, produces cluster assignments with cost comparable to the algorithms that sample biased vectors for their projection.\n\nBeyond this obvious approach, it seems challenging to further exploit multiple projections in a sophisticated manner while keeping the running time close to our current algorithm. Even without considering running time, it is unclear to us whether projecting to O(1) dimensions would improve the approximation ratio significantly (say, by more than a constant factor) over projecting to one dimension. It is certainly interesting to further explore and exploit the power of multiple projections.\n\n**Clarifications about Table 1.** Thank you for the feedback, we will make the caption clearer. Additionally, we will add a table showing the absolute running times and their standard deviation in the full version. (see the rebuttal pdf for the corresponding table for Table 1) \n\n**Biased and covariance versions.** The observed slowdown appears to be an idiosyncracy of the method for computing the column-wise standard deviation in the scientific computing library used in our implementation – it is not as optimized as it could be. In the case of the covariance algorithm, the slowdown comes from additionally having to compute a Cholesky factorization. \n\n**High cost on the Gaussian dataset.** In this dataset there is a small cluster of points at the origin, which, if no center is placed in this cluster, gives a very large clustering cost. In one of the executions of the algorithm, this point was not sampled, which is a low probability event due to the randomness of our algorithm."}, {"review_id": "OnbRXhFNuo", "reviewer": "Reviewer_UQjJ", "summary": "The paper proposes a new clustering algorithm that seeks to have the accuracy of k-means++ while avoiding the time complexity of O(ndk). In particular, the paper focuses on settings where k is large and seeks a O(nd+nlogn) time complexity. This is a practically relevant problem.\n\nThe main algorithm proposed in the paper is a simple algorithm based on projecting all data points onto a random one-dimensional subspace and performing the k-means++ seeding procedure on the dimensionality-reduced data. Interestingly, it is shown that this can be done in time O(nd+nlog(n)) and it has a poly(k) approximation guarantee with respect to the optimal k-means clustering. While the poly(k) guarantee is worse than the O(log k) guarantee of k-means++, a log(k) approximation guarantee can be obtained if we use the proposed algorithm to build a coreset of size poly(kd)*log(n), and then use k-means++ on the resulting coreset.\n\nWhile the techniques in [26] (based on approximate nearest neighbor search) achieve similar goals to those of the present paper (a fast alternative to k-means++ with a complexity that doesn’t depend on k), the algorithm in the present paper is attractive for its surprising simplicity.", "questions": "A natural way to perform a one-dimensional reduction for clustering would be to take the first principal component of the dataset and then perform k-means++ on it. Would such a projection be expected to perform better than the random Gaussian projection used? I realize that computing the first PC would probably be slow, but it may be worth discussing. This may be connected with spectral clustering approaches as well, and with the “biased” versions of the proposed algorithm. \n\nA natural question that the proposed algorithm raises is whether one can use a constant number of random projections to improve the poly(k) approximation factor (maybe just reducing the polynomial degree). Could you comment on that?", "limitations": "The limitations of the proposed approach are discussed in a fair manner.\n", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The proposed algorithm is natural and intuitive, but the theoretical analysis is quite involved.\n\nThe fact that a one-dimensional projection can be shown to provide an approximation guarantee (although a poly(k) one) is interesting and nontrivial, since a Johnson-Lindenstrauss type approach typically requires a projection onto log(n) dimensions. \n\nAfter the one-dimensional projection, a standard implementation of k-means++ seeding does not avoid the O(nk) dependence. As such, the paper proposes a careful data structure to perform k-means seeding on a one-dimensional dataset. The proof that this approach runs in time O(n logn) is technically sophisticated and could be of independent interest. The potential function must be carefully defined, and its use to show that each point is only updated O(log n) times is elegant.\n\nThe paper is well written and clear, and the results should be of interest to people working on the theory of clustering algorithms and to people looking for practical approaches for performing k-means clustering on large datasets with large k.\n", "weaknesses": "The empirical results in the paper are generally positive, but perhaps a bit underwhelming, as the proposed approach doesn’t seem to have a strong advantage over the Lightweight coreset approach from [10]. In particular, the proposed algorithm is slower than the Lightweight approach, and the accuracy of the two approaches is similar (except on the Gaussian dataset case, which was designed to adversarially exploit a weakness of Lightweight).\n\nI found it a little confusing to distinguish between the different variants of the algorithm, and it may be helpful to give them clear names (rather than saying “Ours”). In particular, in Section 1, there is a brief discussion about how the approximation can be reduced from poly(k) to O(log k), by incurring an additional poly(nk)*log(n) time. Are the results in 3 and Table 1 for the variant with the O(log k) approximation? Also, in section 1, it says that this improvement is further discussed in the supplementary material, but it wasn’t very clear where. Is this just referring to the general discussion on coresets in Appendix A? It may be useful to have an explicit theorem about the algorithm that combines the proposed algorithm with k-means++ on a coreset (and that algorithm should have a name). I apologize if I missed this somewhere.\n\nIt may be useful to discuss some of the literature on fast clustering algorithms beyond k-means. For instance, there are “fast” implementations of PAM for k-medoids (such as FastPAM, Clarans and BanditPAM) and of dbscan (such as dbscan++). It may be the case that all those incur the O(ndk) time that this paper tries to avoid, but a mention of that would be useful to the community (specially as it relates to the claim that there are no other clustering algorithms with O(n*log(n)) complexity).\n\nSome other minor comments/typos:\n\n- line 144: k-measn -> k-means\n- line 278: “compared a” -> “compared to a”\n- line 279: “entre dataset” -> “entire dataset”\n- line 344: “running independent” -> “running time independent”", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the insightful feedback! Here is our response to the individual comments and questions in your review:\n\n**Advantage over Lightweight coresets.** Compared to lightweight coresets, a crucial property of our algorithm is that it has a rigorous guarantee on its worst-case (multiplicative) approximation ratio. The lightweight coreset instead has an *additional additive factor* in its guarantee, which depends on the clustering cost of the mean of the data. In critical applications, our algorithm avoids the catastrophic failure that is possible with lightweight coresets (for instance, on the Gaussian dataset where the approximation ratio can become arbitrarily large as the clusters are moved away from the origin). Consequently, when working with a massive dataset with unknown structure, it is always safer to use our algorithm compared to lightweight coresets. Additionally, on the KDD-cup dataset, the quality of the coresets produced by our sensitivity sampling based approach appears to be better.\n\n**Variant with reduced approximation ratio.** We briefly discussed how to reduce the approximation ratio of our algorithm at Line 106 in our introduction, and indeed, more discussions are deferred to Appendix A. Specifically, in Theorem A.2 we describe how to build a coreset using a clustering where the size of the coreset depends on the approximation ratio of the clustering. To reduce the approximation ratio of the clustering produced by our algorithm, we apply Theorem A.2 to the clustering to construct a coreset and then run k-means++ on the coreset. Thank you for your suggestion on including a separate theorem about this variant of our algorithm. We will make sure to add the theorem to the final version and include a more accurate pointer to Appendix A. In fact, our Section 3.1 is dedicated to experiments where we apply Theorem A.2 to our algorithm to construct coresets and we compare it with other coreset construction algorithms in the literature. Correspondingly, our results shown in Figure 2 and the left half of Table 1 are about coreset constructions. In contrast, in Section 3.2 we directly run our initial clustering algorithm without reducing the approximation ratio via a coreset, and correspondingly Figure 3 and the right half of Table 1 are about direct implementations of our clustering algorithm and its comparison with k-means++.\n\nWe also performed additional experiments, in which we ran the version with a reduced approximation ratio and compared it to k-means++. See the rebuttal pdf for a plot which shows the relative cost of the centers produced by this variant for three choices of the coreset size hyperparameter (relative coreset size vs original dataset size). We found that the clustering costs are usually within 10% of full k-means++, while on the KDD dataset it can be as much as 30%. This variant can be slower than k-means++ on smaller datasets for small $k$, but on large datasets such as Census and Song and for $k > 100$ we achieve speedups of 20-120 times, when choosing the hyperparameter to be 0.01 or lower.\n\n**Algorithms beyond k-means.** Thank you for the great suggestion of surveying fast clustering algorithms beyond k-means. In our final version we will make sure to discuss the prior results you mentioned as well as other related works. After reading about them carefully, we did not find any previous result that shows a running time close to O(nd). All algorithms mentioned either have linear dependence on $k$ (taking $k$ as the number of core points in DBSCAN++) or exhibit running time that grows with $n^2$.\n\n**Using the first principal component.**\nThis is an interesting question. The biased and covariance variants of our algorithm are both similar in spirit to your suggestion of projecting to the first principal component. In particular, the covariance variant of our algorithm uses the estimated covariance matrix of the data to sample a vector to project onto. This vector generally captures more of the variance in the data and the clustering (and assignment) produced using this vector generally yields an improvement over sampling uniformly (see e.g. bottom row of Figure 3). When the variance along the first principal component is only slightly larger compared to other directions, projecting deterministically along the first principal component may give suboptimal performance, especially when it leads to (deterministically) collapsing several clusters together.\n\n**Using more than one projection.** Thanks for the great question! We also thought of this natural idea of leveraging more than one projection to improve the approximation ratio, but it seems challenging to achieve this while keeping the running time as small as our current algorithm, especially the running time for producing a clustering after the dimension reduction. Even without considering running time, it is unclear to us whether projecting to O(1) dimensions would improve the approximation ratio significantly (say, by more than a constant factor) over projecting to one dimension. It is certainly interesting to explore further and exploit the optimal relationship between the target dimension and the approximation ratio."}, {"review_id": "qDsDGZDrrJ", "reviewer": "Reviewer_fbAv", "summary": "$k$-means clustering is a classical and fundamental method in machine learning. This paper proposes a very simple method that projects the $n$ data points onto a one-dimensional space by generating a random Gaussian vector. Moreover, the one-dimensional projections can be used for coreset construction and the seeding in $k$-means++. The experimental results have proven the efficiency of the proposed algorithm. ", "questions": "The approximation ratio $\\widetilde{O}(k^4)$ can be improved to $O(\\log{k})$ with running time $O(\\text{nnz}(X) + n\\log{n}) + \\text{poly}(kd) \\log{n}$. However, why does not this result show in the experiments? ", "limitations": "See the Weaknesses part. ", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "(1) The proposed method is very simple and easy to understand.  \n(2) The idea of projecting the $n$ input points onto one-dimensional space is kind of novel.  \n(3) This paper provides strict proofs for the running time and approximation ratio.  \n(4) Experimental results show the efficiency for coreset construction and $k$-means++ implementation. ", "weaknesses": "(1) The essence of the proposed method is dimension reduction. To be specific, the pairwise distances of the $n$ data points are roughly preserved by projecting onto one-dimensional space. The projected distances are used to $k$-means++ seeding and an approximate clustering. By the sorted $n$ scalars, the seeding can be implemented in time $O(n \\log{n})$ independent of $k$ but at the cost of $\\widetilde{O}(k^4)$ approximation ratio. For me, I think the technique is straightforward and the idea's novelty is a little limited.  \n(2) The colors of the curves in Figure 2 and Figure 3 are not easy to distinguish. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your helpful feedback! Here is our response to the individual comments and questions in your review:\n\n**Dimension reduction techniques.** We would like to emphasize that our dimension reduction analysis is much more sophisticated than simply showing that the pairwise distances between the n data points are roughly preserved. As we discuss at Line 221, it is *not possible* to guarantee that all pairwise distances between the n data points are preserved up to a factor better than poly(n) after a one-dimensional projection. Nevertheless, we prove a much better approximation ratio bound poly(k) for the k-means objective. As we mention at Line 229, our analysis follows the approach of [21] (Cohen et al. ‘15) which involves controlling the pairwise distances between only the k optimal centers rather than the entire dataset. Moreover, in [21] and other previous work on dimension reduction for clustering (see Line 215), the target dimension is at least $\\\\Omega(\\\\log k)$. We consider an extremely low target dimension, namely one dimension, in order to facilitate a very fast algorithm after dimension reduction for constructing the final clustering. See Lemma B.3 for details on the precise properties of one-dimensional projections we use. The running time analysis of our algorithm after dimension reduction is also far from being straightforward and it requires a careful potential function argument (see Lemma C.5).\n\n**Experiments on improved approximation ratio.** We achieve the improved approximation ratio by using the initial clustering computed by our fast algorithm to create a coreset, and then running k-means++ on the coreset. Our Section 3.1 is exactly dedicated to experiments that implement this coreset pipeline to improve the approximation ratio. We will make this clearer in the final version.\n\nWe also performed additional experiments, in which we ran the version with a reduced approximation ratio and compared it to k-means++, see the rebuttal pdf for a plot which shows the relative cost of the centers produced by this variant for three choices of the coreset size hyperparameter (relative coreset size vs original dataset size). We found that the clustering costs are usually within 10% of full k-means++, while on the KDD dataset it can be as much as 30%. This variant can be slower than k-means++ on smaller datasets for small $k$, but on large datasets such as Census and Song and for $k > 100$ we achieve speedups of 20-100, when choosing the hyperparameter to be 0.01 or lower. \n\n**Colors in the figures.** Thanks for the feedback! We will make sure to adjust the colors in Figures 2 and 3 to make them more distinct in the final version."}]

Author rebuttal:
Here is a one-page pdf containing a figure and a table showing additional experimental results. More details can be found in our responses to the reviewers.

Meta-review: This paper advances the state of the art for clustering.
The paper provides a randomised algorithm which runs intimate independent of k, the number of clusters, and in input sparsity time. This should be of interest to communities involved in clustering large scale data
Decision: Accept (poster)