Title: SMALL CORESETS TO REPRESENT LARGE TRAINING DATA FOR SUPPORT VECTOR MACHINES

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

1. INTRODUCTION:

Popular machine learning algorithms are computationally expensive, or worse yet, intractable to train on Big Data. The notion of using coresets (Feldman & Langberg, 2011; Braverman et al., 2016; Bachem et al., 2017) , small weighted subsets of the input points that provably approximate the original data set, has shown promise in accelerating machine learning algorithms such as kmeans clustering (Feldman & Langberg, 2011) , mixture model training (Feldman et al., 2011; Lucic et al., 2017) , and logistic regression (Huggins et al., 2016) .

Coreset constructions were originally introduced in the context of computational geometry (Agarwal et al., 2005) and subsequently generalized for applications to other problems (Langberg & Schulman, 2010; Feldman & Langberg, 2011) . Coresets provide a compact representation of the structure of static and streaming data, with provable approximation guarantees with respect to specific algorithms. For instance, a data set consisting of K clusters would yield a coreset of size K, with each cluster represented by one coreset point. Even if the data has no structure (e.g., uniformly distributed), coresets will correctly down sample the data to within prescribed error bounds. For domains where the data has structure, the coreset representation has the potential to greatly and effectively reduce the time required to manually label data for training and the computation time for training, while at the same time providing a mechanism of supporting machine learning systems for applications with streaming data.

Coresets are constructed by approximating the relative importance of each data point in the original data set to define a sampling distribution and sampling sufficiently many points in accordance with this distribution. This construction scheme suggests that beyond providing a means of conducting provably fast and accurate inference, coresets also serve as efficient representations of the full data set and may be used to automate laborious representation tasks, such as automatically generating semantic video representations or detecting outliers in data (Lucic et al., 2016) .

The representative power and provable guarantees provided by coresets also motivate their use in training of one of the most popular algorithms for classification and regression analysis: Support Vector Machines (SVMs). Despite their popularity, SVMs are computationally expensive to train on massive data sets, which has proven to be computationally problematic with the rising availability of Big Data. In this paper, we present a novel coreset construction algorithm for efficient, large-scale Support Vector Machine training.

In particular, this paper contributes the following:

1. A practical coreset construction algorithm for accelerating SVM training based on an efficient importance evaluation scheme for approximating the importance of each point.

2. An analysis proving lower bounds on the number of samples required by any coreset construction algorithm to approximately represent the data.

3. An analysis proving the efficiency and theoretical guarantees of our algorithm and characterizing the family of data sets for which applications of coresets are most suited.

4. Evaluations against synthetic and real-world data sets that demonstrate the practical effectiveness of our algorithm for large-scale SVM training.

2. RELATED WORK:

Training a canonical Support Vector Machine (SVM) requires O(n 3 ) time and O(n 2 ) space where n is the number of training points (Tsang et al., 2005) . Work by Tsang et al. (2005) introduced Core Vector Machines (CVMs) that reformulated the SVM problem as the Minimum Enclosing Ball (MEB) problem and used existing coreset methods for MEB to compress the data. The authors proposed a method that generates a (1 + ε) 2 approximation to the two-class L2-SVM in O(n/ε 2 + 1/ε 4 ) time, when certain assumptions about the kernel used are satisfied. However, CVM's accuracy and convergence properties have been noted to be at times inferior to the performance of existing SVM implementations (Loosli & Canu, 2007) . Similar geometric approaches including extensions to the MEB formulation, those based on convex hulls, and extreme points, among others, were also investigated by Rai et al. (2009) ; Agarwal & Sharathkumar (2010); Har-Peled et al. (2007); Nandan et al. (2014) .

Since the SVM problem is inherently a quadratic optimization problem, prior work has investigated approximations to the quadratic programming problem using the Frank-Wolfe algorithm or Gilbert's algorithm (Clarkson, 2010) . Another line of research has been in reducing the problem of polytope distance to solve the SVM problem (Gärtner & Jaggi, 2009) . The authors establish lower and upper bounds for the polytope distance problem and use Gilbert's algorithm to train an SVM in linear time.

