Coresets for Classification – Simplified and Strengthened
Year: 2021

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 ± ) relative error with Õ(d · μy(X)/ ) points, where μy(X) is a natural complexity measure of the data matrix X ∈ Rn×d and label vector y ∈ {−1, 1}, introduced in [MSSW18]. Our result is based on subsampling data points with probabilities proportional to their `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.

heading: 1 Introduction
text: Coresets are an important tool in scalable machine learning. Given n data points and some objective function, we seek to select a subset of m n data points such that minimizing the objective function on those points (possibly where selected points are weighted non-uniformly) will yield a near minimizer over the full dataset. Coresets have been applied to problems ranging from clustering [HPM04, FL11], to principal component analysis [CEM+15, FSS20], to linear regression [DMM06, DDH+09, CWW19], to kernel density estimation [PT20], and beyond [AHPV05, BLK17, SS18].
We study coresets for linear classification. Given a data matrix X ∈ Rn×d, with ith row xi and a label vector y ∈ {−1, 1}n, the goal is to compute β∗ = arg minβ∈Rd L(β), where L(β) =∑n i=1 f(〈xi, β〉 · yi) for a classification loss function f , such as the logistic loss f(z) = ln(1 + e−z) used in logistic regression or hinge loss f(z) = max(0, 1− z) used in soft-margin SVMs. We seek to select a subset of m n points xi1 , . . . , xim along with a corresponding set of weights w1, . . . , wm such that, for some small > 0 and all β ∈ Rd,∣∣∣∣∣∣ m∑ j=1 wj · f(〈xij , β〉 · yij )− L(β)
∣∣∣∣∣∣ ≤ · L(β). (1) This relative error coreset guarantee ensures that if β̃ ∈ Rd is computed to be the minimizer of the weighted loss over our m selected points, then L(β̃) ≤ 1+ 1− · L(β ∗).
It 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 [MSSW18]. 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 (NeurIPS 2021).
Definition 1 (Classification Complexity Measure [MSSW18]). For any X ∈ Rn×d, y ∈ {−1, 1}n, let µy(X) = supβ 6=0 ‖(DyXβ)+‖1 ‖(DyXβ)−‖1 , where Dy ∈ R
n×n is a diagonal matrix with y as its diagonal, and (DyXβ)+ and (DyXβ)− denote the set of positive and negative entries in DyXβ.
Roughly, µy(X) is large when there is some parameter vector β ∈ Rd that produces significant imbalance between correctly classified and misclassified points. This can occur e.g., when the data is exactly separable. However, as argued in [MSSW18], we typically expect µy(X) to be small.

heading: 1.1 Our Results
text: Our main result, formally stated in Corollary 9, is that sampling Õ ( d·µy(X)2
2
) points according to
the `1 Lewis weights of X and reweighting appropriately, yields a relative error coreset satisfying (1) for the logistic loss, the hinge loss, and generally a broad class of ‘hinge-like’ losses. This significantly improves the previous state-of-the-art using the same µy(X) parameterization, which
was Õ ( d3·µy(X)3
4
) [MSSW18]. See Table 1 for a detailed comparison with prior work.
Theoretical Approach. The Lewis weights are a measure of the importance of rows in X , originally designed to sample rows in order to preserve ‖Xβ‖1 for any β ∈ Rd [CP15]. They can be viewed as an `1 generalization of the leverage scores which are used in applications where one seeks to preserve ‖Xβ‖2 [CLM+15]. Like the leverage scores, the Lewis weights can be approximated very efficiently, in Õ(nnz(X) + dω) time where ω ≈ 2.37 is the constant of fast matrix multiplication. They can also be approximated in streaming and online settings [BDM+20]. Our coreset constructions directly inherit these computational properties.
The `1 Lewis weights are a natural sampling distribution for hinge-like loss functions, including the logistic loss, hinge loss, and the ReLU. These functions grow approximately linearly for positive z, but asymptote at 0 for negative z. Thus, ignoring some technical details, it can be shown that∑n i=1 f(〈xi, β〉 · yi) concentrates only better under sampling than ∑n i=1 |〈xi, β〉 · yi| = ‖DyXβ‖1.
As shown by Cohen and Peng [CP15], taking Õ(d/ 2) samples according to the Lewis weights of X (which are the same as those of DyX) suffices to approximate ‖DyXβ‖1 for all β ∈ Rd up to (1± ) relative error. We show in Thm. 8 using contraction bounds for Rademacher averages that it in turn suffices to approximate ∑n i=1 f(〈xi, β〉 · yi) up to additive error roughly (‖X‖1 + n). We then simply show in Corollaries 6 and 9 that by setting ′ = Θ( /µy(X)) and applying Def. 1, this result yields a relative error coreset for a broad class of hinge-like loss functions including the ReLU, the log loss, and the hinge loss.
Experimental Evaluation. In Sec 5, we compare our Lewis weight-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 [MSSW18], seeming to outperform when the µy(X) complexity parameter is large.

