A Consolidated Cross-Validation Algorithm for Support Vector Machines via Data Reduction
Authors: Boxiang Wang
Yi Yang
Venue: NeurIPS 2022 Accept (2022)
Keywords: Cross-validation
Data reduction
Exact leave-one-out lemma
Reproducing kernel Hilbert spaces
Support vector machines

Abstract: We propose a consolidated cross-validation (CV) algorithm for training and tuning the support vector machines (SVM) on reproducing kernel Hilbert spaces. Our consolidated CV algorithm utilizes a recently proposed exact leave-one-out formula for the SVM and accelerates the SVM computation via a data reduction strategy. In addition, to compute the SVM with the bias term (intercept), which is not handled by the existing data reduction methods, we propose a novel two-stage consolidated CV algorithm. With numerical studies, we demonstrate that our algorithm is about an order of magnitude faster than the two mainstream SVM solvers, kernlab and LIBSVM, with almost the same accuracy. 

A Consolidated Cross-Validate Validation Algorithm for Support Vector Machines via Data Reduction
Boxiang Wang
Archer Y. Yang Department of Mathematics and Statistics McGill University
Department of Statistics and Actuarial Science
University of lowa Iowa City, IA 52242, USA
Montreal, QC H3A 0B9, Canada archer.. archer. saahber.yan@mmgill....
boxiang-wang@un edu
Abstract
We propose consolidated cross-validation (CV) algorithm for training and tuning the support vector machines (SVM) on reproducing kernel Hilbert spaces. Our consolidated CV algorithm utilizes recently proposed exact leave-one-out formula for the SVM and accelerates the SVM computation via data reduction strategy. In addition, to compute the SVM with the bias term (intercept), which is not handled by the existing data reduction methods, we propose novel two-stage consolidated CV algorithm. With numerical studies, we demonstrate that our algorithm is about order of magnitude faster than the two mainstream SVM solvers, kernlab and LIBSVM, with almost the same accuracy.
1 Introduction
This paper concerns one of the most successful classifiers, the kernel support vector machine (SVM) (Cortes and Vapnik 1995 Vapnik 1995 1998), which has been popularly used on structured data in the past two decades. The success of the SVM mainly attributed its appealing geometric interpretation, solid theoretical foundation, and high predictive power. To assess the predictive accuracy of the SVM, cross-validation (Wabaa and Wold 1975) Arlot and Celisse 2010) is perhaps the most commonly used method in practice. In k-fold CV procedure, the training data is randomly split into K equal-sized groups Based on data splitting, part of the data is used for training each competing model and the rest of the data is reserved for evaluating the prediction error. The model with the smallest CV error is finally elected. Typical choices of are 5. 10, or n (the sample size), where K n yields the so-called leave-one-out cross-validation (LOOCV).
LOOCV is generally less used than ten-fold and five-fold CV, largely because of the two popular arguments: (1) high computational cost of LOOCV; (2) much larger variance than five-fold ten-fold CV. We must point out that while the first argument is true some sense, the second argument is not generally true about LOOCV, For instance, Kohavi (1995) and Hastie al. 2009) argue that leave-one-out almost unbiased, but it has high variance, leading to unreliable estimates. A series of revealing works, e.g., Burman (198)); Bengio and Grandvalet (2004) Molinaro et al. (2055; Zhang and Yang (015)), have shown that, both empirically and theoretically. for modeling procedures with low instability, LOOCV often has the smallest variability. For example, in the context of the kernel SVM, Wang and Zou (202I) provided convincing numerical examples to show that (1) LOOCV has almost bias in estimating the generalization error; (2) LOOCV does not necessarily have higher variance than ten-fold and five-fold CV. Consequently LOOCV results in a smaller overall error when estimating the prediction error compared with ten-fold and five-fold CV.
From the aforementioned arguments, we can see the only legitimate complaint of LOOCV would arise from its expensive computation, as typical approach needs to fit the models times on the leave-one-out data before evaluating their performance with each of the sample removed, so the
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

