Robust and Fully-Dynamic Coreset for Continuous-and-Bounded Learning (With Outliers) Problems
Year: 2022

Abstract:
In many machine learning tasks, a common approach for dealing with large-scale data is to build a small summary, e.g., coreset, that can efficiently represent the original input. However, real-world datasets usually contain outliers and most existing coreset construction methods are not resilient against outliers (in particular, an outlier can be located arbitrarily in the space by an adversarial attacker). In this paper, we propose a novel robust coreset method for the continuous-and-bounded learning problems (with outliers) which includes a broad range of popular optimization objectives in machine learning, e.g., logistic regression and k-means clustering. Moreover, our robust coreset can be efficiently maintained in fullydynamic environment. To the best of our knowledge, this is the first robust and fully-dynamic coreset construction method for these optimization problems. Another highlight is that our coreset size can depend on the doubling dimension of the parameter space, rather than the VC dimension of the objective function which could be very large or even challenging to compute. Finally, we conduct the experiments on real-world datasets to evaluate the effectiveness of our proposed robust coreset method.

heading: 1 Introduction
text: As the rapid increasing of data volume in this big data era, we often need to develop low-complexity (e.g., linear or even sublinear) algorithms for machine learning tasks. Moreover, our dataset is often maintained in a dynamic environment so that we have to consider the issues like data insertion and deletion. For example, as mentioned in the recent article [20], Ginart et al. discussed the scenario that some sensitive training data have to be deleted due to the reason of privacy preserving. Obviously, it is prohibitive to re-train our model when the training data is changed dynamically, if the data size is extremely large. To remedy these issues, a natural way is to construct a small-sized summary of the training data so that we can run existing algorithms on the summary rather than the whole data. Coreset [18], which was originally studied in the community of computational geometry [1], has become a widely used data summary for many large-scale machine learning problems [7, 27, 34, 38, 36, 25]. As a succinct data compression technique, coreset also enjoys several nice properties. For instance, coreset is usually composable and thus can be applied in the environment like distributed computing [28]. Also, it is usually able to obtain small coresets for streaming algorithms [23, 15] and fully-dynamic algorithms with data insertion and deletion [10, 24].
∗Part of this work was done when Zixiu Wang was an intern under the supervision of Yiwen Guo at ByteDance.
†Corresponding author.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
However, the existing coreset construction methods are still far from being satisfactory in practice. A major bottleneck is that most of them are sensitive to outliers. We are aware that real-world dataset is usually noisy and may contain outliers; note that the outliers can be located arbitrarily in the space and even a single outlier can significantly destroy the final machine learning result. A typical example is poisoning attack, where an adversarial attacker may inject several specially crafted samples into the training data which can make the decision boundary severely deviate and cause unexpected misclassification [5]. In the past decades, a number of algorithms have been proposed for solving optimization with outliers problems, like clustering [11, 14, 12, 21, 42], regression [39, 37, 17], and PCA [8].
To see why the existing coreset methods are sensitive to outliers, we can take the popular sampling based coreset framework [19] as an example. The framework needs to compute a “sensitivity” for each data item, which measures the importance degree of the data item to the whole data set; however, it tends to assign high sensitivities to the points who are far from the majority of the data, that is, an outlier is likely to have a high sensitivity and thus has a high chance to be selected to the coreset. Obviously, the coreset obtained by this way is not pleasant since we expect to contain more inliers rather than outliers in the coreset. It is also more challenging to further construct a fully-dynamic robust coreset. The existing robust coreset construction methods [19, 26] often rely on simple uniform sampling and are efficient only when the number of outliers is a constant factor of the input size (we will discuss this issue in Section 3.1). Note that other outlier-resistant data summary methods like [21, 13] usually yield large approximation factors and are not easy to be maintained in a fully dynamic scenario, to our knowledge.