heading: 1.2 Related Work
text: Our work is closely related to [MSSW18], which introduces the µy(X) complexity measure. They give relative error coresets with worse polynomial dependences on the parameters through a mixture of uniform sampling and sampling by the squareroots of the leverage scores. This approach has the same intuition as 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 Ω(d2) 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 `1 matrix concentration result and give optimal linear dependence on the dimension d.
Regularized Classification Losses. Rather than using the µy(X) 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(β), where κ > 0 is some parameter and R(β) is some norm – e.g., ‖β‖1, ‖β‖2, or in the important case of soft-margin SVM, ‖β‖22.
Curtin et al. show that simple uniform sampling gives a relative error coreset with Õ ( n1−κd/ 2 ) points in this setting [CIM+19]. They also show that no coreset with o(n(1−κ)/5) points exists. In Appendix B, we tighten this lower bound, showing via a reduction to the INDEX problem in communication complexity that the Õ(n1−κ) 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 µy(X), which is avoided by [CIM+19].
Other Related Work. 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, ALS+18, CWW19, 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, GM21]. Another line of related work includes coresets for standard optimization algorithms such as FrankWolfe algorithm [Cla10], Gilbert’s algorithm [CHW12] and Stochastic Gradient Descent [HKS11].

heading: 2 Preliminaries
text: Notation. Throughout, for f : R→ R and a vector y ∈ Rn, we let f(y) ∈ Rn denote the entrywise application of f to y. For a vector y ∈ Rn we let yi denote it’s ith entry. So f(y)i = f(yi).
For data matrix X ∈ Rn×d with rows x1, . . . , xn ∈ Rd and label vector y ∈ {−1, 1}n we consider classification loss functions of the form L(β) = ∑n i=1 f(〈xi, β〉 · yi) = ∑n i=1 f(DyXβ)i, where Dy ∈ Rn×n is the diagonal matrix with y on its diagonal. For simplicity, we write X instead of DyX throughout, since we can think of the labels as just being incorporated into X by flipping the signs of its rows. Similarly, we write the complexity parameter of Def. 1 as µ(X) = supβ 6=0 ‖(Xβ)+‖1 ‖(Xβ)−‖1 .
Throughout we will call f(z) = ln(1 + ez) the logistic loss and f(z) = max(0, 1 + z) the hinge loss. Note that these functions have the sign of z flipped from the typical convention. This is just notational – we can always negate X or β and have an identical loss function. We use these versions as they are both `∞ close to the ReLU function, a fact that we will leverage in our analysis.
Basic sampling results. Our coreset construction is based on sampling with the `1 Lewis weights. We define these weights and state fundamental results on Lewis weight sampling and below. Definition 2 (`1 Lewis Weights [CP15]). For any X ∈ Rn×d the `1 Lewis weights are the unique values τ1(X), . . . , τn(X) such that, letting W ∈ Rn×n be the diagonal matrix with 1/τ1(X), . . . , 1/τn(X) as its diagonal, for all i,
τi(X) 2 = xTi (X TWX)+xi,
where for any matrix M , M+ is the pseudoinverse. M+ = M−1 when M square and full-rank. Theorem 3 (`1 Lewis Weight Sampling). Consider any X ∈ Rn×d, and set of sampling values pi with ∑n i=1 pi = m and pi ≥ c·τi(X) log(m/δ) 2 for all i, where c is a universal constant. If we generate a matrix S ∈ Rm×n with each row chosen independently as the ith standard basis vector times 1/pi with probability pi/m then there exists an ` > 1 such that if σ ∈ {−1, 1}m is chosen with independent Rademacher entries
E S,σ  sup β:‖Xβ‖1=1 ∣∣∣∣∣ m∑ i=1 σi[SXβ]i ∣∣∣∣∣ `  ≤ ` · δ.
In particular, if each pi is a scaling of a constant factor approximation to the Lewis weight τi(X) (which means that ∀i, c̃τi(X) ≤ pi ≤ cτi(X) for some constants c, c̃), S has m = O ( d log(d/δ ) 2 ) rows.
Theorem 3 is implicit in [CP15], following from the proof of Lemma 7.4, which shows a high probability bound on |‖SXβ‖1 − 1| via the moment bound stated above. This moment bound is proven on page 29 of the arXiv version. The claim on the bound on m can be derived as follows. We have ∑n i=1 τi(X) = d, which gives that m = ∑ pi ≤ cd log(m/δ)/ 2 for some constant c. If we set m = O(d log(d/(δ ))/ 2) we have log(m/δ) = O(log(d/(δ )) which gives m = cd log(m/δ)/ 2 as needed.
We will translate the above moment bound to give approximate bounds for classification loss functions like the ReLU, logistic loss, and hinge loss, using the following standard result on Rademacher complexities: Theorem 4 (Ledoux-Talagrand contraction, c.f. [Duc]). Consider V ⊆ Rm, along with L-Lipschitz functions fi : R → R with fi(0) = 0. Then for any ` > 1, if σ ∈ {−1, 1}m is chosen with independent Rademacher entries,
E σ sup v∈V ∣∣∣∣∣ m∑ i=1 σifi(vi) ∣∣∣∣∣ `  ≤ (2L)` · E σ sup v∈V ∣∣∣∣∣ m∑ i=1 σivi ∣∣∣∣∣ `  .

heading: 3 Warm Up: Coresets for ReLU Regression
text: We start by showing that `1 Lewis weight sampling yields a (1 + )-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 a similar structure, with some added complexities.
We first show that Lewis weight sampling gives a coreset with additive error ‖X‖1. By setting ′ = /µ(X), we then easily obtain a relative error coreset under the assumption of Def. 1. Theorem 5 (ReLU Regression – Additive Error Coreset). Consider X ∈ Rn×d and let ReLU(z) = max(0, z) for all z ∈ R. For a set of sampling values pi with ∑n i=1 pi = m and pi ≥ c·τi(X) log(m/δ) 2 for all i, where c is a universal constant, if we generate S ∈ Rm×n with each row chosen independently as the ith standard basis vector times 1/pi with probability pi/m then with probability at least 1− δ, for all β ∈ Rd, ∣∣∣∣∣ m∑ i=1 [S ReLU(Xβ)]i − n∑ i=1 ReLU(Xβ)i
∣∣∣∣∣ ≤ ‖Xβ‖1. If each pi is a scaling of a constant factor approximation to the Lewis weight τi(X), S has m =
O ( d log(d/(δ ))
2
) rows.
Corollary 6 (ReLU Regression – Relative Error Coreset). Consider the setting of Thm. 5, where∑n i=1 pi = m and pi ≥ c·τi(X) log(m/δ)·µ(X)2 2 for all i. With probability at least 1 − δ, ∀β ∈ R
d, | ∑m i=1[S ReLU(Xβ)]i − ∑n i=1 ReLU(Xβ)i| ≤ · ∑n i=1 ReLU(Xβ)i. If each pi is a scaling of a
constant factor approximation to the Lewis weight τi(X), S has m = O ( d log(d/(δ ))·µ(X)2 2 ) rows.
Proof of Corollary 6. We have n∑ i=1 ReLU(Xβ)i = ∑
i:[Xβ]i≥0
[Xβ]i = ‖(Xβ)+‖1, (2)
Additionally, since by definition µ(X) = supβ 6=0 ‖(Xβ)+‖1 ‖(Xβ)−‖1 = supβ 6=0 ‖(Xβ)−‖1 ‖(Xβ)+‖1 ,
‖Xβ‖1 ‖(Xβ)+‖1 = 1 + ‖(Xβ)−‖1 ‖(Xβ)+‖1 ≤ 1 + µ(X). (3)
Combining (2) with (3) gives that ∑n i=1 ReLU(Xβ)i ≥ 1 1+µ(X) · ‖Xβ‖1, which then completes the corollary after applying Theorem 5 with ′ = 1+µ(X) .
Proof of Theorem 5. We prove the theorem restricted to β such that ‖Xβ‖1 = 1. Since the ReLU function is linear in that ReLU(cz) = c · ReLU(z), this yields the complete theorem via scaling. It suffices to prove that there exists some ` > 0 such that
B def = E
S  sup β:‖Xβ‖1=1 ∣∣∣∣∣ m∑ i=1 [S ReLU(Xβ)]i − n∑ i=1 ReLU(Xβ)i ∣∣∣∣∣ `  ≤ ` · δ.
The theorem then follows via Markov’s inequality and the monotonicity of z` for z, ` ≥ 0. Via a standard symmetrization argument (c.f. the Proof of Theorem 7.4 in [CP15]) we have
B ≤ 2` · E S,σ  sup β:‖Xβ‖1=1 ∣∣∣∣∣ m∑ i=1 σi[S ReLU(Xβ)]i ∣∣∣∣∣ `  ,
where σ ∈ {−1, 1}m has independent Rademacher random entries. We can then apply, for each fixed value of S the Ledoux-Talagrand contraction theorem (Theorem 4) with V = {SXβ : ‖Xβ‖1 = 1} and fi(z) = ReLU(z) for all i. fi(z) is 1-Lipschitz with f(0) = 0. This gives
B ≤ 4` · E S,σ  sup β:‖Xβ‖1=1 ∣∣∣∣∣ m∑ i=1 σi[SXβ]i ∣∣∣∣∣ `  ≤ (4 )` · δ
for some ` > 1 by Theorem 3. This completes the theorem after adjusting by a factor of 4, which only affects the sample complexity by a constant factor.

heading: 4 Extension to the Hinge Like Loss Functions
text: We next extend Theorem 5 to a family of ‘nice hinge functions’ which includes the hinge loss f(z) = max(0, 1 + z) and the log loss f(z) = ln(1 + ez). These functions present two additional challenges: 1) they are generally not linear in that f(c · z) 6= c · f(z), an assumption which is used in the proof of Theorem 5 to restrict to considering β with ‖Xβ‖1 = 1 and 2) they are not contractions with f(0) = 0, a property which was used to apply the Ledoux-Talagrand contraction theorem. Definition 7 (Nice Hinge Function). We call f : R→ R+ an (L, a1, a2)-nice hinge function if for fixed constants L, a1 and a2,
(1) f is L-Lipschitz (2) |f(z)− ReLU(z)| ≤ a1 for all z (3) f(z) ≥ a2 for all z ≥ 0.
We start with an additive error coreset result for nice hinge functions. We then show that under the additional assumption of a2 > 0, the additive error achieved is small compared to ∑n i=1 f(Xβ)i, yielding a relative error coreset. This gives our main results for both the hinge loss and log loss, which are (1, 1, 1)-nice and (1, ln 2, ln 2)-nice hinge functions respectively.
Theorem 8 (Nice Hinge Function – Additive Error Coreset). Consider X ∈ Rn×d and let f : R→ R+ be an (L, a1, a2)-nice hinge function (Def. 7). For a set of sampling values pi with ∑n i=1 pi = m and pi ≥ Cmax(τi(X),1/n) 2 for all i, where C = c ·max(1, L, a1) 2 · log ( log(nmax(1,L,a1)/ )m
δ
) and c
is a fixed constant, if we generate S ∈ Rm×n with each row chosen independently as the ith standard basis vector times 1/pi with probability pi/m, then with probability at least 1− δ, ∀β ∈ Rd,∣∣∣∣∣ m∑ i=1 [Sf(Xβ)]i − n∑ i=1 f(Xβ)i ∣∣∣∣∣ ≤ · (‖Xβ‖1 + n). Observe that for a fixed function f , L, a1 are constant and so, if each pi is a scaling of a constant factor approximation to max(τi(X), 1/n), S has m = O ( d log(log(n/ )d/(δ )) 2 ) = Õ ( d 2 ) rows.
Proof. Let J = c1 log( nmax(1,L,a1)
) for some constant c1. We will show that for each integer j ∈ [−J, J ], with probability at least 1− δ2J ,
sup β:‖Xβ‖1∈[2j ,2j+1] ∣∣∣∣∣ m∑ i=1 [Sf(Xβ)]i − n∑ i=1 f([Xβ]i) ∣∣∣∣∣ ≤ · 2j + · n. (4) Via a union bound this gives the theorem for all β with ‖Xβ‖1 ∈ [2−J , 2J ]. We then just need to handle the case of Xβ with norm outside this range – i.e. when ‖Xβ‖1 is polynomially small or polynomially large in n and the other problem parameters. We will take a union bound over the failure probabilities for these cases, and after adjusting δ by a constant, have the complete theorem. We make the argument for ‖Xβ‖1 outside [2−J , 2J ] first.
Small Norm. For β with ‖Xβ‖1 ≤ 2−J , ‖Xβ‖∞ ≤ 2−J ≤ L . Thus, f(Xβ)i ∈ [f(0)− , f(0)+ ] for all i. Thus by triangle inequality, and the fact that f(0) ≤ ReLU(0) + a1 = a1:
sup β:‖Xβ‖1≤2−J ∣∣∣∣∣ m∑ i=1 [Sf(Xβ)]i − n∑ i=1 f(Xβ)i ∣∣∣∣∣ ≤ a1 · ∣∣∣∣∣ m∑ i=1 1/pji − n ∣∣∣∣∣+ · ( m∑ i=1 1/pji + n ) , (5)
where 1/pji is value of the single nonzero entry in the i th row of S, which samples index ji from f(Xβ). Let Z1, . . . , Zm be i.i.d., each taking value 1/pj with probability pj m for all j ∈ [n]. Then∣∣∣∣∣ m∑ i=1 1/pji − n ∣∣∣∣∣ = ∣∣∣∣∣ m∑ i=1 (Zi − EZi) ∣∣∣∣∣ . For all j ∈ [n] we have pj ≥ C·max(τj(X),1/n) 2 ≥ c·max(1,a1)2·log(J/δ) n 2 , so applying a Bernstein bound, if the constant c is chosen large enough we have:
P [∣∣∣∣∣ m∑ i=1 1/pji − n ∣∣∣∣∣ ≥ nmax(1, a1) ] ≤ 2 exp ( −
2n2/(2 max(1, a1) 2)
n2 2 c log(J/δ)·max(1,a1)2 + n2 3 c log(J/δ)·max(1,a1)3
) ≤ δ
4J .
(6)
Combining (6) with (5), with probability at least 1− δ, we have
sup β:‖Xβ‖1≤2−J ∣∣∣∣∣ m∑ i=1 [Sf(Xβ)]i − n∑ i=1 f(Xβ)i ∣∣∣∣∣ ≤ a1 · nmax(1, a1) + · ( 2 + max(1, a1) ) n ≤ 4 · n.
Adjusting constants on , this gives the theorem for β with ‖Xβ‖1 ≤ 2−J .
Large Norm. We next consider β with ‖Xβ‖1 ≥ 2J . Since by assumption |f(z)−ReLU(z)| ≤ a1 for all z ∈ R, we can apply triangle inequality to give for any β ∈ Rd,∣∣∣∣∣ m∑ i=1 [Sf(Xβ)]i − n∑ i=1 f(Xβ)i ∣∣∣∣∣ ≤ ∣∣∣∣∣ m∑ i=1 [S ReLU(Xβ)]i − n∑ i=1 ReLU(Xβ)i ∣∣∣∣∣+ a1 · ( m∑ i=1 1/pji + n ) .
Applying Theorem 5 and the bound on ∑m i=1 1/pji given in (6), we thus have, with probability at least 1− 2δ, for all β with ‖Xβ‖1 ≥ 2J ,∣∣∣∣∣ m∑ i=1 [Sf(Xβ)]i − n∑ i=1 f(Xβ)i
∣∣∣∣∣ ≤ 2‖Xβ‖1 + 3a1n ≤ ‖Xβ‖1, where the final bound uses that ‖Xβ‖1 ≥ 2J ≥ ( nmax(1,a1) )c1 for a large enough constant c1. This
gives the theorem for β with ‖Xβ‖1 ≥ 2J .
Bounded Norm. We now return to proving that (4) holds for any j ∈ [−J, J ] with probability at least 1− δ2J . Let f̄(z) = f(z)− f(0). Then for any β ∈ R
d we have:∣∣∣∣∣ m∑ i=1 [Sf(Xβ)]i − n∑ i=1 f([Xβ]i) ∣∣∣∣∣ ≤ ∣∣∣∣∣ m∑ i=1 [Sf̄(Xβ)]i − n∑ i=1 f̄([Xβ]i) ∣∣∣∣∣+ f(0) · ∣∣∣∣∣ m∑ i=1 1/pji − n ∣∣∣∣∣ . We again apply the bound on ∑m i=1 1/pji given in (6) and the fact that f(0) ≤ a1. This gives that with probability at least 1− δ4J , for all β ∈ R d,∣∣∣∣∣ m∑ i=1 [Sf(Xβ)]i − n∑ i=1 f([Xβ]i) ∣∣∣∣∣ ≤ ∣∣∣∣∣ m∑ i=1 [Sf̄(Xβ)]i − n∑ i=1 f̄([Xβ]i)
∣∣∣∣∣+ f(0) · nmax(1, a1) ≤
∣∣∣∣∣ m∑ i=1 [Sf̄(Xx)]i − n∑ i=1 f̄([Xx]i) ∣∣∣∣∣+ · n. (7) Now, for ` ≥ 0, by a standard symmetrization argument (c.f. the proof of Thm. 7.4 in [CP15]),
B def = E
S  sup β:‖Xβ‖1∈[2j ,2j+1] ∣∣∣∣∣ m∑ i=1 [Sf̄(Xβ)]i − n∑ i=1 f̄(Xβ)i ∣∣∣∣∣ `  ≤ 2` E S,σ  sup β:‖Xβ‖1∈[2j ,2j+1] ∣∣∣∣∣ n∑ i=1 σi[Sf̄(Xβ)]i ∣∣∣∣∣ `  ,
where σ ∈ {−1, 1}m has independent Rademacher random entries. We can then apply, for each fixed value of S the Ledoux-Talagrand contraction theorem (Thm. 4) with V = {SXβ : ‖Xβ‖1 ∈ [2j , 2j+1]} and fi(z) = 1/pji · f̄(pji · z). Note that fi(0) = 0 since f̄(0) = 0. Additionally, fi is L-Lipschitz since by assumption f(z) is L-Lipschitz so f̄(pji · z) is (pji · L)-Lipschitz. We have,
fi([SXβ]i) = 1/pji · f̄(pji · 1/pji [Xβ]ji) = [Sf̄(Xβ)]i.
So, applying Theorem 3, for some ` > 1 we have, since pi ≥ Cτi(X) 2 for C = cmax(1, L, a1) 2 · log(log(nmax(1, L, a1)/ )m/δ) = Ω(max(1, L 2) · log(Jm/δ)),
B ≤ (4L)` · E S,σ  sup β:‖Xβ‖1∈[2j ,2j+1] ∣∣∣∣∣ n∑ i=1 σi[SXβ]i ∣∣∣∣∣ `  ≤ (4L)` · ( /L)` · δ 4J · (2j+1)`.
Adjusting by a constant, this gives via Markov’s inequality that with probability at least 1− δ4J ,
sup β:‖Xβ‖1∈[2j ,2j+1] ∣∣∣∣∣ m∑ i=1 [Sf̄(Xβ)]i − n∑ i=1 f̄(Xβ)i ∣∣∣∣∣ ≤ · 2j . (8) In combination with (7), we then have that probability at least 1− δ2J ,
sup β:‖Xβ‖1∈[2j ,2j+1] ∣∣∣∣∣ m∑ i=1 [Sf(Xβ)]i − n∑ i=1 f([Xβ]i) ∣∣∣∣∣ ≤ · 2j + · n. This gives (4) and completes the theorem.

heading: 4.1 Relative Error Coresets
text: 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 9 (Nice Hinge Function – Relative Error Coreset). Consider the setting of Thm. 8 under the additional assumption that a2 > 0. If ∑n i=1 pi = m and pi ≥ Cmax(τi(X),1/n)·µ(X)2 2 for all i,
where C = c ·max(1, L, a1, 1/a2)10 · log ( log(nmax(1,L,a1,1/a2)·µ(X)/ )m δ ) and c is a fixed constant,
with probability ≥ 1− δ, for all β ∈ Rd, | ∑m i=1[Sf(Xβ)]i − ∑n i=1 f(Xβ)i| ≤ · ∑n i=1 f(Xβ)i.
For fixed f(·), L, a1, a2 are constant and so, if each pi is a scaling of a constant factor approximation to max(τi(X), 1/n), S has m = O
( dµ(X)2 log(log(nµ(X)/ )dµ(X)/(δ ))
2
) = Õ ( dµ(X)2
2
) rows. This
gives our main result for the hinge and log losses, which are (1, 1, 1) and (1, ln 2, ln 2)-nice.

heading: 5 Empirical Evaluation
text: We now compare our method (lewis), square root of leverage score method (l2s) of [MSSW18], uniform sampling (uniform), and an oblivious sketching algorithm (sketch) of [MOW21]. Our evaluation uses the codebase of [MSSW18], 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 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 l2s 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 in numpy.
We note that [MSSW18] used a fast random sketching-based QR decomposition to compute the leverage scores – this can also be applied to 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 5 times as much time as l2s weight computation.
Datasets. We use the same three datasets as in [MSSW18]. The WEBB SPAM1 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 library2. COVERTYPE consists of 581,012 cartographic observations of different forests with 54 features and 49% positive labels. The task is 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.
Loss functions. We evaluate the algorithms on two loss functions: 1) logistic loss f(z) = ln(1 + ez) and 2) hinge loss f(z) = max(0, 1+z). As before, we use z = 〈β, x〉 ·y. Note that [MSSW18] gives guarantees only for logistic loss for l2s. We also evaluate the above two losses with regularization term 0.5‖β‖22. 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.
Evaluation. Our evaluation follows that of [MSSW18]. Let β̃ be the parameter vector minimizing the sum of the loss function on the coreset and β∗ be the true minimizer. We report the relative loss |L(β∗)−L(β̃)|
L(β∗) , where L(β) = ∑n i f(〈xi, β〉 · yi) is the sum of loss over all data points. Ideally, this
ratio should be close to 0. In Figure 1, we plot the log relative loss as a function of coreset size.
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 µy(X) than the bounds [MSSW18] for l2s, and so this agrees with the fact that the value of µy(X) is high for KDD CUP ’99. [MSSW18] estimated µy(X) values of WEBB SPAM, COVERTYPE and KDD CUP ’99 to be 4.39, 1.86 and 35.18 respectively. For COVERTYPE and
1https://www.csie.ntu.edu.tw/ cjlin/libsvmtools/datasets/ 2https://scikit-learn.org/
WEBB SPAM, the performance of lewis is comparable or a little worse than that of l2s. Furthermore, on these two datasets, with regularization, uniform sampling does relatively well for very small sample sizes, which agrees with the results of [CIM+19].
Comparison of distributions. To give a better intuition behind our results, we illustrate how different the Lewis weights are from the other sampling distributions on our three datasets in Fig. 3. Given two distributions p̄ = (p1, p2, .., pn) and q̄ = (q1, p2, .., qn), we plot the frequencies of {max(pi/qi, qi/pi)}i. We let p̄ to be the uniform or l2s distributions and take q̄ to be Lewis weights. We observe that the Lewis weights are far from uniform on all datasets, especially KDD CUP ’99. This may explain why lewis performs so well on this dataset. l2s and lewis are much closer in general, explaining their relatively similar performance. Note that these score comparisons are based only 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 a partial picture of the differences between methods. In particular, our theoretical bounds and the bounds for l2s in [MSSW18] both depend on µy(X), which depends on the label vector.
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. auc stands
for Areas Under the Curve. A perfect classifier has auc = 1 and all other classifiers have auc < 1. The lower the curve is in the plot, better it is as a classifier. Each plot is a result of 100 trials.
Acknowledgments and Disclosure of Funding
Cameron Musco was partially supported by an Adobe Research grant, along with NSF Grants 2046235 and 1763618.

Review summaries:
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.

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.  As 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.  In general, I like this paper, however, I have some comments concerning the Related Work (see below).

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.  Technically, 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. 

The authors propose a novel way of building coresets for linear classification problems. They build upon the two following works:  - [MSSW18], in which the concept of the classification complexity measure $\mu_y(X)$ is proposed and first used in coreset theorems - [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$.  The 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: - 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]. - 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$.  Their 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]).  The 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].