Robust Sparsification via Sensitivity
Authors: Chansophea Wathanak In
Yi Li
David Woodruff
Xuan Wu
Venue: ICML 2025 poster (2025)
Keywords: Coreset
Robust Machine Learning
Subspace Embedding
Clustering
Primary area: theory->optimization
TL;DR: We construct robust coreset for any optimization problem that admits bounded sensitivity and vanilla coreset.

Abstract: Robustness to outliers is important in machine learning. Many classical problems, including subspace embedding, clustering, and low-rank approximation, lack scalable, outlier-resilient algorithms. This paper considers machine learning problems of the form $\min_{x\in \mathbb{R}^d} F(x)$, where $F(x)=\sum_{i=1}^n F_i(x)$, and their robust counterparts $\min_{x\in\mathbb{R}^d} F^{(m)}(x)$, where $F^{(m)}(x)$ denotes the sum of all but the $m$ largest $F_i(x)$ values. 

We develop a general framework for constructing $\epsilon$-coresets for such robust problems, where an $\epsilon$-coreset is a weighted subset of functions $\{F_1(x),\dots,F_n(x)\}$ that provides a $(1+\epsilon)$-approximation to $F(x)$. Specifically, if the original problem $F$ has total sensitivity $T$ and admits a vanilla $\epsilon$-coreset of size $S$, our algorithm constructs an $\epsilon$-coreset of size $\tilde{O}(\frac{mT}{\epsilon})+S$ for the robust objective $F^{(m)}$. This coreset size can be shown to be near-tight for $\ell_2$ subspace embedding. Our coreset algorithm has scalable running time and leads to new or improved algorithms for the robust optimization problems. Empirical evaluations demonstrate that our coresets outperform uniform sampling on real-world data sets.

Robust Sparsification via Sensitivity
Chansophea Wathanak In' Yi David P. Woodruff Xuan Wu
Abstract
regression methods since the 1960s (see, e.g., (Andersen, 2008) for comprehensive survey), and it remains active area of research today. In this paper, we present frame- work to address the issue of outliers for a large family of optimization problems, including regression, by reducing their scale through the construction coresets.
Robustness to outliers is important in machine learning. Many classical problems, including subspace embedding, clustering, and low-rank approximation, lack scalable, outlier-resilient al- gorithms. This paper considers machine learn- ing problems of the form min F(z), where F(x) Σi= Ri(r), and their robust coun- terparts min (x), where Fz()(()) de- notes the sum of all but the m largest Fi(x) val- ues. We develop a general framework for con- structing e-coresets for such robust problems, where an e-coreset a weighted subset of func- tions (z), F,, (x)) that provides (1 + +))- approximation to F(r). Specifically, if the origi- nal problem F has total sensitivity T and admits a vanilla s-coreset of size S, our algorithm con- structs an E-coreset of size Ó(m²) + S for the robust objective p(m), This coreset size can be shown to be near-tight for l subspace embed- dings. Our coreset algorithm has scalable running time and, by employing a sensitivity flattening argument, leads to new or improved algorithms for robust optimization problems, including gression and PCA. Finally, empirical evaluations demonstrate that our coresets outperform uniform sampling on real-world data sets.
A natural and popular approach for handling outliers is to consider robust versions of the original optimization for- mulations. Specifically, consider an optimization problem of the form min F(x), where F(x) = >> -i=1 (x).
The robust version of F(x), denoted by F(() (z), aggre- gates all but the largest m values over (x) (i = 1, 1,....n). n). Formally, for each æ E Rd, the values F (Ir), (.,) (x) are sorted in increasing order as F, (x) 2 (z) z
...2 Fr. (I)), and F((m) (x) is then defined as F(() (x) Ej=1" (x)). This robust formulation coincides with the least trimmed regression (Rousseeuw, 1985) and was first considered in algorithmic machine learning by (Charikar et al., 2001) in the context of facility location. More recently, it has been studied in several important machine learning problems, including PCA (Simonov et al., 2019) and cluster- ing (Chen, 2008; Krishnaswamy al., 2018). However, all those algorithms have high-order polynomial running times, making them neither scalable nor even practical.
In the case of no outliers (which will be referred to as the vanilla case), a popular scalable solution is to sparsify the input by constructing a coresct. (strong) E e-coreset is a weighted subset of the dataset such that the loss of every candidate solution on this subset approximates the original loss within relative error of E. In the past 20 years, core- sets have been extensively studied for a variety of machine learning problems (Har-Peled & Mazumdar, 2004; Feldman & I Langberg, 2011; Munteanu et al., 2018: Chhaya et al., 2020; Jubran et al., 2021; 1; Huang et al., 2021; Braverman et al., 2022).
1. Introduction
Outliers, which can occur frequently in real-world data, pose significant challenges to many machine learning problems. For instance, in the classic regression problem, a small num- ber of contaminated data points can drastically skew the solution. This issue has driven the development of robust
In the robust case, early coresets have either exponential size (Feldman & Schulman, 2012) or weaker bi-criteria ap- proximation guarantee (Feldman & Langberg, 2011; Huang et al., 2018). Recently. in the context of clustering with outliers, Huang et al. (Huang et al., 2023a) construct the first strong coreset with a similar size to the vanilla case. Inspired by their work, more strong robust coresets for clus- tering have been developed (Huang al., 2025; Jiang
The authors are listed in alphabetical order. 'School Physical and Mathematical Sciences. Nanyang Technological University, Singapore "College of Computing and Data Sciences, Nanyang Technological University, Singapore 'Department of Computer Science, Carnegie Mellon University, USA. Correspondence to: Yi Li <yili@@ edu.".
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Robust Sparsification via Sensitivity
Lou, 2025). Beyond clustering, Wang et al. (Wang et al., 2021) constructed local robust coresets for continuous and bounded functions. These coresets preserve F(z) only for within specific ball, which means that they do not satisfy the requirements of a strong coreset. This naturally leads to the following question.
An (e, ()-corettt is also referred to as a (vanilla) e-coreset.
The typical way to reduce the scale of the problem is to solve, instead of the original min L (F; the core- set version minzerd of F. The following is folklore result the guarantee of the optimal solution of the coreset version.
((m) (F;z) if F is (e, -coresset
Question 1.1. Consider an optimization problem of the form minzeRa F(r),, where F(x) Fi(x) +.... FF..).. (z)..). Under what conditions can an efficient construction of a strong e-coreset of small size be achieved for the robust version F(m) (x)?
Lemma 1.2. Suppose that F is an (s,mus coresel of IF and E (0,1). Let & arg ongminnere ((m) (F;x)
and x² = arg argmin ((m) (F:x). It holds that (F;)): S t (im) (F;x)")
Our answer to Question 1.1 is perhaps surprising. We show that two simple conditions are sufficient for the existence of small coreset for p(m); F(x) has small vanilla coreset and has bounded total sensitivity. The first condition is natural, as the robust coreset extends the concept of a vanilla coreset. The second condition, based on the existence of small vanilla coresets, is a mild condition, since a majority of current vanilla coreset constructions rely on bounded total sensitivity. We remark that the total sensitivity is a widely used complexity measure in sparsification problems and has been a crucial quantity in establishing theoretical guarantees for coreset sizes across many classical machine learning problems, including subspace embeddings, regression, PCA, clustering, and projective clustering (Drineas et al., 2006; Woodruff, 2014; Feldman & Langberg, 2011; Braverman et al., 2021a; Woodruff & Yasuda, 2023).
Below we describe how two classical problems, computing subspace embedding and computing clustering, fit in our framework.
Subspace Embedding Let p 2 1. For a matrix A E Rexd (n >> d), we say a matrix E Rmmd with m < n is an e--susppace embedding for A with distortion parameter & if (1 =] || I BxlB - [)++)]laa AA]l holds simulta- neously for all x E Rd. A typical construction of B is sam- pling rows of by Lewis weights and rescaling the samples. This can be viewed within our sparsification framework by defining fax)) = (a,, 2)I and F = (fi..... fnJ. where a denotes the i-th row of A, so that ((F;)) = || Suppose that f = {(f.g: Wiy)) )} is an e-coreset of F, where in , im E [r>] denote the indices of sampled rows, then 1/p one can take the j-th row of B to be by = ai - Then the E-coreset property gives exactly that B is an Sp-subspace embedding for A with distortion parameter e.
1.1. Problem Definition
k-Median Coresets Suppose that X = f. Ind are n points in Rd. Define set of h centers C (cr.... ).). where G, E Rd. The clustering cost of X with respect to C' is defined to be Σ minel|æ;- ce ll2 The coreset for the k-median problem is to find a subset X" = {xig..... Ti,,, } with weights wi...., Wm 2 0 such that the weighted clus- tering cost of X' approximates the clustering cost of X for every choice of C: that is, Σソ= Wj min. | - ce ll2 = (1+t) Ei=1 ming fatp//lz.-- |lz, eieeeeell for all subsets of C' C Rd with CI = k. This again can be viewed within our sparsification framework by defining fe(ci,..., Ck) = miny ||,; eg l2 and J = (fr.... fn). An e-coreset of the k-median prob- lmm is exactly an s-coreset of F.
Suppose that F = [(f,w))} is a finite weighted set of functions, where each f Idd + R20 is associated with a weight wy 2 0. The loss function for F is L(F;x) = Eisaner Wy f()) and the robust version of the loss func- tion with m outliers is defined
c (F:z)= = min PCF
Σ wy f(z).
|FF ism (fwy)E
The associated optimization problem is to solve minzeR" (F)
When Wy = 1 for all ʃ E F, we also say that F is un- weighted and write F = {f].
Coresets Suppose that Fi is a weighted (multi-) subset of F; that is, each function in ftr is also in F and each function f in F is associated with a weight w 2 0 (for some f e F. multiple/ f with different weights may appear in F).
1.2. Related Works
Coresets for clustering have been a rich and extensively stud- ied research area for over 20 years. Stemming from (Har- Peled & Mazumdar, 2004; Har- & Kushal, 2007), early coreset algorithms rely on ad-hoc geometric constructions, giving size bounds that are exponential in the dimension d. Chen (2009); Langberg & Schulman (2010); Feldman & Langberg (2011) initiated the use of sampling algorithms in constructing coresets for clustering, achieving size bounds
We say F is an (E, m) -rouuut coreset (or simply, an (e, m)- coreset) of FF if F is weighted subset of F and it holds for every E RR and every 0,1,..., that
(1 6) c() S c (F:x) s (1++)) (1+ (1+ (F;x).
2

---

Robust Sparsification via Sensitivity
polynomial in d. Recently, coresets with size independent of d have been constructed by employing modern dimension reduction techniques for clustering and new group sampling methods (Feldman et al., 2020; Sohler & Woodruff, 2018:
3. Our Results and Technical Overview
Our main result is the following robust coreset construction algorithm.
Huang& & Vishnoi, 2020; Cohen-Addad et al., 2021; 2022;
Theorem 3.1 (Informal statement of Theorem 4.1). There exists an algorithm, for every loss function F(x) = Σjer fx) such that F has total sensitivity T and admits a vanilla coreset of size Q, constructs with probability at least 0.99 an (e, m)-oresset for F with size O .log Tm )
Cohen-Addad et al., 2022; Huang et al., 2024).
Beyond robustness, coresets have also been explored in var- ious other settings to address new challenges in machine learning. For instance, Bachem et al. (2018); Braverman et al. (2019) give simultaneous coresets to handle multi- ple objectives, Braverman et al. (2021b) design coresets for datasets with missing values, Huang et al. (2021) con- struct coresets for time series data, and Huang et al. (2019); Bandyapadhyay et al. (2021); Braverman et al. (2022) con- sider the setting with fairness constraints.
[mm
When applied to &g subspace embeddings, this theorem gives coreset size of Ö md
log md) + Q. We show in is necessary for an (e, m)- coreset. Note that an (e, m coreset must also be a vanilla E-coreset, which shows that Q is also necessary. Thus our bound is nearly tight for &g subspace embeddings.
Section D that a size of S mad
2. Preliminaries
Building upon our coresets, we develop new algorithms for robust optimization tasks. For example, we design algo- rithms for robust regression (Theorem 5.1) and robust PCA (Theorem 5.3) with a runtime of ((0m))_0mm) + ((nd), using a sensitivity flattening technique. Additionally, our coresets can be used to improve existing algorithms, such as (Simonov al., 2019). Furthermore, Theorem 3.1 yields a new coreset for robust k-median. Detailed discussions can be found in Section 5. We remark that our coreset construc- tion also extends to another popular setting that removes a total weight of m instead of exactly m functions of F; see Appendix C.
Notation In this paper, we always assume that the function set is finite. We use [n] to denote the set {l...., n). The notations S 9 and f ž g indicate f S Cg and f 2 Cg. respectively, for some constant C > 0.
For matrix A, its Frobenius norm is denoted by ||A||F = (2,, s. 2/2 and its operator norm by Alllopp := sup,yollAAan |
For random variable X, we write X ~ D to indicate that X follows the probability distribution D. For a finite set S, we denote by Uni the uniform distribution on S. We denote by Geometric(p) the geometric distribution with expected value 1/p.
In Section 6, we conduct experiments on real-word datasets to demonstrate that our coreset constructions are effective in approximating the loss function and considerably reduce the running time for robust regression problems while main- taining good approximation of the objective function.
Sensitivities For weighted set F = {(f, wy)}, the sensi- tivity of f E F is defined as
fx)
af(f)=
sup "ERd
E
(g. wgg(x)
3.1. Technical Overview
Our coreset construction algorithm contains two stages. In the first stage, we identify small set S C F containing "contributing" functions and include S in the coreset with unit weights. In the second stage, we compute a vanilla core- set for J \ S and apply refinement process (Algorithm 2) to adapt it for robust objectives.
The sensitivity of F is defined as
OF Σox(1)
JEF
We say that F has total sensitivity T if OF S T for every F' F.
We begin with the construction of S. A function f E A is called contributing if for some x E IRd, f(x) 2 &. m
We note that it may be difficult to compute the precise values of sensitivities (f) In fact, it suffices to com- pute an upper bound āf( 2 of(s) such that ãx = Eser of( = O(r)). To simplify the presentation, we also refer to (f) as sensitivities.
((m) (A; Our goal is to include all contributing functions in S, since this will ensure that removing any m functions from F \ incurs at most m E e relative error. To do this, we sample each E F with probability 1 and then include in S the functions of (2s)) sensitivity within the sample. We can repeat this procedure sufficiently many times to ensure that all contributing functions are included. We need to (i) show for one round that each contributing f will, with good probability, survive the sampling and have
m
For f2-subspace embeddings, the sensitivity is classic quantity called the leverage score. Constant-factor approx- imation of the leverage scores of a matrix A E Raxd can be found in time O(nd+ + poly(d)) (see, e.g., (Drineas et al., 2006; Woodruff, 2014)).
3

---

Robust Sparsification via Sensitivity
((s) sensitivity within the sample; and (ii) bound the total number of contributing functions.
Algorithm Uniform( (A, e,
Input: set A of functions, parameters & and m
We first establish (i). Consider an event E that f survives the sampling while all outliers of ((m) (A; except f do not. Then Pr(E)= 2 (1 - ) 1 = 9 hn) By Markov's inequality, we know that conditioned on E, with constant probability, the aggregation of the sample on is at most - (A: so the sensitivity of f within the sample is at least _ ) M(E). We have therefore established (i) with the "good probability" being S2 (-
Output: A subset D - A
1: BB+ 0
2: for each f E A, with probability 1 addd f to B
3: for each f E B, compute the sensitivity a (f)
4: D {ʃ E B : (f( 2 f
5: Return D
Algorithm 2 Refine(D,e, m)
Next we examine (ii). Since the total sensitivity of F is
Input: A coreset D, parameters E and m
at most T, there are O(²)) functions with sensitivity at least (Es). which implies that each round returns O functions. If the number of contributing functions is N, then by a union bound, we need ((m log N) rounds of sampling to ensure with constant probability that all con- tributing functions are included. This implies that N I |S| 0 Tm log N). Solving this inequality for N gives that N 0 Tm log )
Output: A refined subset 1 adapted for the robust opti-
mization problem
1: D 00
2: for (f.wy) E D do
3: compute the sensitivity dD(f)
4: f + m I
5: Add ny copies of (f, my to D
6: end for
7: Return D
Now, consider the second stage. We begin by constructing vanilla e-coreset D of F S. where DI Q. A potential issue is that the weight of a function in D may be too large and its removal could result in a violation of the coreset property. To resolve this, we "split" functions in D into multiple copies, each with a smaller weight. Specifically, we split each into I of]l functions. The resulting size of the modified coreset is at most ΣSED = af( + 1 <
4.1. Analysis of Algorithm 3
Let A be set of functions : R - Rzu- We need the following definition in our analysis.
Definition 4.2. A function f A is called contributing if there exists x E Rd such that f() 2 . (A) (A;
Tm +Q, which is still affordable. Moreover, by the property of sensitivity and the guarantee of the first stage that S contains all contributing functions, we know that removing any m split functions will incur a total error at most m m/c
The following lemma shows that fixed contributing func- tion will be added to D with probability 6(1/m) in each repetition of Algorithm 1.
L(D; s O(s) L(F S;z) s O(s) (F:x).
Lemma 4.3. Assume that f is contributing, then with prob- 1 ability at least 5m the set returned by Uniform(AA A, e, m) contains f.
4. Coreset Construction
Our main result is the following theorem.
By definition, there exists x E Rd such that f(x) 2 (m) (A; Fix this æ. Let L C. A denote the set of outliers excluded by (im) namely. L consists of the m functions f in A with largest values of f(x).
Proof.
Theorem 4.1. Consider a sparsification problem for F(x) Eyer f(x and E (0, 2) Suppose that F has total sensitivity T and there exists an algorithm that computes a vanilla e-coreset for F of size Q. Then, Al- gorithu 3 computes an (E, mrrbuusst coreset for F of size ( Tmm. Moreover, if the vanilla coreset algorithm runs in time Eo(n,) on n input points and the sensitivity oracle com- putes the sensitivities of n points in time t, (n), then Al- gorithm 3, with probability at least 0.99, runs in time ((to([F),e) + to m + +O(V log mF m log( mf
Let L' = L (/) so LL' S m. Consider the event & where f E B while L' //BB B = 0. Then Pr[E] = (1 1 m 1 1 <
Observe that
c llog Im + Q, with probability at least 0.99.
E
Σ h(x) E
= -(xx) + 1
Σ
hh(x)
m
LAE
hEAi(LUESH)
S $f(x) + 1. pr(m) (x)
m <1+ + } f(x)
< 2
f(x).
4

---

Robust Sparsification via Sensitivity
Algorithm 3 Coreset Coreset(A,,,,)) m)
We are ready to prove Theorem 4.1.
Input: A set A of functions, parameters and m, and an algorithm Vanilla(A) to construct an e-coreset for A
Proof of Theorem 4.1. Let P denote the return of Coreset(A, m.). We first bound IP|. Since the total sensitivity of F is at most T, at most 4T functions in A are added into S in each repetition of Algorithm 1. Thus, 8
Output: An (c. m--obuust coreset for A
1: S +-00 0
2: R + (m log Tm)
|S| = 0 Tm log T by Algorithm 2. Observe that
). It remains to bound the set returned
3: for i = 1,,, ... R do
4: D - Uniform m))
5: SUD
| & E nz=
E
m -D(if]
6: end for
7: V Vanilla(A (S)
(Jwo))ED
(Lwy)ED
8: S 1[ :fl:fffe f S}
= T'
9: Return S ee..
S
Σ
+ +Q.
E
(Swy)eD
The coreset size is hence bounded by O
I' log Tm) + Q. :
By Markov's 's inequality, with probability at least ! 1 5m
2 cm >
I the event& & happens and ELEB h(z) S 1 fx).. This
Next, we prove that P is indeed an (c, -crreeet. We shall show that for every # E Rd and f = O...., m, c (P; x) e (1 + Ce) _ (F;rr) for some absolute constant C. The proof will be completed by rescaling e.
implics that (f) 2 Esen h(a] 2 1. Therefore, f is m
f((r)
added to D with probability at least _. 5m.
Lemma 4.4. The number of contributing functions in A is 0 Tm
We first prove that (P;z) s (1 (A) suffices to remove at most items from P and show that the weighted sum of the remaining items is at most (1 +
log
Tm e
log((a;-1) for i 2 1. We prove by induction that the number of con- tributing functions is upper bounded by o; for every 2
Proof. Define a sequence 4g = n,, 20Tm
Cε) - (A:z).
Let Lg denote the set of outliers excluded by (P;(P;;) then |T-z| S 1 S m. By Lemma 4.3 and Lemma 4.4, we know that with constant probability, every contributing F, has been added into S. Conditioning on this event,
The statement trivial for i 0, since the total number of functions is always bounded by n. Now, assume the number of contributing functions is bounded by az we prove that the number is also bounded by
Σ f(x) S [L SELO\S
((im)(;;)))) S ((m) (P;z)
20I'm
m
0++1
logg(2.))
(L)
8
S c(0) (A: (:)
To see this, we remark that for an contributing f A. a single repetition of Algorithm 1 returns with probability at least Now consider 5m log(2a,) independent repeti- tions of Uniform(F,e, By a union bound, we see that with probability
Let L'2 = If S} to be removed from P. Clearly [T/]] S Since L' C S and Refine(V, F,e,m)
returns an e-coreset for A \ S, we have
Σ Wy (fF) (FwL)EML
1 a-a -0--11111 (1- 5m
1
5m (2a)) > 1 a 20;
5m
2'
< Σ g(z) (1++)-
Σ g(x) DEA/S
all contributing functions will be found. Since the total sensitivity is bounded by T. there are at most 1T' func- tions added into D in each repetition, which implies that the number of total contributing functions bounded by 5m log(2a.) 4T 20Tm log(2o.), This establishes (1).
DES/Le
< (1+
Σ g(x)
(EAI(LLnS)
$ <11+c)
Σ g(x)+ + E g(x)
We may continue iterating as long as 01+1 S aai otherwise, 0
we have log[2a;] < 201'm and so a, = O(Tm log Tm = as desired. If the process does not terminate, the sequence {ar} is a monotone decreasing and positive sequence, thus converging to a unique limit lim;- 04 = a. Letting i + xo on both sides of (1), we obtaín that log(2a) = 20T which also implies a = O T' log Tm ), as desired.
gEAVLL
gEL,i4
<(1 + 28)
Cit) (A;
We have estalished that _(¹) (P;x) S (1 + (
It remains to prove that ( (P:z) 2 (1 CE) (i)) x).
LI
It suffices to ensure that, after removing at most items
g
5

---

Robust Sparsification via Sensitivity
from A, the sum of the remaining items is most (1
Hence, the overall runtime of Algorithm is ( (B)).
Cs) (P;x) æ) (where C' could be different).
By a Chernoff bound, we see that [B] - n. with probability at least 1 - 8.
m +0(
m log x)
m
Let G2 denote the set of outliers excluded by (P;
Let G2 = {f (f.1) E S ) to be removed from A.
Algorithm 2 runs in time O( ny + ID] = O + DD).
Clearly GG I t. We shall show that
Σ
51 (1+ Cε) C0 (P:x).
Back to Algorithm 3. By the analysis above, with prob- ability at least 0.99, the invocation of Uniform in ev- ery iteration of the for-loop generates a set B of size [B] S " + O(V m in time R 41( + +OV -. log It).. Line 3 runs in time to(n, E), Line 3 in time O(n) = ((to ()) and Line in time O(mT/e + n)) The overall runtime therefore O(V
SEA/G
Note that
log R). In total, the for-loop runs
m
[l) = Es(s) M1x + Ew..
(1.1)881Z= SEPI(G,US)
= -(x + Σ Ew
E f(x) (1W))EG,)
Oloo(n,)) + R- (
I log Rt). m
SES/Gs
(Lar))))
5. Applications
2 E
E f(x) SEALS (WW))EG2}3
E wsr f(x),
I-
FESYO,
Robust Regression The standard Eg-regression problem is ||x Ax - bll2. for which a standard approach
to solve min to reduce the dimension is to solve instead mingeR" ||SAr- Sbllg. where S is an ly-subspace embedding matrix for the concatenated matrix (A b). Regarding fg-subspace embeddings, the total sensitivity T = d and the vanilla coreset size can be made Q O ) using poly (n)
where we used the fact that P\ S is an e-coreset of A A\S. We need to upper bound E(fw)JEGss wy f(x). Suppose that there are nly copies of the same I in Gz \ \8. Then
Wyn'y m ((s(((]] Mx)
Σ WP
1(x)= (1))
Σ
time algorithm (Batson et al., 2012) or Q = O ((dlodd using classical leverage score sampling that runs in time O - poly(d) (see. e.g., (Drineas et al., 2006; Woodruff, 2014)). In the interest of runtime, we shall use leverage score sampling and thus, by Theorem 4, the (E, m)-corsset size is ( md llog vd + dlog ). Based on our coreset con- struction, we present Algorithm 4 for robust lz-regression with m outliers, which is to solve min F(m) (Ax b), where ((m) (u) denotes the sum of us except the m largest coordinates (in absolute values).
ef
(F
JEG,/S (Swy)EV
n'p
wy f(x)
Σ
m oAs((s)
/EG, (fw))EV
Σ
r Σ Wg ,(())
m
SEG (Fay)EV
(W.g))EV
< (1+ Σ f(x)
Theorem 5.1. Suppose that E (0, 1). Algorithm 4 returns an å which satisfies with probability at least 0.9 that
SEAYS
It follows that
(mm (Aø - b) s (1E) min F(mm) (Ar - b)
- (P;4)) 2 f(1)
(1- -(L+))
1
Σ f(x)
FER
The algorithm runs in time ((m/s)) + O(nd).
SESIG.
/EALS
2 Σ f(z)+ Σ f(x) Σ f(x). JESYG,
We need the following lemma, whose proof is deferred to Appendix A.
fEAVS
SEAYO.
Lemma 5.2. Suppose that A E Rud and b E R", where the leverage scores of A are bounded by 1/r. Let S e Raxa be a random diagonal matrix, where S. = v2 with probability 1/2 and S.. = 0 with probability 1/2. Let x² arg min Az - bll2 and ă = arg min ||SAz Sbll2. When 2 d log d + 1/s, it holds with probability at least 0.98 that A - bl12 S (1 + Ax bll2.
We have completed the proof of the correctness of the core- set. Next we analyse the runtime.
We begin by analyzing Algorithm 1. Line 1 can be im- plemented by indexing functions f E A as 1,2,...,n [A), generating independent Geometric(1/ /m) variables Z2. and selecting functions at indices Z1, Z1 + Zz, Z,+ Zz- + Zg. and so on. Thus, Line takes O( time, as- suming (1) time to generate a geometric random variable. Lines and 1 take i (I and O( B)) time, respectively.
Now we are ready to prove Theorem 5.1.
Proof of Theorem 5.1. Let x" arg min F(m)(As
6

---

Robust Sparsification via Sensitivity
Algorithm 4 RobustRegression/ (A, b, m)
(1 (1+ 1 p(() (Ax* b)
1-E 1-E
Input: A E Raad and b E RR, parameters and m
1 (1 + 14:) (Ax
Output: (1 + apprrox solution to min, F(m) (Ax - b) 1: (D, (wx}) + Coreset((A (A e), m) {Each row Dr.. E
This completes the proof of correctness. The overall failure probability is 0.01 + 0.02 = 0.03, which come from the event and Lemma 5.2.
Rd+ is associated with weight w
2: Rescale each row of D as D,,x < Vw,Di,
3: + -O(log d + 1/s)
By Theorem 4.1, coreset D has size N Ö D()= + O log d) and thus D' has size rN. Each iteration of the for-loop from Line 4 to Line 4 takes time (( Oppolymdd/z)). The whole for-loop takes the time L. poly(md/s) = (0(m)))(mm/c) which dominates the run- time after Line 1. For Line 1, we have to(n, e) = Ond + poly(d/E) and & (n) = O(nd + poly(d)) and thus Line I takes time Ond log md + +pllyydddss) with probability at least 0.99. The claimed overall runtime follows.
4: Duplicate each row of D by r times and rescale by /F
yielding D'= (H' 5²) {H' E Braxd and y' E R
5: L + 20(m)
6: X 0
7: i 1,2,..................... do
8: Generate a diagonal matrix S with i.i.d. diagonal entries Sa Unif([O, v23)
9: Compute x' gig [|HH' Sy/Il2
10: X
(x))
11: end for
Robust PCA Given A Raxd, the rank-k PCA of A is given by AUUT, where U E d has the top-k right singular vectors of A as columns. This U can also be viewed as the minimizer to minveull | A - AUU ||e where 4 = {U E Raxk U has orthonormal columns). J. In the robust setting, we let (x()(() to denote the sum of ||0: (where x, denotes the i-th row of X) except the m largest rows. The task is to solve minveu F(m) (A AUUT). Analogously to Theorem 5.1, we have
12:
Compute ā + xe (( 5/112
13:
Return
b) and D (H y) (after executing Line 2). Let denote the set of the indices of the largest m coordinates of Hxt y, where 2² arg ming ((")(x== y), and J' denote the rm indices in H'x yf that correspond to the indices in J.
Consider the event & that SH' contains none of the rows of indices in J. This event happens with probability 2-rm in one trial of Line 4, hence it will happen in at least one trial among L 20(m)) trials with probability least 0.99.
Theorem 5.3. Suppose that E (0, 11) There is algo- rithm with runtime d0(m) + O(nd) which outputs an U satisfying with probability at least 0.9 that
(AOOT A) S (1 14s) min F(m) (AUUT A)- GEll
Consider the trial in which & happens. In this case, let (H" v²" be the rows of (H' y') whose indices are outside J'. is clear that the leverage scores of H" are at most 1/r. By Lemma 5.2 and our choice of r, we have with probability at least 0.98 that
The proof is highly similar to that of Theorem 5.1 and is therefore postponed to Appendix B.
A popular application of coreset is to be employed pre- processing subroutine accelerate the existing algorithm. For example, Simonov et al. (2019) give an n O(d") time for PCA with m outliers for any m. For fixed m, we can first run Algorithm 3 to construct an (e, m))coreset S for robust PCA. So |S| = Ó(dme + de -2). Then we run the algorithm of (Simonov et al., 2019) on S to obtain a (1 + approximmaioo with running time (dme-1)0 + Ô(d log(ms-))).
|1'" v'1 < (1 e)²
min ||4 x v"11
#ER
-1++s) v = (1 + +) (rmm) (H' - s/)
It follows that
( -) y) = F(rm) =) v F(rm) (H'ss 3'''s'9) -y')
< |H''' -0--v" 1 2 21+ (mm) H' st y²) +)² 3)² (m) (m) H y)-
= (1 +
We remark that Simonov et al. (2019) also prove a lower bound that rules out any constant- factor approximation in time f(d)) assuming the ETH. At first glance, this appears to contradict the two algorithms given above. How- ever, this lower bound assumes that can be as large as ((n), in which case our algorithms would also run in time d", consistent with the lower bound.
Using the coreset properties and Lemma 1.2, we then have
F(m) b) S 1 -
(m))HH y)
E]+ (oa) - y)
1-6
(1+
Robust k-median For the k-median problem, the total sen- sitivity is O(k) (Langberg & Schulman, 2010; Feldman &
((m) (Ax² b)
1-8 8
7

---

Robust Sparsification via Sensitivity
distortion parameter distortion parameter
Table I: Runtimes (in seconds) for robust regression on our
Energy dataset
coresets and the whole dataset, with m = 10, for the Energy dataset (top) and the Emission dataset (bottom).
empirical
0.3
0.2
Coreset size
Mean
Standard deviation
0.1
1400
1.542
0.207
1500
1.602
0.214
1400
1500
coreset size
2000 2100
1600
1.625
0.237
1700
1.673
0.250
0.2
Emission dataset
1800
1.699
0.225
empirical
0.15
0
1900
1.781
0.301
2000
1.805
0.307
0.1
4
2
I-HH
2100
1.860
0.317
0.05
19734 (whole dataset)
13.981
0.249
1400
1500
coreset size
2000 2100
Coreset size
Mean
Standard deviation
Figure/ 1: Results of subspace embedding coresets with 10 and 0.25. Blue plots correspond to our coreset algorithm and the red plots to uniform sampling.
650
0.280
0.025
700
0.284
0.024
750
0.289
0.024
800
0.299
0.023
850
0.303
0.023
Langberg, 2011) and = = mmi ,--l)) (Cohen- Addad et al., 2022; Huang et al., 2024). Hence, the coreset size is O mal log mk & + min(k1/3 (-))) In Section C, we compare our results with existing robust coresets for clustering (Huang al., 2023a; 2025).
900
0.315
0,035
950
0.352
0.043
1000
0.396
0.022
36733 (whole dataset)
7.543
0.054
6. Experiments
different coreset sizes using all (ny,εy) pairs.
We conduct the experiment on two real-world datasets from the UCT Machine Learning Repository: Appliances En- engy Prediction' (referred as Energy) and Gas Turbine Emission (Emission). The Energy dataset has dimension 19735 x 28 and the Emission dataset 36733 x 11.
These results are compared with uniform sampling, which, given a specified size n, uniformly sample n rows to form a coresct B. For each n, we run 100 independent trials, calculating the empirical distortion parameter é max x x||] Bx| Ax 1| before. The mean and standard deviation of for each are then plotted.
Coreset Verification We verify that Algorithm 3 produces an effective coreset for subspace embedding with 2.
The results are shown in Figures 1. For the energy dataset, our coresets consistently achieve much smaller distortion than the preset value of æ = 0.25. Additionally, the distor- tion is significantly lower than that of uniform sampling, with the mean approximately 40%-50% smaller and also about standard deviation smaller. About 10% of the rows suffice to yield subspace embedding with a distortion parameter of at most 0.15. For the Emission dataset, we see again that the distortion is much lower than the preset value of = 0.25. The mean distortion is about one standard deviation smaller than that of uniform sampling. About 5% of the rows achieve distortion parameter of most 0.1.
Recall that for a matrix E Raxd, the function set F consists fz) 2),, where a; the i-th row of A. Fixing parameters and m, indepedently Algorithm 3 1000 times. Each run produces coreset Dj and we compute its empirical distortion parameter εj maxxex ((m)) (D;;; ((m) (F;z) where X Rd consists of 5000 samples drawn independently from (00, Ta). The size of 'D, is random and is rounded up ny- the smallest integer multiple of 100, and report éj as the dis- tortion parameter for the specified coreset size ný (we could pad D, with arbitrary unselected if E to achieve size nj, which would only reduce distortion). Finally, we plot the mean and standard deviation of the distortion parameter for
Solving Optimization Problem Now apply coresets to robust regression. Recall that, given A RRd and b E R". robust regression seeks to solve min F(m) (Ax - b), where F(u) is the sum of u, excluding the m largest coordinates (in absolute value).
appliaancesteeergyyyrred..c htttps://archive.iis usi edu asstarrbineeccotnndtoooo hwt.rraaaissssonaaaaaaaaeea.
the best of our knowledge, the only algorithms for ro-
8

---

Robust Sparsification via Sensitivity
0.5
0.5
0.02
0
0
8
0.4
0
0
0.4
0
0
8
8
6
0.3
00
0.3
0
0.01
0.2
0.2
1400
2100
1400
2100
1400
2100
Figure 2: Robust regression on the Energy dataset with m 10. Subplots show the relative error of the following quantities. Left: robust loss function p(m), Middle: -nrmm Right: 2n-norm
0.05
0.05
0.05
0.04
0.04
I
0.04
0.03
0.02
0
0
0
0
0
0.03
0.02
0
8
0.03
0.02
3
0.01
0.01
0.01
I
650
1000
650
1000
650
1000
Figure 3: Robust regression on the Emission dataset with m = 10. Subplots show the relative error of the following quantities. Left: robust loss function F(m), Middle: -nomm, Right: nn-nrm.
bust fz-regression with theoretical runtime guarantees that are substantially better than (*) are that Simonov et al. (2019) and our Algorithm 4. However, both remain computa- tionally expensive, with runtimes exponential in d? and m/c, respectively. The robust éz-regression problem, also known as the least trimmed squares, has a long history of research. A popular heuristic approach is FastLTS' (Rousseeuw & van Driessen, 2006), which, for example, is implemented in Maple's s statistics package (MapleSoft). We use FastLTTS in our experiments.
and Table 1. We observe that the runtimes on coresets are substantially smaller. Additionally, our coresets signif- icantly outperform uniform sampling in terms of the ob- jective function, achieving lower mean relative errors and smaller standard deviations. Our coresets achieve mean relative error of the objective function value in the range of 0.01 and 0.02 with coreset sizes of only 7.1% to 10.6% of the full dataset, significantly outperforming uniform sam- pling by at least one standard deviation. While the objective function well-approximated, the solution approximation shows larger relative error of approximately 0.25-0.3. We hypothesize that this is partly due to the large condition number of the data matrix (> 2878).
We perform 1000 trials with different coresets, solving the regression problem using FastLTTS for each coreset, yielding solutions ē for = 1,..., 1000. We also solve the original regression problem on the full data matrix using FastLTS to obtain a solution é. Next, we evaluate the approximation of the objective function (F(m)(A
The results for robust regression on the Emission dataset are presented in Figure and Table 1. As with the Energy dataset, we observe substantial reduction in runtimes when using coresets. Once again, our coresets significantly out- perform uniform sampling in terms of the objective function. The mean relative error of the objective function decreases from 0.02 to 0.01 as the coreset size increases from 2% to 2.7% of the data size. The solution error in both Ex and &g norms are similar for both our coresets and uniform sampling, with mean relative errors around 0.03. We hy- pothesize that this is partly due å having predominantly small coordinates except for one, making it relatively easy to approximate. However, small differences in the approxi- mation can result in much larger differences in the objective function value.
(m)) (At - b) 1| as well as the approximation of the solution in E2 and 6 norms: || 2 / ||:||| and ||06- - -|//=/////// /l. Finally, we plot these quantities against the size of the coresets (rounded to the nearest multiple of 100 for the Energy dataset and the nearest multiple of 50 for the Emission dataset) and compare with the results using uniform sampling. We also report the r on our coresets of different sizes (including computing the coresets) as well as for the entire dataset. The runtime for the entire dataset averaged over 10 trials.
The results for the Energy dataset are presented in Figure 2
'FastLTS is theoretically guaranteed converge the optimal solution the convergence rate not understood. In practice, the parameters are chosen heuristically.
*All experiments were 1165G7 @ 2.80GHz CPU and GB memory using Python ver- sion 3.12.8.
machine with an Intel i5-
9

---

Robust Sparsification via Sensitivity
Acknowledgements
J. W. (eds.), Advances in Neural Information Processing Systems, volume 34, pp- 17360-17372. Curran Asso- ciates, Inc., 2021b. URL https: httttp:://proceedingg
The authors would like to thank the anonymous reviewers for their helpful suggestions, particularly regarding the ex- panded discussion on related work. C.W. is supported by NTU research scholarship. Y. Li is supported in part by, and X. Xuan is supported by, Singapore Ministry of Education AcRF Tier grant 1.0E-22P20112--02
90Fd4488F5588844433311111 300 pdf.
Braverman, V., Cohen-Addad, V., Jiang, S., Krauthgamer, R., Schwiegelshohn, C., Toftrup, M. B., and Wu, X. The power of uniform sampling for coresets. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022. IEEE Computer Society, 2022.
D.P. Woodruff is supported in part by Simons Investigator Award and Office of Naval Research (ONR) award number N0001421 12647.
Impact Statement
Charikar, M., Khuller, S., Mount, D. M., and Narasimhan, G. Algorithms for facility location problems with outliers. SODA, volume 1, pp. 642-651. Citeseer, 2001.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Chen, K. A constant factor approximation algorithm for k-median clustering with outliers. In Proceedings the nineteenth annual ACM-SIAM symposium on Discrete algorithms, pp. 826-835, 2008.
References
Andersen, R. Modern Methods for Robust Regression. Quan- titative Applications the Social Sciences. SAGE Publi- cations, Inc., 2008
Chen, K. On coresets for k-median and k-means clustering in metric and euclidean spaces and their applications. SIAM Journal Computing, 39(3):923-947, 2009.
Bachem, O., Lucic, M., and Lattanzi, S. One-shot coresets: The case of k-clustering. In AISTATS, volume of Proceedings of Machine Learning Research, pp. 784-792.
Chhaya, R., Dasgupta, A., and Shit, S. On coresets for regularized regression. In International conference on machine learning, pp. 1866-1876. PMLR, 2020.
PMLR, 2018.
Bandyapadhyay, S., Fomin, F. V., and Simonov, K. On coresets for fair clustering metric and euclidean spaces and their applications. In ICALP, volume 198 of L.Ples, pp. 23:1-23:15. Schloss Dagstuhl- Leibniz-Zentrum für Informatik, 2021.
Cohen-Addad, V., Saulpic, D., and Schwiegelshohn, C. A new coreset framework for clustering, STOC, pp. 169- 182. ACM, 2021.
Cohen-Addad, V., Green Larsen, K., Saulpic, D., Schwiegelshohn, C., and Sheikh-Omar, O. A. Improved coresets for Euclidean k-means. Advances in Neural Information Processing Systems, 35:2679-2699 2022.
Batson, J., Spielman, D. A., and Srivastava, N. Twice- ramanujan sparsifiers. SIAM Journal Computing, 41 (6):1704-1721, 2012. doi: 10.1113/090772287.
Braverman, V., Jiang, H., Krauthgamer, R., and Wu, X. Coresets for ordered weighted clustering. In ICML,
Cohen-Addad, V., Larsen, K. G., Saulpic, D., and Schwiegelshohn, C. Towards optimal lower bounds for k-median and k-means coresets. In STOC, pp. 1038-1051. ACM, 2022.
volume 97 of Proceedings of Machine Learning Research, pp. 744-753. PMLR, 2019.
Braverman, V., Feldman, D., Lang, H., Statman, A., and Zhou, S. Efficient coreset constructions via sensitiv- ity sampling. In Balasubramanian, V. N. and Tsang, I. (eds.), Proceedings of The 13th Asian Conference on Machine Learning, volume 157 of Proceedings of Machine Learning Research, pp. 948-963, PMLR, 17- .ml..
Drineas, P., Mahoney, M. W., and Muthukrishnan, S. Sam- pling algorithms for 12 regression and applications. In Pro- ceedings of the Sevenleenth Annual ACM-SIAM Sympo- sium on Discrete Algorithm, SODA '06, pp. 1127-1136, USA, 2006. Society for Industrial and Applied Mathe- maties. ISBN 0898716055.
19 Nov 2021a.
/tess/ul55//raaaerma2laa.a
Feldman, D. and Langberg, M. A unified framework for approximating and clustering data. In STOC, pp. 569-578, ACM, 2011. https: http///xxvvv.. org.vv.orr/aaaa /bs/ 1106.1379.
Braverman, V., Jiang, S., Krauthgamer, R., and Wu, X. Core- sets for clustering with missing values. In Ranzato, M., Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan,
10

---

Robust Sparsification via Sensitivity
Feldman, D. and Schulman, L. J. Data reduction for weighted and outlier-resistant clustering. In Proceed- ings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pp. 1343-1354. SIAM, 2012.
Jiang, S. H.-C. and Lou, J. Coresets for robust clustering via black-box reductions to vanilla case. ICALP, 2025.
Jubran, I., Sanches Shayda, E. E.,, Newman, I. I., and Feld- man, D. Coresets for decision trees of signals. Advances in Neural Information Processing Systems, 34:30352- 30364, 2021.
Feldman, D., Schmidt, M., and Sohler, C. Turning big data into tiny data: Constant-size coresets for k-means, pea, and projective clustering. SIAM Comput. 49(3): 601-657, 2020.
Krishnaswamy, R., Li, S., and Sandeep. S. Constant ap- proximation for k-median and k-means with outliers via iterative rounding. In Proceedings of the 50th anmual ACM SIGACT symposium on theory of computing, pp. 646-659, 2018.
Har-Peled, S. and Kushal, A. Smaller coresets for k-median and k-means clustering, Discret. Comput, Geom., 37(1): 1-19,2007,
Har-Peled, S. and Mazumdar, S.
On coresets for k-manss and k-median clustering. STOC, pp. 291-300. ACM, 2004. attps://aazivy owg.z/v..rrg//ooo abs 1111112811........
Langberg, M. and Schulman, L. J. Universal epsilon- approximators for integrals. In SODA, pp. 598-607. SIAM, 2010.
Huang, L. and Vishnoi, N. K. Coresets for clustering in Euclidean spaces: importance sampling is nearly optimal. In STOC, pp. 1419.1129. ACM, 2020.
MapleSoft.
Least trimmed squares. https:
/ //www. wwplesoft. com /ttp://t/////tptttttte//s/// maple/view http://ww..pppttttsttttisssssee. ieeeeattTiimmmdduuurreeeett.eeee
Last
Huang, L., Jiang, S. H., Li, J., and Wu, X. Epsilon-corese coresets for clustering (with outliers) in doubling metrics. In FOCS, pp. 814 825, IEEE Computer Society, 2018.
accessed: 25 Jan 2025.
Munteanu, A., Schwiegelshohn, C., Sohler, C., and Woodruff, D. On coresets for logistic regression. Ad- vances in Neural Information Processing Systems, 31, 2018.
Huang, L., Jiang, S. H., and Vishnoi, N. K. Coresets for clustering with fairesss constraints. In NeurlPS, pp. 7587- 7598, 2019.
Rousseeuw, P. Regression techniques with high break- down point. In Mathematical Statistics and Applications, pp. 283-297. Springer Dordrecht, 1985.
Huang, L., Sudhir, K., and Vishmoi, N. Coresets for time series clustering. Ranzato, M., Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W. (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 22849 22862. Curran Associates, Inc., 2021. URL https: pttppe/eeeenns... neurips oc http:/cpcppppe/////./../
Roussccuw, P. J. and van Driessen, K. Computing LTS regression for large data sets. Data Min. Knowl. Discov., 12(1):29-45, 2006. doi: 10.1007/S 1061 8-005-0024-4.
Simonov, K. Fomin, F., Golovach, P., and Panolan, F. Refined complexity of PCA with outliers. In Chaud- huri, K. and Salakhutdinov, R. (eds.), Proceedings of the 36th International Conference on Machine Learn- ing, volume 97 of Proceedings of Machine Learning Research, pp. 5818-5826. PMLR, 09-15 Jun 2019. peatts::/ppooot h/pppppcocennn../// www.. wttp:sss.r..rrees/99/.
Paper.
pdf.
Huang, L., Jiang, S. H., Lou, J., and Wu, X. Near-optimal coresets for robust clustering. ICI.R 2023a.
Huang, L., Jiang, S. H.-C., Lou, J., and Wu, X. Near- optimal coresets for robust clustering. In The Eleventh International Conference on Learning Representations, 2023b. https: : www.//peereeee.eeeeeeeeeee / http://eee/oo.eeeeeeeeeeeeeoeooe forum? 1d=Nc12kRM@8V2
URL https: / s simonovl 9a html.
Sohler, C. and Woodruff, D. P. Strong coresets for k-median and subspace approximation: Goodbye dimension. In FOCS. pp. 802-813, IEEE Computer Society, 2018.
Huang, L., Li, J., and Wu, X. On optimal coreset construc- tion for euclidean (ke, 2) cluutsstei, In Proceedings of the 56th Annual ACM Symposium Theory of Computing, pp. 1 2024.
Wang. Z., Guo, Y., and Ding, H. Robust and fully-dyname learning (with out-
coreset for continuous-and-boume liers) problems. Advances in Neural Information Process- ing Systems, 34: 34:14319-1433 2021.
Huang, L., J., Lu, P., and Wu, X. Coresets for constrained clustering: General assignment constraints and improved size bounds. In SODA, 2025.
Woodruff, D. and Yasuda, T. Sharper bounds for lp sensi- tivity sampling. In Krause, A., Brunskill, E., Cho, K.

---

Robust Sparsification via Sensitivity
Engelharrd, B., Sabato, S., and Scarlet, J. (eds.), Pro- ceedings of the 40th International Conference Ma- chine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 37238-37272. PMLR, 23-29 Jul 2023. httphhttpss//prcceeeeeee hiw..nmmmm prrsss/ 2202//oodrruf223.hhoo html.
Woodruff, D. P. Sketching tool for numerical linear algebra. Foundations and Trends in Theoretical Computer Science, 101--))1--,7, 2014.
12

---

Robust Sparsification via Sensitivity
A. Proof of Lemma 5.2
Without loss of generality, we may assume that A has orthonormal columns. By the stardard proof for approximate regression such as that of Theorem 2.16 in (Woodruff, 2014), it suffices assume that has orthonormal columns and show that with
probability least 0.98, (i) || S SA oolop S 1/2 and (ii) || S S S V=l|e|12 for a specific vector u I such that A 0.
We first show (i). Let O; denote the i-th row of A (viewed as column vector), then
S SH - - ATS SH A
Σ ha,a
where G/s i.idd Rademacher variables. 1 a. a:)a llop (1/r) a,a llop = (1/r)]14 1/r. It follows from matrix Bernstein inequality that
We also have ||a,a llop
1a,13 S 1/r and (a Pllop
1 2
|A S SH -lopp
s 2de -r < 0.01
(where e > 0 is an absolute constant), provided that v 2 log d.
Next we show (ii). Let {m:} i.i.d. uniform variables on {0, 1]. We can then write
2
S ST Sull3
3.8
Σ 3.8
Σ
Ej +
1
&
2
2
3.8
Σ (aEelaj,ee)uge +
Es
ajUj, Σ agte
3.t
+
Σ E2 Σ
UzUjs apti
apts
+ Σ Uj Σ ag4b
Since A -==00 0, we know that E; 0,2; and so
S
ST Sull2 Σ Eeseela,
J.C.
which is quadratic form w.r.t. Rademacher variables & and
- < |ul|
EIAT ST STel
Σ
B(E/6)Ya, Elagaas0
J.L
Let G be matrix with Gjæ (aj, aebuyue. We can calculate
|G
Σ (e) -
Elaa 1lla0
1 < 7
Σ 13
||0|
J.8
and
||G||op (ddiddda)))))))))) Allop
sup (ddag(()AAr))) 1==1
13

---

Robust Sparsification via Sensitivity
|| sup max x))
||
||el|
sup max||a,;182111
||=||==1
< |
follows from Hanson- Hanson-Wright inequality that
Pr (IIIAA S Soll2 - EIIA S S 2 t) s 2xxp
(-emin
fa
1/////1 ))
|11l//122
Setting t = 2////// (where C' is some absolute constant), we see that with probability at least 0.99,
| ST Sull2 = |
C S <ellull2
provided that r 2 (C++ + 1)/s, establishing (ii).
B. Proof of Theorem 5.3
We present the algorithm in Algorithm 5.
Algorithm 5 RobustPCA(AA,,,))
Input: A E Raxd parameters and
Output: + ea-aproxx solution to minyeu ((m) (AUU - A)
1: (D, (w;)) t Coreset A, E, m) (Each row Di., E IR is associated with weight w;}
2: Rescale each row of D as D < Di, and set all weights to be 1
3: r < -OOlo d + 1/e)
4: Duplicate each row of D by times and rescale by vF. yielding D'
5: L + 20(mm)
6: 00
7: for 1,2, ...., L,,LL6 do
8: St random diagonal matrix with i...d. diagonal elements such that Sü is uniform on {0, v2)
9: Compute U' arg minyeu I|SD'UTT -SD'
10: XU
11: end for
12: Compute Ü + arg mingex F(rm) (D'UU - D
13: Return Ú
To begin, we can write ||AX Al
||AX All
Σ
|a;X a. ((X)
where a denotes the i-th row of A. We first show that the sensitivities for f((X) the i-th leverage score of A. Let A QR be the QR decomposition, where Q Bxd has orthonormal columns and R is invertible, then
| TQRXI
| T
ff
sup X=AX#0
|QRX|]
sup X:QX#0
[QX
Since has orthonormal columns, we know that ||X 1
|X Also, |1e] Q 113 < |le
Q
X
thus
0 S | Q12
14

---

Robust Sparsification via Sensitivity
where the equality is attained when X (QTes es QTe: i-th leverage score of A. This justifies Line of the algorithm.
qTex). Therefore, of lee Q12, which is exactly the
We also need to show an analogy of Lemma 5.2 for approximate PCA, which we state formally below.
Lemma B.1. Suppose that A E Raxd and its leverage scores are bounded by 1/r. Let 5 E R be random diagonal matrix, where S = 22 with probability 1/2 and S = 0 with probability 1/2. Let U = arg mignnuuulAAUT A/) and Ü arg minveu AAAU 2
When r 2 loog d + 1/E, it holds with probability at least 0.98 that
|Aũ - - & (1 + =)\(AU((*)) - AAIEe
Proof. The proof is nearly identical to that of Lemma 5.2 except that we need now to verify that | L -. V va), we have |
for a specific matrix Raxd such that V 0. Write V = (v) 12
ST SV
E ST S2. It follows from the calculations in the proof of Lemma 5.2 that
ST SVII = Σ
Sstelag, as) Σ (wi))(v))e
j.6
Thus,
1
I
S S 1
Now we can write G = E, Gū, where (Gi)j.e = (aj, (v)(s) and so
2
2 ΣΣ (or)
||G| s 22
1
Σ (1;)}
$ ,2
1
1 b
1
|G|oo I Σ
G4
lop
S
Σ
The desired result follows from Hanson
Hanson-Wright Wright inequality in the proof of Lemma 5.2.
The remainder of the proof is nearly identical to that of Theorem 5.1, we just give sketch below. Let
U
min (m)) (AU'U A), U = min F(m) (DUUT- - D).
Ueu
Ueul
Define J to be the of indices of the largest m rows (in Eg norm) of DUUT D and J' to be the rm indices in D'UUT- - D' that correspond to the indices in J.
Consider the event & that SD' contains none of the rows of indices in J'. With probability at least 0.99, this event happens in at least one of the L trials.
Consider the trial which & happens. Let D" be the resulting matrix from D' after removing rows of indices in J'. By the preceding lemma and our choice of r, it holds with probability at least 0.98 that
[U) 1 < (1 + ((r)) (D'UL(U)) - -D).
It follows that F(m) (DÜUT- - D) = F(r)) (DÜUT- D') & (1 + =)+ ((mm) (D'I(tt) D') = (1 (D - -D).
Using the coreset properties, we have
1 pm)) (DūTT D) <
(1 51 p(m) (DU*(UU) -D)
Ffm) (AÜOT - -A) <
(1 E)
<
p(m)
(DU*(U")T D
15

---

Robust Sparsification via Sensitivity
(1 +) F(m) (AU -A)
1-E - (1 + (EU -
This completes the proof of correctness.
The analysis of the failure probability and the runtime is identical to the proof of Theorem 5.1, where we compute the SVD of SD' to find U"
C. Partial Removal Model
In our definition, the robust loss function removes m functions regardless of their weights, which we will refer to as the full removal model. In clustering (Huang et al., 2023b; 2025), an alternative definition has been used, which allows partial removal. Instead of removing exactly m functions, this definition removes total weight of m. Formally, let F w)) i [n]} be weighted set of functions. The robust loss function is then defined
((m) (Fix)=
Σ Edfi(t). 1m1
min OS w Sw. ||r ler-err
|| 111m
Here, we write w/ & w for two vectors w, w E R" to mean w S wi for every i E [m].
Our main result is the following theorem, which shows that our coreset algorithm also works under this partial removal model.
Theorem C.1. For every = e (0, }) and m [n], the output of Algorithm 3 also an coresst for F under partial removal model with constant probability.
Proof. As in the proof of Theorem 4.1, we condition the event that all contributing functions are in S, which happens with constant probability.
Let P denote the output of Coresct (, m). We shall show that P an (e, moreessset under the partial removal model;
that is, for every e Rd and t {0,-.. .m.. it holds that ( (P:x) e (1 Cε) c (A; for some absolute constant
C' > 0.
We first prove that (P; < (1 + Ce) (A; Let by denote the set of outliers' excluded by _(0) (Aşx), then | s t. Let bg ((f.1) E L.). We claim that suffices to prove that
Σ f(x)+ Σ wy f(x) < (1 + 32) C( (A;
(2)
(
(Iw)))PIS
To see this, notice that the total weight of L, is at most
1 |az| S I, thus the left-hand-side of (2) is at least (()) (P;x).
To prove (2), we begin by noting that
Σ f(x) Σ f(x).
(3)
(11))EVL
JESYLz
Next, it remains to show that
EN wy f(x) (1++E) Σ f(x) + 22 C(9) (A;z),
(4)
(IwS))PPS
SE(ARS)VL
which, when combined with (3), will give exactly (2).
To prove (4), note that P P i
e-coreset of A \ by construction, so
Σ wy fx)
(SW)))S)S
"Since functions in have unit weights, we can assume without loss of generality that no outlier is partially removed.
16

---

Robust Sparsification via Sensitivity
(1++)) Σ ((x) SEAYs
(5)
= =1++) Σ ((+)+(1+ Σ (x))
(6)
(AI
$ (1++) Σ f(x) + (1++)) E (()))
SE(A/S
$ (1++) Σ +(x)+ 28 (A:z). JE(A\S))L
Here, (5) follows from the coreset property, (6) from the relationship of sets, (7) from the definition of interesting functions and the conditioning on the event that all contributing functions have been added into S, and (8) from the fact that & S 1 < 1.
remains to prove that ( (A: S (1 + Ce) (P:x) for some absolute constant C > Let w' E Pl denote the weight vector induced by (P: namely (P;z) = Eiteetee f.0 S w/ S w, and ||w - w'll st.
Let wyy w/y for each f e S and w for each f E A.S. We note that 0 S w" I 1 and ||| 11l-"1111 Eyes(1 (16(111w))) (1-))11))))- S || w/1l1 This means that w" is valid weight vector for ((1) (A;z) and we can proceed
C ( (A:x) S Σ Wuy f(x)
SEA
Σ w/y f(x) + w.g. ((x)
SES
SEAYS
Σ w/. [(()) + Σ f(x)
<
(fA))$
SEAYS
< Σ w/y ((x) (1z)+(11+ 25) Σ f(t)
(fA)E$
(SWE)M)
We claim that
Σ wy f(x) Σ wyx)((x++ + a (A;z).
(9)
(fw))EP($
(FW))PSS
then follows that which implies that (recalling that E 1041
(A:2) S 21+ Σ w/y f(x) + +((1 28) c( (A; (fwyjEP
1 1 2e
(A;o) <
((0) (P;z)
1-e(1 =(1 ( 22)
$ (1 + 62) ((9) (P:x).
Now we prove our claim (9). We have that
Σ
W/ f(-)(x)
Σ
f(x) + 1-lll-W - -wll1- sup
f(x)
(WI)EPIS
Σ
w/ f(x) +t E. c(t)
..( (A:x)
m
(SW))EPS
Σ
W/ f(x) + (A:2).
(SW))EPSS
The proof is now complete.
17

---

Robust Sparsification via Sensitivity
As corollary of the theorem, obtain improved coreset size for robust k-median under the partial removal model when the number of outliers is small. The current state-of-the-art (e, m) -coreset under this model has size m + ((k2-=t) (Huang al., 2025). In the preceding section, we demonstrated that for robust k-median coreset size under the full removal model, the coreset size is ( mk log mé + 2 min(k' ,, (). By Theorem C.I, this result also holds for the partial removal model. This improves upon the result in (Huang et al., 2025) when m. = o(ke-$)
D. Lower Bound for Subspace Embedding
We prove a lower bound on the size of the robust coreset for subspace embedding. Let L We define a(k- 1)d+2 et for every & [t] and E [d]. Suppose that the matrix A has rows 01, 0....... atd and we let (z 1(, 2> Our main result is the following theorem.
Theorem D.1. Any (e, m))-oreseet for F(x) Eie (x(x) has size at least 42
Proof. Let D be an cororest for F. Define D; (W ((e,, 1) [d]. So D U D.. Let F(x) = EEW wy (xx).
Since F(e,) and EwwnDeD f(e.) EWinSEDD wy, by the coreset property F(x) S (1 +) F(z), we have that,
Σ
wy S (1
(wFi)EDD
If [Dd S
m Tea
we know that
D - m
(())
Σ w/
D
(wg-fEED;
1
m
1I|
(1 + +)) -
(1 3τ) -
t
(1 32)
(t m)
m
S (1 32)
(1 m)
m
m
1 35
Fml) (e:)
1 -
(1 22) (p()(Ee))
But the coreset property asserts that ((m) 2 (1 E) (em) which is contradiction. So |Da]
and
|D| = Eí D. 2 md
le
18


Reviews:
[{"review_id": "SahOyU0CV0", "reviewer": "Reviewer_EHYA", "summary": "This manuscript shows that two simple conditions are sufficient for the existence of a small coreset for$F(m)$: $F(x)$ has a small vanilla coreset and has bounded total sensitivity. Then develops a general framework for constructing ε-coresets for several robust problems. Experiments on real-word datasets demonstrate that the coreset constructions are effective in approximating the loss function and considerably reduce the running time for robust regression problems while maintaining a good approximation of the objective function.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "We thank the reviewer for the questions. Below are our responses.\n\n    this scheme is only compared with uniform sampling. I understand that core sets are carefully designed preferential \n    sampling. So, are the results of such sampling better than those of random sampling?\n\nWe compared against uniform sampling as it is a standard and widely used baseline in the coreset literature. However, we acknowledge the reviewer's point regarding other sophisticated sampling methods. We will incorporate a comparison with leverage score sampling and a discussion in the revised manuscript.\n\n    The article assumes that the m to be removed is known. m is a parameter used to control the number of functions to be\n    removed, which has not been effectively discussed.\n\nOur formulation assumes a given $m$, consistent with the standard definition of problems like trimmed least squares and much of the existing robust coreset literature. Determining the value of $m$ is indeed a different and challenging problem, often tackled with heuristics that lack the strong guarantees our coreset framework enables. This falls outside the scope of this work, which is focused on guaranteed approximation for fixed $m$.\n\n    relative error of the experiments in the appendix is slightly worse than that in the main text\n\nWe agree with this point. The observed difference in relative error is dataset-dependent. Specifically, the Emission dataset (appendix) is nearly 1.8 times the size of the Energy dataset (main text). Since we compared performance using coresets of similar sizes for both, it is understandable that the relative error would be slightly higher when applied to the much larger Emission dataset.\n\n    With the robust formulation, has the context of facility been satisfactorily solved? What I mean is that we often take\n    advantage of the loopholes in other people's theoretical research and continue to conduct theoretical research on the \n    problem, but ignore the most real needs in the modeling process of this problem. Maybe this kind of theoretical \n    research is not practical.\n\nWhile constructing the coreset is a preprocessing step, it directly enables the application of robust algorithms to much larger datasets. For instance, established algorithms for trimmed least squares like FastLTS, while considered practically effective, have worst-case runtimes depending exponentially on $m$ and polynomially on $n$. Our coreset significantly reduces this dependency on $n$, replacing it with a much smaller $md$ (our coreset size is $O(md)$, assuming $\\epsilon$ is a constant). This allows applying such robust methods (with their existing guarantees or practical performance) in large-scale settings where they were previously intractable.\n\n    Why was robust coresets first proposed under the condition of clustering? What are the essential differences between the \n    PCA and regression promoted in this article and clustering?\n\nWe note that the concept of a coreset was first introduced by Har-Peled and Mazumdar in their seminal work as a tool for addressing clustering problems. Over the past two decades, coresets for clustering have received considerable attention, making it unsurprising that robust coresets were initially developed in this context. Our work provides a unifying framework for constructing robust strong coresets (guaranteeing approximation for all $x$) applicable to regression, PCA, and potentially clustering. To our knowledge, prior work on robust coresets for regression and PCA either did not exist or considered different, weaker definitions (e.g., local guarantees, like [WGD21], as discussed further in response to Reviewer YNPP) which do not provide the same level of worst-case theoretical guarantees as our strong coreset definition.\n\n[WGD21] Zixiu Wang, Yiwen Guo, and Hu Ding. Robust and fully-dynamic coreset for continuous-and-bounded learning (with outliers) problems. Advances in Neural Information Processing Systems 34 (2021): 14319-14331.", "claims_and_evidence": "The claims and proofs in this manuscript are clear and explicit, and the writing style is organic unity, loose in form but focused in content, reaching the level of a professor.", "methods_and_evaluation_criteria": "The method proposed in this manuscript is a new entry point for the construction of core sets and can well promote the development of related fields.", "theoretical_claims": "The theoretical derivation is logically rigorous, which is the author's greatest advantage and cannot be refuted. The proofs in the text and the appendix are rigorous and correct. As for practical applications, from the Impact Statement, it seems that this article does not care about.", "experimental_designs_or_analyses": "The experimental part of this article is relatively concise. I have two questions:\n\nIn the experimental part, this scheme is only compared with uniform sampling. I understand that core sets are carefully designed preferential sampling. So, are the results of such sampling better than those of random sampling?\n\nThe article assumes that the m to be removed is known (the form of the robust optimization problem defined in Section 1 uses m, and the input parameters of Algorithm 3 include m, m=10 given in your codes from). m is a parameter used to control the number of functions to be removed, which has not been effectively discussed.", "relation_to_broader_scientific_literature": "As stated in the manuscript: In the robust case, coresets with similar size and performance to the vanilla case were not known until recently in the context of clustering with outliers. Beyond clustering, no other robust coresets have been proposed. So, this is an extension of previous research.", "essential_references_not_discussed": "The author is authoritative in the relevant field, so no other relevant literature is not cited.", "other_strengths_and_weaknesses": "The paper is highly original, considering a wider range of robust core set selections and developing corresponding algorithms. It would be more conducive to promoting related research if the code was made public rather than limited to reviewers, but this is not necessary. The relevant arguments are clear and explicit. However, its importance and impact on the entire machine learning may be local and limited, especially when it comes to specific applications.", "other_comments_or_suggestions": "1. Practicality needs to be considered. If the greatest value of an algorithm improvement comes from the article itself, wouldn’t that be a pity?\n2. Publish the code within an appropriate scope so that more people can comment, improve and use it.", "questions_for_authors": "The discussion about random sampling and m value in the experimental part are two important issues that affect my score. In addition, there are two more issues, but they are relatively unimportant compared to the above issues.\n1、\tWith the robust formulation, has the context of facility been satisfactorily solved? What I mean is that we often take advantage of the loopholes in other people's theoretical research and continue to conduct theoretical research on the problem, but ignore the most real needs in the modeling process of this problem. Maybe this kind of theoretical research is not practical.\n2、\tWhy was robust coresets first proposed under the condition of clustering? What are the essential differences between the PCA and regression promoted in this article and clustering?", "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": "", "extra_scores": {}}, {"review_id": "FX5Om61OZS", "reviewer": "Reviewer_tJCf", "summary": "This paper studies a robust version of the $\\epsilon$-coreset construction for a function class $\\mathcal{F}$. Specifically, if we assume that there are $m$ outliers in $\\mathcal{F}$, the goal is to construct a coreset such that it will always be an $\\epsilon$-coreset even if we remove up to $m$ largest functions, valued with respect to any model $x$. This definition is strong in the sense that, it needs to hold for any model $x$, as the input to the functions. The construction is built upon vanilla coreset construction which refers to the non-robust counterpart, which includes a uniform sampling stage and a refining stage. The uniform sampling tries to collect most of the functions with large sensitivity; while the refining stage verifies the rest, and include any function that escapes the first stage. The paper also shows the results can be used in many problems such as robust linear regression and robust PCA.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "We thank the reviewer for the questions. Below are our responses.\n\n    This is a large running time when m  is large, and may prohibit realistic application of the algorithm to practical problems.\n\nWe acknowledge the exponential dependence on $m$. However, many existing robust algorithms, including practical ones like FastLTS or theoretical approaches, involve computations with worst-case complexities like $\\binom{n}{m} = \\exp(O(m\\log\\frac{n}{m}))$. Using our coresets, the runtime would become $\\exp(O(m\\log d))$ (assuming that $\\epsilon$ is a constant). In typical large-scale scenarios where $n\\gg d$ and $n\\gg m$, this is a significant improvement in the base of the exponent. \n\n     In the proof for Lemma 4.4, Line 212, why is the number of functions added not dependent on m?\n\nThe reviewer is correct to note the number of functions added in a single execution of Line 4 (Algorithm 3) does not explicitly depend on $m$. This line calls Algorithm 1, which adds functions whose sensitivity relative to the sampled set $B$ is at least $\\epsilon/4$. \nBy definition of total sensitivity, the sum of sensitivities is at most $T$, meaning at most $4T/\\epsilon$ functions can satisfy this $\\geq \\epsilon/4$ condition. \nThe threshold is $\\epsilon/4$ to ensure that each contributing function (defined with $\\epsilon/m$) is caught with sufficient probability ($1/(5m)$ as in Lemma 4.3), but the number of functions added in one execution of Algorithm 1 is bounded only in terms of $T$ and $\\epsilon$. \nAs explained above, the dependence on $m$ lies in the probability that each contributing function is captured, and this dependence enters the number of repetitions $R$ (Lines 2 and 3 of Algorithm 3).\n\n    Comparison with the paper \"Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCA, by I. Diakonikolas, D. Kane, A. Pensia, T. Pittas (ICML 2023).\"\n\nYes, the reviewer is correct. The crucial difference is that Diakonikolas et al. (2023) achieve nearly-linear time by leveraging assumptions about the data distribution. Our work provides guarantees in the worst-case setting without such distributional assumptions, which inherently makes the problem harder and often necessitates complexities exponential in parameters like $m$ or $d$.\n\n    If possible, could you also comment on your current running time in terms of how optimal it is?\n\nRegarding optimality for robust PCA: Simonov et al. (2019) established that no polynomial-time algorithm exists under standard complexity assumptions, suggesting that exponential dependency on some parameters is likely necessary for worst-case guarantees. They provide a lower bound of $m^{\\Omega(k)}$ and an upper bound of $n^{O(d^2)}$. Our coreset construction takes $d^{O(m)}$ time. While not directly comparable to their upper bound (better for small $m$, worse for large $m$), plugging our coreset (size $\\approx md$ assuming a constant $\\epsilon$) into their algorithm improves their runtime dependence on $n$, yielding roughly $(md)^{O(d^2)}$. \nThis significantly reduces the base compared to $n^{O(d^2)}$ when $n\\gg md$. While there remains a theoretical gap between our exponential runtime and known lower bounds, our approach offers a concrete improvement over existing worst-case algorithms by mitigating the dependence on $n$.", "claims_and_evidence": "The claims are supported with clear and convincing evidence. The claims are clearly stated, the algorithms are clearly presented, and the proofs are well organized and written.", "methods_and_evaluation_criteria": "The method makes sense. As the paper studies the coreset problem by proposing a robust version to the vanilla $\\epsilon$-coreset construction. The algorithm includes two stages: 1) uniform sampling to detect functions with large sensitivity; 2) constructing a vanilla coreset and refining it by adding more weight to functions with large sensitivity.", "theoretical_claims": "I checked most of the proofs in Section 4 (especially the key algorithm steps), and verified the application of these theorems in Section 5. All steps I checked are sound.", "experimental_designs_or_analyses": "I quickly scanned the experiments and found no issue.", "relation_to_broader_scientific_literature": "The result of this paper, can potentially be applied to many problems, such as regression, PCA, k-median problems, etc. As such, it can be used to build robust algorithms for many different machine learning problems. \n\nOn the other hand, this means the proposed technique is very general. Hence, if we were to solve a specific problem (for example, robust linear regression has a rich literature of its own), it might not be comparable to existing robust algorithms.", "essential_references_not_discussed": "See Questions for Authors.", "other_strengths_and_weaknesses": "The paper is very solid and the proof is sound.\n\nIn Theorem 5.1, the running time of the algorithm for robust regression, it is $d^{O(m)}e^{O(m/\\epsilon)} + O(nd)$, meaning that it is exponential in $m$. This is a large running time when $m$ is large, and may prohibit realistic application of the algorithm to practical problems.", "other_comments_or_suggestions": "In the proof for Lemma 4.4, Line 212, given that the total sensitivity is bounded by $T$, why is it that there are at most $\\frac{4T}{\\epsilon}$ functions added into $D$ in each repetition? I didn't quite get this part. Why is this function unrelated to $m$?", "questions_for_authors": "While this paper is compared to Simonov et al. 2019 for robust PCA, I wonder how do you compare it to more recent paper:\n\nNearly-Linear Time and Streaming Algorithms for Outlier-Robust PCA, by I. Diakonikolas, D. Kane, A. Pensia, T. Pittas (ICML 2023).\n\nSpecifically, the running time in this paper, and that of Simonov et al. 2019 is exponential in either $m$ or $d$, which is avoided in Diakonikolas et al. 2023. One reason might be that there seems no assumption of the $m$ outliers in this paper, while Diakonikolas et al. 2023 has distribution assumptions. Is this correct? Otherwise, the running time seems not reasonable. If possible, could you also comment on your current running time in terms of how optimal it is?", "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": "", "extra_scores": {"ethical_review_concerns": "N/A"}}, {"review_id": "5011zcOhnD", "reviewer": "Reviewer_L5ZF", "summary": "This work studies the coreset for robust optimization problems, where the loss function is defined to allow the removal of the highest $m$ costs. Research on robust coreset is relatively limited compared to the vanilla version. For functions with total sensitivity $T$, using the vanilla coreset algorithm and sensitivity oracle, the authors introduce a meta-algorithm for constructing a robust coreset of additional size $O(Tm/\\varepsilon\\log (Tm/\\varepsilon))$.\n\nRoughly speaking, the robust coreset consists of two parts. The first part is a set of contributing functions with unit weight, achieved through  $O(m\\log(Tm/\\varepsilon))$ rounds of sampling and selection. The second part is a refined coreset of the remaining functions. The refinement is necessary because the weight of a function in the vanilla coreset may be too large, potentially violating the definition of a robust coreset.\n\nIn addition to the meta-algorithm, the robust coreset offers a pathway to develop approximation algorithms for robust optimization problems. This paper presents improved algorithms for (robust) regression and PCA by demonstrating bounded total sensitivity.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "We thank the reviewer for the questions. Below are our responses.\n\n    [1] also explores the robust coreset within a broader context. And their robust coreset also consists of a vanilla \n    coreset and a sampling-based component of size $O(m/\\varepsilon)$ (can be improved with bounded doubling dimension).\n    However, in their study, the coreset property only holds for local $x$. And it includes a relaxiation of $m$, which\n    aligns with the result in [2]. Regrading the generality of this paper, I am curious whether their work can be\n    incorporated into your framework as a special case.\n\n    [1] Robust and Fully-Dynamic Coreset for Continuous-and-Bounded Learning (With Outliers) Problems. [2] Near-optimal Coresets for Robust Clustering.\n\nWe generally agree with the reviewer's comment on [1]. We note that the framework in [1] is based on assumptions that the loss functions satisfy the Lipschitz condition and the boundedness property, which are not assumed in our paper. Therefore, the two papers are not directly comparable. We also refer to our response to the second point of Reviewer YNPP for a detailed comparison.\n\n    From a practical standpoint, the robust coreset is less critical. This is because robust algorithms for optimization\n    problems with outliers often lack guaranteed approximation, leading to a reliance on heuristic methods for solutions. \n    In such cases, compressing the data as a preprocessing step becomes less significant, particularly when the compression\n    method is relatively complex and time-consuming.\n\nWe understand the concern regarding practicality, especially when heuristics are common. However, our robust coreset offers a significant advantage: it enables the use of, or accelerates, algorithms on datasets previously too large. For example, as detailed in the appendix, applying FastLTS for trimmed least squares to the full dataset took 7.543 seconds. By using our coreset, sized at only approximately 2.7\\% of the original data, the same FastLTS implementation achieved good accuracy in just 0.4 seconds.\n\nMore generally, for computationally intensive algorithms with potentially prohibitive runtimes (e.g., scaling as $\\binom{n}{m} = \\exp(O(m\\log\\frac{n}{m}))$ in the worst case),\nwe reduce the effective input size from $n$ to $O(md)$ (assuming $\\epsilon$ is a constant), making these algorithms more feasible for larger-scale problems.\n\n    The effectiveness of the proposed algorithm depends on a bound of total sensitivity  T and a running time of sensitivity \n    oracle t1. In other words, the algorithm is suitable for such problems that (1) total sensitivity is not large (2) The\n    time of computing sensitive is limited. Is there a large class of problems satisfying such condition besides the cases\n    presented?\n\nWhile current prominent applications of sensitivity sampling focus on regression, PCA, and clustering, the framework itself is general. \nWe emphasize that approximate sensitivities, rather than exact ones, are sufficient for coreset construction, making this approach adaptable to a wider range of problems where exact sensitivities might be intractable. Just as efficient algorithms were developed for approximating leverage scores, we anticipate similar progress for sensitivity estimation in other problems, and hope our work encourages such research by demonstrating the utility of sensitivity in the robust setting.\n\n    Line 098, “The total sensitivity of $\\mathcal{F}$” should be “The sensitivity of $\\mathcal{F}$” \n    Line 159, “A function $f$ is” , missing “$\\in A$\" \n    Line 217, $F$ in the Uniform() should be $A$ \n\nWe agree with the reviewer on all these points. We will correct them in the revised version.", "claims_and_evidence": "Theoretical paper. All claims are supported by corresponding proofs.", "methods_and_evaluation_criteria": "In the context of a theoretical paper, the primary evaluation criterion is the correctness of the main theorem. As for the experimental component, the results are meaningful and make sense in the field of coreset.", "theoretical_claims": "Yes. i have checked all the proofs in the main body of the paper", "experimental_designs_or_analyses": "Yes. The work aligns with the consistent experimental style of the coreset research.", "relation_to_broader_scientific_literature": "not sure", "essential_references_not_discussed": "[1] also explores the robust coreset within a broader context. And their robust coreset also consists of a vanilla coreset and a  sampling-based component of size $O(m/\\varepsilon)$ (can be improved with bounded doubling dimension). However, in their study, the coreset property only holds for local $x$.  And it includes a relaxiation of $m$, which aligns with the result in [2]. Regrading the generality of this paper, I am curious whether their work can be incorporated into your framework as a special case.\n\n\n---\n[1] Robust and Fully-Dynamic Coreset for Continuous-and-Bounded Learning (With Outliers) Problems. \n[2] Near-optimal Coresets for Robust Clustering.", "other_strengths_and_weaknesses": "## Strengths\n- The algorithm is concise and easy to implement, making it accessible for further development. The proof is clear and appears to be correct, based on my assessment. Its clarity enhances the understanding of the algorithm's validity and effectiveness.\n- The assumption of sensitivities is reasonable, as it is reasonable when regarding real-world downstream tasks such as PCA and regression.\n\n## Weaknesses\nFrom a practical standpoint, the robust coreset is less critical. This is because robust algorithms for optimization problems with outliers often lack guaranteed approximation, leading to a reliance on heuristic methods for solutions. In such cases, compressing the data as a preprocessing step becomes less significant, particularly when the compression method is relatively complex and time-consuming.", "other_comments_or_suggestions": "- Line 098, “The total sensitivity of $\\mathcal{F}$” should be “The sensitivity of $\\mathcal{F}$”\n- Line 159, “A function $f$ is” , missing “ $\\in A$ “\n- Line 217, $F$ in the Uniform() should be $A$", "questions_for_authors": "The effectiveness of the proposed algorithm depends on a bound of total sensitivity $T$ and a running time of sensitivity oracle $t_1$. In other words, the algorithm is suitable for such problems that (1) total sensitivity is not large (2) The time of computing sensitive is limited. Is there a large class of problems satisfying such condition besides the cases presented?", "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": "", "extra_scores": {}}, {"review_id": "EHREQtag2M", "reviewer": "Reviewer_YNPP", "summary": "The paper proposes a general framework for constructing ε-coresets for robust optimization problems of the form $\\min_{x \\in \\mathbb{R}^d} F(x) = \\sum_{i=1}^n F_i(x)$, where the robust version $F^{(m)}(x)$ aggregates all but the $m$ largest values of $F_i(x)$. This formulation is motivated by the need to handle outliers in machine learning tasks such as regression, PCA, and clustering. The authors develop an algorithm that constructs an ε-coreset of size $O(mT/\\varepsilon \\cdot \\log(mT/\\varepsilon)) + S$, where $T$ is the total sensitivity and $S$ is the size of a vanilla ε-coreset, assuming the latter exists. The approach leverages sensitivity sampling and a novel sensitivity flattening technique, yielding scalable algorithms with near-tight bounds for problems like $\\ell_2$-subspace embeddings.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "We thank the reviewer for the questions. Below are our responses.\n\n    Not very new problem. For example, the outlier problem as proposed in Question 1.1 has been commonly studied, which can be\n    traced back to [RL87].\n\nWe agree that robust estimation [RL87] is classical work in the field. However, our work addresses the distinct and more recent challenge of constructing coresets for robust objectives. This specific problem of robust coreset construction is not addressed in [RL87], and the theory significantly lags behind that of standard (non-robust) coresets. Our paper makes novel contributions specifically to this direction.\n\n    Lack of novelty and more closely related papers should be referred. The paper [WGD21] also studies robust coresets for \n    continuous-and-bounded learning, which already includes applications like regression, PCA, and clustering, as covered in \n    submitted paper. They share some similar technical ideas.\n\nWe thank the reviewer for pointing out [WGD21]. We will add a detailed discussion comparing our work in the revised manuscript. There are crucial differences:\n\n(1) The definition of a coreset in [WGD21] differs fundamentally from ours. Their coreset preserves the loss function within a ball, closer to the notion of a \"weak coreset\" in the literature. In contrast, a \"strong coreset\" preserves the loss function for all parameters, which is the standard, more powerful notion of a coreset in related work and is significantly harder to achieve in the robust setting. It also allows for arbitrary additional constraints in the optimization problem as it preserves the loss function for all parameters. Our work is the first to achieve this for a general class of loss functions.\n\n(2) The approximation guarantee in [WGD21] requires relaxing $m$ (allowing more points to be removed than specified) or depends on an implicit problem-dependent parameter $\\epsilon_0$. Our guarantee holds for the precise given $m$ without such a relaxation or hidden dependencies.\n\n(3) While both [WGD21] and our algorithm use two stages, the techniques differ substantially due to the different definitions of coresets. The first stage of [WGD21] identifies all local potential outliers (with respect to a fixed solution), while our first stage identifies all global \"contributing functions\" (regardless of the solution) through a novel process that combines uniform sampling with sensitivities. \nWhile both methods use a vanilla coreset in the second stage, we introduce an additional sensitivity-flattening step to satisfy the requirements of a strong coreset, which is absent in [WGD21]. \n\nTherefore, while related in appearance, [WGD21] tackles a different (weaker) coreset definition with distinct techniques. Our work provides the first strong robust coreset for this general setting, marking a significant theoretical advance.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "This paper is well-written, the proofs are clear, and seems sound to my knowledge.", "experimental_designs_or_analyses": "It proposes a general procedure that may extend vanilla coreset to coreset with outliers. The experimental part is clear.", "relation_to_broader_scientific_literature": "It may be useful to analyze large scale scientific data in physics, biology, and chemistry.", "essential_references_not_discussed": "Please see \"Other Strengths And Weaknesses\" part.", "other_strengths_and_weaknesses": "1. Not very new problem. For example, the outlier problem as proposed in **Question 1.1** has been commonly studied, which can be traced back to [RL87].\n2. Lack of novelty and more closely related papers should be referred.  The paper [WGD21] also studies robust coresets for  continuous-and-bounded learning, which **already includes applications like regression, PCA, and clustering, as covered in submitted paper**.  They share some similar technical ideas. \n\n[RL87] Peter J. Rousseeuw and Annick Leroy. Robust Regression and Outlier Detection. Wiley, 1987\n\n[WGD21] \"Robust and fully-dynamic coreset for continuous-and-bounded learning (with outliers) problems.\" *Advances in Neural Information Processing Systems* 34 (2021): 14319-14331.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "Please see \"Other Strengths And Weaknesses\" part.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper shows that under bounded sensitivity, robustly construction of coresets can be reduced to noise-free case which has a rich literature. Such reduction is accompanied a natural 2-stage algorithm. Reviewers agree that the results are interesting and novel, and that the techniques are useful.
Decision: Accept (poster)