heading: 1.1 Our Contributions
text: In this paper, we propose a unified fully-dynamic robust coreset framework for a class of optimization problems which is termed continuous-and-bounded (CnB) learning. This type of learning problems covers a broad range of optimization objectives in machine learning [41, Chapter 12.2.2]. Roughly speaking, “CnB learning” requires that the optimization objective is a continuous function (e.g., smooth or Lipschitz), and meanwhile the solution is restricted within a bounded region. We emphasize that this “bounded” assumption is quite natural in real machine learning scenarios. To shed some light, we can consider running an iterative algorithm (e.g., the popular gradient descent or expectation maximization) for optimizing some objective; the solution is always restricted within a local region except for the first few rounds. Moreover, it is also reasonable to bound the solution range in a dynamic environment because one single update (insertion or deletion) is not likely to dramatically change the solution.
Our coreset construction is a novel hybrid framework. First, we suppose that there exists an ordinary coreset construction method A for the given CnB optimization objective (without considering outliers). Our key idea is to classify the input data into two parts: the “suspected” inliers and the “suspected” outliers, where the ratio of the sizes of these two parts is a carefully designed parameter λ. For the “suspected” inliers, we run the method A (as a black box); for the “suspected” outliers, we directly take a small sample uniformly at random; finally, we prove that these two parts together yield a robust coreset. Our framework can be also efficiently implemented under the mergeand-reduce framework for dynamic setting (though the original merge-and-reduce framework is not designed for the case with outliers) [4, 23]. A cute feature of our framework is that we can easily tune the parameter λ for updating our coreset dynamically, if the fraction of outliers is changed in the dynamic environment.
The other contribution of this paper is that we propose two different coreset construction methods for CnB optimization objectives (i.e., the aforementioned black box A). The first method is based on the importance sampling framework [19], and the second one is based on a space partition idea. Our coreset sizes depend on the doubling dimension of the solution space rather than the VC (shattering) dimension. This property is particularly useful if the VC dimension is too high or not easy to compute, or considering the scenarios like sparse optimization (the domain of the solution vector has a low doubling dimension). To our knowledge, the only existing coreset construction methods that depend on doubling dimension are from Huang et al. [26] and Cohen-Addad et al. [16], but their results are only for clustering problems. Our methods can be applied for a broad range of widely studied optimization objectives, such as logistic regression [38], Bregman clustering [2], and truth discovery [31]. It is worth noting that although some coreset construction methods for them have
been proposed before (e.g., [33, 38, 43, 17, 25]), they are all problem-dependent and we are the first, to the best of our knowledge, to study them from a unified “CnB” perspective.

heading: 2 Preliminaries
text: We introduce several important notations used throughout this paper. Suppose P is the parameter space. Let X be the input data set that contains n items in a metric space X , and each x ∈ X has a weight w(x) ≥ 0. Further, we use (X, z) to denote a given instance X with z outliers. We always use | · | and J·K respectively to denote the number of data items and the total weight of a given data set. We consider the learning problem whose objective function is the weighted sum of the cost over X , i.e.,
f(θ,X) := ∑ x∈X w(x)f(θ, x), (1)
where f(θ, x) is the non-negative cost contributed by x with the parameter vector θ ∈ P . The goal is to find an appropriate θ so that the objective function f(θ,X) is minimized. Usually we assume each x ∈ X has unit weight (i.e., w(x) = 1), and it is straightforward to extend our method to weighted case. Given the pre-specified number z ∈ Z+ of outliers in X (for weighted case, “z” refers to the total weight of outliers), we then define the “robust” objective function:
fz(θ,X) := min O⊂X,JOK=z f(θ,X\O). (2)
Actually, the above definition (2) comes from the popular “trimming” idea [39] that has been widely used for robust optimization problems.
Below we present the formal definition of continuous-and-bound learning problem. A function g : P → R is α-Lipschitz continuous if for any θ1, θ2 ∈ P , |g(θ1) − g(θ2)| ≤ α∥∆θ∥, where ∆θ = θ1 − θ2 and ∥ · ∥ is some specified norm in P . Definition 1 (Continuous-and-Bounded (CnB) Learning [41]). Let α, ℓ > 0, and θ̃ ∈ P . Denote by B(θ̃, ℓ) the ball centered at θ̃ with radius ℓ in the parameter space P . An objective (1) is called a CnB learning problem with the parameters (α, ℓ, θ̃) if (i) the loss function f(·, x) is α-Lipschitz continuous for any x ∈ X , and (ii) θ is always restricted within B(θ̃, ℓ). Remark 1. We can also consider other variants for CnB learning with replacing the “α-Lipschitz continuous” assumption. For example, a differentiable function g is “α-Lipschitz continuous gradient” if its gradient ∇g is α-Lipschitz continuous (it is also called “α-smooth”). Similarly, a twice-differentiable function g is “α-Lipschitz continuous Hessian” if its Hessian matrix ∇2g is α-Lipschitz continuous. In this paper, we mainly focus the problems under the “α-Lipschitz continuous” assumption, and our analysis can be also applied to these two variants via slight modifications.
We define the coreset for CnB learning problems below. Definition 2 (ε-coreset). Let ε > 0. Given a dataset X ⊂ X and the objective function f(θ,X), we say that a weighted set C ⊂ X is an ε-coreset of X if for any θ ∈ B(θ̃, ℓ), we have
|f(θ, C)− f(θ,X)| ≤ εf(θ,X). (3)
If C is an ε-coreset of X , we can run an existing optimization algorithm on C so as to obtain an approximate solution. Obviously, we expect that the size of C to be as small as possible. Following Definition 2, we also define the corresponding robust coreset (the similar definition was also introduced in [19, 26] before). Definition 3 (robust coreset). Let ε > 0, and β ∈ [0, 1). Given the dataset X ⊂ X and the objective function f(θ, x), we say that a weighted dataset C ⊂ X is a (β, ε)-robust coreset of X if for any θ ∈ B(θ̃, ℓ), we have
(1− ε)f(1+β)z(θ,X) ≤ fz(θ, C) ≤ (1 + ε)f(1−β)z(θ,X). (4)
Roughly speaking, if we obtain an approximate solution θ′ ∈ P on C, its quality can be preserved on the original input data X . The parameter β indicates the error on the number of outliers if using
θ′ as our solution on X . If we set β = 0, that means we allow no error on the number of outliers. In our full paper [44], we present our detailed discussion on the quality loss (in terms of the objective value and the number of outliers) of this transformation from C to X .
The rest of this paper is organized as follows. In Section 3, we introduce our robust coreset framework and show how to implement it in a fully-dynamic environment. In Section 4, we propose two different ordinary coreset (without outliers) construction methods for CnB learning problems, which can be used as the black box in our robust coreset framework of Section 3. Finally, in Section 5 we illustrate the application of our coreset method in practice. Due to the space limit, some proofs and the more detailed experimental results are placed in our full paper [44].