A variety of prior approaches were based on randomized algorithms with the property that they generated accurate approximations with high probability. Most notable are the works of Clarkson et al. ( 2012) Hazan et al. (2011) . Hazan et al. (2011) used a primal-dual approach combined with Stochastic Gradient Descent (SGD) in order to train linear SVMs in sub-linear time. They proposed the SVM-SIMBA approach and proved that it generates an ε-approximate solution with probability at least 1/2 to the SVM problem that uses hinge loss as the objective function. The key idea in their method is to access single features of the training vectors rather than the entire vectors themselves. Their method is nondeterministic and returns the correct ε-approximation with probability greater than a constant probability, similar to the probabilistic guarantees of coresets. 

3. PROBLEM DEFINITION:



3.1. SOFT-MARGIN SVM:

We assume that we are given a set of weighted training points P = {(x i , y i )} n i=1 with the corresponding weight function u : P → R ≥0 , such that for every i ∈ [n], x i ∈ R d , y i ∈ {-1, 1}, and u(p i ) corresponds to the weight of point p i . For simplicity, we assume that the bias term is embedded into the feature space by defining xi = (x i , 1) for each point and w = (w, 1) for each query. Thus, we henceforth assume that we are dealing with d + 1 dimensional points and refer to w and xi as just w and x i respectively. Under this setting, the hinge loss of a point p i = (x i , y i ) with respect to the separating hyperplane w is defined as

h(p i , w) = [1 -y i x i , w ] + , where [x] + = max{0, x}.

For any subset of points, P ⊆ P, define H(P , w) = p∈P u(p)h(p, w) as the sum of the hinge losses and u(P ) = p∈P u(p) as the sum of the weights of points in set P . To clearly depict the contribution of each point to the objective value of the SVM problem, we present the SVM objective function, f (P, w), as the sum of per-point objective function evaluations, which we formally define below.

Definition 1 (Per-point Objective Function). Define the function f

: (R d+1 × {-1, 1}) × R d+1 → R ≥0 such that for every i ∈ [n] f (p i , w) = w 1:d 2 2 2u(P) + Ch(p i , w),

w 1:d denotes the entries 1 : d of w, h(p i , w) is the corresponding hinge loss, and C ∈ [0, 1] is the regularization parameter.

Definition 2 (Soft-margin SVM Problem). Given a set of d + 1 dimensional weighted points P with weight function u : P → R ≥0 the primal of the SVM problem is expressed by the following quadratic program

EQUATION

)

where f is the evaluation of the weighted point set P with weight function u :

EQUATION

When the set of points P and the corresponding weight function u are clear from context, we will henceforth denote f ((P, u), w) by f (P, w) for notational convenience.

3.2. CORESETS:

Coresets can be seen as a compact representation of the full data set that approximate the SVM cost function ( 2) uniformly over all queries w ∈ Q. Thus, rather than introducing an entirely new algorithm for solving the SVM problem, our approach is to reduce the runtime of standard SVM algorithms by compressing the size of the input points from n to a compact set whose size is sublinear (ideally, polylogarithmic) in n.

Definition 3 (ε-coreset). Let ε ∈ (0, 1/2) and P ⊂ R d+1 × {-1, 1} be a set of n weighted points with weight function u : P → R ≥0 . The weighted subset (S, v), where S ⊂ P with corresponding weight function v : S → R ≥0 is an ε-coreset if for any query w ∈ Q, (S, v) satisfies the coresetproperty

EQUATION

Our overarching goal is to efficiently construct an ε-coreset, (S, v), such that the size of S is sufficient small in comparison to the original number of points n.

4. METHOD:



4.1. METHOD OVERVIEW:

