Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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.
main_review: Strengths:
- Applying lewis weights to construct a coreset for a new problem.
- A single sampling distribution works for many types of losses.
- Paper writing is good.

Weaknesses:
- 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.
- 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.

Post Rebuttal:
I'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.
limitations_and_societal_impact: NA
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: 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.

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.

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.
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: 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].
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. 

This paper should be accepted.

Minor: 
- beware of the indices of your sums. There are some places where a $n$ should be a $m$ (equation of Thm 3 for instance)
- 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.
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.

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).
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. 

In 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).

I believe the results are correct. I have looked into most of the proofs though not all, due to time constraints. 

There are some typos which I have come upon:
- The equation below Line 119, change n to m in the sum term.
-  At the supplementary, Line 410, there is an addition $\leq$.
- At the supplementary, Line 455, $n_0$ instead of $n^0$.

I 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: 
- On coreset for Support Vector Machines
- Coresets for Near-Convex Functions
- Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm 

Questions:
- 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"?
- 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?
- 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? 
- When does your approach outperform that of [MSSW18] (practically speaking)?
- It would be good to see a comparison between your approach and sensitivity-based approaches. 
- Can you plot the approximation error as a function of time?

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_title: null

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)