heading: 3 Our Robust Coreset Framework
text: We first consider the simple uniform sampling as the robust coreset in Section 3.1 (in this part, we consider the general learning problems without the CnB assumption). To improve the result, we further introduce our major contribution, the hybrid framework for robust coreset construction and its fully-dynamic realization in Section 3.2 and 3.3, respectively.

heading: 3.1 Uniform Sampling for General Case
text: As mentioned before, the existing robust coreset construction methods [19, 26] are based on uniform sampling. Note that their methods are only for the clustering problems (e.g., k-means/median clustering). Thus a natural question is that whether the uniform sampling idea also works for the general learning problems in the form of (1). Below we answer this question in the affirmative. To illustrate our idea, we need the following definition for range space. Definition 4 (f -induced range space). Suppose X is an arbitrary metric space. Given the cost function f(θ, x) as (1) over X , we let
R = { {x ∈ X : f(θ, x) ≤ r} | ∀r ≥ 0,∀θ ∈ P } , (5)
then (X ,R) is called the f -induced range space. Each R ∈ R is called a range of X .
The following “δ-sample” concept comes from the theory of VC dimension [32]. Given a range space (X ,R), let C and X be two finite subsets of X . Suppose δ ∈ (0, 1). We say C is a δ-sample of X if C ⊆ X and ∣∣∣∣ |X ∩R||X| − |C ∩R||C|
∣∣∣∣ ≤ δ for any R ∈ R. (6) Denote by vcdim the VC dimension of the range space of Definition 4, then we can achieve a δsample with probability 1 − η by uniformly sampling O( 1δ2 (vcdim + log 1 η )) points from X [32]. The value of vcdim depends on the function “f”. For example, if “f” is the loss function of logistic regression in Rd, then vcdim can be as large as Θ(d) [38]. The following theorem shows that a δsample can serve as a robust coreset if z is a constant factor of n. Note that in the following theorem, the objective f can be any function without following Definition 1. Theorem 1. Let (X, z) be an instance of the robust learning problem (2). If C is a δ-sample of X in the f -induced range space. We assign w(c) = n|C| for each c ∈ C. Then we have
fz+δn(θ,X) ≤ fz(θ, C) ≤ fz−δn(θ,X) (7)
for any θ ∈ P and any δ ∈ (0, z/n]. In particular, if δ = βz/n, C is a (β, 0)-robust coreset of X and the size of C is O( 1β2 ( n z ) 2(vcdim+ log 1η )).
Proof. Suppose the size of C is m and let N = nm. To prove Theorem 1, we imagine to generate two new sets as follows. For each point c ∈ C, we generate n copies; consequently we obtain a new set C ′ that actually is the union of n copies of C. Similarly, we generate a new set X ′ that is the union of m copies of X . Obviously, |C ′| = |X ′| = N . Below, we fix an arbitrary θ ∈ P and show that (7) is true.
We order the points of X ′ based on their objective values; namely, X ′ = {x′i | 1 ≤ i ≤ N} and f(θ, x′1) ≤ f(θ, x′2) ≤ · · · ≤ f(θ, x′N ). Similarly, we have C ′ = {c′i | 1 ≤ i ≤ N} and
f(θ, c′1) ≤ f(θ, c′2) ≤ · · · ≤ f(θ, c′N ). Then we claim that for any 1 ≤ i ≤ (1− δ)N , the following inequality holds: f(θ, c′i+δN ) ≥ f(θ, x′i). (8) Otherwise, there exists some i0 that f(θ, c′i0+δN ) < f(θ, x ′ i0 ). Consider the range R0 = {x ∈ X | f(θ, x) ≤ f(θ, c′i0+δN )}. Then we have
|C ∩R0| |C| = |C ′ ∩R0|/n |C| ≥ (i0 + δN)/n m = i0 N + δ; (9)
|X ∩R0| |X| = |X ′ ∩R0|/m |X| < i0/m n = i0 N . (10)
That is, ∣∣ |C∩R0|
|C| − |X∩R0| |X| ∣∣ > δ which is in contradiction with the fact that C is a δ-sample of X .
Thus (8) is true. As a consequence, we have
fz(θ, C) = n
m m−mn z∑ i=1 f(θ, ci) = 1 m N−mz∑ i=1 f(θ, c′i) ≥ 1 m N−mz∑ i=1+δN f(θ, c′i) (11)
≥︸︷︷︸ by (8) 1 m (1−δ)N−mz∑ i=1 f(θ, x′i) = (1−δ)n−z∑ i=1 f(θ, xi) = fz+δn(θ,X). (12)
So the left-hand side of (7) is true, and the right-hand side can be proved by using the similar manner.
Remark 2. Our proof is partly inspired by the ideas of [37, 35] for analyzing uniform sampling. Though the uniform sampling is simple and easy to implement, it has two major drawbacks. First, it always involves an error “δ” on the number of outliers (otherwise, if letting δ = 0, the sample should be the whole X). Also, the result is interesting only when z is a constant factor of n. For example, if z = √ n, the obtained sample size can be as large as n. Our hybrid robust framework proposed in Section 3.2 can resolve these two issues for CnB learning problems.