Our coreset construction scheme is based on the unified framework of Langberg & Schulman (2010) ; Feldman & Langberg (2011) and is shown as Alg. 1. The crux of our algorithm lies in generating the importance sampling distribution via efficiently computable upper bounds (proved in Sec. 5) on the importance of each point (Lines 1-6). Sufficiently many points are then sampled from this distribution and each point is given a weight that is inversely proportional to its sample probability (Lines 7-9). The number of points required to generate an ε-coreset with probability at least 1 -δ is a function of the desired accuracy ε, failure probability δ, and complexity of the data set (t from Theorem 9). Under mild assumptions on the problem at hand (see Sec. 5.2), the required sample size is polylogarithmic in n.

Intuitively, our algorithm can be seen as an importance sampling procedure that first generates a judicious sampling distribution based on the structure of the input points and samples sufficiently many points from the original data set. The resulting weighted set of points, (S, v), serves as an unbiased estimator for f (P, w) for any query w ∈ Q, i.e., E[f ((S, v), w)] = f (P, w). Although sampling points uniformly with appropriate weights can also generate such an unbiased estimator, it turns out that the variance of this estimation is minimized if the points are sampled according to the distribution defined by the ratio between each point's sensitivity and the sum of sensitivities, i.e., γ(p i )/t on Line 9 (Bachem et al., 2017) .

4.2. CHICKEN AND THE EGG PHENOMENA:

Coresets are intended to provide efficient and provable approximations to the optimal SVM solution, however, the very first line of our algorithm entails computing the optimal solution to the SVM problem. This seemingly eerie phenomenon is explained by the merge-and-reduce technique (Har-Peled & Mazumdar, 2004 ) that ensures that our coreset algorithm is only run against small partitions of the original data set (Har-Peled & Mazumdar, 2004; Braverman et al., 2016; Lucic et al., 2017) . The merge-and-reduce approach leverages the fact that coresets are composable and reduces the coreset construction problem for a (large) set of n points into the problem of computing coresets for n

2|S|:

points, where 2|S| is the minimum size of input set that can be reduced to half using Alg. 1 (Braverman et al., 2016) . Assuming that the sufficient conditions for obtaining polylogarithmic size coresets implied by Theorem 9 hold, the overall time required for coreset construction is nearly linear in n, O ε,δ (d 3 n)1 . This follows from the fact that 2|S| = O δ,ε (d) by Theorem 9, that the Interior Point Method runs in time O(|S| 3 ) = Õδ,ε (d 3 ) for an input set of size 2|S|, and that the merge-and-reduce tree has height at most log n , meaning that an accuracy parameter of ε = ε/ log n has to be used in the intermediate coreset constructions to account for the compounded error over all levels of the tree (Braverman et al., 2016) .

4.3. EXTENSIONS:

We briefly remark on a straightforward extension that can be made to our algorithm to accelerate performance and applicability. In particular, the computation of the optimal solution to the SVM problem in line 1 can be replaced by an efficient gradient-based method, such as Pegasos (Shalev-Shwartz et al., 2011) , to compute an approximately ξ optimal solution in O (dnC/ξ) time, which is particularly suited to scenarios with C small. We give this result as Lemma 11, an extension of Lemma 7. We also note that based on our analytical results (Lemmas 7 and 11), any SVM solver, either exact or approximate, can be used in Line 1 as a replacement for the Interior Point Method.

5. ANALYSIS:

In this section, we prove upper and lower bounds on the sensitivity of a point in terms of the complexity of the given data set. Our main result is Theorem 9, which establishes sufficient conditions Algorithm 1: CORESET(P, u, ε, δ)

Input::

A set of training points P ⊆ R d+1 × {-1, 1} containing n points, a weight function u : P → R ≥0 , an error parameter ε ∈ (0, 1), and failure probability δ ∈ (0, 1).

Output::

An ε-coreset (S, v) with probability at least 1 -δ.

