{'fraction_non_alphanumeric': 0.05858248957712924, 'fraction_numerical': 0.012126265634306134, 'mean_word_length': 4.235220753305064, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Robust Coreset Construction for Distributed Machine Learning

Motivated by the need of solving machine learning problems over distributed datasets, we explore the use of coreset to reduce the communication overhead. Coreset is a summary of the original dataset in the form of a small weighted set in the same sample space. Compared to other data summaries, coreset has the advantage that it can be used as a proxy of the original dataset, potentially for different applications. However, existing coreset construction algorithms are each tailor-made for a specific machine learning problem. Thus, to solve different machine learning problems, one has to collect coresets of different types, defeating the purpose of saving communication overhead. We resolve this dilemma by developing coreset construction algorithms based on k-means/median clustering, that give a provably good approximation for a broad range of machine learning problems with sufficiently continuous cost functions. Through evaluations on diverse datasets and machine learning problems, we verify the robust performance of the proposed algorithms.


I. INTRODUCTION
The recent decade has observed a dramatic growth in distributed data generation, powered by various Internet of Things (IoT) applications and social networking applications. It has been predicted that the rate of such distributed data generation will exceed the current Internet capacity in the near future [1]. This phenomenon presents both opportunities and challenges for machine learning. On the one hand, the real-time and location-based nature of the distributed data enables novel applications based on machine learning, such as augmented reality and cognitive assistance. On the other hand, the distributed nature of the data sources, coupled with the difficulty of collecting the data to a central location due to network bandwidth, energy, and/or privacy constraints, calls for a fundamentally different way of applying machine learning that is suitable for distributed datasets.
Broadly speaking, three approaches have been proposed for distributed machine learning: sharing the output, sharing the model, and sharing the data. In the first approach [2], data sources independently compute and share outputs of local models, which are then aggregated into a global output (e.g.,  by majority vote). In the second approach [3], [4], data sources share models learned on local data, which are then aggregated into a global model (e.g., by taking weighted average). In the third approach [5], [6], [7], data sources share summaries of their local data, which are then used to compute a global model. Each approach has its pros and cons: the first approach usually has the smallest communication overhead, but only supports one query; the second approach builds a global model that can be used for multiple queries, but only supports one model; the third approach may incur a larger communication overhead, but can potentially support multiple models, hence amortizing the overhead. In this work, we take the third approach, with a particular interest in supporting diverse machine learning models. Fig. 1 illustrates a typical application scenario in the context of mobile edge computing [4], where data sources report local summaries to an edge server, which then computes various models from these summaries.
In particular, we consider data summarization using coreset [8]. A coreset is a small weighted dataset as a proxy of the original dataset with provable approximation guarantees. Compared to other data summaries (e.g., sketches), a coreset preserves the sample space of the original dataset, and is hence more convenient to use, e.g., a classifier learned from the coreset can classify a new data point, the principle components learned from the coreset can be used for feature selection, both in the original sample space. Algorithms have been developed to construct coresets for various machine learning problems (see Section II-B), such that the model learned on the coreset approximates the model learned on the original dataset. However, existing coreset construction algorithms are tailormade for specific machine learning problems, which means that we have to collect different coresets to solve different problems. The question we raise is: Is there a coreset that is good for a broad set of machine learning problems?
In this work, we answer the above question affirmatively by proving that a particular type of coreset, generated by k-means/median clustering, can give a good approximation for a broad set of machine learning problems.

A. Related Work
Distributed learning is considered one of the most promising lines of research for large-scale learning [2], particularly for naturally distributed data. The main challenge in distributed learning is to incorporate information from each distributed dataset, without the high overhead of collecting all the data.
Traditionally, this is achieved by collecting the outputs of learned models or the models themselves [9]. The first approach (i.e., collecting outputs) is more popular among earlier works. For example, [10] proposed various heuristic decision rules (e.g., majority vote) to combine outputs of local classifiers, and [11] proposed to train a global classifier using labeled outputs of local classifiers. The solution in [11] was modified in [12] to improve efficiency for large-scale distributed data, and extended in [9] to include various ways of composing the global training set. The idea was later used to build a descriptive model from distributed data [13]. To further improve the accuracy, a distributed-pasting-votes framework was proposed in [14] to learn sets of classifiers (ensembles).
The second approach (i.e., collecting models) is more useful when we want to learn not just one answer, but the rule to give answers. For example, the distributed boosting framework in [15] requires nodes to share locally trained classifiers, and the federated learning framework in [3] requires nodes to report locally learned models to a single node, which then aggregates the models and broadcasts the result to others.
Meanwhile, research on data summarization has inspired a third approach: collecting data summaries. Data summaries, e.g., coresets, sketches, projections [16], [17], are derived datasets that are much smaller than the original dataset, and can hence be transferred to a central location with a low communication overhead. This approach has been adopted in recent works, e.g., [5], [6], [7]. We are particularly interested in a specific type of data summary, coreset, as it can be used as a proxy of the original dataset. See Section II-B for a detailed review of related works on coreset.

B. Summary of Contributions
We are the first to explore using coreset to support diverse machine learning problems on distributed data. Specifically: 1) We empirically show that although existing coreset construction algorithms are tailor-made for specific machine learning problems, an algorithm based on k-means clustering yields good performance across different problems. 2) We harden the above observation by proving that the optimal k-clustering (including k-means/median) gives a coreset that provides a guaranteed approximation for any machine learning problem with a sufficiently continuous cost function (Theorem III.1). We further prove that the same holds for the coreset given by a suboptimal k-clustering algorithm, as long as it satisfies certain assumptions (Theorem III.2). 3) We adapt an existing algorithm designed to support distributed k-clustering to construct a robust coreset over distributed data with a very low communication overhead. 4) Our evaluations on diverse machine learning problems and datasets verify that k-clustering (especially kmeans) and its approximations provide coresets good for learning a variety of machine learning models.
Roadmap. Section II reviews the background on coreset. Section III presents our main theoretical results on the universal performance guarantee of k-clustering-based coreset. Section IV presents our distributed coreset construction algorithm. Section V evaluates the proposed algorithm. Section VI concludes the paper.