heading: 3.2 The Hybrid Framework for (β, ε)-Robust Coreset
text: Our idea for building the robust coreset comes from the following intuition. In an ideal scenario, if we know who are the inliers and who are the outliers, we can simply construct the coresets for them separately. In reality, though we cannot obtain such a clear classification, the CnB property (Definition 1) can guide us to obtain a “coarse” classification. Furthermore, together with some novel insights in geometry, we prove that such a hybrid framework can yield a (β, ε)-robust coreset.
Suppose ε ∈ (0, 1) and the objective f is continuous-and-bounded as Definition 1. Specifically, the parameter vector θ is always restricted within the ball B(θ̃, ℓ). First, we classify X into two parts according to the value of f(θ̃, x). Let ε0 := min { ε 16 , ε·infθ∈B(θ̃,ℓ) fz(θ,X) 16(n−z)αℓ } and z̃ := (1 + 1/ε0) z;
also assume xz̃ ∈ X is the point who has the z̃-th largest cost f(θ̃, x) among X . We let τ = f(θ̃, xz̃), and thus we obtain the set {x ∈ X | f(θ̃, x) ≥ τ}. (13) that has size z̃. We call these z̃ points as the “suspected outliers” (denoted as Xso) and the remaining n − z̃ points as the “suspected inliers” (denoted as Xsi). If we fix θ = θ̃, the set of the “suspected outliers” contains at least 1ε0 z real inliers (since z̃ = (1 + 1/ε0) z). This immediately implies the following inequality:
τz ≤ ε0fz(θ̃, X). (14)
Suppose we have an ordinary coreset construction method A as the black box (we will discuss it in Section 4). Our robust coreset construction is as follows:
We build an ε1-coreset (ε1 = ε/4) for Xsi by A and take a δ-sample for Xso with setting δ = βε01+ε0 . We denote these two sets as Csi and Cso respectively. If we set β = 0 (i.e., require no error on the number of outliers), we just directly take all the points of Xso as Cso. Finally, we return C = Csi ∪ Cso as the robust coreset.
Theorem 2. Given a CnB learning instance (X, z), the above coreset construction method returns a (β, ε)-robust coreset (as Defintion 3) of size
|Csi|+min { O ( 1
β2ε2 (vcdim+ log
1 η )
) , O ( z
ε0
)} (15)
with probability at least 1 − η. In particular, when β = 0, our coreset has no error on the number of outliers and its size is |Csi|+O ( z ε0 ) .
Proof. (sketch) It is easy to obtain the coreset size. So we only focus on proving the quality guarantee below.
Let θ be any parameter vector in the ball B(θ̃, ℓ). Similar with the aforementioned classification Xsi ∪ Xso, θ also yields a classification on X . Suppose τθ is the z-th largest value of {f(θ, x) | x ∈ X}. Then we use Xri to denote the set of n − z “real” inliers with respect to θ, i.e., {x ∈ X | f(θ, x) < τθ}; we also use Xro to denote the set of z “real” outliers with respect to θ, i.e., {x ∈ X | f(θ, x) ≥ τθ}. Overall, the input set X is partitioned into 4 parts:
XI = Xsi ∩Xri, XII = Xso ∩Xri, XIII = Xso ∩Xro, and XIV = Xsi ∩Xro. (16)
Similarly, θ also yields a classification on C to be Cri (the set of “real” inliers of C) and Cro (the set of “real” outliers of C). Therefore we have
CI = Csi ∩ Cri, CII = Cso ∩ Cri, CIII = Cso ∩ Cro, and CIV = Csi ∩ Cro. (17)
Our goal is to show that fz(θ, C) is a qualified approximation of fz(θ,X) (as Defintion 3). Note that fz(θ, C) = f(θ, CI ∪CII) = f(θ, CI)+ f(θ, CII). Hence we can bound f(θ, CI) and f(θ, CII) separately. We consider their upper bounds first, and the lower bounds can be derived by using the similar manner.
The upper bound of f(θ, CI) directly comes from the definition of ε-coreset, i.e., f(θ, CI) ≤ f(θ, CI ∪ CIV) ≤ (1 + ε1)f(θ,XI ∪XIV) since CI ∪ CIV is an ε1-coreset of XI ∪XIV. It is more complicated to derive the upper bound of f(θ, CII). We consider two cases. (1) If CIV = ∅, then we know that all the suspected inliers of C are all real inliers (and meanwhile, all the real outliers of C are suspected outliers); consequently, we have
f(θ, CII) ≤ fz(θ, CII ∪ CIII) ≤ f(1−β)z(θ,XII ∪XIII) (18)
from Theorem 1. (2) If CIV ̸= ∅, by using the triangle inequality and the α-Lipschitz assumption, we have f(θ, CII) ≤ f(θ,XII) + 2z(τ + αℓ)). We merge these two cases and overall obtain the following upper bound:
fz(θ, C) ≤ (1 + ε1)f(1−β)z(θ,X) + 4zτ + 4zαℓ. (19)
Moreover, from (14) and the α-Lipschitz assumption, we have τz ≤ ε0fz(θ,X) + ε0(n − z)αℓ. Then the above (19) implies
fz(θ, C) ≤ (1 + ε)f(1−β)z(θ,X). (20)
Similarly, we can obtain the lower bound
fz(θ, C) ≥ (1− ε)f(1+β)z(θ,X). (21)
Therefore C is a (β, ε)-robust coreset of X .

