Robust and Fully-Dynamic Coreset for Continuous-and-Bounded Learning (With Outliers) Problems
Authors: Zixiu Wang
Yiwen Guo
Hu Ding
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: coreset
Continuous-and-Bounded learning
outliers
dynamic setting

Abstract: In many machine learning tasks, a common approach for dealing with large-scale data is to build a small summary, {\em 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 {\em continuous-and-bounded learning} problems (with outliers) which includes a broad range of popular optimization objectives in machine learning, {\em e.g.,} logistic regression and $ k $-means clustering. Moreover, our robust coreset  can be efficiently maintained in fully-dynamic 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.

Robust and Fully-Dynamic Coreset for Continuous-and-Boundee Learning (With Outliers) Problems
Zixiu Wang Yiwen Guo
Hu Ding-
School Computer Science and Technology.
University of Science and Technology of China
"ByteDance Lab
wzx20140mail. www.emmmaaa.......emmmmmmmmmeeet ustc. edu..eedduceco en, guoyiven880gmail.com com, hudingoustc.edi edu,
Abstract
In many machine learning tasks, a common approach for dealing with large-scale data is to build small summary, e.g., coreset, that efficiently represent the original input. However, real-world datasets usually contain outliers and most ex- isting coreset construction methods not resilient against outliers (in particular, an outlier can be located arbitrarily in the space by an adversarial attacker). In this paper, propose novel robust coreset method for the continuous-and-ouundd learning problems (with outliers) which includes a broad range of popular op- timization objectives in machine learning, e.g., logistic regression and k-means clustering. Moreover, our robust coreset can be efficiently maintained in fully- dynamic environment. To the best of our knowledge, this is the first robust and fully-dynamic coreset construction method for these optimization problems. An- other 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 exper- iments on real-world datasets to evaluate the effectiveness of our proposed robust coreset method.
Introduction
As the rapid increasing of data volume in this big data era, often need develop low-complexity (e.g.. linear or even sublinear) algorithms for machine learning tasks. Moreover, our dataset is often maintained in dynamic environment so that we have 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 be deleted due to the reason of privacy preserving. Obvi- ously, 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 to construct a small-sized summary of the training data so that we can existing algorithms
the summary rather than whole data. Coreset [18], which was originally studied the community computational geometry [1], has become widely used data summary for many large-scale machine learning prob- lems [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 be applied in the environ- ment like distributed computing [28]. Also, 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.
I Correspondiig author.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

However, the existing coreset construction methods are still far from being satisfactory in practice. major bottleneck 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 single outlier can significantly destroy the final machine learning result. typical exam- ple 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, 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 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; how- ever, it tends to assign high sensitivities to the points who are far from the majority of the data, that is, an outlier likely to have 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 ro- bust coreset. The existing robust coreset construction methods [19, 26] often rely 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.
1.1 Our Contributions
In this paper, we propose a unified fully-dynamic robust coreset framework for a class of opti- mization problems which is termed santinuouu-and-buunddd (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 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 ordi- nary coreset construction method A for the given CnB optimization objective (without considering outliers). Our key idea 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 A. For the "suspected" inliers, we run the method A (as a black box); for the "suspected" out- liers, we directly take a small sample uniformly at random; finally, we prove that these two parts together yield robust coreset. Our framework can be also efficiently implemented under the merge- and-reduce framework for dynamic setting (though the original merge- andge-anddreduce 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- 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
el al. [16], but their
discovery [31]. It is worth noting that although some coreset construction methods for them have

---

been proposed before (e.g.. [33, 38, 43, 25)), they are all croblem-dependee and we are the first, to the best of our knowledge, to study them from a unified "CnB" perspective.
2 Preliminaries
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 E X has a weight w(x) 2 0. Further, we use (X, 2) to denote given instance X with 2 outliers. We always use |.1 and [-] respectively to denote the number of data items and the total weight of given data
set. We consider the learning problem whose objective function is the weighted sum of the cost over X, i.e.
f(0. = Σ w(x)f(0,x), ZEX
(1)
where f(0, .²) is the non-negative cost contributed by z with the parameter vector P. The goal is to find an appropriate 9 so that the objective function f(0, X)) is minimized. Usually we assume straightforward to extend our method to
each x E X has unit weight (i.e., w(xx) = 1), and weighted case. Given the pre-specified number E Z+ of outliers in X (for weighted case, "2" refers to the total weight of outliers), we then define the "robust" objective function:
f2 X)
min OcX,[o]=
((O)
Actually, the above definition (2) comes from the popular "trimming" idea [39] that has been widely used for robust optimization problems.
learning problem. A function g : P + R is a- Lipschitzz continuous for any 61,0, E P. Ig(01) g(B2) S al|A@]]. where AO = 0, O2 and
Below we present the formal definition of comtinuous-and-
is some specified norm in P.
Definition 1 (Coniinous-aud-Boundd)
(CnB) Learning [41]). Let a, L > O and θ E P. Denote by B(O,E) E) the ball centered at á with radius & in the parameter space P. An objective (1) called a CnB learning problem with the parameters (ar, E, 0) if (i) the loss function f(;xx)) a-Lipschitz continuous for any x E X, and (ii) f is always restricted within B(8, E).
We can also consider other variants for CnB learning with replacing the "a-Lipschitz continuous" assumption. For example, a differentiable function g is "a-Lipschitz continuous gra- dient" if gradient V is a-Lipschitz continuous (it is also called "aassmoth"") Similarly, function g is "a--ipschitz continuous Hessian" " if its Hessian matrix V²g g is a-Lipschitz continuous. in this paper, we mainly focus the problems under the "a-Lipschitz continu- ous" assumption, and our analysis can be also applied to these two variants via slight modifications.
Remark 1.
We define the coreset for CnB learning problems below.
Definition (E (e-corese)). Let E > O. Given dataset X C X and the objective function f(0, X), we say that a weighted set C C. X is an e-coreset of X for any 0 E B(0,)), E), we have
I5(0,C) (o0,))--OO,X00 (() < (),
If C is an E-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 be as small as possible. Follow- ing 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 E [0, 1). Given the dataset X C X and the objective function f00 x), we say that a weighted dataset C C X is a (3, r)obuut coreset of X for any 0 E (00 f), we have
(1- (1- (x) (1 < (1
(4)
Roughly speaking, if we obtain an approximate solution E P on C, its quality can preserved on the original input data X. The parameter /3 indicates the error the number of outliers if using
3

---

0' as our solution on X. If we set 3 = 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
robust coreset framework and show how to implement it in 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 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].
follows. In Section 3, we introduce
3 Our Robust Coreset Framework
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.
3.1 Uniform Sampling for General Case
As mentioned before, the existing robust coreset construction methods [19, 26] are based on uni- form sampling. Note that their methods are only for the clustering problems (e.g., k-means/median clustering). Thus a natural question 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 arbitrary metric space. Given the cost function f(0, x) as (1) over X, we let
R R= = ( [ 2) 20 10,,0,0))))
(5)
then (X, R) is called the f-induced range space. Each R is called a range of X.
The following "O-sample" concept comes from the theory of VC dimension [32]. Given range space (X, RR, let C' and X be two finite subsets of X. Suppose 8 E (0, 1). We say C/ is a 8-sample of X if C C and
XOO X
|CnR| |C|
< for any RR.
Denote by vcdim the VC dimension of the range space of Definition 4, then can achieve 8- sample with probability 1 - 77 by uniformly sampling O (vedim + log 7,)) points from X [32]. The value of vedim depends on the function "f" For example, if "f" is the loss function of logistic regression in IRd, then vcdim sample can serve as a robust coreset if is a constant factor of n. Note that in the following theorem, the objective f can be any function without following Definition
be as large as (d) (38]. The following theorem shows that 8-
Theorem 1. Let (X, 2) be instance of the robust learning problem (2). If C is 5-sample of X in the f-induced range space. We assign wle w(c)= = তट for each c E C. Then we have
Jz+8n (0, X) S (= S f2 f=,6n(0,
(7)
for any P and any â E (0, z/n]. In particular, if 6 = Bz/n, C is a (3,0)-robust coreset of X and the size of C is O ( + log 4))
Proof. Suppose the size of C' is and let N = nm. To prove Theorem I, we imagine generate two new sets as follows. For each point E C, we generate n copies; consequently we obtain a new set C' that actually is the union of copies of C. Similarly, we generate
set X' that is the union of m copies of X. Obviously, [C"| X' = N. Below, we fix an arbitrary 9 E P and show
that (7) is true.
We order the points of X' based on their objective values; namely, X' {a/
S Sis N)
and 2(0,21) & f(0, z4)) < f(0, 2'x). Similarly, we have C" {c/ < i N) and

---

( 5 f(0,c() ... . f(0,dy) dy). Then we claim that for any 1 1 (1 - 8)N, the following
inequality holds:
S(0, [(0,4+8)) 2 x()
(8)
Otherwise, there exists some to that f(0, c (0+5N) f(0, s/o)) Consider the range Ra fa X f(0,z) S f(0, c +oN)}. Then have
IC n Rol
IC' n Rol/n
(No + +NN/nn + 6;
in
(9)
|C|
|C|
m N
X n Rol
XX' n Rol/m
fo/m in N
(10)
[
X
That is, |CnRl
8 which is in contradiction with the fact that C' is 8-sample of X.
[X]
Thus (8) is true. As a consequence, we have
1 N-ms ms
N N--re ms Σ
fz(0,C)
f(0,c,)
Σ
f(0,c))
f(0,c)
(11)
m
m
m
8)N
(1-8)a-2
1(0, =
E
1(0,
10, X).
(12)
m
by (8)
So the left- 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, always involves an error "8" on the number of outliers (otherwise, if letting 8 O, the sample should be the whole X). Also, the result is interesting only when z is constant factor of n. For example, if = vn, the obtained sample size can be as large as n. Our hybrid robust frumework proposed in Section 3.2 can resolve these two issues for CnB learning problems.
3.2 The Hybrid Framework for (B,s)-Robus, Coreset
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 hybrid framework can yield (B, --robust coreset.
Suppose = E (0, 1) and the objective f is continuous bounded as Definition 1. Specifically, the parameter vector 0 is always restricted within the ball (B E). First, we classify X into two parts according to the value f(,, xr). Let 6p == min { [ e e-inf /=(8,X) and ă := (1 + 1/E0) 2;
16 16(n-zjae
also assume 2g X is the point who has the 2-th largest cost f(θ, x) among X. We let f(, xz). and thus we obtain the set
{Jr X [(Ō, 2 7).
(13)
that has size غ. We call these points as the "suspected outliers" (denoted as Xęo) and the remaining n points as the "suspected inliers" (denoted as Xg1). we fix 0 = 8, the set the "suspected outliers" contains at least 1 real inliers (since 2 = (1 + 1/Eo) 2). This immediately implies the following inequality:
80
Tz S (0,
(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:
build an corcees (E1 e/4) for Xas by A and take a 8-sample for Xao with setting 8 I+ce We denote these two sets as Cas and Cao respectively. If we set 3 (i.e., require no error on the number of outliers), we just directly take all the points of Xao as Cas. Finally, we return
BEa
C' C.. U Coo as the robust coreset.
5

---

Theorem 2. Given a CnB learning instance (X,2), the above coreset construction method returns (B.bust coreset (as Defintion 3) size
|Casl + min {o ( 1
(vedim log 17 )))
Eo 2
(15)
32E2
with probability at least 1 - n)- In particular, when 0, coreset has the number of outliers and its size is [Ceal + O
Proof. (sketch) It is easy to obtain the coreset size. So we only focus on proving the quality guar- antee below.
Let be any parameter vector in the ball B(0 E). Similar with the aforementioned classification
Xei U X also yields a classification on X. Suppose To is the 2-th largest value of { x) E X]. Then we use Xys denote the set of n 2 "real" inliers with respect to 6, ie.. {a
X f(0, x) < Tol: we also use Xro to denote the set of "real" outliers with respect to 8, i.e.
{a E X f00 2) 2 To}. Overall, the input
is partitioned into 4 parts:
Xeo n Xxo. and XIv Xa1 Xro = X.i n Xri, X11 Xeo n Xxs, XII
(16)
Similarly, 0 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 have
Ci Cas O Cri. Cu1 = C. n Cri. Cuu = C.o n Cro, and Civ = C.i n Cro-
(17)
Our goal is show that f=(0, is a qualified approximation of fz (0. (as Defintion 3). Note that (0, C) S(0, Un) = f(0 Gi) + 1(0, Cnr). Hence we can bound s(0, Ct) and s(0, Cn) separately. We consider their upper bounds first, and the lower bounds can be derived by using the similar manner.
The upper bound of f(0, Ct) directly comes from the definition of s-coreset, i.e., f(0, Ci) s f(0, G C s (1 + f X1 U Xiv) since Ci U Crv is an si-coreset of X1 U
It is more complicated to derive the upper bound of (8, C1).. We consider two cases. (1) If Ciy 0. then we know that all the suspected inliers of C are all real inliers (and meanwhile, all the real have
outliers of C' are suspected outliers); consequently,
f1) S (0, Cn U Cm)) S (0, Xn U Xmn)
(18)
from Theorem 1. (2) If Civ * 0. by using the triangle inequality and the a-Lipschitz assumption, we have f00, Cn) S f(, Xn) + 22(T + at)). We merge these two cases and overall obtain the following upper bound:
fz C) = (1 + (6, + 427 + 42al.
(19)
Moreover, from (14) and the a-L assumption, we have T= S 60/z X) + co(n - z)af.
Then the above (19) implies
(0, < (1+)))))))))
(20)
Similarly, we can obtain the lower bound
f0 C) 2 (1 (0,
(21)
Therefore C is a (3,e)-robust coreset of X.
3.3 The Fully-Dynamic Implementation
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 2 is dynamically changed.
The standard e-coreset usually has two important properties. coresets of two disjoint sets X, and X2, their union C₁ UC2 should be e-coreset of X UX2. Also, C1 is an coreestt of C2 and C2 is an e2-coreset of Ca. C1 should be an (e1 + 62 + Ecorese of C3. Based on these two properties, one can build coreset for incremental data stream by using
C₁ and C2 are respectively the e-

---

the "oerge-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 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 that we can easily resolve this obstacle by using an (n) size auxiliary table L together with the merge- and-reduce technique (note that even for the case without outliers, maintaining a fully-dynamic coreset already needs (2(n)) space [24)). We briefly introduce our idea below.
Recall that partition the input data X into two parts: the n - 2 "suspected inliers" and the & "suspected outliers", where Σ (1 1 1/20)2. We follow the same notations used in Section 3.2. For the first part, we just apply the vanilla merge-and-reduce technique to ob- tain a fully-dynamic coreset Cas for the other part, we can just take a Ó-sample or take the whole set (if we require 3 be 0), and denote it as Czo. Moreover, we maintain a table L to record the key values v.luuue = f(0, x) and its position r.posi tion in the merge-and- reduce tree, for each a E X; they are sorted by the r. vasus in the table. To deal with the dy-
suspected inliers
f increesingg
suspected outleers
eritical peinter
namic updates (e.g., g., deletion and insertion), we also maintain a critical pointer p pointing to the data item 2g (recall rg has the ž-th largest cost s(0, .)) among X defined in Section 3.2).
Figure 1: robust coreset construction.
The illustration for our fully-dynamic
When a new data item coming or an existing data item æ is going to be deleted, we just need to compare it with f(0,xx) so as to decide to update Css or C.o accordingly; after the update, we also need to update Z3 and the pointer in L. If the number of outliers 2 is changed, we just need to update 23 and p first, and then update C.i and C.o (for example, if is increased, we just need to delete some items from C.o and insert some items to C. 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 (x) be the size of the vanilla e-coreset. In order to achieve an e-coreset overall, we need to construct an log -coreset with size (s/ log n) in every reduce part [1]. We use M to denote (s/ log n) for short and assume that we can compute a coreset of X in time t(Ix]) [40], then we have the following result.
Theorem In our dynamic implementation, the time complexity for insertion and deletion is ((t(M) log To update to 2 + A with A 2 0, the time complexity is O ( log n), where& E the error bound for the robust coreset in Definition
4 Coreset for Continuous-and
Learning Problems
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 s-coreset construction methods for the CnB learning problems.
4.1 Importance Sampling Based Coreset Construction
We follow the importance sampling based approach [30]. Suppose X (x1,..., ,I,). For each data point I;, it has a sensitivity a, = supa TØ.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 8; is an upper bound of a; and let S En 84. The coreset construction is as follows. We sample a subset C from X, where each element of C is sampled i..dd with probability P; = stS; we assign a weight w; data item 24 of C. Finally, we return C' as the coreset.
f(0.z)
-s to each sampled .
7

---

Theorem 4 ((7)). Let vedim be the VC dimension (or shattering dimension) of the range space induced from f(0,z) x). If the size of C is (vedim log + log 1 then C' is an E-coreset with probability at least 1- 77-
Therefore the only remaining issue is how to compute the upper bounds s,8. Recall that we assume our cost function is a-Lipschitz (or a-smooth, a-Lipschitz continuous Hessian) in Definition That is, we can bound the difference between (0, and [0, .z), and such a bound can help us to com- pute sq- In our full paper [44], we show that computing s; is equivalent to solving quadratic frac- tional programming. This programming can be reduced to a cemi-defintte programming (SDP) [3], which can be solved in polynomial time up to any desired accuracy [22]. We denote the solving time of SDP by Tdd), where d is the dimension of the data point. So the total running time of the coreset construction is On [(d)).
drawback of Theorem 4 that the coreset size depends on vedim induced by f(8,2). 2). For some objectives, the value vedim can be very large or difficult to obtain. Here, we prove that for continuous-and-bouite
cost function, the coreset size can be independent of vedim; instead, depends on the doubling dimension ddim [9] of the parameter space P. Doubling dimension is widely used mcasure to describe the growth rate of the data, which can also be viewed as a gen- eralization of the Euclidean dimension. For example, the doubling dimension of a d-dimensional Euclidean space is (dd).
Theorem 5. Given a CnB learning instance X with the objective function f(0, X) as described in Definition 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] =
(ddim log + log t)). C will be an s-coreset with probability 1 1. The hidden con- 1 stant of [C) depends on the Lipschitz constant a and anf inf ven(o.)) n f0,
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 often much easier to know (or estimate), e.g., the doubling dimension of a given instance in Ed is just (dd,, even the cost function can be very complicated. Another motivation of Theorem is from sparse optimization. Let the parameter space be RD, and restrict 0 to be k-sparse (i.e., at most k non-zero entries with & < D). It is easy to see the domain of 0 is union of (P) k-dimensional subspaces, and thus its doubling dimension is O(k log D) which is much smaller than D (each ball of radius r in the domain can be covered by (2) 20(k) 20 log D) balls of radius r/2).
The reader is also referred to [26] for more detailed discussion on the relation between VC (shat- tering) dimension and doubling dimension.
4.2 Spatial Partition Based Coreset Construction
The reader may realize that the coreset size presented in Theorem 5 (and also Theorem 4) is data- dependent. That is, the coreset size depends on the value S, which can be different for different input instances. To achieve data-independent coreset size, we introduce the following method based on spatial partition, which is partly inspired by the previous k-median/means clustering core- set construction idea of [15, 17, 25]. We generalize their method to the mantinuuu-anndboundde learning problems and call as Generalized Spatial Partition (GSP) method.
GSP coreset construction. We set o = mingex f(ō, x) and T Y f(,, X). Then, we partition all the data points to different layers according to their cost with respect to Ø. Specifically, we assign a point æ to the 0-th layer if f() 2 < T; otherwise, we assign it to the llog( [(0 |-th layer. Let L be the number of layers, and is easy to see L is at most log n + 1. For any و S L. we denote the set of points falling in the j-th layer Xy. From each X,. we take small sample C₁ uniformly at random, where each point of C₁ is assigned the weight [X,l/(c}], Finally, the union set U Cj form our final coreset.
'In practice we often add a positive penalty item to the objective function for regularization, so we can assume that inf (e f X) is not small.
8

---

Theorem 6. Given a CnB learning instance X with the objective function f as described in Definition 1, let ddim be the doubling dimension of the parameter space. The above coreset con- struction method GSP can achieve an E-coreset of size @ log (ddim log ! log )) in linear time. The hidden constant of [C| depends on the Lipschitz constant and inf 0e3(00) (0,
To prove Theorem 6, the key is show that each Cj can well represent the layer X, with respect to any 0 in the bounded region B(O,E). E). First, we use the continuity property to bound the difference between f(0, 2) and f(0.z) z) for each x E Xj with a fixed 0: then, together with the doubling dimension, we can generalize this bound to any 0 in the bounded region.
5 Experiments
In this section, we illustrate the application of our proposed robust coresct method in machine learn- ing. We leave the more detailed experimental results to the full version of this paper [44].
Logistic regression (with outliers). Given x, IR and y E {+1}, the loss function of Logistic regression is
f(0, x) = In(1 + exp(-y (0, x))).
(22)
k-median/meann clustering (with outliers). The goal is to find A cluster centers Cen {cI, cz. : Ck3 C Rdd; the cost function of k-median (resp. k-means) clustering for each x E Rd is r)) = mine,eCen d(cs, x) (resp. x)),, where d(c,,x) denotes the Euclidean distance between G2 and xr
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: QR -eedeooomooiitoon 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 outliers with the largest losses and run an existing algorithm (for ordinary logistic regression or k-meaas clustering) on the remaining n = points; then updates the outliers based 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 scikit- learn package* 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 8, we just simply run the algorithm 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 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 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 (0, 200) to each dimension for these outliers. For the supervised learning task logistic regression, 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 and Table 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
"nttps://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.
Methed
[C]
Loss ratio
Speed-up
GSP+
4 x 10a
1,466
x x66.9
Method
Loss
Speed-up up
GSP+
8 x
1,031
19.199
GSP+
5 x 10
1.06
x41,1
UNIFORM+
x
1.134
x x
GSP+
10
1.008
x 15.4
UNIFORM
1,050
29.
UNIFORM+
5 10"
1.029
X78.9
QR+
10
UNIPORM+
10"
1.011
x46.9
8 10
1,012
x17.9
GSP
1.00
GSP+
Uniform Uniform+
Accuracy
QR
QR+
GSP
GSP+
Uniform
Uniform+
QR
0.90
2000 3000 4000 5000 6000
7000 8000 9000 10000
2000
3000
4000
7000 8000 9000 10000 Coreset Size (b) Accuracy
5000 6000
Coreset Size.
(a) Loss
350
GSP+
Uniform+
300
250
Speed-up
200
150
100
Height Merge-and-Reduce Tree
(c) Speed-up with the Merge-and- Reduce in the dynamic setting.
The performances different coreset methods for logistic regression on Covetype. The results are normalized over the results obtained from the original data (without using coreset).
Figure 2:
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 up ratio of running time in the dynamic setting. Our robust coreset construction uses the merge-and annee--nd-rdduee tree method. When the update happens in one bucket, we perform "bottom-up" re-construction for the coreset. We let the bucket size be n 22,,, where (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.
the height of the tree; thus the higher the tree, smaller the bucket size
6 Conclusion
In this paper, we propose novel robust coreset framework for the continuous and -add--ndd----oae 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); also interesting to consider implementing our method for distributed computing or federated learning.
10

---

Acknowledgment
We would like to thank the anonymous reviewers for their helpful suggestions and comments.
References
[1] Pankaj K. Agarwal, Sariel Har-Peled, and Kasturi R. Varadarajan. Approximating extent mea- sures of points. J. ACM, 51(4):606 635, 2004.
[2] Arindam Banerjee, Srujana Merugu, Inderjit S. Dhillon, and Joydeep Ghosh. Clustering with bregman divergences. Mach. Learn. Res., 6:1705 117705-179,, 2005.
[3] Amir Beck and Mare Teboulle. A convex optimization approach for minimizing the ratio of indefinite quadratie functions over an ellipsoid. Mathematical Programming. 118:13-35, 2009,
[4] Jon Louis Bentley and James B. Saxe. Decomposable searching problems I: static-to-de to-dmmmic transformation. J. Algorithmss 1(4):301-358 1980.
[5] Battista Biggio and Fabio Roli. Wild patterns: Ten years after the rise of adversarial machine learning. Patlern Recognit., 84:317-331 2018.
[6] Jock A. Blackard and Denis J. Dean. Comparative accuracies of artificial neural networks and discriminant analysis in predicting forest cover types from cartographic variables. Computers and Electronics Agriculture, 24(3): 13: 131-111, 1999.
[7] Vladimir Braverman, Dan Feldman, and Harry Lang. New frameworks for offline and stream- ing coreset constructions. CoRR, watbh//612.00000 2016.
[8] Emmanuel J. Candès, Xiaodong Li, Yi Ma, and John Wright. Robust principal component analysis? ACM, 58(3):1111-11:37, 2011.
[9] T.-H. Hubert Chan, Anupam Gupta, Bruce M. Maggs, and Shuheng Zhou. On hierarchical routing in doubling metrics. ACM Trans. Algorithms, 1555525:: 2016.
[10] Timothy M. Chan. Dynamic coresets. Discret. Comput. Geom,, 42(3):469 2009.
[11] Moses Charikar, Samir Khuller, David M. Mount, and Giri Narasimhan. Algorithms for facility location problems with outliers. In S. Rao Kosaraju, editor, Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, January 7-9, 2001, Washington, DC, USA, pages 642-651. ACM/SIAM, 2001.
[12] Sanjay Chawla and Aristides Gionis. k-means--: A unified approach to clustering and outlier detection. SDM, 2013.
[13] Jiecao Chen, Erfan Sadeqi Azer, and Qin Zhang. A practical algorithm for distributed cluster- ing and outlier detection. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, 3-8 December 2018, Montréal, Canada, pages 2253-22132 2262, 2018
[14] Ke Chen. A constant factor approximation algorithm for k-median clustering with outliers. In Shang-Hua Teng, editor, Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, California, USA, January 20-22, 2008, pages 826-835. SIAM, 2008
[15] Ke Chen. On coresets for k-median and k-means clustering in metric and euclidean spaces and their applications. SIAM J. Comput., 39(3):923-99)) 947, 2009.
[16] Vincent Cohen-Addad, David Saulpic, and Chris Schwiegelshohn. A new coreset framework for clustering. In Samir Khuller and Virginia Vassilevska Williams, editors, STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25. 2021, pages 169-182. ACM, 2021.

---

[17] Hu Ding and Zixiu Wang. Layered sampling for robust optimization problems. In Proceed- ings of the 37th International Conference on Machine Learning. ICML 2020. 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 2556-2566. PMIR, 2020.
[18] Dan Feldman. Introduction to core-sets: updated survey. CoRR, abs/2011 1009844 2020.
[19] Dan Feldman and Michael Langberg. A unified framework for approximating and clustering data. In Lance Fortnow and Salil P. Vadhan, editors, Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011, I, pages 569-578. ACM, 2011.
[20] Antonio Ginart, Melody Y. Guan, Gregory Valiant, and James Zou. Making Al forget you: Data deletion in machine learning. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelz- imer, Florence d' Alché-Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Sys- tems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 3513-3526, 2019.
[21] Shalmoli Gupta, Ravi Kumar, Kefu Lu, Benjamin Moseley, and Sergei Vassilvitskii. Local search methods for k-means with outliers. Proc. VLDB Endow., 10(7):757-768, March 2017.
[22] Bernd Gärtner and Jiri Matousek. Approximation Algorithms and Semidefinite Programming. Springer-Vent Verlag Berlin Heidelberg, 2012.
[23] Sariel Har-Peled and Soham Mazumdar. On coresets for k-means and k-median clustering, In László Babai, editor, Proceedings of the 36th Annual ACM Symposium on Theory of Comput- ing. Chicago. IL, USA. June 13-16, 2004, pages 291-300. ACM, 2004.
[24] Monika Henzinger and Sagar Kale. Fully-dynamic coresets. In Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders, editors. 28th Annual European Symposium on Algorithms, ESA 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference), volume 173 of LIPIcs, pages 57:1-57:21. Schloss Dagstuhl- Leibniz-Zentrum für Informatik, 2020.
[25] Jiawei Huang, Ruomin Huang, Wenjie Liu, Nikolaos M. Freris, and Hu Ding. A novel sequen- tial coreset method for gradient descent algorithms. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 4412-4422. PMLR, 2021.
[26] Lingxiao Huang, Shaofeng Jiang, Jian Li, and Xuan Wu. Apsilon-coresets for clustering (with outliers) in doubling metrics. In Mikkel Thorup, editor, 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 814-825. IEEE Computer Society, 2018
[27] Jonathan H. Huggins, Trevor Campbell, and Tamara Broderick. Coresets for scalable bayesian logistic regression. In Daniel D. Lee, Masashi Sugiyama, Ulrike von Luxburg, Isabelle Guyon, and Roman Garnett, editors, Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, 2016.
Spain, pages
[28] Piotr Indyk, Sepideh Mahabadi, Mohammad Mahdian, and Vahab S. Mirrokni. Composable core-sets for diversity and coverage maximization. In Richard Hull and Martin Grohe, edi- tors, Proceedings of the 33rd ACM Database Systems, PODS'14, 14, Snowbird, UT, USA, June 22-27, 2014, pages 100-108. ACM, 2014.
Symposium on Principles of
[29] Manohar Kaul, Bin Yang, and Christian S. Jensen. Building accurate 3d spatial networks to enable next generation intelligent transportation systems. In 2013 IEEE 14th International Conference on Mobile Data Management, Milan, Itll, June 3-6, 2013 Volume 1, pages 137- 146, 2013.
12

