Venue: ICLR 2018 conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper studies the approach of coreset for SVM. In particular, it aims at sampling a small set of weighted points such that the loss function over these points provably approximates that over the whole dataset. This is done by applying an existing theoretical framework to the SVM training objective.

The coreset idea has been applied to SVM in existing work, but this paper uses a new theoretical framework. It also provides lower bound on the sample complexity of the framework for general instances and provides upper bound that is data dependent, shedding light on what kind of data this method is suitable for. 

The main concern I have is about the novelty of the coreset idea applied to SVM. Also, there are some minor issues:
-- Section 4.2: What's the point of building the coreset if you've got the optimal solution? Indeed one can do divide-and-conquer. But can one begin with an approximation solution? In general, the analysis of the coreset should still hold if one begins with an approximation solution. Also, even when doing divide-and-conquer, the solution obtained in the first line of the algorithm should still be approximate. The authors pointed out that Lemma 7 can be extended to this case, and I hope the proof can be written out explicitly.
-- section 2, paragraph 4: why SGD-based approaches cannot be trivially extended to streaming settings? 
-- Definition 3: what randomness is the probability with respect to? 
-- For experiments: the comparison with CVM should be added.

review_title: Review

final_score: rating: 7: Good paper, accept
review_content: The paper suggests an importance sampling based Coreset construction for Support Vector Machines (SVM). To understand the results, we need to understand Coreset and importance sampling: 

Coreset: In the context of SVMs, a Coreset is a (weighted) subset of given dataset such that for any linear separator, the cost of the separator with respect to the given dataset X is approximately (there is an error parameter \eps) the same as the cost with respect to the weighted subset. The main idea is that if one can find a small coreset, then finding the optimal separator (maximum margin etc.) over the coreset might be sufficient. Since the computation is done over a small subset of points, one hopes to gain in terms of the running time.

Importance sampling: This is based on the theory developed in Feldman and Langberg, 2011 (and some of the previous works such as Langberg and Schulman 2010, the reference of which is missing). The idea is to define a quantity called sensitivity of a data-point that captures how important this datapoint is with respect to contributing to the cost function. Then a subset of datapoint are sampled based on the sensitivity and the sampled data point is given weight proportional to inverse of the sampling probability. As per the theory developed in these past works, sampling a subset of size proportional to the sum of sensitivities gives a coreset for the given problem.

So, the main contribution of the paper is to do all the sensitivity calculations with respect to SVM problem and then use the importance sampling theory to obtain bounds on the coreset size. One interesting point of this construction is that Coreset construction involves solving the SVM problem on the given dataset which may seem like beating the purpose. However, the authors note that one only needs to compute the Coreset of small batches of the given dataset and then use standard procedures (available in streaming literature) to combine the Coresets into a single Coreset. This should give significant running time benefits. The paper also compares the results against the simple procedure where a small uniform sample from the dataset is used for computation. 


Evaluation: 
Significance: Coresets give significant running time benefits when working with very big datasets. Coreset construction in the context of SVMs is a relevant problem and should be considered significant.

Clarity: The paper is reasonably well-written. The problem has been well motivated and all the relevant issues point out for the reader. The theoretical results are clearly stated as lemmas a theorems that one can follow without looking at proofs. 

Originality: The paper uses previously developed theory of importance sampling. However, the sensitivity calculations in the SVM context is new as per my knowledge. It is nice to know the bounds given in the paper and to understand the theoretical conditions under which we can obtain running time benefits using corsets. 

Quality: The paper gives nice theoretical bounds in the context of SVMs. One aspect in which the paper is lacking is the empirical analysis. The paper compares the Coreset construction with simple uniform sampling. Since Coreset construction is being sold as a fast alternative to previous methods for training SVMs, it would have been nice to see the running time and cost comparison with other training methods that have been discussed in section 2.

review_title: Small Coresets to Represent Large Training Data for Support Vector Machines

final_score: rating: 5: Marginally below acceptance threshold
review_content: The paper studies the problem of constructing small coreset for SVM.
A coreset is a small subset of (weighted) points such that the optimal solution for the coreset is also a good approximation for the original point set. The notion of coreset was originally formulated in computational geometry by Agarwal et al.
(see e.g., [A])
Recently it has been extended to several clustering problems, linear algebra, and machine learning problems. This paper follows the important sampling approach first proposed in [B], and generalized by Feldman and Langberg. The key in this approach is to compute the sensitivity of points and bound the total sensitivity for the considered problem (this is also true for the present paper). For SVM, the paper presents a bad instance where the total sensitivity can be as bad as 2^d. Nevertheless,
the paper presents interesting upper bounds that depending on the optimal value and variance of the point set. The paper argues that in many data sets, the total sensitivity may be small, yielding small coreset. This makes sense and may have significant practical implications.

However, I have the following reservation for the paper.
(1) I don't quite understand the CHICKEN and EGG section. Indeed, it is unclear to me 
how to estimate the optimal value. The whole paragraph is hand-waving. What is exactly merge-and-reduce? From the proof of theorem 9, it appears that the interior point algorithm is run on the entire dataset, with running time O(n^3d). Then there is no point to compute a coreset as the optimal solution is already known.

(2) The running time of the algorithm is not attractive (in both theory and practice).
In fact, the experimental result on the running time is a bit weak. It seems that the algorithm is pretty slow (last in Figure 1). 

(3) The theoretical novelty is limited. The paper follows from now-standard technique for constructing coreset.

Overal, I don't recommend acceptance.

minor points:
It makes sense to cite the following papers where original ideas on constructing coresets were proposed initially.

[A]Geometric Approximation via Coresets
Pankaj K. Agarwal Sariel Har-Peled Kasturi R. Varadarajan

[B]Universal epsilon-approximators for integrals, by Langberg and Schulman

---------------------------------------------------------

After reading the response and the revised text, I understand the chicken-and-egg issue.
I think the experimental section is still a bit weak (given that there are several very competitive SVM algorithms that the paper didn't compare with).
I raised my score to 5. 


review_title: coreset for svm. 

Meta-review: While the paper shows some encouraging results for scaling up SVMs using coreset methods, it has fallen short of making a fully convincing case, particularly given the amount of intense interest in this topic back in the heydey of kernel methods. When it comes to scalability, it has become the norm now to benchmark results on far larger datasets using parallelism, specialized hardware in conjunction with algorithmic speedups (e.g., using random feature methods, low-rank approximations such as Nystrom and other approaches). As such the paper is unlikely to generate much interest in the ICLR community in its current form.
Decision: Reject