heading: 3.3 The Fully-Dynamic Implementation
text: In this section, we show that our robust coreset of Section 3.2 can be efficiently implemented in a fully-dynamic environment, even if the number of outliers z is dynamically changed.
The standard ε-coreset usually has two important properties. If C1 and C2 are respectively the εcoresets of two disjoint sets X1 and X2, their union C1∪C2 should be an ε-coreset of X1∪X2. Also, if C1 is an ε1-coreset of C2 and C2 is an ε2-coreset of C3, C1 should be an (ε1 + ε2 + ε1ε2)-coreset of C3. Based on these two properties, one can build a coreset for incremental data stream by using
the “merge-and-reduce” technique [4, 23]. Very recently, Henzinger and Kale [24] extended it to the more general fully-dynamic setting, where data items can be deleted and updated as well.
Roughly speaking, the merge-and-reduce technique uses a sequence of “buckets” to maintain the coreset for the input streaming data, and the buckets are merged by a bottom-up manner. However, it is challenging to directly adapt this strategy to the case with outliers, because we cannot determine the number of outliers in each bucket. A cute aspect of our hybrid robust coreset framework is that we can easily resolve this obstacle by using an O(n) size auxiliary table L together with the mergeand-reduce technique (note that even for the case without outliers, maintaining a fully-dynamic coreset already needs Ω(n) space [24]). We briefly introduce our idea below.
Recall that we partition the input data X into two parts: the n − z̃ “suspected inliers” and the z̃ “suspected outliers”, where z̃ = (1 + 1/ε0)z. We follow the same notations used in Section 3.2. For the first part, we just apply the vanilla merge-and-reduce technique to obtain a fully-dynamic coreset Csi; for the other part, we can just take a δ-sample or take the whole set (if we require β to be 0), and denote it as Cso. Moreover, we maintain a table L to record the key values x.value = f(θ̃, x) and its position x.position in the merge-andreduce tree, for each x ∈ X; they are sorted by the x.values in the table. To deal with the dynamic updates (e.g., deletion and insertion), we also maintain a critical pointer p pointing to the
data item xz̃ (recall xz̃ has the z̃-th largest cost f(θ̃, x) among X defined in Section 3.2).
When a new data item x is coming or an existing data item x is going to be deleted, we just need to compare it with f(θ̃, xc) so as to decide to update Csi or Cso accordingly; after the update, we also need to update xz̃ and the pointer p in L . If the number of outliers z is changed, we just need to update xz̃ and p first, and then update Csi and Cso (for example, if z is increased, we just need to delete some items from Cso and insert some items to Csi). To realize these updating operations, we also set one bucket as the “hot bucket”, which serves as a shuttle to execute all the data shifts. See Figure 1 for the illustration. Let M(ε) be the size of the vanilla ε-coreset. In order to achieve an ε-coreset overall, we need to construct an εlogn -coreset with size M(ε/ log n) in every reduce part [1]. We use M to denote M(ε/ log n) for short and assume that we can compute a coreset of X in time t(|X|) [40], then we have the following result. Theorem 3. In our dynamic implementation, the time complexity for insertion and deletion is O(t(M) log n). To update z to z ± ∆z with ∆z ≥ 0, the time complexity is O(∆zε t(M) log n), where ε is the error bound for the robust coreset in Definition 3.