---

[30] Michael Langberg and Leonard J. Schulman. Universal epsilon epsilon-approxiie approximators for integrals. In Moses Charikar, editor. Proceedings of the Twenty-FFi First Aunual ACM- SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 598-607. SIAM, 2010.
[31] Yaliang Li, Jing Gao, Chuishi Meng, Qi Li, Lu Su, Bo Zhao, Wei Fan, and Jiawei Han. A survey truth discovery. SIGKDD Explor, 17(2):1-16, 2015.
[32] Yi Li, Philip M Long, and Aravind Srinivasan. Improved bounds the sample complexity of learning. Journal of Computer and System Sciences, 62(3): 2001.
[33] Mario Lucic, Olivier Bachem, and Andreas Krause. Strong coresets for hard and soft bregman clustering with applications to exponential family mixtures. In Arthur Gretton and Christian C. Robert, editors, Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, AISTATS 2016, Cadiz, Spain, May 9-11, 2016, volume 51 of JMLR Workshop and Conference Proceedings, pages 1-9. JMLR.org, 2016.
[34] Mario Lucic, Matthew Faulkner, Andreas Krause, and Dan Feldman. Training gaussian mix- ture models scale via coresets. Mach. Learn. Res., 18:160:1-160:22 2017.
[35] Adam Meyerson, Liadan O'Callaghan, and Serge A. Plotkin. A k-median algorithm with running time independent of data size. Mach. Learn., (661-3)661-88)) 2004.
[36] Baharan Mirzasoleiman, Kaidi Cao, and Jure Leskovec. Coresets for robust training of deep neural networks against noisy labels. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Process- ing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
[37] David M. Mount, Nathan S. Netanyahu, Christine Piatko, Ruth Silverman, and Angela Wu. On the least trimmed squares estimator. Algorithmica, 69(1): 2014.
[38] Alexander Munteanu, Chris Schwiegelshohn, Christian Sohler, and David P. Woodruff. On coresets for logistic regression. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Bianchi, and Roman Gareet,, editors, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pages 6562-6571, 2018
[39] Peter J. Rousseeuw and Annick Leroy. Robust Regression and Oulier Detection. Wiley, 1987.
[40] Melanie Schmidt. Coresets and streaming algorithuss for the k-means problem and related clustering objectives. PhD thesis, Universität Dortmund, 2014.
[41] Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning- From Theory to Algorithms. Cambridge University Press, 2014.
[42] Adiel Statman, Liat Rozenberg, and Dan Feldman. k-means++4: Outlers-resistant clustering. Algorithms, 13(12), 2020.
[43] Elad Tolochinsky and Dan Feldman. Generic coreset for scalable learning of monotonic ker- nels: Logistic regression, sigmoid and more, 2018.
[44] Zixiu Wang, Yiwen Guo, and Hu Ding, Robust and fully-dynamic coreset for continuous-and- bounded learning (with outliers) problems. CoRR, abs/2107. 07000068, 2021.
13