// Compute the optimal solution using an Interior Point Method. w * ← InteriorPointMethod(P, u, C) K yi ← u(P c yi )/ (2u(P) • u(P yi )) for each y i ∈ {-1, 1}; // Compute an upper bound for the sensitivity of each point according to Eqn.( 5).

for i ∈ [n] do p ∆ ← (p yi -p i ) where pyi = 1 u(Py i ) q∈Py i u(q) q γ(p i ) ← u(pi) u(Py i ) + Cu(pi) 2f (P,w * ) w * , p ∆ - Ky i C 2 + 2f (P, w * ) p ∆ 2 2 + w * , p ∆ - Ky i C t ← i∈[n] γ(p i ) Let m ← Ω t ε 2 d log t + log(1/δ) (K 1 , . . . , K n ) ∼ Multinomial (m, π i = γ(p i )/t ∀i ∈ [n]) S ← {p i ∈ P : K i > 0} // Compute the weights v : S → R ≥0 for every point p i ∈ S. for i ∈ [n] do v(p i ) ← tKiu(pi) γ(pi)|S| return (S, v)

for the existence of small coresets depending on the properties of the data. Our theoretical results also highlight the influence of the regularization parameter, C, in the size of the coreset. Definition 4 (Sensitivity (Braverman et al., 2016) ). The sensitivity of an arbitrary point p ∈ P, p = (x, y) is defined as

EQUATION

where u : P → R ≥0 is the weight function as before.

5.1. SENSITIVITY LOWER BOUND:

We first prove the existence of a hard point set for which the sum of sensitivities is approximately Ω(nC), ignoring d factors, which suggests that if the regularization parameter is too large, then the required number of samples for property (3) to hold is Ω(n). Lemma 5. There exists a set of n points P such that the sensitivity of each point p i is bounded below by Ω d 2 +nC n(C+d 2 ) and the sum of sensitivities is bounded below by Ω d 2 +nC C+d 2 .

The same hard point set from Lemma 5 can be used to also prove a bound that is nearly exponential in the dimension, d. Corollary 6. There exists a set of n points P such that the total sensitivity is bounded below by

Ω d 2 +C(2 d / √ d) d 2 +C .

We next prove upper bounds on the sensitivity of each data point with respect to the complexity of the input data. Despite the non-existence results established above, our upper bounds shed light into the class of data sets for which coresets of sufficiently small size exist, and thus have potential to significantly speed up SVM training.

5.2. SENSITIVITY UPPER BOUND:

For any arbitrary point p = (x i , y i ) ∈ P, let P yi ⊂ P denote the set of points of label y i , let P c yi = P \ P yi be its complement, and let w * denote the optimal solution to the SVM problem (2). We assume that the points are normalized to have a Euclidean norm of at most one, i.e., ∀(x, y) ∈ P x 1:d 2 ≤ 1, where x 1:d refers to original input point, without the bias embedding. Lemma 7. The sensitivity of any point p i ∈ P is bounded above by

EQUATION

where p ∆ = pyi -p i and K yi = u(P c yi )/ (2u(P) • u(P yi )).

Let P + = P 1 ⊂ P and P -= P \ P 1 denote the set of points with positive and negative labels respectively. Let p+ and pdenote the weighted mean of the positive and labeled points respectively, and for any p i ∈ P + let p + ∆i = p+ -p i and p - ∆i = p--p i . Lemma 8. The sum of sensitivities over all points P is bounded by S(P) ≤ 2 + C (Var(P + ) + Var(P -))

EQUATION

where f (P, w * ) is the optimal value of the SVM problem, and Var(P + ) and Var(P -) denote the total deviation of positive and negative labeled points from their corresponding label-specific mean

Var(P + ) = pi∈P+ u(p i ) p + ∆i 2 = pi∈P+ u(p i ) p+ -p i 2 Var (P -) = pi∈P- u(p i ) p - ∆i 2 = pi∈P- u(p i ) p--p i 2 .