computational cost is roughly n times as large as the cost of a single fit on the full data. To mitigate the computational burden, Golub et al. (1779) proposed a shorteut formula of LOOCV for smoothing splines such that the whole computation time is of the same order of fitting a single model, and the shorteut formula later evolved into the generalized cross-validation (GCV) for ridge regression.
Nevertheless, for the kernel classifiers, how to efficiently compute the exact LOOCV is a long- standing open problem. The shorteut cross-validation formula has been long considered as a unique property of some linear smoothers, and many works such as the generalized approximated cross- validation (GACV) (Wahba et al. 1999) resorted approximating LOOCV, while there is no theoretical guarantee that LOOCV can always be well approximated. To solve the exact (rather than approximated) LOOCV, until very recently, Wang and Zoul (2022) successfully proposed a leave-one-ord out lemma extending the Golub-Heath- Wahba formula to the kernel classifiers. Specifically, they showed the exact LOOCV error can be obtained by slightly varying the class labels without literally leaving out some samples during the CV procedure. Since no sample is left out, all the folds of LOOCV are using the same complete data and thus redundant computational efforts can be saved to dramatically accelerate LOOCV. Based on the leave-one-out lemma, Wang and Zou (2022) unified the training and tuning of the SVM and developed a new magicavm algorithm, which often runs a magnitude faster than the state-of-art SVM solvers, e.g., kernlab (Karatzoglou et al. 2004) and LIBSVM Chang and Lin 2011).
In this work, the main contribution is to propose a consolidated CV algorithm via data reduction. The data reduction method was first proposed by Ghaoui et al. (2010) for the lasso method ( (Tibshirani 1996) and then extended to the SVM (Ogawa et al.) 2013) Wang et al., 2014, Pan and Xu [018]] Hong et al. 2019). The key renovation of our proposal is reduce all the cross-validated data in a consolidated manner, thereby aiming to speedup the whole SVM procedure. Our method is fundamentally different from the existing methods which isolate the model training and tuning. Moreover, the existing data reduction methods cannot handle the SVM with the bias (intercept), which is essentially useful for achieving high prediction accuracy. To handle the SVM with the bias, we propose novel two-stage consolidated CV; such an extension is highly non-trivial
We implement the consolidate CV in a ccvsvm algorithm. Simulations and nine benchmark data are used to demonstrate the superior performance of ccvsvm To give quick demonstration. our consolidated CV algorithm reduces the run time from more than 1.5 hours (by LIBSVM) to less than one minute, when performing the exact LOOCV for the kemee SVM on data set arrhythmia.
The remainder of this paper is organized as follows. In Section 2, we discuss the exact leave-one-out lemma and then propose a consolidated CV algorithm via data reduction. Section 3 extends the consolidated CV to handle the general SVM problems with the bias. In Section 4, we demonstrate the computational advantages of fitting the kernel SVM using our proposed methods over the other competitors with simulations and real data applications. The paper is concluded in Section 5 with extensions through kernel approximations and discussions on future directions.
2 Methodology
2.1 SVM and the Exact Leave-One-Out Lemma
Since we need to work with the fundamentals of the SVM, we first review the SVM in this section.
We focus on binary classification. Let L(u) =11=u)+= max(1 0) be the hinge loss. Suppose there are n training samples, (x;, = 1,2,..., n. where each x; E RR and y,: = 1. The SVM can be formulated as function estimation problem in reproducing kernel Hilbert space (Wahbal 1990):
i = argmin fEHx
Σ (1 vxi(xx)) Acll
(1)
n
where A > is tuning parameter chosen from a decreasing sequence \r > 12 >...>.> AL. HK. the RKHS, is generated by a bivariate kernel function K : X' X - R. and the classifier f is thus dubbed kernel SVM. Throughout this paper, we consider the universal kernel, whose induced RKHS HK rich enough to yield arbitrarily accurate decision boundaries (Steinwart 2001 Micchelli et al. 2006). A commonly used universal kernel is the radial kernel K (x,,,x) exp(- X X2 1)

---

By the representer theorem
Wahba 1990). problem ① has mnite-iimnnsional solution:
dg argmin a
Σ (1 ooK( + Naa'Ka
(2)
where K is the n x n kernel matrix with Ki = (x;,, xj) and is assumed to be positive definite; K; is its ith row. Thus problem 2 has unique minimizer f(x Ei (x,(x;, To tune the model, with the LOOCV procedure, the SVM fitted the training data with the jth sample opted out: for each / = 1,2,..., I and each j = .,2, n, let at be
a
-
argmin a(--
Σ
( ( [F
(1 1-
+ -- "y)a,
nh
where K1-1 is the leave-one-out kernel matrix induced by the training data without the jth sample. Problem 2 refers to the complete data problem, and problem 33 refers to the LOOCV problem.
The bottleneck of the LOOCV problem is mainly due to the computation involving n different leave-one-out kernel matrices. To reduce the computational burden, this work is based on the exact leave-one-out lemma (Wang and Zou 2022) for the kernel SVM, and the key idea is to obtain the exact LOOCV from the complete kernel matrix.
Lemma 2.1. (Exact leave-one-out lemma) For given j. let u.!² Yi if + j and 0/51 0. Define
1 Σ il-
al = argmin or R
(l--) + Ma''Ka
(4)
Then the solution of problem
3 can be obtained
5 (a|
af
[-1] J41P a.
Although problem can be transformed into problem (4, the solutions of the two problems have
different lengths. Lemma 2.1 indicates that a; (ā ..... af=ي, 0, a aلا ..... ||- 1.1) i.e.
a/77" the jith element of the solution af a|-"), is zero, and the solution of problem 1 can be retrieved by knocking off the jth element from af-3)
As consequence of transforming problem (3) into problem (4). the same kernel matrix K is used in all the folds during LOOCV, rather than the leave-one-out matrices Ki-ji, while slightly different responses are crafted for different j. By sharing the same kernel matrix, some redundant calculations can be saved and Wang and Zou 2022 developed the efficient algorithm magicsvm.
2.2 Consolidated CV via Data Reduction
On the basis of Lemma 2 we propose data reduction strategy to accelerate the LOOCV computa- tion of the kernel SVM, which is referred to as consolidated CV.
For notational convenience, the complete data problem 2 be written special of problem with j = 0. i.e. à = af-0) and
n Σ n
[-0] 0 argmin a
00 th
K(a).
Xaa'Ka Ka
ar n!
where we define y: Y: for each = 1, .... n. By solving problem (4) for all j = 0, 0.1...., n, we both train the SVM through the complete data problem and tune it using LOOCV.
The idea of consolidated CV motivated by the sparsity of the solution a in problem 4 To this, we check the optimality condition of problem (4) by taking the sub-differential of the objective with respect to each K, for each j = 1, 1......::
1 2f Al (0/ K(a)-")) + 2xr0 Vi 1, I.....n, 0 E n
3

---

where (t( is the subgradient of the hinge loss function: aL(t) -1, < 11))(t)))))))))) - 0f
and (t(t) [1-1, if It follows that
if Dن K K [-
<1,
2ndp
0,
if u
Kia
By translating of back to yis we see
if v, K; 11 51 < and
2mAi
(5)
0,
if KK 1 :ori =
Expression ( hints a possible data reduction strategy: before invoking the actual calculation of a if we are advised that y, K' for some i, then we can directly set à-=ي to zero;
likewise, if y K;á < is given, then [-ا] must be yz/(2n)r) unless i = j. We can pre- determine the values of some coordinates and only need to focus on the calculation of the remaining ones. Hence the dimension of problem (4) can be reduced.
The key to performing the data reduction through expression (5) to know whether y K [-
or > 1 for some before d [-jl 5l is actually computed. We present the following theorem.
Theorem 2.2. For some > 1, suppose we have solved
8 = argmin a
Σ (1
vKKaa) + N
1=1
For each i = 1,2, 1...... n. define
a A d
A-11 X VB KK
B
K'000-1
2
2A:
2n
A-1 + A1
A1-1 \ /B 26 Ká
B
2d:
2
2ndi
where B = max; K K(x;, x:). Then for each = 0, 1,...,
n, it holds
a S y: à' < a Vi Vi Further, let (i: a < 1} and (i: a > 1}.
(6)
Then the solution of problem
satisfies that
o/-1
ifi L; ifiER. R.
1,1
2mAi'
0,
1; for some unbounded kernels such as polynomial kernels, we calculate B = ma K (x:, x;) based on training data.
In Theorem 2.2. for radial and Laplacian kernels, we can directly
Note that Theorem 2.2 holds for af-=1, Vj 0, 0.1...., n. By utilizing knowledge of á;-1, the solution of the complete data problem with the tuning parameter A can pre-determining certain coordinates for both the complete data problem and all LOOCV problems with \ i.e., a ---> for all j 0, l,...,n, through L and R. thus performing data reduction in consolidated fashion.
To solve problem Theorem 2.2 implies that a/=-1 for i L and E can be pre-determined, so we only need to solve أ!-ا) for i where = (CUR)) Denote by one-to-one mapping from (1, 2,.,.... nx3} to S, where n, is the cardinality of Let I the x n, sub-matrix of K such that its ith column r; (, Let Σ be the n, X n2 matrix such that Eg Kr(rr)

---

Algorithm Consolidated cross-validation
Input: A > A2 X1, K.y. y-
1: Obtain
④1 argmin ar Rt"
Σ (1 W() + +aaaaa
2: for /or:=20 2,3, ...., L do
3: Construct the L and according Theorem 2.2 Let S (CUR)C.
4: Construct the matrices I and Σ.
5: for j 0, I..... .......7' do
6: if j > O and 0zJ = 0 then
Obtain à 2 dx
7:
8:
else
Construct the vector ybl,
9:
Obtain ?i | by solving problem (8. (If > 0, initialize the algorithm by i)
10:
Obtain a; - from expression
11:
12: end if
end for
14:
end for
Output: Oc, af-"1, for each j 1, ,,, and / 1,2,...,
For each j = 0, 1,..., n, let ybl be the n-vector with the ith element to be o! if E S, and
i S. The solution of problem 4 is obtained as
y
ifi C, if E R.
2nAi
(7)
0,
if E S,
where //
100, the r (i)th element of ((),1
|- Mi
argmin R
n Σ
I'm
".' Klybi
+ 1 yIll I' Aon Em + n
(8)
2nA;
The dimension of problem (8) is na. which is lower than the dimension of the original problem The matrices and Σ are the same for each j = 0, I....,, n. We shall introduce an optimization algorithm for solving problem (8) in the next section.
4
In addition, by utilizing fact that an SVM solution unchanged if non- con-support--vetton data are left out, namely, åy, 0 for some implies a oú, we can directly obtain the jth LOOCV solution from the complete data problem without solving problem (8). We summarize the consolidated CV algorithm in Algorithm
2.3
A Consolidated Algorithm for Solving Problem
Due Theorem 2 can perform LOOCV by solving problem S reduced-optimization problem, for each j. To overcome the computational challenge caused by non-smoothness of the hinge loss, we consider smoothed loss,
2 1+ 1 1- < <u<<ttt
(u)
[u - (1+T))
u <
for some small т >
One can show that Lr has a Lipschitz continuous gradient,
[14 (41) E' (12) < 111 12) 12 E R. Thus a smoothed surrogate of problem ( is
أ!ーي argmin
Σ
n
T M'n
1 U k(yli)) + 1 - I' A Em
2n
i=1
5

---

Problem can be solved using the proximal gradient descent (PGD) algorithm (Parikh and Boyd 2014.. Specifically, the matrix inversion is computed first
1 FT
P-
24
(10)
TLT
Then, for each 0, ....,..,, we update
n 1- p-1
T'z(1)
n 'T'bi I 22t
(11)
/ + n- We claim the above algorithm is consolidated since until convergence, and then let
the same matrix inversion P-1 obtained from equation (IO) can be used in equation (II) for (all folds.) By saving huge computational efforts in inverting n. matrices, the consolidated CV algorithm much more efficient than the standard CV implementation. We also include the warm-start, say, using i to initialize !) - in problem g and Nesterov's s acceleration to further hoost the algorithm.
We just discussed the PGD algorithm for solving a smoothed SVM problem (9) Interestingly, the exact SVM solution based on problem (8) can be obtained by iteratively solving problem (9) with and т - 18 for k > 1. The iteration is able reach the exact
72 where solution of problem (8) finite number steps, following a simple projection step. To conserve space, we omit details and refer interesting readers to Wang and Zou 2022)
3 Two-stage Consolidated CV for the General SVM Problems
The consolidated CV developed in Section does not include the bias; nonetheless, the SVM without the bias may have lower prediction accuracy and its use is limited in certain applications. Although regularized bias can be used by adding a constant feature to the data matrix, the standard practice of the SVM does not regularize the bias term. Thus goal is to compute the SVM with the bias, namely, the general SVM problems. In this section, we extend the consolidated CV to handle the general SVM problems. Such an extension turns out to be non-trivial.
The general SVM problem is formulated as follows,
(Bo.,, ōu) = argmin
Σ y:(- + K(a)4, + AaaKaa
(12)
BOER. oe Hith n1 i=1
and the corresponding LOOCV problems are, j == 11,,....,
(B1 al
ΣΣ 1 1/ (30 K;a)], + tyaaKKa.
argmin
(13)
For notational convenience, we let J. Vi and let ($o.,, āx1) (31 , a -f)")), so we extend problem (13) with j to include the complete data problem (12 as a special case.
The key difficulty of developing the consolidated CV procedure for the general SVM problems is that 18,, -1=" is hard to bound. To this end, propose two-stage consolidated CV procedure, where we give consolidated bound of |.0 A(.-") for all j in the first stage.
For 7 > 1, suppose we have found the solutions of problems (12 and 13 with the tuning parameter
A1-1- Denote these solutions by (Bo,
i)-1) and (6]--1 ā In Lemma 3.1 for each
give consolidated bound of y, à -1 for all j 0, 1......, n and j +
Lemma 3.1. For each i = 1, 2, ..... define
A A
A-1 d /B à Ká.
+ max
yi V,
j=0,1..,m
2
2
j
(14)
min
d + Av 2
yi K'a
A-1- d
v By
a.
Ká.
j=0,1 I.... j
2
1-1

---

Algorithm 2 Bi-section algorithm find 80,, and S
Input: y, % = 10- 1: Compute B+ and B as
B max
max ( 11.
max {1 9/1
+
1)
(1:7) 13
B min
min {G,,1 - 1},,
min
{1 - c/,1} 6.
(w
[tm==1}
2: Let at Bttet et t Bb+ + (at + tct)/2.
3: repeat
4: Compute 2 (b+). (bt).
5: Let at t- bt and b+ + (b+
<
6: Let t b+ and b+ (a+ bb / 2 (b+ 2 0.
7:
until lat - -c c+|ccc <c.
8: Let Bo + at.
3 + B=, b t +c)/2. 9: Let + B
repeat
11: Compute // (b
12: Let + b- and b t- (b + ) bb (b-
13: Let t b and b- + (a b 11
until Ja - c <.
Let P c C
Output: B and Po.1
where B max; K (X x:) and B for the radial kernel. Then for any i = 1,... n, it holds that
T S v K, 1-5l
tt Vi
(15)
On the basis of the bounds of y,Kaaa-)) given in Lemma 3.1 next present Lemma 3.2 and
Lemma 3.3 to give bounds of =1 that are consolidated for all = 0,,,,..,,
Lemma 3.2. With Cj2 and o, from Lemma 3.1 for a given constant b, define Si = {i y&b
}} and S2(b) {i: yab + 6/ > 1]. Let (b) = (iE(S,())usa())) T(y: 1) and n- n_(b) (b) EEE(S [ly -1). Define a (bb) = Eies(() Vi + nb(b) 1 and + (b)
Σ Eies, Vi (b) 1. Then we have
(1) both +f (b) and wb (b) are non-increasing in b;
(2) 1 (b) 0 implies b > a for all j = 0, 1....,
(3) & (b) implies b 31--0) for all j 0, I....,n.
Following Lemma 3.2 we develop a bi-section algorithm in Algorithm to give consolidated bounds 8l-1)
for 0.1 for all j = 0, ...
As shown in Lemma 3.3 Algorithm 2 yields consolidated bounds for 3|-51 for all j = 0, 1..... n.
Lemma 3.3. Suppose the input of Algorithm of Algorithm 2 3 and 87 satisfies that
C and cttp satisfies inequality 115). then the output
27, < A0- < for Vj = =0,1 001, 0,.....,1
(16)
7

---

It immediately follows from Lemma 3.3 that
| - B < Pou - 90,1
(17)
for any j. achieving the goal of the first stage.
We have constructed the bounds in inequalities (15) and (6).. However, these bounds are too loose to develop data reduction rules in practice. The loose bounds are mainly caused by the maximum and minimum operators that are involved in equations (14). To this end, in the second stage, we give refined bounds, which are presented below.
Lemma 3.4. For each 1.2....... ..2.....7. define
Vi
ViK
A1-1 X
VB K
B
B
-o,1)
B
2dt
2dt
16n2
2ndi
Andd
A-1 + A
N-1 A
V
BB
a/
B²
B -o,.)
B
2dt
2
16n
2ndi
4nd
where Bo,1 and 3o, are produced by Algorithm
Then for any j = I,..., n, it holds that
c S K.KKa,
1- S c Vj 0, 0......, n, and # i.
(18)
Hence by Lemmata 3.1 and 3.4 we have
T = max [c T.)) S K & min min t.d cx.
(19)
for any j = 0, 1, n, and j # i. We then use m F. and min (ct, sty) as the input in the bi-section algorithm yield the output Bot and 35, By inequality (88) and Lemma 3.2, we have
P01 < B
<
3t P.t
Vj = 0, ,....,
(20)
Therefore, we glean inequalities (88) and 20 which are the refined bounds of inequalities (15) and (16). Using the refined bounds, we now present the main theorem. Theorem 3.5. The solution of problem
12 âi satisfies:
if E;
6,,1
2n
0,
if E R
for any j j= =;,..., the solution of problem
13 á 1 satisfies:
Y/
if È and i # j; if E R. or = j.
a
a
2ndi
0,
where &t and GT, are given in inequality
19
and
C = (: = 1 and 3i + a < 1 U
{ i: - and - -Bo, + +2 < x1
R di:ve = 1 and Bo, + cT. > 1 U i: -1 and - 33., + o. > 1]
Thus by Theorem 3.5 problem 133 can be solved through some dimtesedddimessionnll optimization problems, which are similar to problem ( where the bias is excluded. Therefore, we can follow the discussions in Section 2.3 to employ the same PGD algorithm and the exact smoothing technique obtain the exact solution for problem (3) Details of the algorithm are omitted to conserve space.

---

Table 1: Run time (in second), objective value, and test error of four kernel SVM solvers under
mixture Gaussian distributed data with p = {20, 200), and n = {200, 400, 800, 1600). The test error is assessed on independently generated test data. The numbers are the average quantities over 50 independent runs and the standard errors are presented in parentheses.
p
7
method
time (s)
objective
test error
method
time (8)
objective
test error
20
200
ccvevn
5.1
0.814 (.005)
0.351 (.007)
kernlab
73.4
0.814 (.005)
0.351 (.007)
magicavn
7.7
0.814 (.005)
0.351 (.007)
LIBSVM
144.4
0.828 (.014)
0.351 (.007)
400
covEvn
44.2
0.827 (.003)
0.332 (.005)
kernlab
334.3
0.827 (.003)
0.332 (.005)
magicavn
87.8
0.827 (.003)
0.332 (.005)
LIBSVM
879.7
0.827 (.003)
0.332 (.005)
800
ccvevn
446.8
0.846 (.002)
0.309 (.002)
kernlab
2220.2
0.846 (.002)
0.309 (.002)
magicavn
847.3
0.846 (.002)
0.309 (.002)
LIBSVM
6519.7
0.846 (.002)
0,310 (.002)
1600
ccvavn
3829.5
0.853 (.001)
0.297 (.001)
kernlab
25530.5
0.853 (.001)
0.297 (.001)
magicavn
7024.1
0.853 (.001)
0.297 (.001)
LIBSVM
63886.
0.853 (.001)
0.297 (.001)
200
200
ccvavn
6.8
0.780 (.006)
0.337 (0015)
kernlab
337.6
0.780 (.006)
0.339 (.015)
magicavn
12.9
0.780 (.006)
0.337 (.015)
LIBSVM
932.5
0,780 (.006)
0.342 (.015)
400
cCvBvn
66.0
0.794 (.003)
0.366 (.015)
kernlab
2304.1
0,794 (.003)
0,366 (.015)
magicavn
150.1
0.794 (.003)
0.366 (.015)
LIBSVM
6641.9
0.794 (.003)
0.368 (.015)
800
ccvevn
530.4
0,811 (.001)
0.346 (.015)
kernlab
36771.4
0.811 (.001) 0.346 (.015)
magicavn
996.1
0.811 (.001)
0.346 (.015)
LIBSVM
109365.5
0.811 (.001)
0.346
1600
cCvEvn
5489.2
0.821 (.001)
0.322 (.013)
kernlab
461245.7
0.821 (.001)
0.322 (.013)
magicavn
10803.9
0.821 (.001)
0.322 (013)
LIBSVM
1436416.1
0.821 (.001)
0.322 (011)
4
Numerical Studies
In this section, we demonstrate the computational advantages of fitting the kernel SVM using ccvsvm over the three other competitors, magicsvm, kernlab, and LIBSVM, with simulations and real data.
4.1 Simulations
commonly used simulation data from mixture Gaussian distributions (Hastie et al., 2009) is used. We generate mean vectors Ms, from N(p Ip) where to = 1.2...., 10 in which p 1I, 1, 0, .,, 0) with half of the coordinates to be zero. Each positive-class training sample is independently generated from N(U, ,3)) where k is drawn from the discrete uniform distribution on (1, 10}. Using the same procedure, we obtain the negative-class training data from N(H 3²) where l is also uniform on {1, 2.... 10] and μ = (0, O..0..... 0, 1,..... 1). For each combination of the feature dimension p = 20 and 200 and the sample size n = 200, 400,800, and 1600, we fit the kernel SVM using the four kernel SVM solvers, ccvsvm, magicsvm, kernlab, and LIBSVM, to compute the entire solution paths a sequence of 50 tuning parameters, uniformly distributed on the logarithm scale between e and e The radial kernel is used and the bandwidth is the default option of kernlab ab, which generally performs well. We compared the run time, objective function value, and test error of the four solvers, where the run time includes the whole computation process including training and tuning the model. The objective function value is computed from equation (2). Test error is assessed on 10, 000 test samples which are independently generated from the same distribution. Computations were conducted on an Intel(R) Xeon(R) Gold 6230 CPU @ 2.10 GHz.
Table 1 shows that, to reach the same objective value and the test error, our ccvsvm algorithm is roughly twice as fast as magicsvm, and it about an order of magnitude faster than kernlab and LIBSVM In addition, we observe that kernlab and LIBSVM significantly slow down increases, c.g., LIBSVM is about 20 times slower when p grows from 20 to 200, whereas the speed of ccvsvm and magicsvm is quite insensitive to the change of dimensions. Remarkably, for n = 1600, our ccvavm algorithm finishes training and tuning the SVM using LOOCV within two hours, while with the same accuracy, LIBSVM spends about 400 hours, lasting over 16 days.
200 and
We exemplify the effect of data reduction using the simulation data with n = 800 and p 20 and profile the execution time for training and tuning the SVM with À = 0.1. We observe magicsvm took only 0.12 seconds for matrix inversions and 11.17 seconds for LOOCV through problem ( whereas ccvsvm spent 0.03 seconds on matrix inversions and 5.81 seconds on LOOCV via problem (8). The advantage of ccvsvm over magi cavm is mainly attributed to the reduced dimension of problem compared with problem
9

---

Table 2: Run time (in second) of four SVM solvers for benchmark data, averaged over 50 runs.
data
p
CCVBVm
magicsvm
kernlab
LIBSVM
arrhythmia
452
191
48.076
113.099
1554.579
5061.881
australian
690
14
202.863
412.323
902.463
2178. 6444
chess
3196
37
21768.612
38942.348
240 hours
240 hours
heart
270
13
8.464
16.466
89.373
168.477
leuk
7218
0.464
0.828
1548.724
4811.612
malaria
22283
0,504
0.819
4804.442
13835.144 143
musk
476
166
62.169
127.656
1563.262
4778.779
sonar
208
60
4.736
7.033
98.080
221.505
valley
606
100
149.034
311.147
2230.010
6428.014
4.2 Benchmark Data Applications
We test the performance on benchmark data applications. We study nine commonly used real data applications from the UCI machine learning repository (Dua and Graff 2017). The sample sizes range from 208 to 3, 196. Two high-dimensional data sets with the number of features p = 7.218 and 22, 283 are included. Each data set is split into a training set and test set with the ratio 9 1. The kernel SVM is trained and tuned by the four solvers on the training set, and the test error assessed on the test set. We adopt the training-test split-ratio 9 because we aim to assign most of the samples to the training set and the computation time can be evaluated using relatively large data.
Table 2 exhibits the timing comparisons, where we discover our ccvsvm algorithm is clearly the fastest. about as twice as fast as magicsvm and significantly faster than kernlab and LIBSVM. Especially for the two high- sigh-dimensional examples, magicsvm is thousands or even tens of thousands faster than kernlab and LIBSVM, and ccvsvm further cuts the run time of magicsvm into half. Similar to the simulations, all the four kernel SVM solvers deliver almost the same objective values and test errors on the real data applications; for sake of space limit, the accuracy results are omitted.
Discussions and Extensions
In this work, we have introduced consolidated CV procedure and developed algorithm called ccvsvm for the kernel SVM, which is one of the most successful classifiers. Our work is built on the recently proposed leave-one-our lemma and the csvm algorithm: the ccvsvm algorithm can even double the speed of magi cavm, which has already shown remarkable computational advantages the mainstream SVM solvers, kernlab and LIBSVM.
Scaling ccvavm to large data sets. For large-scale data, we suggest incorporating kernel approxima- tion into the existing consolidated CV algorithm. Specifically, random features (Rahimi and Recht 2007) or Nyström subsampling (Rudi et al. 2013) can be applied in the exact leave-one-out formula of the SVM to find low-cost approximation of the kernel matrix. Integrating these approximation techniques into our methods can further improve the numerical performance. These strategies can also improve generalization performances they induce a form of implicit computational regu- larization. In the supplemental materials (Section C), we develop consolidated CV methods with kemel approximation, essentially converting the original consolidated kernel SVM to consolidated linear SVM, which then can be efficiently solved by the proposed ccvavm algorithm. To give a quick demonstration, consider the simulation example in Section 4.1 with p 20 and increase 5, 000, 000. Averaged by 50 runs, the SVM with random features can be rapidly trained and tuned in 831 seconds, giving test error 0.286 which is close Bayes error, 0.260. The computation time is only 15.7 seconds when n 100, 000. However, when n is 800, the test error of the SVM with random features 0.351, which is well above 0.309, the test error of our exact kernel SVM solver given in Table I
be
We leave full investigations of this strategy to future works.
The proposed method is only for LOOCV and SVM since it utilizes the special structure of support vectors. However, in future works, it is interesting to explore if the consolidated CV can be generalized other K-fold CV or the hold-out validation more broadly. It is also interesting to extended the idea of consolidated CV to solve the solution paths of other computationally expensive machine learning methods such as support vector regression and kernel quantile regression.
Limitation.
Societal impact. This work does not present any foreseeable societal consequence.
10

---

References
ARLOT, S. and CELISSE, A. (2010). A survey of cross-validation procedures for model selection. Statistics Surveys 4 40-79.
BENGIO, and GRANDVALET, Y. (2004). No unbiased estimator the variance k-fold pross-validation. Journal of Machine Learning Research 1089-1105.
BURMAN, (1989). comparative study of ordinary cross-validation, v-fold cross-validation and repeated learning-testing methods. Biometrika 76 503-514.
CHANG, C.-C. and LIN, C.-J. (2011). Libsvm: A library for support vector machines. ACM Transactions on Intelligent Systems and Technology (TIST) 2 1-27.
CORTES, C. and VAPNIK, V. (1995). Support- networks. Machine Learning 20 273-297.
DUA, D. and GRAFF, C. (2017). UCI machine learning repository.
URL URL.http://archive ics uci .duummldm
GHAOUI, L. E., VIALLON, V. and RABBANI. T. (2010). Safe feature elimination for the lasso and sparse supervised lcarning problems, arXiv preprint arXiv: arXiv:1009.44 1009.4219.
GOLUB, G. H., HEATH, M. and WAHBA, G. (1979). Generalized cross-validation a method for choosing good ridge parameter. Technometrics 21 215-223.
HASTIE, T., TIBSHIRAN,, R. and FRIEDMAN, J. (2009). The Elements of Statistical Learning. Springer Series Statistics, Springer New York Inc., New York, NY, USA.
HONG, B., ZHANG, W., LIU, W. YE, J., CAL, D., HE, and WANG, (2019). Scaling up sparse support vector machines by simultaneous feature and sample reduction. Journal of Machine Learning Research 20 1-39.
KARATZOGLOU, A., SMOLA, A., HORNIK, K. and ZEILEIS, A. (2004). kernlab-an S4 package for kernel methods in R. Journal of Statistical Software 11 1-20.
KOHAVI, R. (1995). A study of cross-validatie and bootstrap for accuracy estimation and model selection. In International Joint Conference Artificial Intelligence, vol. 14.
MICCHELLI, C. A., XU, Y. and ZHANG, H. (2006). Universal kernels, Journal of Machine Learning Research 7 2665-22667.
MOLINARO, A. M., SIMON, R. and PFEIFFER, M. (2005). Prediction estimation: comparison of resampling methods. Bioinformatics 21 3301-3307.
OGAWA, K., SUZUKI,
TAKEUCHI, (2013). Safe sereening of non-support vectors in pathwise svm computation. In International Conference on Machine Learning.
PAN, X. and Xu, Y. (2018). novel and safe two-stage screening method support vector machine, IEFE Transactions on Newral Networks and Learning Systems 30 2263-2274.
PARIKH, N. and BOYD, S. (2014). Proximal algorithms. Foundations and Trends Optimization 1 127-239.
RAHIMI, A. and RECHT, B. (2007). Random features for large-scale kernel machines. In Advances Neural Information Processing Systems, vol. 20.
RUDI, A., CAMORIANO, R. and RoSASco, L. (2015). Less more: Nyström computational regularization. In Advances in Neurul Information Processing Systems, vol. 28.
STEINWART. I. (2001). On the influence of the kernel on the consistency of support vector machines. Journal of Machine Learning Research 2 67-933.
TIBSHIRANI, R. (1996). Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society: Series (Methodological) 58 267-288.
VAPNIK, V. (1995). The Nature of Statistical Learning Theory. Springer Science Business Media.
VAPNIK, V. (1998). Statistical Learning Theory. Wiley.
WAHBA, G. (1990). Spline Models for Observational Data, vol. 59, SIAM.

---

WAHBA, G., LIN, Y. and ZHANG, Н. (1999). GACV for support vector machines. In Advances in Neurul Information Processing Systems, vol. 12.
WAHBA, G. and WOLD, S. (1975). Periodic splines for spectral density estimation: The use cross validation for determining the dogree of smoothing. Communications in Statistics and Methods 125-141.
WANG, B. and ZOU, H. (2021). Honest leave-one-our cross-validation for estimating post-tuning generalization error. Stat 10.
WANG, B. and Zou, H. (2022). Fast and exact teeve-one-ou analysis of large-margin classifiers. Technometrics 64 291-298.
WANG, J., WONKA, and YE, (2014), Scaling SVM and least absolute deviations exact data reduction. In International Conference on Machine Learning.
ZHANG, Y. and YANG, Y. (2015). Cross-validation for selecting model selection procedure. Journal of Econometrics 187 95-112.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(C) Did you discuss any potential negative societal impacts of your work? [Yes] We wrote "This work does not present any foresseable societal consequence."
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material as a URL)? [Yes] The code and data are in the supplemental materials.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e-g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you using existing assets (e.g., code, data, models) or curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent obtained from people whose data you're 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable
information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
12


Reviews:
[{"review_id": "iqu_ydHeNKT", "reviewer": "Reviewer_Tqdk", "summary": "This paper presents a data reduction strategy and an algorithm that learns an SVM and a leave-one-out-cross-validated version much faster than the standard scheme which would require training once for every fold. The paper exploits the sparsity within the solution process to reduce the amount of computation required. The paper describes the theory around this and several experiments showing greatly superior running times from the scheme.", "questions": "1. Do the authors have some sense of how much computation the data reduction strategy saves and the characteristics of the problem that relate the most with computation reduction? This is in line with what I listed as the second weakness of the paper.", "limitations": "The authors clearly addressed the limitations of their work. There is no potential negative societal impact of their work that they can account for and affect.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The development is clearly an important development for SVMs, which are an important class of algorithms. It represents an original and clever development.\n2. The paper has convincing experimental results, showing that the new algorithm achieves nearly the same objective values but in much lower running time.\n\nWeaknesses:\n1. The paper should provide the algorithm in pseudocode form to ease reproducibility due to the multiple parts of the algorithm. If space is a concern, then the key optimization problems or equations can be put in the pseudocode and then cited in the text.\n2. There should be more analysis of how effective the data reduction strategy suggested by equation 5 is. Clearly it is effective as demonstrated by the running times. However, I think the authors should still show what fraction of computations is eliminated due to the strategy and give a sense of the factors in the dataset that are most responsible for reduction in computations.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "W2zs2aB3vJh", "reviewer": "Reviewer_vgth", "summary": "In this paper, an integrated Cross-Validation procedure is introduced for one of the leading classifiers, kernel SVM, and an algorithm called ccvsvm is developed. This algorithm is based on the recently proposed leave-one-out lemma and magicsvm algorithms. Numerical experiments demonstrate that the algorithm is more than an order of magnitude faster than the two SVM solvers but with almost the same accuracy compared to existing data reduction methods.", "questions": "Q1: Numerical experiments demonstrating the effectiveness of the proposed method have been carried out with a maximum number of cases of around 3,000. Would the proposed method still be effective if, for example, the number of instances exceeds 10,000?\n\nQ2: Do you already have ideas for extending the proposed method to machine learning algorithms other than SVM? If so, it would improve the value of the paper if you could present them in the Discussion.", "limitations": "This paper is not applicable as there are no problems in terms of limitations or potential societal impact.", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The proposed method can perform leave-one-out cross-validation very fast, as shown by theoretical aspects and numerical experiments.\n\n- Demonstrations are carried out using kernlab and LIVSVM, the main packages of existing support vector machines.\n\nWeaknesses:\n- Due to its reliance on support vector machine mechanisms, it is currently impossible to demonstrate its effectiveness with other machine learning algorithms.\n\n- Numerical experiments have been carried out on relatively small benchmark data sets. For example, the performance has not been tested when the number of cases exceeds 10 000.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Vx88_QqL6j9", "reviewer": "Reviewer_5kDp", "summary": "The authors propose a consolidated crossed validation for Support Vector Mahines (ccvsvm), based on the recent leave-one-out lemma and magicsvm, having as objective to reduce the training time via data reduction. Specifically, this two-stage ccvsvm deals with the SVM bias term, which is not handled by some existing data reduction methods. The authors demonstrate with numerical experiments that the proposed algorithm is about an order of magnitude faster than the two mainstream SVM solvers, kernlab and  LIBSVM, with almost the same accuracy.", "questions": "•\tThe manuscript section organization is missing from the introduction, it should be included.\n•\tOne particular characteristic of this proposed solution is the sparsity on the solution of SVM. Is it possible to use the solution of the k-1 fold to improve the initial solution on the k-fold (finding the initial support vectors and non-zero alpha values)?\n", "limitations": "The authors address some of the method’s limitations and provide some future lines to generalize to other K-fold CV or other computationally-expensive ML methods", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "•\tStrengths: The core idea of the work is original in the sense of thinking at the same time data reduction (as part of CV), the QP optimization process and the LOO at the same time. The quality of the research work is solid. The work is clear and simple in explaining the state of the art, their contribution, the definition of their methods, and their general experimental setting.\n•\tWeaknesses: It will be great to have the code available to (at least partially) reproduce the experiments. Section 4.1 is of particular interest and table 1 underline how the proposed ccvsvm algorithm results efficient, but, again, reproducibility is a key. This comment also applies to section 4.2.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "93zBeDPJTlk", "reviewer": "Reviewer_uBSd", "summary": "This paper proposed a computationally efficient algorithm to perform leave-one-out cross-validation using the support vector machine with Gaussian kernel. The authors proposed a two-stage cross-validation that is applicable to the support vector machine with the bias term.", "questions": "Major questions:\n* For a support vector machine classifier, while training if we remove a data point that is not a support vector and add a data point that is not a support vector from the support vector machine trained using the full data, the solution does not change. Is this property used in the implementation?\n* Can the proposed algorithm be applied to support vector regression algorithm with the $\\epsilon$-insensitive error function?\n* Can the proposed algorithm be applied to arbitrary kernels with unbounded values such as polynomial kernels? \n\nMinor questions:\n* Is there a typo in the equation just after line 109?", "limitations": "Yes.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* Nice and detailed theoretical analysis.\n\nWeaknesses:\n* Empirical results on small data sets.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept