Distributed Optimal Margin Distribution Machine
Authors: Yilin Wang
nan cao
Teng Zhang
Hai Jin
Venue: ICLR 2022 Submitted (2022)
Keywords: Distributed machine learning
margin distribution
classification
kernel learning

Abstract: Optimal margin Distribution Machine (ODM), a newly proposed statistical learning framework rooting in the novel margin theory, demonstrates better generalization performance than the traditional large margin based counterparts. Nonetheless, the same with other kernel methods, it suffers from the ubiquitous scalability problem in terms of both computation time and memory. In this paper, we propose a Distributed solver for ODM (DiODM), which leads to nearly ten times speedup for training kernel ODM. It exploits a novel data partition method to make the local ODM trained on each partition has a solution close to the global one. When linear kernel used, we extend a communication efficient distributed SVRG method to further accelerate the training. Extensive empirical studies validate the superiority of our proposed method compared to other off-the-shelf distributed quadratic programming solvers for kernel methods.

Under review as a conference paper at ICLR 2022
DISTRIBUTED OPTIMAL MARGIN DISTRIBUTION MA- CHINE
Anonymous authors Paper under double-blind review
ABSTRACT
Optimal margin Distribution Machine (ODM), newly proposed statistical learn- ing framework rooting in the novel margin theory, demonstrates better generaliza- tion performance than the traditional large margin based counterparts. Nonethe- less, the same with other kernel methods, suffers from the ubiquitous scalability problem in terms of both computation time and memory. In this paper, we propose a Distributed solver for ODM (DiODM), which leads to nearly ten times speedup for training kernel ODM. It exploits novel data partition method to make the local ODM trained on each partition has solution close to the global one. When linear kernel used, we extend communication efficient distributed SVRG method to further accelerate the training. Extensive empirical studies validate the superi- ority of our proposed method compared other off-the-shelf distributed quadratic programming solvers for kernel methods.
INTRODUCTION
Recently, the study on margin theory (Gao & Zhou 2013) demonstrates an upper bound disclos- ing that maximizing the minimum margin does necessarily result in good performance, and instead, the distribution rather than a single margin is much more important. Later on, the study on lower bound (Gronlund et al., 2019) further proves that the upper bound is almost optimal up to a logarithmic factor. Inspired by these insightful works. the Optimal margin Distribution Machine (ODM) is proposed (Zhang & Zhou| 2019). which explicitly optimizes the margin distribution by maximizing the mean and minimizing the variance simultaneouslyy and exhibits much better gen- eralization performance than the traditional large margin based counterparts. Due to the superiority shown on both binary and multi-class classification tasks (Zhang & Zhou 2014, (017), many works attempt to extend ODM to more genreal learning settings, just to list a few, cost-sensitive learn- ing (Zhou & Zhou 2016 Cheng et al., 2017), weak supervised learning (Zhang & Zhou, 2018a b
Luan et al.
2020: Zhang& & Jin 2020), labti-label learning (Tan et al. 2020), online learning (Zhang 2020 and regression (Rastogi et al. (020)).
al.
Plenty of successes on various learning tasks validate the superiority of this new statistical learning framework. However, these ODM based extensions suffer from the scalability problem because of both computation time and memory, the same as other kernel methods. Some works have devoted to accelerate the training of ODM for large scale data, e.g., CSVRG (Tan et al.] (219) takes advantage of the coreset method, whose main idea is to adaptively construct the landmark points to sketch the whole data. Other approximation methods being able directly speed up ODM include random Fourier feature (Rahimi & Recht, 2007) and Nyström (Williams & Seeger 2001). Notice that the random Fourier method adopts data-independent kernel mapping while the Nyström method takes a Iistribution-unavane
sampling, they are both inferior to coreset method due to the insufficient use of data, which may only lead degraded generalization performance. All these methods are proposed for computing data generated devices become as diverse as computers, mobile phones, smart watches, cars, etc, and the amount of data created each day grows tremendously, which cpu core hardly afford and motivates us to seek the distributed training methods.
cpu core, but with the dramatic progress of digital technologies, the
Up to many machine learning methods have already owned their distributed versions, among which the closest one to our problem is the distributed SVMs, whose ideas can be concluded into two classes. The first one works in distributed data level, i.e., dividing the data into partitions on

---

Under review as a conference paper at ICLR 2022
which local models are trained and then combined to produce the larger local or global models. For example, in (Graf et al. 2004 Hsieh et al.) 2014; Singh et al.) 2017), a tree architecture on parti- tions is designed first, guided by which the solutions of different partitions
aggregated; in (Yu et al. 2005| Navia- Vazquez et al.) 2006, Loosli et al. 2007). some key instances identification and exchange are further introduced to accelerate the training: in at. 2017)) both low-rank and clus- lering structure of the kernel matrix are considered to get an approximation of kereel matrix. The other one works in distributed optimization level, that is directly applying the distributed optimiza- tion method, such as augmented Lagrangian method (Forero et al., 2010) and alternating direction method of multipliers (Boyd et al. 2010), or extending existing solver distributed environment, e.g. distributed SMO (Cao et al. 2006).
al.
Although many distributed solver for quadratic programming (QP) problems can directly ap- plied to ODM, these off-the-shelff solvers all ignore the intrinsic structure of the problem and can hardly achieve the greatest efficiency. We propose a specially designed Distributed solver for ODM (DiODM) in this work. To be specific, we put forward novel data partition method so that ODM trained on each partition has a solution close to that trained on the whole data. There- fore, when some partitions are merged to form larger partition, the solution of ODM on it can be quickly obtained by concatenating the corresponding local solutions as the initial point. Besides, in the case of linear kernel being used, we extend communication efficient distributed SVRG method to further accelerate the training. To summarize, the remarkable differences of DiODM compared with existing distributed QP solvers are threefold:
1) DiODM incorporates novel partition strategy, which makes the solution of local ODM on each partition close to the global one so that the training can be accelerated.
2) When linear kernel is used, DiODM extends communication efficient distributed SVRG method to further accelerate the training.
3) DIODM can maintain the generalization performance of ODM meanwhile achieve nearly ten times speedup, much more efficient than existing distributed QP solvers.
In the rest of this paper, some preliminaries are first introduced in section 2, followed by the technical detail of the proposed DiODM in section 3. In section 4, we present the results of experimental and give empirical observations. Last, in section 5 we conclude the paper with future work.
2 PRELIMINARIES
Before diving into the technical details, we first give some default notation in our paper. Sets are designated by upper case letters with mathcal font (e.g., S). The input space is X' C NN and y = [1} is output space. [.] is the round up function. For any positive integer M, the set of some positive definite kernel k where HH is the corresponding reproducing kernel Hilbert space (RKHS), x(xx =) (d(z). d(=)) holds for any x and z. In this paper we consider the shift-invariant kernel such as RBF kernel for simplicity, which satisfies n(x, z) = k(x 2).
integers (1...., M) } is denoted by [M]. For the feature mapping é X H associated
The traditional large margin based methods maximize the minimum margin, and consequently the obtained decision boundary is only determined by a fraction of instances with the minimum mar- gin (Schölkopf& & Smola 2001). which may hurt the generalization performance.
On the other hand, ODM explicitly optimizes the margin distribution. Given a labeled data set ((r,, Vi) ODM is initially formalized by maximizing the margin mean and minimizing the margin variance:
min w.
1 S 1
17
+ s.t. - Vi E [M], (M(M]
Σ
(I)
2M
where 17, À are the off parameters, %/4 = yow d(x;)) is the margin of the labeled instance (x,, y1) and 7 is the mean of %. Note that the two slack variables & and c; are deviations from the margin mean, therefore the third term is exactly the margin variance.
The margin mean can be fixed as 1 since scaling w does not affect the decision boundary. Besides, instances with margin less than are more likely to be misclassified, therefore we introduce new
2

---

Under review as a conference paper at ICLR 2022
hyper-parament E [0, 1] to weight the ε.- Last but not least, notice that instances lying the hyperplane yow ((x;) = all contribute to the decision boundary, to achieve a lightweight model. we can tolerate the deviation smaller than the given threshold 6. Plugging all these back into Eqn. yields the primal problem of ODM:
c + uC
min p(w) = w Keiee
Σ
2
2M
(1 - 0)2
SE[M]
s.t. 1 0 - S yow o(x;) 2 1 + + Es Vi E [M].
By introducing the Lagrange multipliers 3 E RMd for the 2M inequality constraints respectively, the dual problem of ODM is
min dis, B) (c 3) Q(C - 13+ Mc S.BER
33) 2
[u||<|| + [13]] (0 (0- M (0+ 13
where [Q = y:Ml yyM,,((a k(;; æÿ) and c = (1 - 0)² /// Xv is a constant. The detailed derivation can be [S: 3]. the dual ODM can be rewritten standard
found in supplementary. By denoting convex QP problem:
min DER
f(a) = a Ha + aTa
(2)
2
in which
Q + Mcal H
Q Q + Mcl
( 1)1M (0 1)
b
Q
Notice that Eqn. 2 only involves 2M decoupled box constraints, thus it can be efficiently solved by a dual coordinate descent method. To specific, each iteration, only one variable is selected to be updated while other variables are kept as constants, which yields the following univariate QP problem of
1 min f(a + te:)
H ltt
[V((a)]tt+ + f(a).
(3)
2
which has a closed-for formm-ffmmmmoo solution:
[al; max( [V(a)) 0).
PROPOSED METHOD
DiODM works in distributed data level, that is it works by dividing the data into partitions which local models are trained and then used to find the larger local or global models. For simplicity, we assume there are K = p" partitions at first with the same cardinality m, i.e., set ( si) Je)ee are ordered so that the first m instances are on the first partition, and the second m instances are on the second partition, etc. That is for any instance (æ,, y:), the index of partition which it belongs is P(i) [ 1)/m].
M//K The data
Me(m is the data on the k-th partition, then the local ODM on it is Suppose {(x) (k) .
(1)
min
d&(Ci Bx) (Cx Bxx) (M) (Ce Bxk
+ 2
mc
(ul
+ || + (0 - I) + 1,
x (3)). This problem can be rewritten as standard convex QP problem in the manner of Eqn. and efficiently solved by dual coordinate descent method as Eqn. (3)
where [Q()]], = y: fj x(x
(k) (k)
Once the parallel training of ph local ODMs completed, merge every partitions to form p'-1 larger partitions. On each larger partition, a new local ODM trained again by dual coor- dinate descent method, but the optimization procedure is not started from the scratch. Instead, the
3

---

return a'. Under review as a conference paper at ICLR 2022
p solutions obtained the p corresponding smaller partitions making up this larger partition, concatenated as the initial point of the optimization. Since by our proposed novel partition strategy, this concatenated solution is already good approximation to the optimal solution of ODM on the larger partition. We will elaborate on this subsequent sections.
The above procedure is repeated until the solution converges all the partitions merged together. We give the pseudo-code of DiODM in Algorithm !
Algorithm DiODM
Input: Data set D = {( vi)
Parameter: Partition control parameter p, number of stratums S, number of iterations L.
Output The solution a.
1: Get landmarks by Eqn. (5) D.
2: Sample instances without replacement to get partitions DI,...,Ppp Der.
3: Initial the dual solution a = 0.
4: for ...., do
5: if a: converge then
6: break
7: end if
8: for p po..-...... do
9: Solve the ODM with dual coordinate descent.
10: end for
11: Merge every p partitions form partitions.
12: a' =
13: end for
14:
3.1 CONVERGENCE
In this subsection, we present theorem to guarantee the convergence of the proposed method. Notice that the optimization variables on each partition are decoupled, they can be jointly optimized by the following problem:
=(c,3)= TÔC - -B) 2 C
min
me (uI[C12 11311 (0 1)1M + (0 T,
where Q = diag(Q( (e.gg Q(1) is a block diagonal matrix. It can be seen that the smaller the K, the more close the above formula to ODM, and when K 1, exactly degenerates to ODM. Therefore, DiODM deals with ODM by solving a series of problems which approaches to it, and the solution of former problems can be helpful for the optimization of the latter problems.
Theorem 1, Suppose the optimal solutions of ODM and its approximate problem, i.e., ă(C.3) are a' = (5 and ä (5* respectively, then the gaps between these two optimal solutions satisfy
0 5 d'(", a((5,87) SUR(QQ SU) PPQQ+M(AU (MM-M mm)c).
U
a 1= S
(Q ((M - m)c),
Mcu
where Q= Eis.P(PP))) [1 is the of the absolute values of the Q's entries which turn to zero in Q and U max( oo. | (l upperbounds the infinity norm of solutions.
Due to the page limitations, we only provide the sketch of proof here. The full proof can be found in the supplementary.
Proof sketch. The left-hand side of the first inequality is due to the optimality of C and B
By comparing the definition of d(C, (3) with that of d(c, B), we can easily find that the only differ- ences the change of Q to Q and M m. Thus the gap between d(S", ,3²) and d(C", Bt) can
4

---

Under review as a conference paper at ICLR 2022
be upper bounded by the infinity norm of a² and the sum of the absolute values of the Q's entries
which turn zero in Q. The gap between d((", 3*) and d(ş", (3*) can be upper bounded in a sim- ilar way. Combining these together with the optimality of 5* and B*, i.e. d(5", 3*) - d(5", can yield the right-hand side of the first inequality.
Notice that f(ă²* ) is a quadratic function, hence besides the gradient g and Hessian matrix H, all its higher derivatives are all zero, and it can be precisely expanded at or as
f(aa) 9 (ā" a²) (a" a²) H(@ aa),
in which g (a" x²) is nonnegative according to the the first order optimality condition. Further- more, H can be lower bounded by the sum of a positive semidefinite matrix and a scalar matrix:
Q
I
Mev
I
By putting all these together, we can show that ||ā a 11 upper bounded by f(ā²) f(a*), ie.. d((", ( d((", 18*). and with the right-hand side of the first inequality we can derive the second inequality.
This theorem indicates that the gap between the optimal solutions of ODM and its approximation, that is the problem solved in each iteration of DiODM, depends on M m and Q. As the iteration going on, the partitions become larger and larger, then the number of instances m on each partition tends to be the total number of instances M; Furthermore, the matrix Q approaches to Q which makes Q decrease. Therefore, the solution obtained in each iteration DiODM is getting closer and closer to that of ODM, that is to say, our proposed algorithm converges.
3.2 PARTITION STRATEGY
In this section we detail the partition strategy, which plays an important role our proposed method, since partition strategy can significantly affect the optimization efficiency. Up to now, most partition strategies utilize the clustering algorithms to form the partitions. For example, DC-SVM (Hsich) et al. 2014) adopts the kernel k-means and simply regards each cluster partition. However, ODM heavily depends on the mean and variance of training data. Directly treating clusters as partitions will lead to significant difference among the distribution of partitions and the whole data, which makes the local solutions on each partition are far from the global one.
To preserve the original distribution as much possible, we borrow the idea from stratified sam- pling, i.e., we first divide the data set into some homogeneous strata, and then apply random sam- pling within each stratum. To be specific, suppose the goal is to generate K partitions. We first choose S landmark points {Φ(z,) mark point by assigning the rest instances to the stratum in which its nearest landmark point lies, i.e., the index of stratum a; belongs to is
in RKHS, and then construct one stratum for each land-
((i) = arg min [(((.)) ((z.)]
.E[S]
For each stratum C., we equally divide it into K pieces by random sampling without replacement, and take piece from each stratum make up a partition and totally K partitions created.
The remaining question is how to select these landmark points. Obviously, they should be represen- tative enough to sketch the whole data distribution. To this end, we introduce the minimal principal angle which is defined between different stratum:
(x, 2)
E E,,,
T min 1
arccos
x |||
Apparently, the larger the angle, the higher variation among the strata, and the more representative each partition is, which is strictly described by the following theorem.
Theorem 2. For shift-inw infffiiivaiannt kernel k with k(0) = = that is [|ø(x)] = r for any æ. With the partition strategy described above, for any l E [K], we have
2
de(Cn, Ba)
M + 2 + U22² cos 720 M²),
2
where θ Eise(MI,es ((0))))))) and U is same with Theorem 1.
5

---

Under review as a conference paper at ICLR 2022
Proof sketch. Follow the construction process mentioned in appendix, generate data Dj where DD/ = [D] = M. According to our settings, the number of instances in [D] belong to the s-th stratum equals to [.,). Give the definition of de (Ck. S&) and d' (St (%) in appendix, have (h, (3)) = d& (Ck. 3x) since Dr and Dj share the same margin mean and variance under the same hyperplane.
Denote 0z2- = 1 31,, 2/2 = [C- - B.]. By contrasting the definition of (S). (%)) with that of , f*), can find that the differences consists of three parts. The first part is
Me
(v11 ||,11 -
and the second part is
00 + (3) +0 (0- - (*)) Note that both of above parts can be upper bounded by the infinity norm of az.- The third part can be denoted
gx(%%)
1
Q67% To.
1 "--² Q7" "ry"
2
With the boundness that -U2 - M0n Thi S SU2 < Us 1, 0 5 1, we have
9x(%)) SU² Σ (k((=
.aj (0) x(2,,, my))
[JE[M]
Upper bound k<xx(() . (x)) ( 223) by minimal principal angle and the law of cosines, can easily find that g (*()) $ U 222 2 + U cos 7(20 M By combining the upper bound of above three parts, we can complete the proof.
As shown in theorem 2 we derive an upper bound on the gap between the optimal object value on D and on DE. Note that 20 > M2 holds for any E [S] when |C,| < M/2, which can be easily satisfied. Thus, we can get more approximate solution in each partition by maximizing the minimal principal angle
However, due to the high computation cost, it is impossible to directly maximize minimal principal angle. Instead, we implement a greedy iterative process:
21 arg max n(z, 2), 2 RED
arg max EE
SC,-1(z)
(5)
where SC,(2) =( KJ K. 2,a is the Schur complement of candidate land- mark 2s+1 based on the landmarks {=1,..., 2.} which have been already selected, K,, 2.)], I K. E Rax= is defined as [K]jsj x;),, In the process of solving 2. we actually seek the instance which maximize the determinant of kernel matrix construct by {ži,..,,z,) J. It is obviously that the maximum determinant is achieved when @( ((2.) is orthogonal to (6(2)...., 6(2,-1)) Therefore, we can maximize the minimal principal angle by choosing the instance with maximum Schur complement.
is noteworthy that each partition generated by our proposed strategy extracts proportional instances from each stratum, thus preserves the distribution. Besides, compared with other partition strategies based on k-means (Singh et al., (2017), we consider not only in the original feature space, but also in the situation where data can hardly be linear separated. Last but not the least, our partition strategy has lower time complexity.
3.3 ACCELERATION FOR LINEAR KERNEL
The solving process of dual coordinate descent requires too much storage and computing resources, mainly caused by the enormous kernel matrix. It is noteworthy that when linear kernel is used, we can directly solve the primal form of ODM to avoid computing and storing kernel matrix. Denote the gradient of p(w) on instance (æ,, y:) as Vp, (w)) we have
Myyw a; + 0 1) lie,
>u(y,w x; 0 - 1) 1)ya:: a lie
(p,(w) u
(1 8)2
(1 (1-6) 0)2

---

Under review as a conference paper at ICLR 2022
where I {i y;w² 2; < 0), and I2 y, x. 1 1)
Since the the objective function of ODM diffcrentiable, distributed SVRG (DSVRG) (Lee et al, 2017) can be exploited in this scenario. It generates series of extra auxiliary data sets sampling from the the original data set without replacement which share the same data distribution as the whole data set, that unbiased estimation of the gradient nodes are joined together to compute the full gradient first. Then each node performs the iterative update of SVRG in serial in "round robin" fashion, i.e., let all nodes stay idle except one node performing certain steps of iterative updates using its local auxiliary data and passing the solution the next node. We show the process of solving DiODM by DSVRG algorithm in Algorithm 2
be computed. In each iteration, all
Algorithm Accelerated DiODM for linear kernel
Input: Training data set D { (æ y:) J:) J=1
Parameters: Number of partitions K, number of stratums S, number of stages St, step size v), the number of iterations T.
Output: Solution at S, stage S
1: Get S landmark points by Eqn. (5 on D.
2: Sample instances without replacement to get partitions Di....,DA Dr
3: Generate the auxiliary array Ri...., R₂ where R; {il(z,,)) (1) D
4: $ +-- 1.
5: for 1 1, , St do
6: The center node sends wo to each node.
7: for each node j .....
........ K in parallel do
8:
Compute hej LiED, (ww)
9:
send h/ to center.
10:
end for
11:
h 37 Σラ h
12:
Initial the solutions w + wl
13:
for = 0, 1, ..,...., T
do
Sample instances (x, vi) from D, where i R. w w 1+1 nV,,(wtt)) (p,(w") + h!)
16:
R. - R.
if R. ++1
then
18:
send w +1 to node + 1.
19:
5 s
20:
end if
21:
end for
22: w'+1 w/ 1+1
23:
end for
24:
return S.
4 EXPERIMENTS
In this section, evaluate the performance of proposed algorithms by comparing with other
QP solvers.
4.1 SETUP
We evaluate the performance of proposed algorithms seven real-world data sets The statis- ties of these data sets are summarized in Table All features are normalized into the interval [0, 1]. For each data set, eighty percent of instances randomly selected training data, while the rest are selected as testing data. All the experiments are performed on a Spark (Zaharia et al. (2012) cluster with one master and five workers. Each machine equipped with 16 Intel Xcon E5-2670 CPU cores and 64G RAM.

---

Under review as a conference paper at ICLR 2022
DiODM is compared with three ofate-of-the-art distributed QP solvers, that is, Cascade ap- proach (Ca-ODM) (Graf et al. (2004). DiP approach (DiP-ODM) (Singh et al. (2017)) and DC approach (DC-ODM) (Hsich et al. (2014)). We denote our proposed dual coordinate descent based algorithm as DiODM and accelerating algorithm as ace-DiODM. Besides, in evaluating the effi ciency of acc-DiODM, state-of offte-of-the-art gradient based methods implementd, that is SVRG method (oDM) (Johnson & Zhang (013)) and CSVRG method (ODMesurg)
(Tan et al. 2019)
Data sets
gisette
phishing
a7a
cod-rna
ijenn
skin-nonskin
SUSY
#Instances #Features
7,000 5,000
11,055 68
32,561 123
59,535 8
141,691 22
245,057 3
5,000,000
18
Table
Data set statisties.
4.2 RESULTS WITH LINEAR KERNEL
Figure presents the time cost and test accuracy on data with linear kernel. In the Figure (e), we show the training speedup ratio with cores increasing from to 32 for DiODM and acc-DiODM. When 32 cores used, DiODM achieves more than 9 times training speedup while acc-DiODM achieves over 5 times training speedup. In other six figures, we can see that both DiODM and ace-DiODM show highly competitive performance compared with other methods. Specifically, acc- DiODM achieves better test accuracy and faster training speed than Ca-ODM, DPP-ODM and DC- ODM. DiODM achieves the better test accuracy on 5 data sets and just slightly worse than DC-ODM on skin- monnnnonkiin data set. On time cost, DiODM achieves faster training speed on all data sets.
HI Bond trureig
SUBY, Surnng roul
choito
Cx-CMM 50%
Ca/COM nitter
C
M0-20CV
-e- R0-20CM
lgl
glett
Cx-CtM
3
acc 00:-0
Figure 1: Comparisons of different methods using linear kernel. Each point of acc- ace-DiODM except Figure (a) indicates the result when every one third of stages executed. Other points except in Figure (e) indicate the result stop at different levels.
4.3 RESULTS WITH RBF KERNEL
Figure P the time cost and test accuracy on six data sets. It can be seen that DiODM shows highly competitive performance compared with other methods. Specifically, DiODM achieves the best test accuracy on data sets and just slightly worse than DC-ODM on other 2 data sets. On time cost, DiODM achieves the fastest training speed on all 6 data sets.
4.4 COMPARISON WITH GRADIENT BASED METHODS
Figure 3 compares the training speed and generalization performance between acceleration method and other gradient based methods. We observe that our method can get competitive test accuracy. Meanwhile, method achieves over 5 times faster speed than other methods. This
8

---

Under review as a conference paper at ICLR 2022
(b) trining
(0) trkinng
SUSY.
Teo: (osaieey
Twe Anoamnyy
86
DFP-20M
OFP-GDM
DPV.GDM
0C:00M
0C:00M
Time)x10'))
Takking Timex1
Traniig Temep1109g)
(8)
(e)
cod-ma trining meuult
a7w: training readl
phisting training moult
89-
18
2
Ca-0314
Ci-001
CDV DPI-DDM
DFP-CCM
DFP-GEM
DIOOM
DIGDM
DC-03M
0C:00M
DC CC-DOM
01
75
40
60
100
Trakkng 1000
Trainin Treej))
Trakning Timed))
Figure 2: Comparisons of different methods using RBF kernel. Each point indicates the result when stop at different levels.
indicates that our distributed acceleration method achieves great training speed while hold the gen- eralization performance.
(b)
trariing
Teol (ccereo))))
Tee: ferssrrr
69-
ODMww
O0Mum
ODM DoSDIODM
ac2-BO0M
CDM
COM
ODM
80
30
20
120
150
100
30
Traniing Tanw))
Trainig ng Trmet))
Trakkng T(map))
(6)
(6)
phissh trinng result
sköh-nonskm: training result
SUSY: trainng result
02-
50
DDMuwg
D0Muro
GDMug
ODM....
75
82
20
40
60
100
200
400
600
600
1000
Traniing Tmmoj0
Trairing Time)0
Trakning Timab))
Figure 3: Comparisons of different gradient based methods.
CONCLUSION
While lots of works have been proposed solve QP problems, these off-the-shelf solvers usually ignore the intrinsic structure of the problem, thus can hardly be implemented in ODM. We propose a distributed ODM solver called DiODM, in order to retain the first- and second- order statistics in both linear and nonlinear feature space. Additionally, an accelerating method is implemented to improve the training speed for linear kernel. According to our experiments, DiODM shows the superiority to other distributed QP solvers and generates great training acceleration in distributed environment. In the future, we will consider the circumstance in which data is located on different devices and can not be gathered together due limited bandwidth or user privacy.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Stephen Boyd, Neal Parikh, Eric Chu, Borja Pelcato, and Jonathan Eckstein. Distributed optimiza- tion and statistical learning via the alternating direction method of multipliers. Foundations and Trends in Machine Learning, 3(1):1-122, 2010.
Lijuan Cao, S. S. Keerthi, Chong Jin Ong. Jianqiu Zhang, Uvaraj Periyathamby, Xiuju Fu, and Henry P. Lee. Parallel sequential minimal optimization for the training of support vector ma- chines. IEEE Transactions Neural Networks, 1039: 2006.
Fanyong Cheng, Jing Zhang, Cuihong Wen, Zhaohua Liu, and Zuoyong Li. Large cost-sensitive margin distribution machine for imbalanced data classification. Neurocomputing, 224:45-57, 2017.
Pedro A. Forero, Alfonso Cano, and Georgios B. Giannakis. Consensus- based distributed support vector machines. Journal of Machine Learning Research, 11:1663-1701 2010.
Wei Gao and Zhi-Hua Zhou. On the doubt about margin explanation of boosting. Artificial Intelli- gence, 203:1-18, 2013.
Hans P Graf, Eric Cosatto, Leon Bottou, Igor Dourdanovic, and Vladimir Vapnik. Parallel support vector machines: The cascade svm. In Advances in Neural Information Processing Systems 17, pp. 521-528, Vancouver, Canada, 2004. MIT Press.
Allan Grønlund, Lior Kamma, Kasper Green Larsen, Alexander Mathiasen, and Jelani Nelson. Margin-based generalization lower bounds for boosted classifiers. In Advances in Neural In- formation Processing Systems, pp. 1963-11972, Vancouver, Canada, 2019.
Cho-Jui Hsieh, Si Si, and Inderjit S. Dhillon. A civide-and-conquer solver for kernel support vector machines. In Proceedings of the 31st International Conference Machine Learning, pp. 566- 574, Beijing, China, 2014.
R. Johnson and T. Zhang. Accelerating stochastic gradient descent using predictive variance reduc- tion. In Advances in Neural Information Processing Systems 26, pp. 315-323, Lake Tahoe, NV, 2013.
Jason D. Lee, Qihang Lin, Tengyu Ma, and Tianbao Yang. Distributed stochastic variance reduced gradient methods by sampling extra data with replacement. Journal of Machine Learning Re- search, 18(122):1-43 2017.
Gaëlle Loosli, Stéphane Canu, and Léon Bottou. Training invariant support vector machines using selective sampling. In Large-Scale Kernel Machines, pp. 301-320, 2007.
Tianxiang Luan, Tingjin Luo, Wenzhang Zhuge, and Chenping Hou. Optimal representative distri- bution margin machine for multi-instanee learning. IEEE Access, 8:74864-74874, 2020.
Angel Navia- Vazquez, D. Abellan. Distributed support vector machines. IEEE Transactions Neural Networks, 17(4): 1091-1097, 2006.
Emilio Parrado-Hernander and J. Navarro-
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Advances in Neural Information Processing Systems, pp. 1177-1184, Vancouver, Canada, 2007.
Reshma Rastogi, Pritam Anand, and Suresh Chandra. Large-margin distribution machine-based regression. Neural Computing and Applications, 32:3633-3666 2020.
Bernhard Schölkopf and Alexander Smola. Learning with kernels: support vector machines, regularization, optimization, and beyond. MIT Press, Cambridge, MA, 2001.
Si Si, Cho-Jui Hsieh, and Inderjit S. Dhillon. Memory efficient kernel approximation. Journal of
Machine Learning Research, 18:1-32, 2017.
Dinesh Singh, Debaditya Roy, and Krishna Mohan. Dip-svm : Distribution preserving kernel
support vector machine for big data. IEEE Transactions on Big Data, 3(1):79-90, 2017.
10

---

Under review as a conference paper at ICLR 2022
Zhi-Hao Tan, Teng Zhang, and Wei Wang. Coreset stochastic variance-reduced gradient with appli- cation to optimal margin distribution machine. In Proceedings of the 33th AAAI Conference on Artificial Intelligence, pp. 5083-5090. Honolulu, HI, 2019.
Zhi-Hao Tan, Peng Tan, Yuan Jiang, and Zhi-Hua Zhou, Multi-label optimal margin distribution machine. Machine Learning, 109(3):623-642, 2020.
Christopher Williams and Matthias Seeger. Using the nyström method to speed kernel machines. In Advances Neural Information Processing Systems, pp. 682-688, Cambridge, MA, 2001.
Hwanjo Yu, Jiong Yang, Jiawei Han, and Xiaolci Li. Making svms scalable to large data sets using hierarchical cluster indexing. Data Mining and Knowledge Discovery, 11(3):295-333 290,21,,,,,,, 2005.
Matei Zaharia, Mosharaf Chowdhury, Tathagata Das, Ankur Dave, Justin Ma, Murphy McCauly, Michael J. Franklin, Scott Shenker, and Ion Stoica. Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing. In 9th USENIX Symposium on Networked Systems Design and Implementation, pp. 15-28, San Jose, CA, 2012.
Teng Zhang and Hai Jin. Optimal margin distribution machine for multi-instance learning. In Proceedings of the 29th International Joint Conference on Artificial Intelligence, pp. 2383-2389, 2020.
Teng Zhang and Zhi-Hua Zhou. Large margin distribution machine. In Proceedings of the 20th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 313-322, New York, NY, 2014.
Teng Zhang and Zhi-Hua Zhou. Multi-class optimal distribution machine. Proceedings of the 34th International Conference on Machine Learning, pp. 4063-4071, Sydney, Australia, 2017.
Teng Zhang and Zhi-Hua Zhou. Optimal margin distribution clustering. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence, pp. 4474-4481, New Orleans, LA, 2018a.
Teng Zhang and Zhi-Hua Zhou. Semi-supervised optimal margin distribution machines. In Pro- ceedings of the 27th International Joint Conference Artificial Intelligence, pp. 3104-3110, Stockholm, Sweden, 2018b.
Teng Zhang and Zhi-Hua Zhou. Optimal margin distribution machine, IEEE Transactions on Knowl- edge and Data Engineering. 32(6): 143-1156, 2019.
Teng Zhang, Peng Zhao, and Hai Jin. Optimal margin distribution learning in dynamic environ- ments. In Proceedings of the 34th AAAI Conference Artificial Intelligence, pp. 6821-6828, New York, NY, 2020.
Yu-Hang Zhou and Zhi-Hua Zhou. Large margin distribution learning with cost interval and unla- beled data. IEFE Tronsactions Knowledge and Data Engineering, 2877):174--1763, 2016.

---

Under review as a conference paper at ICLR 2022
A APPENDIX
A.1 PRELIMINARIES
Given labeled data set (111,01),.... yMr) the primal problem of ODM is
1
X
c vef (1 01-
min p(w) whiee
= [||
2M
E M
s.t. 0 & S you )(x,) 6 1 + 0 + Vi [M].
Denote X [0(x1),--.)) (.fe,,)....... o (m)))] Y diag(yi, yM). i 6 = (eii...;eea jeas] the
above primal form can be rewritten as
X(|E + =||=(1)
min p(w)= =
w w.f.c
2M - 0)2
(6)
s.t. (1 - (1-0)1m) 0)1M E YX w S (1+ +
where 1 is the M-dimensional all one vector.
With Lagrange multipliers S, R& for the two constraints respectively, the Lagrangian of Eqn. leads
L w 12+ X(| + u||el1?) (YX w - (01-()01 + E)
2M - 0)2
+ + YYX w (1 + 1)1M - c).
and the KKT conditions are
w = = 3). g M(1 0)2 -
X C, M M(L 0)2
B,
(8)
du
( ())
Blyww o(x;) (1 + -;) =
(9)
Eqn. (8) is derived by setting the partial derivative of L w.r.t. E) to zero. Eqn. 9 is the complementary slackness conditions. Observe that y,w ((x;) < 1 and y,w o(x;) 1 9 cannot hold simultaneously, therefore at least one of the two slack variables & and 6; is zero According to Eqn. (8). we have &. 0 for any [M].
The following dual problem of ODM follows by substituting Eqn. g back into Eqn. 7
Me
min S.EER
d(s, = (C 3) TCC - 33) + 2 (u||C]|2 + || - (0 -0-1)1 1) (0 1110 M,
2
where Q = XX and c = (1 (1)0)2//a //\/Au is constant. By denoting a = [ç: []. above problem
can be rewritten as a standard convex quadratic programming:
1 =a² [ McvI
-Q
(A 1)1
min DER2M
((a)
Q
Mel
a+
(0 + 1)
Suppose the instances the k-th partition are {xx (k) (K) lem ODM on the k-th partition
31 )
...... (R) (k) ym }}. then the dual prob-
1 _ -Bx) Q (Cx
min
dc(Ck, Bu)
Bxx)
<a ERT
+
mc
2 (ulico co + |1 112) + (0 - II + (0 + 1,
where Q: = Y,X, Y,, X = |0(2 (k) .... p( }1 and Y₁ diag(vi (k) No-
tice that the optimization variables Çs and B& are decoupled on each partition, by merging all the K problems together, we can get the formulation of DiODM:
min ā(C, = -3 - + me G.BERM
2 (1| + [| + (0 - 1)13 + (# 1,
where diag( Q Qı,..., Qx) is block diagonal matrix, Ç (G: (a), and B [B: : Bk)
12

---

Under review as a conference paper at ICLR 2022
A.2 PROOF OF THEOREM 1
Theorem 1. Suppose the optimal solutions of ODM and DiODM are o² - :5 and ā B") respectively. The gaps between the optimal objective values and solutions satisfy
0 S . d(5" (8) S (Q + (MM m)c).
(10)
U
a a=1² Mcu
(Q + ((M (m))),),
(11)
where U = max((1<*1l
|
bo | 1oo | oo,) and Q = Eij.P() [Q]]]
Proof. The left-hand side of Eqn. TOp is due to the optimality of Ç* and 3
Without loss of generality, suppose the instances { , (ÆM, yas) are ordered by partition index, ie., the first m instances are on the first partition, and the second m instances are on the second
partition, etc. According to the definition of d(ç, 33) and d(c, and by denoting 7 Ç - -, we have
Q) B] + (M- -m)c a(c,3)= a( + (S (
1
(u||c]) + 11,3113)
2
=ā(;, + 1
7n9 Ing + (M- - m)c
Σ
(u||<|]2 + [|3113).
2
P.:P(W+P()
In particular, the following holds:
(M m)c
d(<', = á((": B3r) + 2
E
A95( +
(1/1<<112 ||0|++++00 (138
(12)
2
P))P()))))))
(')) = ăiĆ", 3r) + 1
Σ
76 Q2i5
(M -m]e
(u:1i²113 + +1
(13)
2
k.j:P(*PG))
Notice that at least one of Ç and 3, is zero, thus hy < 1
|8
max 181) = U. Subtracting
Eqn. [12) from Eqn. (13) yields the right-hand side of Eqn. TO)
1
a(C", 3*) d(c", (,,)B'
Σ
(55
(1)
2
(M- m)c
[u(1[=112- ||( + || - 1|31
2
1
(M - m)c
M ,in Q +
Cullč*I' + =100~13))
2
2
< <U + MM mn).
where the first inequality follows from the optimality of ç" and 3 and the third inequality is derived by the boundness of Ç. 7
y and u S 1.
Since f(a) is a quadratic function, it can be expanded x as
(a* ʃ(ā²) = f(a*) Vf(a") "[(aa")(a** - aa) + (Ø+ -a") V2 [a)=-'" -a*) a*)
2 f(a") (ā* aa") 2 V"'((")(aa"" a*)
[(aa) -āa- Q McvI
Q
Q Q+ Mcl (a*
Q
-a*)T 2 s(a") -aa-
{
[Moul
(a -a")
Mcl
2 f(a²) + Mcellä Mceela'-a'111 1/
where the first inequality follows from the first order optimality condition, and the third inequality uses the fact v < 1. Thus ||ă 212 can be upper bounded by
U2
o - 21 < Meu (d(( ()) -
<
Mav (Q + M(M m)c),
which shows that Eqn. (1) holds and concludes the proof.
13

---

Under review as a conference paper at ICLR 2022
A.3 PROOF OF THEOREM 2
Theorem 2.
For stift-invariant kernel k. with k(() = r², that is [|x( = r for any x. With the
parfition strategy described above, any k E [K], we have
U
dx.(k, ,d(5" -
+ 2UM + M22
2
U cos T 22)
where θ = EESjENAA (((.)))((),
Proof. Construct data set D based partition Dr by repeating each instance K times which appeared in DR. so that [D/] = (D] = M. According to our settings, the number of instances in
[Dd] belong the s-th stratum equals to |C,l- Denote D/2 {(x) (8) .v4""
(/(h))))) )<E(M and guarantee
that <((;;) = (a(a, (.)). Denote the dual form of ODM on 2/ as
min B%) = 2 (ck T) B%) + Mc.
(u||sk]1 +181113
CR
+ (0- 1) S
(0 + 3
where Q = YY Y X = 10(2)
(k))
o('n ). and Y diag(!/ (8) ,..., ymm (
g.
Denote the primal form of ODM on Dj
1
A
5 + ve?
min Pk((w)
[ 1|2
WLii
2
2M
(1 0)²
{E[M]
s.t. 0 - E S y ((x)))
S 1 + cg Vi E [M].
For convenience, let k = 1 so that Dx = {xx, y:) 31)lie(m hee[m) From the primal problem of ODM on Dz.
we have
Pk (wx))
2 =
1 112
+
A
2 + vc?
- 11000 +
Σ
2 + vc K
2m [E(m)
(1 0)2
2M
(1 0)2
(e(m]
1 1
e²2 + Ve,
2
112
+
pk (wx),
2M
(1 0)2
iE[M]
We can infer that the optimal solution of ODM on Dr and Dj are the same. Therefore, d' (S,, (C(Cn, Ba). According to the definition,
dc (B) d((*.3*)
(Cc: B1) Q - 3h) - -- TQ(* 3²)
1
Mc.
+ (u|())12 +||%|11 - -11
+ (0 1) - -(*)+ + (0 + 1) - -3¹)
Σ (Chikiggh (0)),,
(k) (0 n(0/
(k) x (k)) 7 (
[.E[M
+ 2 (11211 - -115*11)= + Me
Mev
(113)12 - 1118*12)
2
+ (0 1 - -c*) + (0 + Tr 33)
(14)
and -U2 < 21n33. 2ki S U2 0 / 1, 1,050 Then dClCe, (B) - , can be upper
bounded by
(x(() 2 (1)) ((,,, + U2M + M (15)
d, (k)
,9* s U2 Σ
[JEM
14

---

Under review as a conference paper at ICLR 2022
Notice that 2() = 2(10(<,))1 + [10(,)))1 [l((z.) (() Sequentially,
Σ (N<(re/ (1) arl (1)) x2 my))
1
Σ (1lo(2s) - ((x,))1 - |10( -60,, )
2
[]E[M]
1
Σ (1((())) - o(xx))1 - 11á(z) (10) 01(02 (13)
2
Σ (10(x;; - o(x,))l - (0) - 002z) )13)
+ 2
{(p))=)()))
For the situation where p(z;) * ((x;), the maximal value of [ - ((x,)1² is 4r square of diameter of the ball. The minimal value of |,((;;) - o(xx) )12 is 2r cos T) which can be computed by the law of cosines since the angle between ((x;) and ((x;) is greater than т.
According to the law of cosines, we can also upper bound (Ø(x;) - o(2,) 1 by 2r cos
when (x(;;) = ()x;,) It is obviously that [))(x,)) - ((x,))11 2 0, thus
Σ (n(ax (K), .x, (00) - k(x; 22)) S (.E(M)
Σ
(4r² 2r - (1-00877 T))
((m:))/((as)
(16)
+
Σ
2r cOs
((,))=
Substitute Eqn. 16 into Eqn.
15
we can derive the bound
((27" - -2( c)sT)) U2M
d% 3%,) d(S", s 2
Σ
2
v(m:))/i(ms)
Σ
22 (1-cos11 cos T)) + 2UM
p(a.)=p(2,)
< U2220( + COST) + U3 0)(1 - cos T) + U2M²c
M
2
U
= u22
cos (00 M²)
2 + +UM
15


Reviews:
[{"review_id": "bXrZS_daEYy", "reviewer": "Reviewer_NozY", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Pros\n1.\tThe paper proposes a novel partition strategy for training kernel method in distributed scenario, leading to nearly ten times speedup.\n2.\tThe paper is thorough and accomplished. Both linear and nonlinear kernels are fully considered. Both theoretical analyses and empirical studies are clearly presented.\n3.\tThe experiments are conducted on data sets obtained from public repositories and necessary links to the readers are given.\n\nQuestions during rebuttal period: \nMany studies have been devoted to reduce the time cost of kernel method, e.g., random feature, Nystrom method, etc. What is the advantage of DiODM compared to these off-the-shelf kernel acceleration methods?\n", "summary_of_the_paper": "This paper proposes a distributed optimal margin distribution machine (DiODM), which can significantly reduce the training time so as to handle large scale data. Specifically, when nonlinear kernel applied, DiODM can lead to nearly ten times speedup based on the proposed novel partition strategy; as for linear kernel, DiODM extends a communication efficient distributed SVRG to further accelerate the training. The paper also presents the theoretical analysis inspiring the partition strategy, and extensive experimental results verifying the superiority of the proposed algorithm.", "summary_of_the_review": "Generally, this is a solid work for accelerating ODM. The authors not only propose a novel partition strategy leading to excellent performance, but also detail the intuition behind, i.e., utilizing the stratified sampling to preserve data distribution. The theoretical analyses are broken down into many small steps and easy to follow.\nThe experiments are conducted on data sets obtained from public repositories and necessary links to the readers are given. Considering all these, I vote for acceptance.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "YnYaydZ_QAs", "reviewer": "Reviewer_jk73", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "\nStrengths:\nOverall, the paper proposes a solid contribution to a problem with broad applications, e.g., classification. They also show the effectiveness of their methods both theoretically and emprically. Moreover, the paper is pretty well-written and easy to follow. It is worth noting that tey authors make the presentation of equations and theoretical material accessible by providing the optimal levels of details so that they convey the main points without being tedious. \n\nWeaknesses:\n\nDespite many strengths, there are a few issues with the paper as I explain below:\n\n(a) In page 2, regarding the sentence \"therefore the third term is exactly the margin variance.\" it is my understanding the third term is the upper bound on the margin variance, not the margin variance itself. \n\n(b) It is my understanding the Theorem 1 only implies that the difference between optimal solutions and optimal values of the main QP problem and partitioned QP problem are upper-bounded. What does this Theorem imply about the optimality of the solution obtained by running Alg. 1 with L iterations and S stratums?  \n\n(c) It seems that as the iterations grow the local QP problems on each partition get bigger, which I believe is a weakness of the proposed method. In fact, related to (b), it would be beneficial to know that after how many iterations we could stop the algorithm, while the local problems are not prohibitively large. \n\n(d) What are the parameters (e.g., L and S in Alg. 1 and T, S, and K in Alg. 2) used in the experiments? \n\n\n\n\n\n\n\n\n", "summary_of_the_paper": "The paper focuses on the Optimal margin Distribution Machine (ODM), i.e., a more robust version of the traditional maximum margin problems such as training Support Vector Machines (SVM). In particular, the authors introduce a novel iterative distributed algorithm for solving the resulting Quadrating Programming (QP) problem. They furthermore propose a method for optimally partitioning the data. In the case of linear kernels, they show that their method can benefit from the SVRG gradient methods. The proposed methods come with theoretical guarantees and they show that the proposed methods outperform or have competitive performance with three different QP solvers on seven real datasets. ", "summary_of_the_review": "Overall, I believe the authors address a generic and important problem. The proposed methods are novel and are supported with acceptable theoretical and empirical evidence. I believe the issues I raised above are only minor, but important to address, if possible.  ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Lx5MjuQPX1R", "reviewer": "Reviewer_AGhv", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "strengths:\n1.  Result in theorem 1 seems useful as the bound depends on m.\n2. Result in theorem 2 is indeed helpful in motivating the intuitive landmark selection strategy.\n3. Improvements in fig2 seem encouraging.\n\nCritical comments:\n1. The paper seems to present a parallel solver rather than a distributed one. This is because a run of the solver with entire data is also a sub-step. Simulations are also performed with multiple cores rather than nodes. I think this must be highlighted in title and abstract too. Currently, it seems that the paper is presenting a distributed algorithm, which is not the case. \n\n2. The tree structured based parallel strategy has limited novelty as such ideas are popular among parallel methods.\n\n3. Some important details are missing in Algo1 (and elsewhere). For e.g., it is mentioned that solutions are concatenated to initialize the next level solvers. What exactly is meant by concatenation ? is it averaging ? There are works that study various aggregation strategies (e.g., https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=8911318 etc.). Also step14 in algo1 must be return \\alpha^1.\n\n4. Speed up is achieved primarily because for solver instances with higher data get better initialization. Since this does not improve the rate of convergence and only may effect the involved constants, the method is intended to achieve limited improvement. It would be insightful if improvement of the constants involved in rate of convergence are theoretically bounded etc.\n\n5. Since the solver runs with entire data too, and the problem is convex, convergence is anyway guaranteed.\n\n6. Since partition strategy is one of the contributions, it would have been nice to compare empirically the proposed strategy with baselines in terms of computation-accuracy trade-off.\n\n7. Section 3.3 is repetition of Lee et.al, 17 and hence can go into background/related work.\n\n8. What are the baselines Ca-ODM, DiP-ODM and DC-ODM? References seem to be missing. Without such details it is hard to evaluate the simulations section. \n\n9. Since acc-DiODM is Lee et.al.'17, the section 4.2 may be postponed to appendix.\n\n10. It is not clear what  the baselines in figure 3 are. Again this makes evaluation of simulations section difficult.\n\n11. A major weakness of simulation section is comparison with state-of-the-art distributed-SVM solvers is missing. This seems very important as the form of the optimization is same as that in SVM. For example, https://arxiv.org/pdf/1005.2012.pdf etc.", "summary_of_the_paper": "The paper presents a parallel solver for speeding up training time of ODM. The key idea is to perform computation via a tree structure. Solvers at parent level are initialized with \"concatenated\" (averaged?) solutions from child level. The hope is that convergence will be faster because of closeness to optimal though the data size grows.\n\n A Schur complement based strategy for partitioning for the data is presented.\n\nFor linear kernels, the DSVRG solver of Lee et.al.'17 is (directly) employed. Simulations show that for linear kernel, the Lee et.al., outperforms the proposed method.\n\nHowever, with non-linear kernels, the proposed methods improves over some baselines.", "summary_of_the_review": "Overall, the methodology seems to have limited novelty and limited potential for improvement over baselines. Important details seems to be missing in the presentation. Simulations seem to be weak.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "8E8EA2uiPny", "reviewer": "Reviewer_cre7", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "One of my concerns is that the optimization problem for ODM is quite close to the standard L1/L2-SVMs. As the authors mentioned, there are a lot of previous results on distributed solvers for SVMs. It seems to me that this paper proposes a distributed solving method for a similar problem to SVM(ODM). The authors should clarify the differences between the proposed method and previous results on distributed SVMs, so that the technical contribution is clear. ", "summary_of_the_paper": "The paper considers the optimization problem for ODM and proposes a distributed method for solving the problem. The authors prove its convergence to the optimum and show some experimental results comparing the proposed methods and previous work.", "summary_of_the_review": "The problem seems quite similar to the standard SVMs and a new distributed solver for the problem looks not significantly new.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: While some of the reviewers find that the paper proposes a solid contribution to a problem, I will tend
to agree with other ones that the proposed approach has limited novelty and limited potential for improvement over baselines. In addition,  simulations are pretty weak due to lack of comparisons to strong baselines and to lack of clarity.
Decision: Reject