Theorem 9. Given any ε ∈ (0, 1/2), δ ∈ (0, 1) and a weighted data set P with corresponding weight function u, with probability greater than 1 -δ, Algorithm 1 generates an ε-coreset, i.e., a weighted set (S, v), of size S ∈ Ω t ε 2 d log t + log(1/δ) in O(n 3 ) time, where t is the upper bound on the sum of sensitivities from Lemma 8, t = 2 + C (Var(P + ) + Var(P -))

f (P, w * ) .

For any subset T ⊆ P, let w * T denote the optimal separating hyperplane with respect to the set of points in T . The following corollary immediately follows from Theorem 9 and implies that training an SVM on an ε-coreset, (S, v), to obtain w * S yields a solution that is provably competitive with the optimal solution on the full data-set, w * P = w * . Corollary 10. Given any ε ∈ (0, 1/2), δ ∈ (0, 1) and a weighted data set (P, u), the weighted set of points (S, v) generated by Alg. 1 satisfies f ((P, u), w * S ) ≤ (1 + 4ε)f ((P, u), w * P ), with probability greater than 1 -δ.

Sufficient Conditions Theorem 9 immediately implies that, for reasonable ε and δ, coresets of polylogarithmic (in n) size can be obtained if d = O(polylog(n)), which is usually the case in our target applications, and if C (Var(P + ) + Var(P -))

f (P, w * ) = O(polylog(n)).

For example, a value of C ≤ log n n for the regularization parameter C satisfies the sufficient condition for all data sets with normalized points.

Interpretation of Bounds Our approximation of the sensitivity of a point p i ∈ P, i.e., its relative importance, is a function of the following highly intuitive variables.

1. Relative weight with respect to the weights of points of the same label (u(p i )/u(P yi )): the sensitivity increases as this ratio increases. 2. Distance to the label-specific mean point pyi -p i 2 : points that are considered outliers with respect to the label-specific cluster are assigned higher importance. 3. Distance to the optimal hyperplane ( w * , p ∆ ): importance increases as distance of the difference vector p ∆ = pyi -p i to the optimal hyperplane increases.

Note that the sum of sensitivities, which dictates how many samples are necessary to obtain an εcoreset with probability at least 1 -δ and in a sense measures the difficulty of the problem, increases monotonically with the sum of distances of the points from their label-specific means.

We conclude our analysis with an extension of Lemma 7 to the case where only an approximately optimal solution to the SVM problem is available. Lemma 11. Consider the case where only a ξ-approximate solution ŵ is available such that f (P, ŵ) ≤ f (P, w * ) + ξ, for ξ ∈ (0, f (P, w * )/2). Then, the sensitivity of any arbitrary point p i ∈ P is bounded above by

s(p i ) ≤ u(p i ) u(P yi ) + Cu(p i ) ŵ, p ∆ - Ky i C 2 + 4 (f (P, ŵ) -2ξ) p ∆ 2 2 + ŵ, p ∆ - Ky i C 2 (f (P, ŵ) -2ξ) ,

where p ∆ = pyi -p i and K yi = u(P c yi )/ (2u(P) • u(P yi )) as in Lemma 7.

6. RESULTS:

We evaluate the performance of our coreset construction algorithm against synthetic and real-world, publicly available data sets (Lichman, 2013) . We compare the effectiveness of our method to uniform subsampling on a wide variety of data sets and also to Pegasos, one of the most popular Stochastic-Gradient Descent based algorithm for SVM training (Shalev-Shwartz et al., 2011) . For each data set of size N , we selected a set of M = 10 subsample sizes S 1 , . . . , S M ⊂ [N ] and ran each coreset construction algorithm to construct and evaluate the accuracy subsamples sizes S 1 , . . . , S M . The results were averaged across 100 trials for each subsample size. Our results of relative error and sampling variance are shown as Figures 1 and 3 . The computation time required for each sample size and approach can be found in the Appendix (Fig. 4 ). Our experiments were implemented in Python and performed on a 3.2GHz i7-6900K (8 cores total) machine with 16GB RAM. We considered the following data sets for evaluation.

