Despite their popularity, even efficient implementations of Support Vector Machines (SVMs) have proven to be computationally expensive to train at a largescale, especially in streaming settings. In this paper, we propose a coreset construction algorithm for efficiently generating compact representations of massive data sets to speed up SVM training. A coreset is a weighted subset of the original data points such that SVMs trained on the coreset are provably competitive with those trained on the original (massive) data set. We provide lower and upper bounds on the number of samples required to obtain accurate approximations to the SVM problem as a function of the complexity of the input data. Our analysis also establishes sufficient conditions on the existence of sufficiently compact and representative coresets for the SVM problem. We empirically evaluate the practical effectiveness of our algorithm against synthetic and real-world data sets.
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.