heading: 4 Coreset for Continuous-and-Bounded Learning Problems
text: As mentioned in Section 3.2, we need a black-box ordinary coreset (without considering outliers) construction method A in the hybrid robust coreset framework. In this section, we provide two different ε-coreset construction methods for the CnB learning problems.

heading: 4.1 Importance Sampling Based Coreset Construction
text: We follow the importance sampling based approach [30]. Suppose X = {x1, · · · , xn}. For each data point xi, it has a sensitivity σi = supθ f(θ,x) f(θ,X) that measures its importance to the whole input data X . Computing the sensitivity is often challenging but an upper bound of the sensitivity actually is already sufficient for the coreset construction. Assume si is an upper bound of σi and let S =∑n
i=1 si. The coreset construction is as follows. We sample a subset C from X , where each element of C is sampled i.i.d. with probability pi = si/S; we assign a weight wi = Ssi|C| to each sampled data item xi of C. Finally, we return C as the coreset.
Theorem 4 ([7]). Let vcdim be the VC dimension (or shattering dimension) of the range space induced from f(θ, x). If the size of C is Θ ( S ε2 ( vcdim · logS + log 1η )) , then C is an ε-coreset with probability at least 1− η.
Therefore the only remaining issue is how to compute the upper bounds sis. Recall that we assume our cost function is α-Lipschitz (or α-smooth, α-Lipschitz continuous Hessian) in Definition 1. That is, we can bound the difference between f(θ, xi) and f(θ̃, xi), and such a bound can help us to compute si. In our full paper [44], we show that computing si is equivalent to solving a quadratic fractional programming. This programming can be reduced to a semi-definite programming (SDP) [3], which can be solved in polynomial time up to any desired accuracy [22]. We denote the solving time of SDP by T(d), where d is the dimension of the data point. So the total running time of the coreset construction is O(n · T(d)). A drawback of Theorem 4 is that the coreset size depends on vcdim induced by f(θ, x). For some objectives, the value vcdim can be very large or difficult to obtain. Here, we prove that for a continuous-and-bounded cost function, the coreset size can be independent of vcdim; instead, it depends on the doubling dimension ddim [9] of the parameter space P . Doubling dimension is a widely used measure to describe the growth rate of the data, which can also be viewed as a generalization of the Euclidean dimension. For example, the doubling dimension of a d-dimensional Euclidean space is Θ(d).
Theorem 5. Given a CnB learning instance X with the objective function f(θ,X) as described in Definition 1, let ddim be the doubling dimension of the parameter space. Then, if we run the importance sampling based coreset construction method with the sample size |C| = Θ ( S2
ε2 ( ddim · log 1ε + log 1 η )) , C will be an ε-coreset with probability 1 − η. The hidden con-
stant of |C| depends on the Lipschitz constant α and infθ∈B(θ̃,ℓ) 1 nf(θ,X) 3.
The major advantage of Theorem 5 over Theorem 4 is that we do not need to know the VC dimension induced by the cost function. On the other hand, the doubling dimension is often much easier to know (or estimate), e.g., the doubling dimension of a given instance in Rd is just Θ(d), even the cost function can be very complicated. Another motivation of Theorem 5 is from sparse optimization. Let the parameter space be RD, and we restrict θ to be k-sparse (i.e., at most k non-zero entries with k ≪ D). It is easy to see the domain of θ is a union of ( D k ) k-dimensional subspaces, and thus its doubling dimension is O(k logD) which is much smaller than D (each ball of radius r in the domain can be covered by ( D k ) · 2O(k) = 2O(k logD) balls of radius r/2).
The reader is also referred to [26] for a more detailed discussion on the relation between VC (shattering) dimension and doubling dimension.