• Pathological -1, 000 points in two dimensional space describing two clusters distant from each other of different labels, as well as two points of different labels which are close to each other. We note that uniform sampling performs particularly poorly against this data set due to the presence of outliers. • Synthetic & Synthetic100K-The Synthetic and Synthetic100K are datasets with 6, 000, 100, 000 points, each consisting of 3 and 4 dimensions respectively. The datasets describe two blocks of mirrored nested rings of points, each of different labels such that Gaussian noise has been added to them. • HTRU2 -17, 898 radio emissions of Pulsar (rare type of Neutron star) each consisting of 9 features. • CreditCard3 -30, 000 client entries each consisting of 24 features that include education, age, and gender among other factors.

• Skin4 -245, 057 random samples of B,G,R from face images consisting of 4 dimensions.

Evaluation We computed the relative error of the sampling-based algorithms with respect to the cost of the optimal solution to the SVM problem, f (P, w * P ) and the approximate cost generated by the subsample, f ((S, v), w * S ). We have also evaluated against Pegasos, running Pegasos the amount of time needed to construct the coreset and comparing the resulted error, applying 128 repetitions as presented at Figure 2 . Furthermore, we have run our coreset constructing under streaming setting, where subsamples are used as leaf size and half of the leaf's size is then used to set the subsample for our sampling approach. In addition, we also compared our coreset construction's related error to CVM's related error with respect to the cost of the optimal solution to the SVM problem, as function of subsample sizes. Finally, we have evaluated the variance of the estimators for the sampling-based approaches and observed that the variances of the estimates generated by our coreset were lower than those of uniform subsampling. contributed by other points j ∈ [n], j = i note that B i \ B j = ∅, thus:

w i , p j = l∈Bi\Bj w il p jl ≥ γ(1/γ) = 1,

which implies that h(p j , w i ) = 0. Thus, it follows that H(w

i ) = j∈[n] h(p j , w i ) = 1.

Putting it all together, we have for the sensitivity of any arbitrary i ∈ [n]: Proof. Consider the set of points P from the proof of Lemma 5 and note that

s(p i ) = sup w∈Q f (p i , w) j∈[n] f (p j , w) ≥ d 2 8n + C h(p i , w i ) ||wi|| 2 2 + C = d 2 8n + C d 2 8 + C .

n = d d/2 ≥ 2 d (1 -1/d) π(d/2) ≥ 2 d √ d = Ω(2 d / √ d).

8 

where the last inequality follows from the fact that for any w ∈ Q, w 1:d 2 ≥ 1 since the points are normalized, and thus,

f (P c yi , w) 2u(P yi ) ≥ w 1:d 2 2 u(P c yi ) 2u(P)u(P yi )

≥ u(P c yi )/ (2u(P) • u(P yi )) .

Now consider the expression involving the supremum from ( 7) and let

EQUATION

be the constant independent of w in the numerator, let p ∆ = pyi -p, and let w ∆ = w -w * for notational convenience. We observe that by λ-strong convexity of the SVM objective function for λ = 1, we have the inequality f (P, w * ) + λ w -w * 2 2 /2 ≤ f (P, w) for any w ∈ Q. Thus, the expression containing the supremum from ( 7) is bounded by

EQUATION

where a = w * , p ∆ , b = -K yi /C, c = 1/(2C), and d = f (P, w * )/C are constants independent of w ∆ . Analytical optimization based on the gradient of the term above yields the optimal solution, w

EQUATION

)

We resolve the interdependency on w * ∆ by observing that

w * ∆ , p ∆ = p ∆ 2cz , p ∆ = p ∆ 2 2 2cz and w * ∆ 2 2 = w * ∆ , w * ∆ = p ∆ 2 2 (2cz) 2 , which implies that w * ∆ 2 2 = w * ∆ , p ∆ /(2cz).

Putting it all together, we obtain