Reviews:
[{"review_id": "foN9XE2GAm", "reviewer": "Reviewer_vMDk", "summary": "This work provide coreset construction framework for functions that are Lipschitz continuous, smooth, and has Lipschitz continuous Hessian. The coreset in this paper is robust, i.e., it aims to handle outliers such that the coreset will be less biased than traditional coreset schemes.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I enjoyed reading the paper, which suggests a robust coreset construction framework for multiple problems such like logistic regression and k-means clustering. The coreset uses sensitivity sampling for inliers, and $\\delta$-sample for outliers. The ideas in this work are not trivial and the paper is well written, however I have some comments :\n1) Line 177, what do you mean by \"not integral\"? did you mean integer?\n2) I suggest moving the graphs to the paper. The graphs at supplementary material presents your efficiency against multiple candidates of coreset construction schemes.  \n3) I noticed some missing definitions, for example, in Theorem 1, line 168, what is Y? I did not completely understand the proof because of missing definitions in this Theorem.\n4)Shouldn't the upper bound in Lemma 2 include $5 \\epsilon$ instead of $3 \\epsilon$ ?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately addressed the limitations, i.e., the coreset in this paper handle bounded learning (the candidate solution set for the problems discussed in the paper is bounded)", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "dho3H_mt2el", "reviewer": "Reviewer_uGsY", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths\n\n- The authors tackle an interesting and relevant problem of constructing coresets in the context of outliers. I also appreciate their effort in trying to make their approach as widely applicable as possible to common optimization problems and scenarios in large-scale machine learning.\n\n- The technical results of the paper seem sound to the best of my knowledge.\n\n- Although the approach of partitioning the input set and sampling from each set separately is not new in importance sampling (cf., stratification [2]), I found its application to outlier-resistant coresets to be interesting and novel.\n\n\nWeaknesses\n\n- The paper is quite dense and the organization and exposition could use improvements. Crucial details in certain parts of the paper (see comments regarding QP & SDP below) are not provided at all or deferred to the supplementary, but yet proofs of technical results (e.g., Lemma 2, Theorem 1, and Theorem 2) are provided inline -- taking up almost 2 pages total in the main paper. To me, this seems to distract from the flow of the paper, and also leads to important omissions. For example, the (only) empirical results of the work can only be found at the end of the supplementary material and additional details regarding the implementation of the method in practice are not provided (e.g., for a given sample size as in Sec. D of the supplementary, what $\\varepsilon$ is used for the hybrid approach?). I would suggest deferring some of the technicalities to the supplementary in order to make room for further clarifying text around the main ideas and the experimental results (currently in Sec. D of the supplementary).\n\n- Computing the sensitivities as described in Sec. 4.1 requires a reduction from a fractional Quadratic Program (QP) to a Semi-definite Program (SDP), with an overall running time of $O(n \\text{poly}(d))$. Solving an SDP for every single point to compute the sensitivity upper bound seems to be highly costly in practice. Moreover, no details of how the sensitivity can be bounded via a QP formulation and SDP reduction are provided in the supplementary (despite the promise of additional details in Lines 307-310). Overall, I have difficulty seeing the added benefit of the sensitivity bounding approach presented in Sec. 4.1 relative to existing techniques for those specific problems (e.g., [3]). This also seems disjointed given the context of outlier-resistant coresets. Given the iterative SDP requirement, I am not sure how to make sense of the speed-up claims of up to $\\approx 250$ in Fig. 4(c) (in the supplementary) relative to “training logistic regression on the original data” given that logistic regression training is quite efficient in practice and theory (e.g., via a gradient-based method).\n\n- Relatedly, I am unclear about the connection to the GEL algorithm and why it is presented in conjunction with the QP-based method. Could we not bound the sum of sensitivities assuming that we have the optimizer for the sensitivity expression in Eq. 19 to obtain a data-independent upper bound on S? It seems to me that leaving the sum of sensitivities to be data-dependent and then theoretically bounding this quantity would yield better practical performance than an alternative approach that, in a sense, forces this sum to be data-independent. The sampling complexity of Theorems 4 and 5 also ignore factors $\\alpha$ and $\\inf_{\\theta \\in \\mathcal{B}} \\mathbb{f}(\\theta, X)$, and it is not immediately clear to me when the bound would be vacuous: e.g., what happens if $\\inf_{\\theta \\in \\mathcal{B}} \\mathbb{f}(\\theta, X) \\approx 0$?\n\n- A more thorough discussion of the sampling complexity of Theorem 2 relative to that of related work in coresets with outliers would be illuminating (e.g., those of [1]).\n\n- Lack of experimental details: the method requires knowing epsilon and $\\tilde \\theta$, among other hyperparameters that are required by the proofs and technical results. Yet, these values are not reported for the evaluations in the paper, and from the point of view of a practitioner, I am left confused as to what $\\tilde \\theta$ should be or how I would obtain it in practice. How were the results in Fig. 4 generated given a specified sample size?\n\n- The experiments do not compare to prior work in coresets with outliers (e.g., [1]), among other related work that was cited in the introduction. Moreover, no computation time figures are reported for the offline setting, which makes it difficult to conclude that the proposed outlier-resilient approach leads to more accurate models (efficiently) in practice. Fig. 4(c) of the appendix reports the speedup in the dynamic setting as a function of the merge-and-reduce tree height, but only for the enhanced methods (with an “+” appended). It would have been illuminating to see computation time (x-axis) vs. normalized accuracy for the compared methods (similar to Fig. 4(b)). A discussion of why Uniform+ outperforms competing approaches in terms of the computational speedup (while performing on par with the coreset-based approaches) in Fig. 4 would be insightful.\n\n\nOverall, I find the paper interesting and technically rigorous. However, I have qualms about the clarity and exposition of the paper and the practical merits of the proposed approach relative to prior work. At times, I felt like the paper tried to achieve too many things at once and some of the contributions seemed either disjointed or weren't well-motivated or emphasized (e.g., Sec. 4). I would suggest a clearer exposition in light of the comments above and more rigorous empirical evaluations that appear in the main paper.\n\n[1] https://arxiv.org/pdf/1804.02530.pdf \n\n[2] https://statweb.stanford.edu/~owen/mc/Ch-var-basic.pdf\n\n[3] https://proceedings.neurips.cc/paper/2018/file/63bfd6e8f26d1d3537f4c5038264ef36-Paper.pdf \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Please discuss limitations and potential negative societal impacts in Sec. 5 as reported in the Checklist.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "SE4HRj5zgFD", "reviewer": "Reviewer_4yNi", "summary": "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.\n\nAn \\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). \n\nThe 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).\n\nSeveral 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.\n\nBesides, 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.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality & significance:\n\nThe main novelty is the initiative of a unified framework for coresets for continuous-and-bounded learning with outliers. The main result which reduces the outlier version to the non-outlier version is novel, and I do think this reduction seems to be strong enough to imply interesting new bounds for concrete instances of continuous-and-bounded learning problems. Unfortunately, authors did not give any such examples, which makes me uncertain about the usefulness of this new unified theory. In particular, the theorem requires the VC-dimension of the f-induced range space to be bounded – can you show an interesting example of continuous-and-bounded learning problem that has VC-dimension bounded? It also makes it hard to tell whether this result can improve previous works without such examples.\n\nAn additional comment is that, your coreset is bi-criteria for the outlier problems – is the violation in the number of outliers necessary? Can you possibly justify this?\n\nAs another contribution, several coreset constructions for general continuous-and-bounded learning (without outliers) are given, and all of the proposed coresets depend on the doubling dimension of the parameter space. But I’m not sure if considering doubling dimension on the parameter space makes sense – indeed, doubling dimension is an intrinsic dimensionality measure, but it is usually applied on data set instead of parameter space. In fact, parameter space is data-independent and usually depends on the problem itself, which does not seem to benefit from low intrinsic dimension.\n\nTechnically, many results are obtained by combining existing techniques in a straightforward way, and I don’t see much novelty. For instance, the dynamic algorithm follows almost immediately from previous works, and it doesn’t add much to the paper; also, the two coresets for non-outlier version of the problem are very much standard and follows from previous framework with only minor modifications.\n\n\nQuality:\n\nI think the paper is technically sound, and all major claims are reasonably supported by proofs. However, a key missing part of the paper is some concrete applications of the unified theory – maybe some new bounds for specific learning problems? Or experiments that validate the theory in a certain way? (I do see some experiment results were reported in the supplementary, but unfortunately the findings of the experiments are not discussed in the main text at all.) This would make the theory more useful to the machine learning community.\n\nClarity:\n\nThe paper is overall very well written. It does a good job to provide necessary information for (at least expert) readers to understand why each claim holds, without needing to read proofs.\n\nOther comments:\n\n1.\tLine 31 “noise” -> “noisy”\n2.\tLine 61 should be “continuous-and-bounded”\n3.\tIn Definition 2, why use a different font for f? In general, please make sure you use the font consistently (which seems not the case in the paper).\n4.\tIn Definition 4, why do we need the assumption that \\mathcal{X} is a metric space? I don’t think you need this.\n5.\tLine 164, what do you mean by “\\delta-approximate subset”? I didn’t find the definition.\n6.\tLine 165, the use of O in “O = ab” seems not a good idea, since O is usually used as in the big O notation.\n7.\tLine 168, what is Y?\n8.\tTheorem 2, line 223, what’s the third parameter 2\\xi(l)? I think the notation only has two parameters?\n9.\tLine 228, can you explain why f_z(\\theta, C) = f(\\theta, C_I + C_{II})? In particular, why don’t we need C_{III} and C_{IV}?\n10.\tIn the statement of Theorem 3, the VC dimension should be a uniform upper bound for weighted range spaces over all weights.\n11.\tIn the statement of Theorem 4, line 321, you mentioned the hidden constant depends on \\inf_{\\theta} f(\\theta, X) – why this is bounded?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "7HzjHdNMxwy", "reviewer": "Reviewer_Pcf3", "summary": "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\na)\tPaper provides an extensive theoretical study analyzing the robust coreset selection framework and proved a theorem stating that the proposed framework can successfully compute a (beta, epsilon) coreset.\nb)\tProvided experimental results show that the proposed coreset selection framework achieves better speedup and accuracy computer to other coreset selection methods.\n\nCons:\na)\tThe theoretical assumption of boundedness is too restrictive for deep networks. Hence, the proposed framework may not work well in a deep learning scenario. It would be nice to have some results using deep models even if the proposed method does not work so that others have an understanding of the limitations of the proposed approach.\n\nb)\tIn the experimental section (in the appendix), the authors mentioned speedups and accuracies achieved. It would be interesting to know how many actual outliers the proposed framework was able to select or filter during training.\n\nc)\tThe used coreset selection methods for experiments are simple. Hence, it would be interesting to know how the proposed coreset selection framework compare to other robust coreset selection frameworks like GLISTER (https://arxiv.org/abs/2012.10630), Coresets for Robust Training of Neural Networks against Noisy Labels (https://arxiv.org/pdf/2011.07451.pdf) and Grad-Match (https://arxiv.org/pdf/2103.00123.pdf)  in terms of speedups and accuracies. It would also be interesting to find if the proposed approach can also be applied with the above-mentioned robust coreset selection methods.\n\nd)  The major limitation of this work is the lack of solid experiments. I would have expected more empirical results particularly given the nature of the problem and not have the experiments relegated to the Appendix. I would encourage the authors to discuss how their approach compares to other subset selection and coreset approaches for robust learning (like those mentioned above).\n\nPost Rebuttal Update:\nThe authors have clarified a few of the issues pointed out. However, a major criticism of this work is the lack of experiments. This, in my opinion, can be a limiting factor for the impact of this work, mainly because a lot of work in this area is empirical and an understanding of how an approach like this performs empirically is critical in understanding its place among the state-of-the-art. However, I do think this paper contributes from a theoretical perspective, and I'll keep my score of weak acceptance. I would strongly encourage the authors to add empirical evaluation in the main text if given a chance.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This paper is mainly theoretical.", "review_text": "", "extra_scores": {"ethical_concerns": "This paper is mainly theoretical.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3-4 hours"}, "extra_text": {}}, {"review_id": "5e6ZJX6NiFp", "reviewer": "Reviewer_CN4f", "summary": "The paper suggests a coreset construction framework for a family of functions that are Lipschitz continuous, smooth, and has Lipschitz continuous Hessian. The framework considers only continuous-and-bounded learning, i.e., optimization problems concerning bounded space of candidate solutions.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper suggests a robust coreset construction framework for several problems, including logistic regression and $k$-means clustering, under the umbrella of continuous-and-bounded learning. The method entails sensitivity sampling for \"inliers\" while using $\\varepsilon$-sample for \"outliers\" to obtain a robust coreset. The ideas are interesting in nature and the work is not trivial.\n\nI enjoyed reading the paper and the results are sound yet there are some misclarifications. Due to time constraints, I have managed to go over some of the proofs and they were sound other than the proof of Theorem 1 and Lemma 2; see my comment section below.\n\nComments:\n- What is $Y$ at Line 168? It seems that $Y$ is the set $B$.\n- There is an additional \"s\" at Line 300.\n- It is very interesting that the sensitivity can be solved using quadratic fractional programming via a relaxation towards semi-definite programming. My question is, what is the total sensitivity in this case? what is the exponent in the $\\mathrm{poly}(d)$ term at the time complexity?\n- At Lemma 2, the bounds are not tight since the coreset is a robust coreset. This means that some of the transitions need to involve an additional multiplicative term of $O(1\\pm\\varepsilon)$. This is due to the fact that you end up dividing the sum of weights of instances of $C$ by the number of points in $X$. Through the literature of $\\varepsilon$-coresets, and robust coresets as well, this term is in the range of $\\left[ 1-\\varepsilon, 1+\\varepsilon\\right]$.\n- The proof of Theorem 1 is not clear as some of the transitions are not clear (see my first comment)\n- Some of the coresets that you have mentioned handled instances of the problems that the paper discusses, e.g., logistic regression. However, I believe that the related work can be further enhanced, e.g., \"Coresets for Near-Convex Functions\" which proposes a unified framework for coreset construction for various loss functions including logistic regression, SVMs, and even robust $\\ell_p$-regression. Using this paper as a black box to bound the sensitivity, how well your model will perform in terms of normalized loss error?\n- Please move some of the graphs to the main manuscript to further enhance your results in the paper.\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "One of the limitations of this work is that it handles bounded learning. It is interesting to show that under the umbrella of robust coresets, such limitation is somewhat necessary. Please provide a brief explanation of why it is not possible to remove such limitation, or where exactly in your method (or analysis), the necessity of this assumption is crucial? \n\nIn addition, Theorem 4 imposes an additional limitation. Specifically speaking, the total sensitivity that is being squared at the sample size. In recent works, e.g., \"On coreset for Logistic Regression\" and \"Coresets for Near-Convex Functions\", the total sensitivity was bounded from below $\\Omega\\left(\\sqrt{n}\\right)$ . This means the sample size in your case is $\\Omega(n)$. I wonder if the total sensitivity that is obtained using your method is much smaller than the bounds achieved in the papers above due to the bounded learning assumption. Please briefly discuss this.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This is a beautiful paper about coresets for handling outliers which will probably inspire many future related papers.
While there are concerns regarding experimental results (that are hidden in the supp. material), the theoretical contribution with an algorithm that it is not hard to implement is strong enough for such a fundamental problem in machine learning.
Please move some more experiments to the main paper in order to attract the practitioners.

Also please add the following references and maybe some more:
https://www.mdpi.com/1999-4893/13/12/311
https://dl.acm.org/doi/10.5555/1347082.1347173

Decision: Accept (Spotlight)