heading: 4.2 Spatial Partition Based Coreset Construction
text: The reader may realize that the coreset size presented in Theorem 5 (and also Theorem 4) is datadependent. That is, the coreset size depends on the value S, which can be different for different input instances. To achieve a data-independent coreset size, we introduce the following method based on spatial partition, which is partly inspired by the previous k-median/means clustering coreset construction idea of [15, 17, 25]. We generalize their method to the continuous-and-bounded learning problems and call it as Generalized Spatial Partition (GSP) method.
GSP coreset construction. We set ϱ = minx∈X f(θ̃, x) and T = 1|X|f(θ̃, X). Then, we partition all the data points to different layers according to their cost with respect to θ̃. Specifically, we assign a point x to the 0-th layer if f(θ̃, x)−ϱ < T ; otherwise, we assign it to the ⌊log( f(θ̃,x)−ϱT )⌋-th layer. Let L be the number of layers, and it is easy to see L is at most log n + 1. For any 0 ≤ j ≤ L, we denote the set of points falling in the j-th layer as Xj . From each Xj , we take a small sample Cj uniformly at random, where each point of Cj is assigned the weight |Xj |/|Cj |. Finally, the union set ⋃L j=0 Cj form our final coreset.
3In practice, we often add a positive penalty item to the objective function for regularization, so we can assume that infθ∈B(θ̃,ℓ) 1 n f(θ,X) is not too small.
Theorem 6. Given a CnB learning instance X with the objective function f(θ,X) as described in Definition 1, let ddim be the doubling dimension of the parameter space. The above coreset construction method GSP can achieve an ε-coreset of size Θ ( logn ε2 ( ddim · log 1ε + log 1 η )) in linear time. The hidden constant of |C| depends on the Lipschitz constant α and infθ∈B(θ̃,ℓ) 1 nf(θ,X).
To prove Theorem 6, the key is show that each Cj can well represent the layer Xj with respect to any θ in the bounded region B(θ̃, ℓ). First, we use the continuity property to bound the difference between f(θ, x) and f(θ̃, x) for each x ∈ Xj with a fixed θ; then, together with the doubling dimension, we can generalize this bound to any θ in the bounded region.

heading: 5 Experiments
text: In this section, we illustrate the application of our proposed robust coreset method in machine learning. We leave the more detailed experimental results to the full version of this paper [44].
Logistic regression (with outliers). Given x, θ ∈ Rd and y ∈ {±1}, the loss function of Logistic regression is
f(θ, x) = ln(1 + exp(−y · ⟨θ, x⟩)). (22)
k-median/means clustering (with outliers). The goal is to find k cluster centers Cen = {c1, c2, · · · , ck} ⊂ Rd; the cost function of k-median (resp. k-means) clustering for each x ∈ Rd is f(Cen, x) = minci∈Cen d(ci, x) (resp. d(ci, x)
2), where d(ci, x) denotes the Euclidean distance between ci and x.
All the algorithms were implemented in Python on a PC with 2.3GHz Intel Core i7 CPU and 32GB of RAM. All the results were averaged across 5 trials.
The algorithms. We use the following three representative coreset construction methods as the black box in our hybrid framework for outliers. (1) UNIFORM: the simple uniform sampling method; (2) GSP: the generalized spatial partition method proposed in section 4.2; (3) QR: a QR-decomposition based importance sampling method proposed by [38] for logistic regression. For each coreset method name, we add a suffix “+” to denote the corresponding robust coreset enhanced by our hybrid framework proposed in section 3.
For many optimization with outliers problems, a commonly used strategy is alternating minimization (e.g., [12]). In each iteration, it detects the z outliers with the largest losses and run an existing algorithm (for ordinary logistic regression or k-means clustering) on the remaining n − z points; then updates the z outliers based on the obtained new solution. The algorithm repeats this strategy until the solution is stable. For logistic regression with outliers, we run the codes from the scikitlearn package4 together with the alternating minimization. For k-means with outliers, we use the local search method [21] to seed initial centers and then run the k-means-- algorithm [12]. We apply these algorithms on our obtained coresets. To obtain the initial solution θ̃, we just simply run the algorithm on a small sample (less than 1%) from the input data.
Datasets. We consider the following two real datasets in our experiments. The dataset Covetype [6] consists of 581012 instances with 54 cartographic features for predicting forest cover type. There are 7 cover types and we set the dominant one (49%) to be the positive samples and the others to be negative samples. We randomly take 10000 points as the test set and the remaining data points form the training set. The dataset 3Dspatial [29] comprises 434874 instances with 4 features for the road information. To generate outliers for the unsupervised learning task k-means clustering, we randomly generate 10000 points in the space as the outliers, and add the gaussian noisy N (0, 200) to each dimension for these outliers. For the supervised learning task logistic regression, we add Gaussian noise to a set of randomly selected 10000 points (as the outliers) from the data and also randomly shuffle their labels.
Results. Table 1 and Table 2 illustrate the loss ratio (the obtained loss over the loss without using coreset) and speed-up ratio of different robust coreset methods. We can see that the robust coreset methods can achieve significant speed-up, and meanwhile the optimization qualities can be well preserved (their loss ratios are very close to 1). Figure 2(a) and 2(b) illustrate the performance
4https://scikit-learn.org/stable/
Table 1: Logistic regression on Covetype. |C| denotes the coreset size.
Table 2: k-means clustering on 3Dspatial with k = 10. |C| denotes the coreset size.
of the (robust) coreset methods with varying the coreset size. In general, our robust coreset can achieve better performance (in terms of the loss and accuracy) compared with its counterpart without considering outliers. Figure 2(c) illustrates the speed-up ratio of running time in the dynamic setting. Our robust coreset construction uses the merge-and-reduce tree method. When the update happens in one bucket, we perform a “bottom-up” re-construction for the coreset. We let the bucket size be n/2h−1, where h is the height of the tree; thus the higher the tree, the smaller the bucket size (and the speed-up is more significant). The results reveal that using the coreset yields considerable speed-up compared to re-running the algorithm on the entire updated dataset.