A. Coreset and Machine Learning
Many machine learning problems can be cast as a cost (or loss) minimization problem. Given a dataset in d-dimensional space P ⊆ R d , a generic machine learning problem over P can be characterized by a solution space X , a per-point cost function cost(p, x) (p ∈ P , x ∈ X ), and an overall cost function cost(P, x) (x ∈ X ) that aggregates the per-point costs over P . For generality, we consider P to be a weighted set, where each p ∈ P has weight w p . Let w min := min p∈P w p denote the minimum weight. For an unweighted dataset, we have w p ≡ 1. The machine learning problem is then to solve for the optimal model parameter x * . Example: Let dist(p, x) := p − x 2 denote the Euclidean distance between points p and x. The minimum enclosing ball (MEB) problem [8] aims at minimizing the maximum distance between any data point and a center, i.e., cost(p, x) = dist(p, x), cost(P, x) = max p∈P cost(p, x), and X = R d . The k-means clustering problem aims at minimizing the weighted sum of the squared distance between each data point and the nearest center in a set of k centers, i.e., cost(p, x) = min xi∈x dist(p, x i ) 2 , cost(P, x) = p∈P w p cost(p, x), and Typically, the overall cost is defined as: (i) sum cost, i.e., cost(P, x) = p∈P w p cost(p, x) (e.g., k-means), or (ii) maximum cost, i.e., cost(P, x) = max p∈P cost(p, x) (e.g., MEB).
A coreset is a small weighted dataset in the same space as the original dataset that approximates the original dataset in terms of cost, formally defined below.
where cost(S, x) is defined in the same way as cost(P, x), i.e., cost(S, x) = q∈S u q cost(q, x) for sum cost, and cost(S, x) = max q∈S cost(q, x) for maximum cost.
From Definition II.1, it is clear that the quality of a coreset depends on the cost function it needs to approximate, and hence the machine learning problem it supports.

B. Coreset Construction Algorithms
Because of the dependence on the cost function (Definition II.1), existing coreset construction algorithms are tailormade for specific machine learning problems. Here we briefly summarize common approaches for coreset construction and representative algorithms, and refer to [16], [17] for detailed surveys.
1) Gradient descent algorithms: Originally proposed for MEB [8], [19], these algorithms iteratively add to the coreset a point far enough or furthest from the current center, and stop when the enclosing ball of the coreset, expanded by 1 + , includes all data points. This coreset has been used to compute -approximation to several clustering problems, including k-center clustering, 1-cylinder clustering, and k-flat clustering [8], [20]. As support vector machine (SVM) training can be formulated as MEB problems [21], similar algorithms have been used to support SVM [21], [22]. Variations have been used for dimensionality reduction [23] and probabilistic MEB [24]. These algorithms are considered as variations of the Frank-Wolfe algorithm [25].
2) Random sampling algorithms: These algorithms construct a coreset by sampling from the original dataset. The basic version, uniform sampling, usually requires a large coreset size to achieve a good approximation. Advanced versions use sensitivity sampling [26], where each data point is sampled with a probability proportional to its contribution to the overall cost. Proposed for numerical integration [26], the idea was extended into a framework supporting projective clustering problems that include k-median/means and principle component analysis (PCA) as special cases [18]. The framework has been used to generate coresets for other problems, e.g., dictionary learning [27] and dependency networks [28], and is further generalized in [29]. Although the framework can instantiate algorithms for different machine learning problems by plugging in different cost functions, the resulting coreset only guarantees approximation for the specific problem defined by the plugged-in cost function.
3) Geometric decomposition algorithms: These algorithms divide the sample space or input dataset into partitions, and then selecting points to represent each partition. Specific instances have been developed for weighted facility problems [30], Euclidean graph problems [31], k-means/median [32], [7].
While there are a few works not fully covered by the above approaches, e.g., SVD-based algorithms in [33], [34], the above represents the key approaches used by existing coreset construction algorithms. Using a generic merge-andreduce approach in [35], all these algorithms can be used to construct coresets of distributed datasets. Of course, the resulting coresets are still tailor-made for specific problems. In contrast, we seek coreset construction algorithms which can construct coresets that simultaneously support multiple machine learning problems.