z ≤ (a + b) 2 + d p∆ 2 2 c + a + b 2d = C 2f (P, w * ) ( w * , p ∆ -K yi /C) 2 + 2f (P, w * ) p ∆ 2 2 + w * , p ∆ -K yi /C ,

and the sensitivity bound follows.

8.4. PROOF OF LEMMA 8:

Proof. Let P + = P 1 ⊂ P and P -= P \P 1 denote the set of points with positive and negative labels respectively and let K + and K -denote the corresponding constants defined by (8). Let p+ and pdenote the weighted mean of the positive and labeled points respectively, and for any p i ∈ P + let p + ∆i = p+ -p i and p - ∆i = p--p i . Since the sensitivity can be decomposed into sum over the two disjoint sets, i.e., S(P) = p∈P s(p) = p∈P1 s(p) + p∈P-s(p) = S(P 1 ) + S(P -), we consider first bounding S(P 1 ). Invoking Lemma 7 yields

S(P 1 ) ≤ 1 + pi∈P+ Cu(p i ) 2f (P, w * ) w * , p + ∆i -K + /C 2 + 2f (P, w * ) p + ∆i 2 2 + w * , p + ∆i -K + /C ≤ 1 + pi∈P+ Cu(p i ) 2f (P, w * ) w * , p + ∆i -K + /C 2 + 2f (P, w * ) p + ∆i 2 2 ≤ 1 + C f (P, w * ) pi∈P+ u(p i ) p + ∆i 2 f (P, w * ) = 1 + C f (P, w * ) pi∈P+ u(p i ) p + ∆i 2 ,

where the second equality follows by the definition of K + and the fact that

pi∈P+ u(p i ) w * , p + ∆i = pi∈P+ u(p i ) w * , p+ - pi∈P+ u(p i ) w * , p i = w * , p+ pi∈P+ u(p i ) - pi∈P+ u(p i ) w * , p i = 0,

and the third by noting that ( w * , p + ∆i -K + /C) 2 ≤ 2f (P, w * ) p + f (P, w * ) = t.

8.5. PROOF OF THEOREM 9:

Proof. By Lemma 8 and Theorem 5.5 of Braverman et al. (2016) we have that the coreset constructed by our algorithm is an ε-coreset with probability at least 1 -δ if

|S| ≥ Ω t ε 2 d log t + log(1/δ) ,

where we used the fact that the VC dimension of a separating hyperplane in the case of a linear kernel is bounded dim(F) ≤ d + 1 = O(d) (Vapnik & Vapnik, 1998) . Moreover, note that the computation time of our algorithm is dominated by computing the optimal solution of the SVM problem using interior-point Method which takes O(d 3 L) = O(n 3 ) time (Nesterov & Nemirovskii, 1994) , where L is the bit length of the input data.

Under review as a conference paper at ICLR 2018 8.6 PROOF OF COROLLARY 10

Proof. By theorem 9, (S, v) is an ε-coreset for (P, u) with probability at least 1 -δ, thus we have f ((P, u), w * P ) ≤ f ((P, u), w * S ) ≤ f ((S, v), w * S ) 1 -ε ≤ (1 + ε)f ((P, u), w * P ) 1 -ε ≤ (1 + 4ε)f ((P, u), w * P ).

8.7. PROOF OF LEMMA 11:

Proof. The proof is almost identical to that of Lemma 7, thus we use the same techniques to arrive at the following inequality with ŵ instead of w * and with w ∆ = w -ŵ: 

s(p i ) u(p i ) = sup

:

O ε,δ notation suppresses ε, δ and polylog(n) factors.

https://archive.ics.uci.edu/ml/datasets/HTRU2

https://archive.ics.uci.edu/ml/datasets/default+of+credit+card+clients

https://archive.ics.uci.edu/ml/datasets/Skin+Segmentation/

Figures and Tables:

Figure 1: The relative error of query evaluations with respect uniform and coreset subsamples for the 4 data sets.

