Coresets for Classification – Simplified and Strengthened
Authors: Tung Mai
Cameron N Musco
Anup Rao
Venue: NeurIPS 2021 Poster (2021)
Keywords: coresets
logistic regression
importance sampling
leverage score sampling
lewis weight sampling

Abstract: We give relative error coresets for training linear classifiers with a broad class of loss functions, including the logistic loss and hinge loss. Our construction achieves $(1\pm \epsilon)$ relative error with $\tilde O(d \cdot \mu_y(X)^2/\epsilon^2)$ points, where $\mu_y(X)$ is a natural complexity measure of the data matrix $X \in \mathbb{R}^{n \times d}$ and label vector $y \in \{-1,1\}^n$, introduced by Munteanu et al. 2018. Our result is based on subsampling data points with probabilities proportional to their  $\ell_1$ $Lewis$ $weights$. It significantly improves on existing theoretical bounds and performs  well in practice, outperforming uniform subsampling along with other importance sampling methods. Our sampling distribution does not depend on the labels, so can be used for active learning. It also does not depend on the specific loss function, so a single coreset can be used  in multiple training scenarios.

Coresets for Classification - -Simliffied and Strengthened
Tung Mai Adobe Research tumai Cadobe. com
Cameron Musco University of Massachusetts Amherst cmusco@cs. umass. edu
Anup Rao Adobe Research
anuprao@adobe.comm com
Abstract
We give relative егrоr coresets for training linear classifiers with a broad class loss functions, including the logistic loss and hinge loss. Our construction achieves
(1 + e) relative error with Ö(d My (X)22/ /e²) points, where (xy is natural complexity measure of the data matrix X Raxd and label vector
1)" introduced in [MSSW18] 18]. Our result is based on subsampling data points with probabilities proportional to their ε Lewis weights. It significantly improves existing theoretical bounds and performs well in practice, outperforming uniform subsampling along with other importance sampling methods. Our sampling dis- tribution does not depend on the labels, so can be used for active learning. It also does not depend on the specific loss function, so single coresct can be used multiple training scenarios.
Introduction
Coresets are important tool in scalable machine learning. Given data points and some objective function, we seek to select subset of m < n data points such that minimizing the objective function those points (possibly where selected points weighted non-uniformly) will yield near minimizer over the full dataset. Coresets have been applied to problems ranging from clustering [HPM04, FL to principal component analysis [CEM* 15, FSS20J, linear regression [DMM06, DDH 09, CWW 19], to kernel density estimation [PT20], and beyond [AHPVO5, BLK17, SS18J.
We study coresets for linear classification. Given a data matrix X R with ith row I, and a label vector y E 111, the goal to compute 3* = arg min L(B), where L(5) =
Σi= [(((,,, 3) y/)) for a classification loss function f. such as the logistic loss f()) = In(1 + e) used logistic regression or hinge loss f() max(0, 2) used in soft-margin SVMs.
We seck to select a subset of m < n points .,,...., Z,m along with a corresponding set of weights and all Rd
w1....: Wmn such that, for some small
Σ wy f((zi, B) vi,) L(3) < L(3).
This relative error coreset guarantee ensures that if 3 E IRd computed to be the minimizer of the weighted loss over our m selected points, then L( < 1+c I-e L(
is well known that common classification loss functions such as the log and hinge losses do not admit relative error coresets with o(n) points [MSSWI8] To address this issue, Munteanu et al. introduce a natural notion of the complexity of the matrix X and label vector y. which we will also use to parameterize our results:
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Definition (Classification Complexity Measure [MSSW18)). For any X E Rnxd {-1,1}", (I( 1l2 where Dy E R
let (X)) = supazo X0) Il and (Dy and (D,X3) B) denote the set of positive and negative entries D
"h is a diagonal matrix with y as its diagonal,
Roughly, (X)(X) large when there is some parameter vector E I that produces significant imbalance between correctly classified and misclassified points. This occur e.g., when the data is exactly separable. However, as argued in [MSSWI8 we typically expect My (X) to be small.
1.1 Our Results
Our main result, formally stated in Corollary 9, is that sampling Ô {
points according to
the & Lewis weights of X and reweighting appropriately, yields a relative emror coresct satisfying (1) for the logistic loss, the hinge loss, and generally broad class of "hinge-like" losses. This significantly improves the previous state-of-the-arr using the same (X) parameterization, which
was ① (x) [MSSW18]. See Table for a detailed comparison with prior work.
Theoretical Approach. The Lewis weights are measure of the importance of rows in X, originally designed to sample rows in order to preserve X 8 for any /3 E IR [CP15]. They can be viewed as an generalization of the leverage scores which used in applications where one seeks preserve ||x [CLM+ 15J. Like the leverage scores, the Lewis weights can be approximated very efficiently, in (nnzz(X (X) + d²)) time where & 2.37 is the constant of fast matrix multiplication. They can also be approximated in streaming and online settings 1BDM+220 Our coreset constructions directly inherit these computational properties.
The & Lewis weights are natural sampling distribution for hinge-like loss functions, including the logistic loss, hinge loss, and the ReLU. These functions grow approximately linearly for positive but asymptote
for negative Thus, ignoring some technical details, it be shown that EL f((a4, B) 3/5) concentrates only better under sampling than >i=1 (It,13 ysl 1 X3111-
As shown by Cohen and Peng [CP15], taking Ödd/²) samples according to the Lewis weights of X (which are the same as those X) suffices to approximate ,I X for all 3 E I2d up to + e) relative error. We show in Thm. 8 using contraction bounds for Rademacher averages that it in turn suffices to approximate Σ f((;;, B3) ys) up to additive error roughly <[I|x|| + n). We then simply show in Corollaries and 9 that by setting c' (cc/Hy()) and applying Def. this result yields relative error coreset for a broad class of hinge-like loss functions including the ReLU, the log loss, and the hinge loss.
Samples
Error
Loss
Assumptions
Distribution
Ref.
Ô
relative
log. hinge
Def.
Lewis
Cors.
22
ReLU
d uex) δ
relative
log
Def.
sqrt lev. scores
[MSSW18]
/nva ,(x) e²
relative
log
Def.
sqri lev. scores
[MSSW18]
|mil] S Vi
rd
relative
log, hinge
regularization n (81),, n [1,1|,, or n [|01]
uniform
[CIM*19 19]
V
additive en
log
[| |avlla v
deterministic
[KL.19]
Table I: Comparison to prior work. Ö(-) hides logarithmic factors in the problem parameters. We note that the bounded norm assumption of [CIM* 19] can be removed by simply scaling X, giving a dependence the maximum
norm of X in the sample complexity. The importance sampling distributions of our work and [MSSWI] 18] are both fact a mixture with uniform sampling. Our work and [KL19, CIM 19] generalize to broader classes of loss functions for simplicity here focus just on the important logistic loss, hinge loss, and ReL.U.

---

Experimental Evaluation. In Sec 5, we compare our Lewis bright-based method to the square root of leverage score method of [MSSW18], uniform sampling as studied in [CIM*19] and an oblivious sketching algorithm of [MOW21]. We study performance in minimizing both the log and hinge losses, with and without regularization. We observe that our method typically far outperforms uniform sampling, even in some cases when regularization is used. It performs comparably to the method of IMSSW18,, seeming to outperform when the (X) complexity parameter is large.
1.2 Related Work
Our work is closely related to [MSSW18], which introduces the By (X) complexity measure. They give relative error coresets with worse polynomial dependences the parameters through a mixture of uniform sampling and sampling by the squaremotss of the leverage scores. This approach has the same intuition ours the squareroot leverage score sampling preserves the 'linear part' of the hinge-like loss function and the uniform sampling preserves the asymptoting piece. However, like many other works on coresets for logistic regression and other problems [HCB16, TF18, CIM+ 19, TMF20, TBFR21] the analysis of Munteanu et al. centers on the sensitivity framework. At best, this framework can achieve (2(d²) sample complexity one d factor comes from the total sensitivity of the problem, and the other from a VC dimension bound on the set of linear classifiers. To the best of our knowledge, our work is the first that avoids this sensitivity framework - Lewis weight sampling results are based on & matrix concentration result and give optimal linear dependence on the dimension
Regularized Classification Losses. Rather than using the (Xy()) parameterization of Def. 1, several other works [TF18, CIM 19] achieve relative error coresets for the log and hinge losses by assuming that the loss function is regularized by n R(3), where ε. > 0 is some parameter and R(3) is some norm e.g., || ||]|| or in the important case of soft-margin SVM, [81|2-
Curtin et al. show that simple uniform sampling gives relative error coreset with Ô (n2 points in this setting [CIM+ 19]. They also show that no coreset with (1-x55) points exists. In Appendix B, we tighten this lower bound, showing via a reduction to the INDEX problem in communication complexity that the Ö(n²~*) bound achieved by uniform sampling is in fact optimal.
Our theoretical results are incomparable to those of [CIM* 19]. However, empirically, Lewis weight sampling often far outperforms uniform sampling - see Sec. 5. Note that our results directly apply in the regularized setting- our relative error can only improve. However, our theoretical bounds do not actually improve with regularization, still depending on (xy()), (X), which is avoided by [CIM+19] 19].
Less directly, our work is connected to sampling and sketching algorithms for linear regression under different loss functions, often using variants of the leverage scores or Lewis weights [DDH* 09, CW14, * 18, CWW19, W1,, CD21]. It is also related to work on sketching methods that preserve the norms of vectors under nonlinear transformations, like the ReLU, often with applications to coresets or compressed sensing for neural networks [BJPD17, BOB 20, GM21J. Another line of related work includes coresets for standard optimization algorithms such as Frank- Wolfe algorithm [Cla10], Gilbert's 's algorithm [CHW12] and Stochastic Gradient Descent [HKS11].
Other Related Work.
2 Preliminaries
Notation. Throughout, for / R -> IR and vector y E R.,, we let fly) E R. denote the entrywise application of f to y. For vector y R" we let yı denote it's 8th entry. So f(y); f(u)).
For data matrix X E Rand with rows X1, ,i,..., Tn E IRd and label vector y E 11, we consider classification loss functions of the form L(3) En [(xx, B) 31) Σ ((D,x3)) where Dy R is the diagonal matrix with y its diagonal. For simplicity, we write X instead of Dy throughout, since we can think of the labels as just being incorporated into X by flipping the signs of [[x,,) 1l1
its rows. Similarly, we write the complexity parameter of Def. 1 as xXX) sup340 [[x3)-II
Throughout we will call f()) In(1 + e²) the logistic loss and [(=) = max (0, + 2) the hinge loss. Note that these functions have the sign of = flipped from the typical convention. This is just notational - we can always negate X or 33 and have an identical loss function. We use these versions as they are both lx close to the ReLU function, fact that we will leverage in our analysis.
3

---

Basic sampling results. Our coreset construction is based on sampling with the & Lewis weights. We define these weights and state fundamental results on Lewis weight sampling and below. Definition 2 (f1 Lewis Weights [CP15]). For any X E Raxd the & Lewis weights are the unique values (X))..... ...., Tn (X) such that, letting W RRxx be the diagonal matrix with (XTr(X)..... T/ (X) as its diagonal. for all i,
Tx())² = o (X"
where for any matrix M, M is the pseudoinverse. M --1 when M square and full-un full-rank. Theorem 3 (f1 Lewis Weight Sampling), Consider any X E Brxd and set of sampling values pa with E P: and p; exr,X) log(m/6) for all i, where is universal constant. we generate a matrix S mx with each row chosen independently the ith standard basis vector times l/ps with probability ps/m then there exists an i > such that if a E 1-1,1 is chosen with independent Rademacher entries
2
E
sup B:
Σ oi [S
S
In particular, if each pe is a scaling of constant factor approximation to the Lewis weight Ti (X) (which means that vi, (X) S P. (X²(X) (X)for for some constants c, S has m O (dlosld/be rows.
Theorem 3 is implicit in [CP15], following from the proof of Lemma 7.4, which shows a high probability bound proven on page 29 of the arXiv version. The claim on the bound on m can be derived as follows. We have Σ (X) d, which gives that m = Σ P: I (og(m/8)). /c2 for some constant If we set m Od d/ (6e)) we have log(m/
[|SX3:1| 1| via the moment bound stated above. This moment bound is
((lo(dd((ée) which gives m cd log(m/00 (oogmm////"
as needed.
We will translate the above moment bound give approximate bounds for classification loss functions like the ReLU, logistic loss, and hinge loss, using the following standard result on Rademacher complexities:
Theorem (Ledoux- (Leaoux-Talagrand contraction, c.f. [Duc]). Consider V C R along with L-Lipschitz functions fi I R with f((0) O. Then for any & if (-1,1) is chosen with independent Rademacher entries,
m
m
sup
Σ 1=1
(2L)
sup Σ
aeti
i=1
3 Warm Up: Coresets for ReLU Regression
We start by showing that & Lewis weight sampling yields (1 + e)-relative error coreset for ReLU regression, under the complexity assumption of Def. 1. Our proofs for log loss, hinge loss, and other hinge-like loss functions will follow similar structure, with some added complexities.
We first show that Lewis weight sampling gives a coreset with additive error e|| By setting è' e/p(X), then casily obtain relative error coreset under the assumption of Def. 1.
Theorem 5 (ReLU Regression Additive Error Coreset). Consider X E Rn and let ReLU(z) =
max(0, 2) for all R. For of sampling values ps with Ex P; m and pt e:Ti(X) log(m//) for all i, where is universal constant, if generate S E Rmxx with each chosen indepen- dently as the ith standard basis vector times 1/ps with probability p./ pa/m then with probability at least 1 - 8. for all B E ERd
m Σ
DISRELU(XB)] - - ReLU(XX), < x||1X8111
If each Pi is a scaling of a constant factor approximation to the Lewis weight Ti (X),, S has m = O d (18)) 5
rows.

---

Corollary 6 (ReLU Regression Relative Error Coreset), Consider the setting of Thm. 5, where Di=1 Dj = m and pi exT(X) log(m//)) for all With probability at least - B E IR4, (S B)]= Ei= ReLU(())) Se Σi=1 (eLUU(X 1f each pt is scaling of
constant factor upproximation the Lewis weight (x)),, has m O (2lgg//66)))
rows.
Proof of Corollary 6. We have
Σ ReLU(X3);
Σ [X 11X3)*
(2)
4[xA].20
Additionally, since by definition p(X) = suP340
1(x)) sup B20 [[x
((x8) 11
((x;)-1:
X 1 [1 |1
1Ixx3)+ 11 2 ((X).
(3)
Combining (2) with (3) gives that Ex= ReLU(XP); 2 T+x(X] || || 1, which then completes the corollary after applying Theorem 5 with e' I+x(X)
1
Proof of Theurem 5. We prove the theorem restricted to 3 such that || 1. Since the ReLU function is linear in that ReI.U(cz) = c ReI.U(z), this yields the complete theorem via scaling. It suffices to prove that there exists some such that
m Is ReLU - Σ ReLU(X3), sup
def
UAE
S -
8:1
The theorem then follows via Markov's incquality and the monotonicity of of for E O. Via standard symmetrization argument (c.f. the Proof of Theorem 7.4 in [CP15]) we have
m
B B
2 2
sup 8111811111
Σ
S,a
where a E (-1, 14.1) 1)m has independent Rademacher random entries. We can then apply, for each fixed value of the Ledoux-Taie -aalarrnd contraction theorem (Theorem with (SX3: ||x = 1} and fz( = Re) for all i. f((z) is 1-Lipschitz with f(0) O. This gives
B B
E S,0
sup
Σ [SX
< (de)*
P:II
11 i=1
for some f > only affects the sample complexity by a constant factor.
1 by Theorem 3. This completes the theorem after adjusting by factor of 4, which
Extension to the Hinge Like Loss Functions
We next extend Theorem 5 to family of 'nice hinge functions' which includes the hinge loss f(z) max(0, 1 1+ 2) and the log loss f(z) = In(1 e²). These functions present two additional challenges: 1) they are generally not linear in that f 2) c f(z), assumption which is used in the proof of Theorem to restrict to considering 3 with |X
and 2) they are not contractions with f0) = 0, a property which was used to apply the Ledoux- -alourrn contraction theorem.
Definition (Nice Hinge Function). call f - R an (I, a,, az)-nice hinge function for fixed constants L, a1 and a2
(1) is I--Lipschitz
(2) ReLU(=)] an for all (3) f(=) 02 for all 2 0.
We start with an additive error coreset result nice hinge functions. We then show that under the additional assumption of > 0. the additive error achieved is small compared to Σ [(X33); 3), yielding a relative error coreset. This gives our main results for both the hinge loss and log loss, which are (1, 1, -ice and (1, In 2, In -ice hinge functions respectively.
5

---

Theorem 8 (Nice Hinge Function Additive Error Coreset). Consider X E Baxd and let f: R. - E. be an (L, 01, (2) -nice hinge function (Def. 7). For set of sampling values p; with Di=1 Pi = m
and Pi C { for all where
c- c-xxx(11 L, )1)² .log logín mas(t_LLai)//emm and
a fixed constant, if we generate S E =nxx with each row chosen independently as the ith standard basis vector times 1/p, with probability pc/m, then with probability at least 1 5, v E R
Σ (ss(
Σ f(XB), c (11 +
Observe that for fixed function f. L, 01 are constant and so, if each is scaling of a constant factor approximation to max(T;(XX), 1/n), S has m O (oe)(log(//)dd((6)))) Ô (á) rows.
Proof. Let ej log( m.x() for some constant 01. We will show that for each integer
j E [--J,J], with probability at least 1
27
sup 9 21+1]
Σ [SS(33))] - Σ ((X 2. + m.
(4)
Via union bound this gives the theorem for all & with || 12--1,2%. We then just need to handle the case of X with norm outside this range - i.e. when ||x is polynomially small or polynomially large n and other problem parameters. We will take a union bound over the failure probabilities for these cases, and after adjusting ó by constant, have the complete theorem. We make the argument for |X3] l1 outside [ ',2" first.
Small Norm. For 3 with || < 2 |ll < < ;. Thus, f(X8), E c, for all i. Thus by triangle inqquality, and the fact that f(0) S ReLU(()) + 01 a1:
m
T Σ ((X3),
m
m
sup 01
Σ [S((X)))
01
1/p5: Σ
+
1/p + n
(5)
where 1/Pj, is value of the single nonzero entry in the hthh row of S, which samples index ja from f(X3). Let Zi...., Zm be i.i.d,, each taking value 1/p, with probability for all j E [n]. Then
Σ 1/Pb.
Σ 12 - -
For all j [n] we have P3 > bound, if the constant e is chosen large enough we have:
(x
e-max(1,, (lg((110) ne"
so applying a Bernstein
2
m
en 1/ps. - nn max a1)
en2 /2 (1,)))
8
<
2exp
S
clog(J/6) ma))) + clog(J/6 max((
n²ess
4.
(6)
Combining (6) with (5), with probability at least 6, we have
" (is((x3)) Σ((8)) @1 en
m
sup 8: 1:18811
m1 + (2+ max(1, n n.
Adjusting constants on this gives the theorem for 3 with || 2-
Large Norm. We next consider 3 with || 2 2'. Since by assumption [f() - ReLU(=)) a for all = E R, we can apply triangle inequality to give for any 3 E Rdd
Sf(x)) Σ ((X 5
Σ ReLU(X)), +
Σ
1/pj. +

---

Applying Theorem 5 and the bound on E 1/pj, given in (6), we thus have, with probability at least 1 - 26, for all B with ||11 1
2 2
m
|f((x3))
Σ f(x3),
- C ||1x8111 + 30tn S e
1=1
where the final bound uses that || 2 2 >
( for a large enough constant c1. This
gives the theorem for 3 with | 2 2
Bounded Norm. We now return to proving that (4) holds for any j E [-J, J] with probability at least 27 Let =(=)= - f(0). Then for any 3 E TRd we have:
m
" Σ ((X
m
"
m
[S((X)))
Σ [s((X))
Σ ((X)))
+ +(0)
Σ
1/ps
We again apply the bound on Σ 1/pj, given in (6) and the fact that ʃ(0) S 01 This gives that with probability at least 4J for all B E R2,
Σ [((()) - Σ ((X3))
m
m Σ
[F(X3)
n Σ [(X3))) + +
en
max(1, (1)
[ff(x))]
Σ
f([x)])
+ n.
(7)
Now, for f 2 0, by standard symmetrization argument (c.f. the proof of Thm. 7.4 in [CP15)),
def B
Σ [S((X3))) E1
< 2 E
Σ a. (((f((()))
sup
sup A 22
a 21+11
where 1] has independent Rademacher random entries. We can then apply, for each fixed value of S the Ledoux- Talagran contraction theorem (Thm. 4) with V = (SX3: |133| E [25, 2] and fa(=) 1/pj. f(P;; =). Note that f+(0) = 0 since f(0) 0. Additionally, fi is
L-Lipschitz since assumption f(z) is L-Lipschitz f(pj, 2) is (p,, Li-Lipschitz. We have,
{((x3))) = 1/pj, flea. L/p,, (X [8f(X
So. applying Theorem 3, for some we have, since p. 2 CT((X) for C = cmax (ng(log( max(1, 1, L, a1 /e)m/m) = (mmxx(1, L2)- log (Jm/))).
6 < <AL) (e/D) 4J (20t2ee.
B S (
E S.a
sup 8:11
Σ [S
21+1
Adjusting by constant, this gives via Markov's inequality that with probability at least 4,
Σ [S((X)));
F(XB); 2
sup 8: x 2 2/-1
In combination with (7), we then have that probability at least
2J'
m
n Σ [(Xx)))
[S((X))
20 n.n.
sup 81 E|2 20+1
1=1
This gives (4) and completes the theorem.

---

4.1 Relative Error Coresets
Our relative error coreset result for nice hinge functions follows as a simple corollary of Thm. 8. The proof is analogous to the proof of Cor. 6, and given in the appendix.
Corollary (Nice Hinge Function- - Relative Error Coreset). Consider the setting of Thm. 8 under the additional assumption that 02 > 0. If
Limi Pi = m and pi 2 C (,)x( for all i, where C c. max(1, L, 01, / 1/22) 10, log log(n max(1,L.a; (/a)))/////)) and i a fixed constant,
with probability 2 1 - 5. for all 3 E Rd
th [(((3) - Ei=1 ((
For fixed J()), T., 0,,01;0 (2 constant and so, if each p. is scaling of constant factor approximation to max(r; (X) 1/n), S has 0 (j(()"1oo) log(log(ng (/0 = =Ō [d(x)) rows. This
gives our main result for the hinge and log losses, which are (1,1,1) and (1, in 2, In 2i-ni
5 Empirical Evaluation
We now compare our method (lewis), square root of leverage score method (12s) of [MSSW18] uniform sampling (uniform), and an oblivious sketching algorithm (sketch) of [MOW21]. Our evaluation uses the codebase of [MSSW 18], which was generously shared with us.
Implementation. Lewis weights are computed via an iterative algorithm given in [CP15], which involves computing leverage scores of a reweighted input matrix in each iteration. We typically don't ton't need many iterations to reach convergence for all datasets we used 20 iterations and observed relative difference between successive iterations around 10-6, Leverage scores are also needed by the 12s routine, and are computed via the numpy qr factorization routine when possible. One dataset (CoveRtypE) involves an almost singular matrix, we resorted to the pinv routine numpy.
We note that [MSSWI8 18] used a fast random sketching- based QR decomposition to compute the leverage scores this can also be applied Lewis weight computation. The number of iterations of the Lewis weight algorithm can also be reduced - it seems that roughly 5 iterations are sufficient for practical purposes. Lewis weight computation will then take about times as much time as 12s weight computation.
Datasets. We the same three datasets as in [MSSW18]. The WEBB SPAM data consists of 350,000 unigrams with 127 features from web pages with 61% positive labels. The task is is to classify as spam or not. The other two datasets are loaded from scikit learn library². COvERTYPE consists of 58 581,012 cartographic observations of different forests with 54 features and 49% positive labels. The task to predict the type of tree. KDD CUP '99 has 494,021 points with 41 features and 20% positive labels. The task is to detect network intrusions.
two loss functions: 1) logistic loss f(z) = In(1 + e and 2) hinge loss f(z) = max(0, 1 ++2) 2). As before, we use 2 = (8, x)) .y. Note that [MSSW 18] gives guarantees only for logistic loss for 12s. We also evaluate the above two losses with regularization term 0,5|| We evaluate sketch only for logistic loss without any regularization - which is what is was designed for. Though it sometime preforms reasonably in other cases, it can have very high variance or high error for certain combinations of loss functions and datasets.
Loss functions. We evaluate the algorithms
Evaluation. Our evaluation follows that of [MSSW18]. Let 3 be the parameter vector minimizing the sum of the loss function the coreset and 8 be the true minimizer. We report the relative loss [L(B")- z(,3 where I(33) = Σ. f((2,, B) y1) is the sum of loss over all data points. Ideally, this ratio should be close to O. In Figure 1, we plot the log relative loss as function of coreset size.
L(3*)
We observe that Lewis weights sampling performs better than all other methods on KDD CUP '99 for both loss functions, with and without regularization. Our bounds for lewis give a better dependence on the complexity parameter Moy (Xy(X than the bounds [MSSW18] for 12s, and this agrees with the fact that the value of Hly (X) is high for KDD CUp '99. [MSSWIC 18] estimated (X) values of WEBB SPAM, COVERTYPE and KDD CUP '99 to be 4.39, 1.86 and 35.18 respectively. For COVERTYPE and
'httss//www.esic.... ntu edu.tw/ wwt.t://wii//issssttooo//////o// gjin//iissmmtook/danasssss
httpss//scikittleamm...
8

---

WEBB SPAM
COVERTYPE
KDD CUP '99
uni
174
12s
LOGISTIC
lente
lows
scrtzh
-1.1
skooch
22
2500
2000
7520
12000
12500 15000
2500
5050
7500
1000) 13500
15000
5000
10000
15000 Z0ACO 25000 20000
relaced 5000
redaced stoe
rodnand 5620
0.5
-1.
log mos mnaateeeen
HINGE
10.5
-0.5
-20
-1.
2000
5001
7000
1000 12590 150m
3500
5000
7501 10000 12500
17600
5500
100m
15950 350m 25000 30000
redlacd stc
redlood stoe
1.2 LOGISTIC
Levia
begawate mikeow SmT
0.0
-0.5
0.0
-1.0
-10
-2.0
2300
19300
13500 13000
2500
5000
1500
1500)
15003
3500
10000
15020
25000
20000
unlf
0.0
1.2 HINGE
-0.5
-15
-0.
1.0
-15
-25
2500
7500 10000 12590 150m
2500 5920
7500 10000 12500
12000
5500 100m 15900 20000 25000 3000K
rolaned..e 5600
zolusod 5600
Figure 1: Each plot represents the performance of the studied methods with respect one combination of dataset and loss function. The z-axis shows the coreset size, and the y-axis shows the log scale of the relative error. Each experiment is run 100 times. The solid line represents the median error. The lower and upper boundary lines represent the 25th and 75th percentiles respectively.
WEBB SPAM, the performance of lewis is comparable or a little worse than that of 12s. Furthermore, on these two datasets, with regularization, uniform sampling does relatively well for very small sample sizes, which agrees with the results of [CIM*11 19].
Comparison of distributions. To give better intuition behind our results, we illustrate how different the Lewis weights are from the other sampling distributions on our three datasets Fig. 3. Given two distributions p (pI, PP,...P and (41, (Q,,P2.... .., 4n), we plot the frequencies of [max((p/qe /q: q (. We let p to be the uniform or 12s distributions and take q to be Lewis weights. We observe that the Lewis weights are far from uniform all datasets, especially KDD CUP '99. This may explain why lewis performs so well on this dataset. 12s and lewis are much closer in general, explaining their relatively similar performance. Note that these score comparisons on the data matrix X, and not the label vector y. which does not affect the leverage scores or Lewis weights. Thus, they only give partial picture of the differences between methods. In particular, theoretical bounds and the bounds for 12s in IMSSW18) W18] both depend on (X,,)), which depends on the label vector.
based only
Classification Error Here, we include additional experimental results based on reviewer feedback. For various coreset sizes and datasets, we plot the log(1 auc) for each of the methods. arc stands

---

WEBB SPAM
COVERTYPE
KDD CUP '99
122
Tadatt 251
"TocS snat
UNIFORM
Figure 2: Comparison of sampling distributions.
for Areas Under the Curve. A perfect classifier has and all other classifiers have 1. The lower the curve is in the plot, better is as a classifier. Each plot is result 100 trials.
WEBB SPAM
COVERTYPE
KDD CUP '99
u
D5
0.42
Intt
-0.43
-1.75
-0.50
200
-0.3
-1.4
-0.00
-1.00
2010
0300
5003
2000
6000
5000
2020
5000
0020
00 dio
Figure 3: Comparison of classification accuracy.
10

---

Acknowledgments and Disclosure of Funding
Cameron Musco was partially supported by Adobe Research grant, along with NSF Grants 2046235 and 1763618.
References
[AHPV05]
Pankaj K Agarwal, Sariel Har-Peled, and Kasturi R Varadarajan. Geometric approxima- tion via coresets. Combinatorial and Computational Geometry, 52:1-30, 2005.
[ALS* 18]
Alexandr Andoni, Chengyu Lin, Ying Sheng, Peilin Zhong, and Ruiqi Zhong. Sub- space embedding and linear regression with Orlicz norm. In Proceedings of the 35th International Conference Machine Learning (ICML), 2018.
[BDM+20] Vladimir Braverman, Petros Drineas, Cameron Musco, Christopher Musco, Jalaj Upad- hyay. David P Woodruff, and Samson Zhou. Near optimal linear algebra in the online and sliding window models. In Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2020.
[BJPD17] Ashish Bora, Ajil Jalal, Eric Price, and Alexandros G Dimakis. Compressed sensing using generative models. In Proceedings of the 34th International Conference on Machine Learning (ICML), 2017.
[BLK17] Olivier Bachem, Mario Lucic, and Andreas Krause. Practical coreset constructions for machine learning. arXiv:/7033 000476, 2017.
[BOB [BOB+20] Mussay Ben, Margarita Osadchy, Vladimir Braverman, Samson Zhou, and Dan Feldman. Data-independent neural pruning via coresets. In Proceedings of the 8th International Conference on Learning Representations (ICLR), 2020.
[CD21] Xue Chen and Michal Dereziński. Query complexity of least absolute deviation regres- sion via robust uniform convergence. arXiv:2102.022
2021.
(CHM+15) Michael B Cohen, Sam Elder, Cameron Musco, Christopher Musco, and Madalina Persu. Dimensionality reduction for k-means clustering and low rank approximation. In Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC), 2015.
[CHW12] Kenneth I. Clarkson, Elad Hazan, and David P Woodruff. Sublinear optimization for machine learning. Journal of the ACM (JACM), 59(5):1-49) 2012.
[CIM* 19] Ryan R Curtin, Sungjin Im, Ben Moseley, Kirk Pruhs, and Alireza Samadian. On coresets for regularized loss minimization. arXiv: /9055 2019.
[Cla10]
Kenneth L Clarkson. Coresets, sparse greedy approximation, and the frank-wolfe algorithm. ACM Transactions on Algorithms (TALG), 6(4):1-30, 2010.
[CLM+15] Michael B Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, and Aaron Sidford. Uniform sampling for matrix approximation. In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, pages 181-190, 2015.
[CP15) Michael B Cohen and Richard Peng. lp row sampling by Lewis weights. In Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC). https://arxiv org/abs// abs/ /41...11...2 0588, 2015.
org/
[CW14] Kenneth L Clarkson and David P Woodruff. Sketching for M-estimators: A unified approach to robust regression. In Proceedings of the 25th Annual ACM-SIAM Symposium Discrete Algorithms (SODA), 2014.
[CWW19] Kenneth Clarkson, Ruosong Wang, and David Woodruff. Dimensionality reduction for Tukey regression. In Proceedings of the 36th International Conference Machine Learning (ICML), 2019.
[DDH+09] Anirban Dasgupta, Petros Drineas, Boulos Harb, Ravi Kumar, and Michael W Mahoney. Sampling algorithms and coresets for Ep regression. SIAM Journal on Computing. 38(5):2060-2078, 2009.
[DMM06] Petros Drineas, Michael W Mahoney, and Shan Muthukrishnan. Sampling algorithms for la regression and applications. In Proceedings of the 17th Annual ACM-SIAM Symposium Discrete Algorithms (SODA), 2006.

---

[Duc]
John C. Duchi. Probability bounds. https://stanforss b http://dddddddddcddd/o/oerrrr probability_ pdf.
[FLI1]
Dan Feldman and Michael Langberg. unified framework for approximating and clustering data. In Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC), pages 569-578, 2011.
[FSS20]
Dan Feldman, Melanie Schmidt, and Christian Sohler. Turning big data into tiny data: Constant-size coresets for k-means, PCA, and projective clustering. SIAM Journal on Computing, 49(3):601-657, 2020.
[GM21]
Aarshvi Gajjar and Cameron Musco. Subspace embeddings under nonlinear transforma- tions. Algorithmic Learning Theory, pages 656-672, 2021.
[HCB16] Jonathan Huggins, Trevor Campbell, and Tamara Broderick. Coresets for scalable Bayesian logistic regression. Advances in Neural Information Processing Systems 29 (NeurIPS), 2016.
[HKSI1] Elad Hazan, Tomer Koren, and Nati Srebro. Beating sgd: Learning svms in sublinear time. In NIPS, pages 1233-1241. Citeseer, 2011.
[HPM04] Sariel Har-Peled and Soham Mazumdar. On coresets for k-means and k-median clus- tering. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC), 2004.
[KL19] Zohar Karnin and Edo Liberty. Discrepancy, coresets, and sketches in machine learning. In Proceedings of the 32nd Annual Conference on Computational Learning Theory (COLT), 2019.
[MOW21] Alexander Munteanu, Simon Omlor, and David Woodruff. Oblivious sketching for logistic regression. In Proceedings of the 38th International Conference on Machine Learning (ICML), 2021.
[MSSW18] Alexander Munteanu, Chris Schwiegelshohn, Christian Sohler, and David P Woodruff. On coresets for logistic regression. Advances in Neural Information Processing Systems 31 (NeurIPS), 2018.
[PT20]
Jeff M Phillips and Wai Ming Tai. Near-optimal coresets of kernel density estimates. Discrete Computational Geometry, 63(4)8677-887 2020.
[Rou15]
Tim Roughgarden. arXiv:1509.0622 06257, 2015.
Communication complexity (for algorithm designers).
[SS18]
Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks:
A core-set approach. Proceedings of the 6th International Conference Learning Representations (ICLR), 2018.
[TBFR21] Murad Tukan, Cenk Baykal, Dan Feldman, and Daniela Rus. On coresets for support vector machines. Theoretical Computer Science, 890:171-191, 2021.
[TF18]
Elad Tolochinsky and Dan Feldman. Generic coreset for scalable learning of monotonic kernels: Logistic regression, sigmoid and more. urXiv:1802.07388 2018.
[TMF20] Morad Tukan, Alaa Maalouf, and Dan Feldman. Coresets for near-convex functions. Advances in Neural Information Processing Systems, 33, 2020.
12


Reviews:
[{"review_id": "hysVWnsrT7", "reviewer": "Reviewer_mLvM", "summary": "This paper studies construction of coresets for training linear classifiers with objective functions such as logistic loss and hinge loss. The coresets they construct are of size $d\\mu_y(X)^2/\\epsilon^2$ upto polylogarithmic factors where $\\mu_y$ is the parameter that denotes the maximum ratio of the correctly classified points to the wrongly classified points by a linear classifier. The authors argue that in general as all the points in the example cannot be classified by a linear classifier exactly, the parameter $\\mu_y(X)$ is low and therefore  can have small coresets. For constructing the coreset, the authors sample points independently from a distribution based on $\\ell_1$ lewis weights which were earlier used to construct $\\ell_1$ subspace embeddings with small number of rows.", "questions": "", "limitations": "", "rating": 7, "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- Applying lewis weights to construct a coreset for a new problem.\n- A single sampling distribution works for many types of losses.\n- Paper writing is good.\n\nWeaknesses:\n- The paper lowers the exponents from earlier constructions but the results aren't very novel. Unless coupled with a lowerbound that matches these parameters, the results in this paper aren't very interesting.\n- My issue with the parameter $\\mu_y(X)$ is that if it is small, then maybe linear classifiers aren't good for that dataset at all. So why would you even want to find a linear classifier where even the best linear classifier performs poorly. Also, when the parameter $\\mu_y(X)$ is small, it seems like a coreset construction algorithm may not have to do much at all. It would be good to plot the fraction of points in the test set that are correctly classified by the $\\tilde{\\beta}$ computed using the coreset vs the number of points in the test set that are correctly classified by a $\\beta$ computed by using a uniform sample of the same size as the coreset. I believe this would give a much better picture of how these coresets improve upon a uniform sample.\n\nPost Rebuttal:\nI'd like to increase my score mainly because they have a near-linear dependence in $d$ and I now realize this may not be possible using earlier techniques and therefore the techniques in this paper may be helpful to decrease coreset sizes for other problems.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "XsdY7ezENla", "reviewer": "Reviewer_cpmn", "summary": "The authors propose a novel way of building coresets for linear classification problems. They build upon the two following works: \n- [MSSW18], in which the concept of the classification complexity measure $\\mu_y(X)$ is proposed and first used in coreset theorems\n- [CP15], in which normalized $\\ell_p$ Lewis weights are shown to be a good probability distribution for row sampling of tall matrices $A\\in\\mathbb{R}^{n\\times d}$, when one wishes to preserve the $p$-norm of the product $Ax$ for any vector $x\\in\\mathbb{R}^d$.\n\nThe authors show that $\\ell_1$ Lewis weights of the input data matrix $X\\in\\mathbb{R}^{n\\times d}$, are useful to build a good probability sampling distribution over the data elements, in order to create efficient coresets for linear classification. To do this, they:\n- first show that normalized $\\ell_1$ Lewis weights are a good probability distribution for sampling coresets when the classification's loss function is the ReLU function; as the proof is elegantly short in this case. This strategy guarantees coreset of size $\\tilde{O}\\left(d\\mu(X)^2\\right)$ whp. The proof is mainly based on  proof strategies found in [CP15].\n- then, via the definition of so-called nice Hinge functions --basically functions that are similar enough to the ReLU, the authors generalize their results to the hinge loss or the log loss functions. The proof needs to separately take into account different subspaces of $\\beta$'s depending on the value of $||X\\beta||_1$.\n\nTheir coreset construction is an improvement (the guaranteed minimal coreset size is much smaller) over similar approaches that take into account this $\\mu(X)$ parameter (basically, [MSSW18]).\n\nThe paper finishes with experimental comparisons with the state-of-the-art from [MSSW18] (that samples with a combination of uniform and square root of the classical $\\ell_2$ leverage scores, an oblivious sketching algorithm, and also simple uniform sampling. The algorithm used to estimate the $\\ell_1$ Lewis weights is that of [CP15].", "questions": "", "limitations": "", "rating": 8, "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": "This paper is well written, and I could not find any error in the proofs. The subject is timely and interesting. The true contribution of the authors, as I see it, is to combine ideas from [MSSW18], [CP15]; as the proofs are mainly based on proof techniques from [CP15]. The exception is the extension to nice hinge functions, for which the authors contributed a way to extend the results easily obtained on the ReLU to other similar hinge functions. \n\nThis paper should be accepted.\n\nMinor: \n- beware of the indices of your sums. There are some places where a $n$ should be a $m$ (equation of Thm 3 for instance)\n- please show why, when each $p_i$ is a scaling of a constant factor approximation of the Lewis weight, $S$ has that number of rows. I find that the sentence \"scaling of a constant factor approximation of the Lewis weight\" could be clearer and showing with a few calculations what you mean will make it clearer.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "H3J88YfqNP4", "reviewer": "Reviewer_uSXH", "summary": "This paper provides improved coresets for a wide class of linear classification problems, improving the seminal work of [MSSW18]. In particular, it improves the d^3 \\mu^3 / \\epsilon^4 bound of [MSSW18] to d \\mu^2 / \\epsilon^2, which is significant. The parameter \\mu measures the imbalance of the data, and it was introduced by [MSSW18] and shown to be necessary for a small-size coreset to exist.\n\nTechnically, the improvement is achieved by using L_1 Lewis sampling which is different from the standard Feldman-Langberg approach commonly used in coreset literature. The experiments show that the new coreset can largely outperform the uniform baseline, and is overall comparable with [MSSW18] while slightly outperform it when \\mu is large.\n", "questions": "", "limitations": "", "rating": 8, "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": "This paper is interesting not only in that it presents an improved result, but also the techniques could have value for future research. Indeed, as observed by the authors, coresets based on the Feldman-Langberg framework has size at least d^2, where one factor of d is from the sensitivity and the other is from the shattering dimension. It's nice to get rid of such dependence. Actually, in other important problems that admit coresets such as k-means, such phenomenon is also observed. For k-means problem, the state-of-the-art coreset size is at least k^2/eps^4, where k is the sensitivity and k/eps^2 is the dimension (of JL). This paper's technique may suggest a way to bypass this limitation of the framework.", "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": "4"}, "extra_text": {}}, {"review_id": "BL5hAYb6a2R", "reviewer": "Reviewer_YW1c", "summary": "This paper deals with constructing coresets using $\\ell_1$ Lewis weights. Such problems usually focused on $\\ell_p$-regression problems but in this paper, a coreset construction scheme was applied to a fairly general class of functions, namely, \"nice hinge loss\" functions, including but not restricted to the RELU loss function, log hinge function, hinge function, etc.\n\nAs for applications, this paper generalizes existing work on logistic regression (without the regularization) using lewis weights. It also discusses a coreset construction for the hinge loss. The authors claim the first result of coreset construction concerning \"nice hinge loss functions\" that do not depend on the sensitivity framework. This enables avoiding the extra multiplicative $O(d^2)$ term in the sample complexity.\n\nIn general, I like this paper, however, I have some comments concerning the Related Work (see below).", "questions": "", "limitations": "", "rating": 7, "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": "The paper suggests a coreset construction scheme for a family of functions, namely \"nice hinge loss functions\", using a none sensitivity framework, i.e., using Lewis weights, specifically, $\\ell_1$ Lewis weights. This work builds upon several works and mainly improves upon and generalizes that of [MSSW18] to a larger family of functions. \n\nIn the paper, the sample complexity depends quadratically on the classification complexity, a notion that was first defined in [MSSW18], yielding a better and smaller bound than previously achieved. In addition, in the paper, a tighter lower bound on the sample complexity has been established with respect to the regularized problems such as the hinge loss and log hinge loss (variants of the SVM problem and logistic regression problem).\n\nI believe the results are correct. I have looked into most of the proofs though not all, due to time constraints. \n\nThere are some typos which I have come upon:\n- The equation below Line 119, change n to m in the sum term.\n-  At the supplementary, Line 410, there is an addition $\\leq$.\n- At the supplementary, Line 455, $n_0$ instead of $n^0$.\n\nI believe that the related work is not updated enough, as it lacks discussion of papers that admit coreset construction with respect to logistic regression and SVMs! To name some: \n- On coreset for Support Vector Machines\n- Coresets for Near-Convex Functions\n- Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm \n\nQuestions:\n- How does your lower bound on the regularized version of the hinge loss (a variant of SVM) compare with the lower bound obtained at \"On coreset for Support Vector Machines\"?\n- How does your upper bound on the sample complexity compare with that of \"Coresets for Near-Convex Functions\" for either logistic regression or SVM with respect to the regularized loss function?\n- In some cases, the $\\ell_2$-Lewis weights are 2-3 times better than your approach in terms of the approximation error for the sample size. Can you give a brief explanation of why this happens? \n- When does your approach outperform that of [MSSW18] (practically speaking)?\n- It would be good to see a comparison between your approach and sensitivity-based approaches. \n- Can you plot the approximation error as a function of time?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "As stated in the paper, similar to [MSSW18], a valid assumption (that was used in this paper), is that the classification complexity is small, i.e., datasets with linear separability are avoided, since the classification complexity would then approaches infinity. In addition, the theoretical bounds obtained in the paper do not improve with regularization. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hours"}, "extra_text": {}}]

Author rebuttal:

Meta-review: After the rebuttal phase, all reviewers see the merits of the paper and this coincides with 
my own impressions. The paper is worth being published.

Decision: Accept (Poster)