III. ROBUST CORESET CONSTRUCTION
Our main result is that selecting representative points using clustering techniques yields a coreset that achieves a good approximation for a broad set of machine learning problems.

A. Motivating Experiment
We start with an initial experiment that compares three algorithms representing the three approaches in Section II-B: the algorithm in [19] representing 'gradient descent', the framework in [18] instantiated for k-means representing 'random sampling', and the algorithm in [7] representing 'decomposition'. We add uniform sampling as a baseline. As the algorithm in [19] was designed for MEB and the others were designed for k-means, we evaluate both MEB and k-means.
The evaluation is based on a synthetic dataset containing 4000 points uniformly distributed in [1,50] 3 ; evaluations on real datasets will be presented later (Section V). All the algorithms are tuned to have the same average coreset size. We evaluate the performance of a coreset S by the normalized cost, defined as cost(P, x S )/cost(P, x * ), where x * is the model learned from the original dataset P , and x S is the model learned from the coreset. The smaller the normalized cost, the better the performance. As these coreset construction algorithms are randomized, we plot the CDF of the normalized costs computed over 100 Monte Carlo runs in Fig. 2.
Not surprisingly, a coreset construction algorithm designed for one problem can perform poorly for another, e.g., the gradient descent algorithm [19] designed for MEB performs poorly for k-means. Interestingly, the decomposition algorithm [7], although designed for k-means, also performs well for MEB. This observation triggers a question: Is the superior performance of the decomposition algorithm [7] just a coincidence, or is there something fundamental?

B. The k-clustering Problem
At the core, the decomposition algorithm in [7] constructs a k-point coreset by partitioning the dataset into k clusters using k-means clustering, and then using the cluster centers as the coreset points. To analyze its performance in supporting a general machine learning problem, we introduce a few definitions.
Given a weighted dataset P ⊆ R d with weight w p (p ∈ P ), and a set Q = {q 1 , ..., q k } of k ≥ 1 points in R d (referred to as centers), the cost of clustering P into Q is defined as for a constant z > 0. The k-clustering problem is to find the set of k centers that minimizes (3). For z = 1, this is the k-median problem. For z = 2, this is the k-means problem. We will use the solution to the k-clustering problem to construct coresets, based on which we can solve general machine learning problems. We use c(P, ·) to denote the cost function of this auxiliary problem and cost(P, ·) to denote the cost function of a general machine learning problem of interest. We denote by µ(P ) the optimal center for 1-clustering of P . It is known that for z = 2, µ(P ) is the sample mean: We denote by opt(P, k) the optimal cost for k-clustering of P . It is known that k-means and k-median are both NPhard problems [36], [37], for which efficient heuristics exist (e.g., Lloyd's algorithm and variations) [38]. Let approx(P, k) denote the cost of a generic k-clustering algorithm, which always satisfies approx(P, k) ≥ opt(P, k).
where P i is the subset of points in P whose closest center in Q is q i (ties broken arbitrarily). For ease of presentation, we use 1 {P i } i∈[k] to denote the partition induced by the optimal k-clustering, and { P i } i∈[k] to denote the partition induced by a suboptimal k-clustering.

C. Coreset by Optimal k-clustering
We will show that the superior performance of the algorithm in [7] observed in Section III-A is not a coincidence; instead, it is a fundamental property of any coreset computed by kclustering, as long as the cost function of the machine learning problem satisfies certain continuity conditions. Sketch of analysis: At a high level, our analysis is based on the following observations: 1) If doubling the number of centers only reduces the optimal k-clustering cost by a little, then using two centers instead of one in any cluster gives little reduction to its clustering cost (Lemma III.1). 2) If selecting two centers in a cluster P i gives little reduction to its clustering cost, then all the points in P i must be close to its center µ(P i ) (Lemma III.2), as otherwise selecting an outlier as the second center would have reduced the cost substantially. 3) If each data point is represented by a coreset point with a similar per-point cost, then the coreset gives a good approximation of the overall cost (Lemmas III.3 and III.4). Therefore, for any machine learning problem with a sufficiently continuous cost function, if the condition in item (1) is satisfied, then the per-point cost of each k-clustering center will closely approximate the per-point costs of all the points in its cluster, and hence the set of k-clustering centers will give a good coreset (Theorem III.1).
Complete analysis: We now present the precise statements, supported by proofs in Appendix A.
is the partition of P generated by the optimal k-clustering.
Lemma III.3. For any machine learning problem with cost function cost(P, Lemma III.4. For any machine learning problem with cost function cost(P, We now prove the main theorem based on Lemmas III.1-III.4.
Theorem III.1. If opt(P, k) − opt(P, 2k) ≤ w min ( ρ ) z , then the optimal k-clustering of P gives an -coreset for P w.r.t. both the sum cost and the maximum cost for any per-point cost function satisfying (i) cost(p, Moreover, as cost(p, x) ≥ 1, By Lemma III.3, k-clustering gives ancoreset for P w.r.t. the sum cost; by Lemma III.4, k-clustering gives an -coreset for P w.r.t. the maximum cost.
Often in practice, the coreset size must satisfy some upper bound specified by the maximum communication overhead. In this case, we can rephrase Theorem III.1 to characterize the quality of approximation as a function of the coreset size.
Corollary III.1.1. Given a maximum coreset size k ∈ Z + (positive integers), for any cost function satisfying the conditions in Theorem III.1, the optimal k-clustering gives an -coreset for P w.r.t. this cost function, where Proof. This is a direct implication of Theorem III.1, as setting by (6) satisfies the condition in Theorem III.1.
Remark: Condition (i) in Theorem III.1 is easily satisfied by any machine learning problem with nonnegative per-point costs, as we can add '+1' to the cost function without changing the optimal solution. Even without this condition, a similar proof will show that the coreset S given by k-clustering approximates the original dataset P in that |cost(P, x) − cost(S, x)| ≤ (∀x ∈ X ), where = p∈P w p for the sum cost, and = for the maximum cost.
Condition (ii) is satisfied by many machine learning problems with distance-based cost functions. For example, for MEB, cost(p, x) = dist(p, x), where x ∈ R d denotes the center of the enclosing ball. For any data points p, p ∈ R d , by the triangle inequality, we have: Hence, its cost function is 1-Lipschitz-continuous (i.e., ρ = 1). See Appendix B for more examples. In Section V, we will stress-test our coreset when this condition is violated.
D. Coreset by Suboptimal k-clustering While Theorem III.1 and Corollary III.1.1 suggest that the optimal k-clustering gives a good coreset, the k-clustering problem is NP-hard [36], [37]. The question is whether similar performance guarantee holds for the coreset computed by an efficient but suboptimal k-clustering algorithm. To this end, we introduce a few assumptions on the k-clustering algorithm: Assumption 1 (local optimality): Given the partition { P i } k i=1 generated by the algorithm, the center it selects in each P i is µ( P i ), i.e., the optimal 1-clustering center for P i .
Assumption 2 (self-consistency): For any P and any k ≥ 1, the cost of the algorithm satisfies Assumption 3 (greedy dominance): For any P , the 2clustering cost of the algorithm satisfies where c(P, Q) is defined in (3), and p * := arg max p∈P w p · dist(p, µ(P )) z is the point with the highest 1-clustering cost. We argue that these are mild assumptions that should be satisfied or approximately satisfied by any good k-clustering algorithm. Assumption 1 is easy to satisfy, as computing the 1mean is easy (i.e., sample mean), and there exists an algorithm [39] that can compute the 1-median to arbitrary precision in nearly linear time. Assumption 2 means that applying the algorithm for 2k-clustering of P should perform no worse than first using the algorithm to partition P into k clusters, and then computing 2-clustering of each cluster. Assumption 3 means that for k = 2, the algorithm should perform no worse than a greedy heuristic that starts with the 1-clustering center, and then adds the point with the highest clustering cost as the second center.
We show that for any k-clustering algorithm satisfying these assumptions, statements analogous to Lemma III.1 and Lemma III.2 can be made. Let { P i } k i=1 denote the partition of P generated by the k-clustering algorithm.
where approx(P, k) is the cost of a (possibly suboptimal) k-clustering algorithm satisfying Assumptions 1-3, then the centers computed by the algorithm for k-clustering of P Algorithm 1: Robust Coreset Construction(P, , ρ) input : A weighted set P with minimum weight wmin, approximation error > 0, Lipschitz constant ρ output: An -coreset S for P w.r.t. a cost function satisfying Theorem III.
give an -coreset for P w.r.t. both the sum cost and the maximum cost for any per-point cost function satisfying (iii) in Theorem III.1.
Proof. The proof follows the same steps as that of Theorem III.1, except that Lemma III.1 is replaced by Lemma III.5, and Lemma III.2 is replaced by Lemma III.6. Note that Lemmas III.3 and III.4 hold for any partition of P , which in this case is { P i } k i=1 generated by the k-clustering algorithm.
Similar to Corollary III.1.1, we can rephrase Theorem III.2 to characterize the quality of a coreset of a specified size.
Corollary III.2.1. Given a maximum coreset size k ∈ Z + , for any cost function satisfying the conditions in Theorem III.1 and any k-clustering algorithm satisfying Assumptions 1-3, the centers computed by the algorithm for k-clustering of P give an -coreset for P w.r.t. the given cost function, where

E. Coreset Construction Algorithm
Based on Theorem III.2, we propose a centralized kclustering-based coreset construction algorithm, called Robust Coreset Construction (RCC) (Algorithm 1), which uses a kclustering algorithm as subroutine in lines 2 and 4. If the coreset size k is predetermined, we can directly start from line 4. The constant z = 1 if the adopted clustering algorithm is for k-median, or z = 2 if it is for k-means.
The k-clustering subroutine: Algorithm 1 can use any kclustering algorithm as subroutine, although our performance guarantee holds only if the algorithm satisfies Assumptions 1-3. We note that these assumptions are easy to satisfy. Consider the standard k-means algorithm (Lloyd's algorithm), which iteratively assigns each point to the nearest center and updates the centers to the means of the clusters. Clearly, this algorithm satisfies Assumption 1. Moreover, with the following initialization, it also satisfies Assumptions 2 and 3. For 2k-clustering of P : 1) if k = 1, then use the mean µ(P ) and the point p * with the highest clustering cost as defined in (9) as the initial centers; 2) if k > 1, then first compute k-clustering of P , then compute 2-clustering of each of the k clusters, and finally use the union of the 2-clustering centers as the initial centers.
Any odd number of initial centers are chosen randomly. Since iterations can only reduce the cost, Lloyd's algorithm with this initialization satisfies Assumptions 1-3.

IV. DISTRIBUTED CORESET CONSTRUCTION
In a distributed setting, the entire dataset P is distributed across n (n > 1) nodes v 1 , . . . , v n , where each v j has a subset P j ⊆ P . We have shown in Section III that the k-clustering centers of P form a robust coreset. However, computing the global k-clustering centers of a distributed dataset is highly non-trivial. Note that a naive solution that only includes local centers in the global coreset may select nearly identical points at different nodes if the local datasets are similar, which is non-optimal and inefficient.
An existing algorithm: The state-of-the-art solution to the distributed k-clustering problem is based on an algorithm called Communication-aware Distributed Coreset Construction (CDCC) [5]. In our context, this solution works as follows: 1) the server allocates a given sample size t among the nodes, such that the sample size t j allocated to node v j is proportional to the local k-clustering cost c(P j , B j ) reported by v j ; 2) each node v j generates and reports a local coreset D j , consisting of the local centers B j and t j points sampled i.i.d. from P j , where each p ∈ P j has a sampling probability proportional to the cost of clustering p to the nearest center in B j ; 3) the server computes a set of k-clustering centers Q D from the coreset D = n j=1 D i . It is shown in [5] that if t = O( 1 2 (kd + log 1 δ )) for k-median and t = O( 1 4 (kd+log 1 δ )+nk log nk δ ) for k-means, then with probability at least 1−δ, D is an -coreset for P w.r.t. the cost function of k-median/means. According to Definition II.1, this implies that if Q P is the set of optimal k-clustering centers for P , then c(P, Q D )/c(P, Q P ) ≤ (1 + )/(1 − ).
Adaptation for coreset construction: First, we skip step (3) (i.e., computation of Q D ) and directly use D = n j=1 D j as the coreset. This is because the coreset of a coreset cannot have a better quality than the original coreset [35].
Moreover, in CDCC, the number of local centers k is a given parameter as it is only designed to support k-clustering. Since our goal is to support a variety of machine learning problems, the number of local centers k j at each v j becomes a design parameter that can vary across nodes. Given a global coreset size N , we will show that the approximation error of the constructed coreset depends on (k j ) n j=1 through 1 √ N − n j=1 kj n j=1 approx(P j , k j ) (see Theorem IV.1). Thus, we set (k j ) n j=1 to minimize this error, and obtain the remaining t = N − n j=1 k j points by sampling. Combining these ideas yields a distributed coreset construction algorithm called Distributed Robust Coreset Construction (DRCC) (Algorithm 2). The algorithm works in three steps: (1) each node reports its local k-clustering cost for a range of k (lines 2-3), (2) the server uses the reported costs to configure the number of local centers k j and the number of random samples t j at each node v j (lines 5-7), and (3) each node independently constructs a local coreset using a combination of samples and local centers (lines 9-12). DRCC generalizes CDCC in that: (i) it allows the input dataset to be weighted report each point q ∈ Sj ∪ B k j j and its weight uq to the server; (w p : weight of input point p; u q : weight of coreset point q); (ii) it allows the number of local centers to be different for different nodes. In the special case of k j ≡ k for all j ∈ [n] and w p ≡ 1 for all p ∈ P , DRCC is reduced to CDCC.
Communication overhead: DRCC has a communication overhead of O(Kn), measured by the total number of scalars reported by the nodes besides the coreset itself. In practice, K should be a small constant to allow efficient computation of local k-clustering for k ∈ [K]. This overhead is much smaller than the O((n − 1)N d) overhead of the merge-and-reduce approach in [35].
Quality of coreset: Regarding the quality of the coreset, we have proved the following result in Appendix A. Given a general per-point cost function cost(p, x), define f x (p) := w p (cost(p, x) − cost(b p , x) + ρdist(p, b p )), where b p is the center in B kj j closest to p ∈ P j . Let dim(F, P ) denote the dimension of the function space F := {f x (p) : x ∈ X } [5].
Theorem IV.1. If cost(p, x) is ρ-Lipschitz-continuous in p for any x ∈ X , then ∃t = O( 1 2 (dim(F, P ) + log 1 δ ) such that with probability at least 1 − δ, the coreset D constructed by DRCC based on local k-median clustering, which contains k j local centers from v j (j ∈ [n]) and t random samples, satisfies for all x ∈ X .
The parameter dim(F, P ) is a property of the machine learning problem under consideration, which intuitively measures the degree of freedom in the solution x ∈ X , e.g., dim(F, P ) = O(kd) for k-means/median in d-dimensional space [18]. See Appendix C for more discussions.
Due to the relationship between t and given in Theorem IV.1, the bound on the right-hand side of (11) depends on parameters t and (k j ) n j=1 through 1 √ t n j=1 c(P j , B kj j ). Thus, given a total coreset size N = t + n j=1 k j , we select these parameters to minimize the error bound (line 5 in Algorithm 2).
Remark: The performance bound in Theorem IV.1 is on the absolute error, instead of the relative error as guaranteed by an -coreset. Nevertheless, if ∃β > 0 and (k j ) n j=1 such that cost(P, x) = p∈P w p cost(p, x) ≥ β n j=1 c(P j , B kj j ) for all x ∈ X , then (11) implies that D is an -coreset for P w.r.t. cost(P, x) with probability at least 1 − δ if t = O( ρ 2 2 (dim(F, P ) + log 1 δ )), i.e., the total coreset size N = O( ρ 2 2 (dim(F, P )+log 1 δ )+ n j=1 k j ). In the special case where cost(P, x) is the k-median clustering cost and k j ≡ k, we have ρ = 1 (Appendix B) and dim(F, P ) = O(kd) [18], and thus the size of an -coreset is O( 1 2 (kd + log 1 δ ) + kn), which generalizes the result in [5] to weighted datasets.

V. PERFORMANCE EVALUATION
We evaluate the proposed coreset construction algorithms and their benchmarks on a variety of machine learning problems and datasets, and compare the cost of each model learned on a coreset with the cost of the model learned on the original dataset. We first perform evaluations in a centralized setting to compare different approaches to construct coresets, and then evaluate different ways of applying the most promising approach in a distributed setting.
Coreset construction algorithms: In the centralized setting, we evaluate RCC based on k-median clustering ('RCCkmedian') and RCC based on k-means clustering ('RCCkmeans'), together with benchmarks including the algorithm in [19] ('gradient descent'), the framework in [18] instantiated for k-means ('random sampling'), and uniform sampling ('baseline'). We note that the algorithm in [7] ('decomposition' in 2 The model x denotes the center of enclosing ball for MEB and the set of centers for k-means. For PCA, x = W W T , where W is a d × l matrix consisting of the first l (l < d) principle components as columns. For SVM,    In the distributed setting, we take the best-performing algorithm in the centralized setting ('RCC-kmeans') and evaluate its distributed extensions, including CDCC [5], a straightforward extension where each node runs local (N/n)-means to compute its portion of the coreset (N : total coreset size, n: number of nodes), and DRCC.
Datasets: We use four different datasets: (1) Fisher's iris data [40], which is a 5-dimensional dataset consisting of measurements of 150 iris specimens and their species, (2) Facebook metrics [41], which is a 19-dimensional dataset consisting of features of 500 posts published in a popular Facebook page, (3) Pendigits data [42], which is a 17dimensional dataset consisting of feature vectors of 7494 handwritten digits, and (4) MNIST data [43], which consists of 60, 000 images of handwritten digits, each trimmed to 20 × 20 pixels.
We normalize each numerical dimension to [0, 1]. We map labels to numbers such that the distance between two points with different labels is no smaller than the distance between points with the same label. Given a d-dimensional dataset (including labels) with L types of labels, we map type-l label Table I for a summary. In testing SVM, we map one label to '1' and the rest to '-1'. Each data point has a unit weight.
To generate distributed datasets, we use three schemes: (i) uniform, where the points are uniformly distributed across n nodes, (ii) specialized, where each node is associated with one label and contains all the data points with this label, and (iii) hybrid, where the first n 0 nodes are "specialized" as in (ii), and the remaining data are randomly partitioned among the remaining nodes.
Machine learning problems: We evaluate three unsupervised learning problems-MEB, k-means, and PCA, and one supervised learning problem-SVM. Table II gives their cost functions, where for a data point p ∈ R d , p 1:d−1 ∈ R d−1 denotes the numerical portion and p d ∈ R denotes the label.
The meaning of the model parameter x is problem-specific, as explained in the footnote. We also provide (upper bounds of) the Lipschitz constant ρ; see Appendix B for analysis. Here     l is the number of principle components computed by PCA, and ∆ is the diameter of the sample space. In our experiments, Results in centralized setting: We evaluate the coreset construction algorithms by the normalized costs of the models learned from the coresets, as explained in Section III-A. Figures 3-6 show the average normalized costs over 100 Monte Carlo runs.
We see that the proposed algorithms ('RCC-kmeans' and 'RCC-kmedian') perform either the best or comparably to the best across all the datasets and all the machine learning problems. The gradient descent algorithm in [19], designed for MEB, can perform very poorly for other machine learning problems. The sampling-based algorithms ('random sampling' in [18] and 'baseline') perform relatively poorly for MEB and PCA. Note that all the algorithms are within 3% of the optimal for MEB.   Besides the average normalized costs, we also evaluated the CDFs of the normalized costs. The results are shown in Figures 7-10. The results show similar comparisons between the algorithms as observed in Figures 3-6. Moreover, we see from the CDFs that the proposed algorithms ('RCC-kmeans' and 'RCC-kmedian') also have significantly less performance variation than the benchmarks, especially the sampling-based algorithms ('random sampling' and 'baseline'). This means that the quality of the coresets constructed by the proposed algorithms is more reliable, which is a desirable property.
Between the proposed algorithms, 'RCC-kmeans' sometimes outperforms 'RCC-kmedian', e.g., Fig. 6 (c-d). Moreover, we note that 'RCC-kmeans' can be an order of magnitude faster than 'RCC-kmedian', as shown in Table III. Other than 'RCC-kmedian', all the algorithms can finish in a few seconds. In Appendix D, we have also validated the approximation bound given by Corollary III.2.1.
Results in distributed setting: We use the two larger datasets, Pendigits and MNIST, to generate distributed datasets at n = 10 nodes according to the three aforementioned schemes ('uniform', 'specialized', 'hybrid'), where node j  (j ∈ [n]) is associated with label 'j − 1', and n 0 = 5. We parameterize CDCC with k = 2 according to the evaluated kmeans problem. For DRCC (Algorithm 2), we solve line 5 by a greedy heuristic. As a benchmark, we also show performance of 'RCC-kmeans', which is the best-performing algorithm in the centralized setting. We generate m 1 distributed datasets using each scheme and repeat coreset construction for m 2 times for each dataset. For Pendigits, m 1 = m 2 = 10. For MNIST, m 1 = m 2 = 5. Figures 11-12 show the average normalized costs. As CDCC blindly designates k coreset points to be local centers at each node, it suffers when the local datasets are  highly heterogeneous (under the 'hybrid' scheme). Meanwhile, a solution that only includes local centers into the coreset ('local N/n-means') may select nearly identical points at different nodes if the local datasets follow the same distribution (under the 'uniform' scheme), thus not fully utilizing the given coreset size. By automatically tuning the numbers of local centers according to the local clustering costs, DRCC is able to customize its configuration to the dataset at hand and thus achieves a more robust performance, i.e., providing better performance on the average across different models and datasets. When DRCC performs worse than CDCC and 'local N/nmeans' (for k-means under the 'uniform' scheme), the difference is very small (< 3%). Note that 'RCC-kmeans' is a centralized algorithm and is only used to provide a lower bound for the other three algorithms that run in the distributed setting.

VI. CONCLUSION
We show, both theoretically and empirically, that the kclustering centers form a coreset that provides a guaranteed approximation for a broad set of machine learning problems with sufficiently continuous cost functions. As k-clustering (including k-means/median) is one of the most well-studied machine learning problems, this result allows one to leverage existing k-clustering algorithms for coreset construction. In particular, we have adapted an existing distributed k-clustering algorithm to construct a robust coreset over distributed data with a very low communication overhead. Our extensive evaluations verify the superior performance of the proposed algorithms in supporting diverse machine learning problems.  Proof. By definition, opt(P, k) = k i=1 opt(P i , 1). By letting X i := {X i,1 , X i,2 } be the centers of the optimal 2-clustering of P i , we have 2k). (12) Thus we have Since opt Proof of Lemma III.2: Proof. By definition of k-clustering, we have for any p 0 ∈ P i , where P 1 i is the subset of points in P i that are closer to µ(P i ) than p 0 (ties broken arbitrarily) and P 2 i := P i \ P 1 i . Then subtracting (14) by (15), we have As dist(p, µ(P i )) z − dist(p, p 0 ) z ≥ 0 for all p ∈ P 2 i , w p (dist(p, µ(P i )) z −dist(p, p 0 ) z ) ≤ opt(P i , 1)−opt(P i , 2) ≤ , ∀p ∈ P 2 i . (17) In particular, for p = p 0 , w p0 dist(p 0 , µ(P i )) z ≤ and thus dist(p 0 , µ(P i )) ≤ ( wmin ) 1 z . The proof completes by noting that this holds for any p 0 ∈ P i .

Proof of Lemma III.3:
Proof. Since ∀x ∈ X and p ∈ P i , (18) multiplying this inequality by w p and then summing over p ∈ P i , we have Summing up (19) over all i ∈ [k], we have Therefore, S is an -coreset for P w.r.t. cost(P, x).

Proof of Lemma III.4
Proof. Taking maximum over p ∈ P i for (5), we have that ∀i ∈ [k] and x ∈ X , Taking maximum over i ∈ [k] for (20): ∀x ∈ X , That is, S is an -coreset for P w.r.t. cost(P, x).
Proof of Lemma III.5: i , P 2 i } be the partition of P i generated by the algorithm for 2-clustering of P i . Under Assumption 1, Combining (21,22) yields approx( P i , 1) − approx( P i , 2) ≤ for any i ∈ [k].
Proof of Theorem IV.1: Proof. The proof is based on a sampling lemma from [5]: Let u q = p∈P mp mq|S| for q ∈ P . If for a sufficiently large constant α, |S| ≥ α 2 (dim(F, P )+log 1 δ ), then with probability at least 1 − δ, ∀f ∈ F : p∈P f (p) − q∈S u q f (q) ≤ ( p∈P m p )(max p∈P f (p) mp ).
In our case, S = n j=1 S j , and B = n j=1 B kj j . Define f x (p) := w p (cost(p, x) − cost(b p , x) + ρdist(p, b p )), where b p is the center in B kj j closest to p ∈ P j . By the ρ-Lipschitz-continuity of cost(p, x), f x (p) ≥ 0 and f x (p) ≤ 2ρw p dist(p, b p ). By lines 6 and 9 in Algorithm 2, k-medianbased DRCC generates S via i.i.d. sampling from P with probabilities proportional to m p = w p dist(p, b p ). Therefore, by Lemma VI.1, there exists |S| = O( 1 2 (dim(F, P ) + log 1 δ )) such that with probability at least 1 − δ, ∀x ∈ X : The righthand side of (25) equals the righthand side of (11) as p∈P m p = n j=1 c(P j , B kj j ) and fx(p) mp ≤ 2ρ. We will show that the lefthand side of (25) also equals the lefthand side of (11). Specifically, and since u q w q = u q for each q ∈ S (line 10 in Algorithm 2), Since q∈S u q dist(q, b q ) = p∈P m p , ∆ = as u b = p∈P b w p − q∈P b ∩S u q (line 11 in Algorithm 2).
APPENDIX B: ANALYSIS OF LIPSCHITZ CONSTANT • For MEB, cost(p, x) = dist(p, x), where x ∈ R d denotes the center of the enclosing ball. For any data points p, p ∈ R d , by triangle inequality, we have: Hence, its cost function is 1-Lipschitz-continuous (ρ = 1).
• For k-median, cost(p, x) = min q∈x dist(p, q), where x ⊂ R d denotes the set of k centers. For any data points p, p ∈ R d , without loss of generality (WLOG), suppose min q∈x dist(p, q) ≥ min q∈x dist(p , q) = dist(p , q ) for some q ∈ x. Then Hence, ρ = 1 for k-median.
APPENDIX C: ANALYSIS OF DIMENSION OF FUNCTION SPACE Definition VI.1 ( [5]). Let F := {f x : x ∈ X }, where each element f x : P → R ≥0 is a function from a set P to nonnegative real numbers. Define B(x, r) := {p ∈ P : f x (p) ≤ r}. The dimension of the function space dim(F, P ) is the smallest integer m such that |{S ∩ B(x, r) : x ∈ X , r ≥ 0}| ≤ |S| m , ∀S ⊆ P. (36)