Figure 2: The relative error of query evaluations with respect to coreset running time and Pegasos running time for the 4 data sets.

Figure 4: Computation + Training Time vs. Sample Size

Figure6: The relative error of query evaluations with respect uniform, coreset, and Core Vector Machine (CVM)(Tsang et al., 2005) subsamples for the 4 data sets.

since by Cauchy-Schwarz and definition of f (P, w * ) we havew * , p + ∆i -K + /C ≤ w * 2 p + ∆i 2 ≤ 2f (P, w * ) p + ∆i 2 .Using the same argument as above, an analogous bound holds for S(P -), thus we have S(P) ≤ 2 + C f (P, w * ) (P + ) + Var(P -))

[ w, pyi -p ] + -u(P c yi )/(2u(P) • u(P yi )) f (P, w)≤ 1 u(P yi ) + sup w∆∈Q C [ w ∆ , p ∆ + ŵ, p ∆ ] + -K yi f (P, w * ) + w -w * 2 2 /2. Now, consider the supremum term and note that (i) f (P, w * ) ≥ f (P, ŵ) -ξ by definition of ŵ and(ii) w -w * 2 2 /2 ≥ w -ŵ 2 2 /4 -ξ,since by the Cauchy-Schwarz inequality we have where the last inequality follows by strong convexity of f and by definition of our approximation:ŵ -w * 2 2 2 ≤ f (P, ŵ) -f (P, w * ) ≤ ξ.Combining (i) and (ii) yields for the supremum termsup w∆∈Q C [ w ∆ , p ∆ + ŵ, p ∆ ] + -K yi f (P, w * ) + w -w * 2 2 /2 ≤ sup w∆∈Q C [ w ∆ , p ∆ + ŵ, p ∆ ] + -K yi f (P, ŵ) -2ξ + w ŵ, p ∆ , b = -K yi /C, c = 1/(4C), and d = (f (P, ŵ) -2ξ) /C are constants independent of w ∆ .This is the exact same expression as in the proof of Lemma 7, with the exception of slightly different values for the constants above. Thus, analytical optimization yields the same optimal solution as before and thus we have

.3 PROOF OF LEMMA 7Proof. Consider any arbitrary point p i ∈ P and let p = x i y i for brevity when the point p i = (x i , y i ) is clear from the context. We proceed to bound s(p i )/u(p i ) by first leveraging the Lipschitz

Table content: <table><tr><td colspan="7">continuity of hinge loss and convexity of f</td></tr><tr><td>s(p i ) u(p i )</td><td colspan="3">= sup w∈Q(P)</td><td colspan="2">f (p i , w) f (P, w)</td></tr><tr><td/><td colspan="2">≤ sup w∈Q</td><td colspan="4">f (p yi , w) + C [ w, pyi -p ] + f (P, w)</td><td>Lipschitz Continuity</td></tr><tr><td/><td colspan="2">≤ sup w∈Q</td><td/><td colspan="2">q∈Py i u(P yi )f (P, w) u(q)f (q, w)</td><td>+</td><td>C [ w, pyi -p ] + f (P, w)</td><td>Jensen's Inequality</td></tr><tr><td/><td colspan="2">= sup w∈Q</td><td colspan="4">f (P yi , w) + f (P c yi , w) -f (P c yi , w) u(P yi )f (P, w)</td><td>+</td><td>C [ w, pyi -p ] + f (P, w)</td></tr><tr><td/><td>=</td><td colspan="2">1 u(P yi )</td><td>+ sup w∈Q</td><td colspan="2">C [ w, pyi -p ] + f (P, w)</td><td>-</td><td>f (P c yi , w) u(P yi )f (P, w)</td></tr><tr><td/><td>≤</td><td colspan="2">1 u(P yi )</td><td>+ sup w∈Q</td><td colspan="2">C [ w, pyi -p ] + -u(P c yi )/(2u(P) • u(P yi )) f (P, w)</td><td>,</td></tr></table>

Peer review (iclr2018):
 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.