heading: 6 Conclusion
text: In this paper, we propose a novel robust coreset framework for the continuous-and-bounded learning problems (with outliers). Also, our framework can be efficiently implemented in the dynamic setting. In future, we can consider generalizing our proposed (dynamic) robust coreset method to other types of optimization problems (e.g., privacy-preserving and fairness); it is also interesting to consider implementing our method for distributed computing or federated learning.

heading: Acknowledgment
text: We would like to thank the anonymous reviewers for their helpful suggestions and comments.

Review summaries:
The goal of this paper is to investigate a coreset approach for robust supervised learning specifically with outliers. The authors study this for logistic regression and k-means clustering. This paper is mainly theoretical and the empirical results are mainly in the appendix.

This paper presents an approach for constructing outlier-resilient coresets for continuous-and-bounded learning problems, which include logistic regression and k-means clustering. The authors build on recent work in dynamic coresets so that the constructions can be maintained in a fully-dynamic setting where input points can be inserted, deleted, and updated. The main idea of the outlier-resistant approach is to partition the original data set into two sets: one consisting of suspected outliers and the other for the “inliers.” For the outliers, the authors sample uniformly at random, and for the inliers, an existing coreset construction is used; these two subsamples are then merged to generate the outlier-resistant coreset. Under the assumptions of continuous and bounded learning, the authors also outline general QP-based and spatial-partition based methods to construct coresets.

This paper studies coresets for continuous-and-bounded learning problems. In the optimization version of the problem, given a weighted input data set X with weight w : X \to \mathbb{R}_+, the goal is to find a parameter \theta in some parameter space P such that \sum_{x \in X} w(x) \cdot f(\theta, x) is minimized where f : P \times X \to \mathbb{R}_+ is a cost function. Furthermore, the continuous-and-boundedness condition requires that the parameter space P form a metric space (so there is an implicit associated distance function on the parameters), and that a) there exist l, \alpha > 0, such that all parameters in P are contained in a ball of radius l, and b) f(\cdot, x) is \alpha-Lipschitz.  An \epsilon-coreset for this problem is defined as a weighted subset S \subseteq X of the data set with weight u : S \to \mathbb{R}_+, such that for every parameter \theta \in P, the total cost on S is close to that on X, i.e., \sum_{x \in S} u(x) \cdot f(\theta, x) \in (1 \pm \epsilon) \sum_{x \in X} w(x) \cdot f(\theta, x).   The paper also studies coresets for the outlier version of the problem, where we are additionally given a parameter z (the number of outliers) and the cost becomes f_z(\theta, X) = \min_{O \subset X, |O| = z} f(\theta, X \setminus O). Coresets are defined similarly for the outlier version, except that this paper allows bi-criteria guarantee: a (\beta, \epsilon)-coreset preserves the cost for every \theta, such that the cost is within [f_{(1+\beta)z}(\theta, X), f_{(1-\beta)z}(\theta,X)] (the exact definition is subject to proper normalization).  Several results are presented. For the outlier version, the first result shows that uniform sampling yields a (\beta, 0)-coreset of size \tilde{O}(n / (\beta z))^2, provided that the VC-dimension for the (metric ball) range space induced by {f(\cdot, x) : x} is bounded. This result is weak and is inadequate for small z (even for moderately small z = O(\sqrt{n})). The second result is more interesting and it gives a reduction that reduces the outlier version to the non-outlier version. Intuitively, it “glues” a black-box coreset for the non-outlier version and a uniform sampling based coreset. Specifically, it yields a (\beta, \epsilon) coreset of size T + min{ O((\beta\epsilon)^{-2} vcdim), O(z / epsilon)}, where T is the size of some \epsilon-coreset in the non-outlier setting, and vcdim is the VC-dimension for the range space induced by {f(\cdot, x) : x}. The paper also gives a fully-dynamic algorithm that maintains the “glued” coreset.  Besides, two coreset results for the non-outlier version are presented. The first one is based on the well-known importance sampling framework [11], but instead of analyzing the VC-dimension of the range space, this paper shows that the VC-dimension term could be replaced by the doubling dimension of the parameter space P. However, the authors were not able to give an upper bound for the total sensitivity, and therefore this first result does not yield an explicit coreset size bound. Then the other result is based on a spatial partition method proposed in [9], which helps to gets rid of the total sensitivity bound, but it introduces a log n factor.