Year: 2021

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.

heading: 1 INTRODUCTION
text: Recently, the study on margin theory (Gao & Zhou, 2013) demonstrates an upper bound disclosing that maximizing the minimum margin does not necessarily result in a good performance, and instead, the distribution rather than a single margin is much more important. Later on, the study on lower bound (Grønlund 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 simultaneously, and exhibits much better generalization performance than the traditional large margin based counterparts.Due to the superiority shown on both binary and multi-class classification tasks (Zhang & Zhou, 2014; 2017), many works attempt to extend ODM to more genreal learning settings, just to list a few, cost-sensitive learning (Zhou & Zhou, 2016; Cheng et al., 2017), weak supervised learning (Zhang & Zhou, 2018a;b; Luan et al., 2020; Zhang & Jin, 2020), multi-label learning (Tan et al., 2020), online learning (Zhang et al., 2020) and regression (Rastogi et al., 2020).
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., 2019) 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 to directly speed up ODM include random Fourier feature (Rahimi & Recht, 2007) and Nyström (Williams & Seeger, 2001). Notice that the random Fourier method adopts a data-independent kernel mapping while the Nyström method takes a distribution-unaware sampling, they are both inferior to coreset method due to the insufficient use of data, which may only lead to a degraded generalization performance. All these methods are proposed for computing on one cpu core, but with the dramatic progress of digital technologies, the 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 one cpu core can hardly afford and motivates us to seek the distributed training methods.
Up to now 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
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 partitions is designed first, guided by which the solutions of different partitions are 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 (Si et al., 2017), both low-rank and clustering structure of the kernel matrix are considered to get an approximation of kernel matrix. The other one works in distributed optimization level, that is directly applying the distributed optimization method, such as augmented Lagrangian method (Forero et al., 2010) and alternating direction method of multipliers (Boyd et al., 2010), or extending existing solver to distributed environment, e.g. distributed SMO (Cao et al., 2006).
Although many distributed solver for quadratic programming (QP) problems can be directly applied to ODM, these off-the-shelf 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 a novel data partition method so that ODM trained on each partition has a solution close to that trained on the whole data. Therefore, when some partitions are merged to form a 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 a 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 a 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 a 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.

heading: 2 PRELIMINARIES
text: 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 ⊆ RN and Y = {1,−1} is output space. d·e is the round up function. For any positive integer M , the set of integers {1, . . . ,M} is denoted by [M ]. For the feature mapping φ : X 7→ H associated to some positive definite kernel κ where H is the corresponding reproducing kernel Hilbert space (RKHS), κ(x, z) = 〈φ(x), φ(z)〉H holds for any x and z. In this paper we consider the shift-invariant kernel such as RBF kernel for simplicity, which satisfies κ(x, z) = κ(x− z). 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 margin (Schölkopf & Smola, 2001), which may hurt the generalization performance.
On the other hand, ODM explicitly optimizes the margin distribution. Given a labeled data set {(xi, yi)}i∈[M ], ODM is initially formalized by maximizing the margin mean and minimizing the margin variance:
min w,γ̄,ξi, i
1 2 ‖w‖2 − ηγ̄ + λ 2M ∑ i∈[M ] (ξ2i + 2 i ) s.t. γ̄ − ξi ≤ γi ≤ γ̄ + i, ∀i ∈ [M ], (1)
where η, λ are the trading-off parameters, γi = yiw>φ(xi) is the margin of the labeled instance (xi, yi) and γ̄ is the mean of γi. Note that the two slack variables ξi and i 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 1 are more likely to be misclassified, therefore we introduce a new
hyper-parameter υ ∈ [0, 1] to weight the ξi. Last but not least, notice that instances not lying on the hyperplane yiw>φ(xi) = 1 all contribute to the decision boundary, to achieve a lightweight model, we can tolerate the deviation smaller than the given threshold θ. Plugging all these back into Eqn. (1) yields the primal problem of ODM:
min w,ξi, i
p(w) = 1 2 ‖w‖2 + λ 2M ∑ i∈[M ] ξ2i + υ 2 i (1− θ)2
s.t. 1− θ − ξi ≤ yiw>φ(xi) ≤ 1 + θ + i, ∀i ∈ [M ].
By introducing the Lagrange multipliers ζ,β ∈ RM+ for the 2M inequality constraints respectively, the dual problem of ODM is
min ζ,β∈RM+
d(ζ,β) = 1 2 (ζ − β)>Q(ζ − β) + Mc 2 (υ‖ζ‖2 + ‖β‖2) + (θ − 1)1>Mζ + (θ + 1)1>Mβ,
where [Q]ij = yiyjκ(xi,xj) and c = (1 − θ)2/λυ is a constant. The detailed derivation can be found in supplementary. By denoting α = [ζ;β], the dual ODM can be rewritten as a standard convex QP problem:
min α∈R2M+
f(α) = 1
2 α>Hα+ b>α, (2)
in which
H = [ Q +McυI −Q −Q Q +McI ] , b = [ (θ − 1)1M (θ + 1)1M ] .
Notice that Eqn. (2) only involves 2M decoupled box constraints, thus it can be efficiently solved by a dual coordinate descent method. To be specific, in 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 t:
min t
f(α+ tei) = 1
2 [H]iit
2 + [∇f(α)]it+ f(α), (3)
which has a closed-form solution:
[α]i ← max([α]i − [∇f(α)]i/[H]ii, 0).

heading: 3 PROPOSED METHOD
text: DiODM works in distributed data level, that is it works by dividing the data into partitions on which local models are trained and then used to find the larger local or global models. For simplicity, we assume there are K = pL partitions at first with the same cardinality m, i.e., m = M/K. The data set {(xi, yi)}i∈[M ] 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 (xi, yi), the index of partition to which it belongs is P (i) = d(i− 1)/me.
Suppose {(x(k)i , y (k) i )}i∈[m] is the data on the k-th partition, then the local ODM on it is
min ζk,βk∈Rm+
dk(ζk,βk) = 1
2 (ζk − βk)>Q(k)(ζk − βk)
+ mc
2 (υ‖ζk‖2 + ‖βk‖2) + (θ − 1)1>mζk + (θ + 1)1>mβk,
where [Q(k)]ij = y (k) i y (k) j κ(x (k) i ,x (k) j ). This problem can be rewritten as a standard convex QP problem in the manner of Eqn. (2), and efficiently solved by dual coordinate descent method as Eqn. (3).
Once the parallel training of pL local ODMs are completed, we merge every p partitions to form pL−1 larger partitions. On each larger partition, a new local ODM is trained again by dual coordinate descent method, but the optimization procedure is not started from the scratch. Instead, the
p solutions obtained on the p corresponding smaller partitions making up this larger partition, are concatenated as the initial point of the optimization. Since by our proposed novel partition strategy, this concatenated solution is already a good approximation to the optimal solution of ODM on the larger partition. We will elaborate on this in subsequent sections.
The above procedure is repeated until the solution converges or all the partitions are merged together. We give the pseudo-code of DiODM in Algorithm 1.
Algorithm 1 DiODM Input: Data set D = {(xi, yi)}Mi=1. Parameter: Partition control parameter p, number of stratums S, number of iterations L. Output The solution α.
1: Get S landmarks by Eqn. (5) on D. 2: Sample instances without replacement to get partitions D1, . . . ,DpL . 3: Initial the dual solution αL = 0. 4: for l = L, . . . , 1 do 5: if α converge then 6: break 7: end if 8: for p = 1, . . . , pl do 9: Solve the ODM with dual coordinate descent.
10: end for 11: Merge every p partitions to form new partitions. 12: αl−1 = αl. 13: end for 14: return αl.

heading: 3.1 CONVERGENCE
text: In this subsection, we present a 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:
min ζ,β∈RM+
d̃(ζ,β) = 1 2 (ζ − β)>Q̃(ζ − β) + mc 2 (υ‖ζ‖2 + ‖β‖2) + (θ − 1)1>Mζ + (θ + 1)1>Mβ,
where Q̃ = diag(Q(1), . . . ,Q(K)) 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, it 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., d̃(ζ,β), are α? = [ζ?;β?] and α̃? = [ζ̃?; β̃?] respectively, then the gaps between these two optimal solutions satisfy
0 ≤ d(ζ̃?, β̃?)− d(ζ?,β?) ≤ U2(Q+M(M −m)c),
‖α̃? −α?‖2 ≤ U 2
Mcυ (Q+M(M −m)c), where Q = ∑ i,j:P (i) 6=P (j) |[Q]ij | is the sum of the absolute values of the Q’s entries which turn to zero in Q̃, and U = max(‖α?‖∞, ‖α̃?‖∞) 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 ζ? and β?.
By comparing the definition of d(ζ,β) with that of d̃(ζ,β), we can easily find that the only differences are the change of Q to Q̃, and M to m. Thus the gap between d(ζ?,β?) and d̃(ζ?,β?) can
be upper bounded by the infinity norm of α? and the sum of the absolute values of the Q’s entries which turn to zero in Q̃. The gap between d(ζ̃?, β̃?) and d̃(ζ̃?, β̃?) can be upper bounded in a similar way. Combining these together with the optimality of ζ̃? and β̃?, i.e., d̃(ζ̃?, β̃?) ≤ d̃(ζ?,β?), 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 α? as
f(α?) + g>(α̃? −α?) + (α̃? −α?)>H(α̃? −α?), in which g>(α̃? −α?) is nonnegative according to the the first order optimality condition. Furthermore, H can be lower bounded by the sum of a positive semidefinite matrix and a scalar matrix:
H [ Q −Q −Q Q ] +Mcυ [ I I ] .
By putting all these together, we can show that ‖α̃? − α?‖2 is upper bounded by f(α̃?) − f(α?), i.e., d(ζ̃?, β̃?) − d(ζ?,β?), 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 of DiODM is getting closer and closer to that of ODM, that is to say, our proposed algorithm converges.

heading: 3.2 PARTITION STRATEGY
text: In this section we detail the partition strategy, which plays an important role in 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 (Hsieh et al., 2014) adopts the kernel k-means and simply regards each cluster as a 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 as possible, we borrow the idea from stratified sampling, i.e., we first divide the data set into some homogeneous strata, and then apply random sampling within each stratum. To be specific, suppose the goal is to generate K partitions. We first choose S landmark points {φ(zs)}s∈[S] in RKHS, and then construct one stratum for each landmark point by assigning the rest instances to the stratum in which its nearest landmark point lies, i.e., the index of stratum xi belongs to is
ϕ(i) = arg min s∈[S]
‖φ(xi)− φ(zs)‖.
For each stratum Cs, we equally divide it into K pieces by random sampling without replacement, and take one piece from each stratum to make up a partition and totally K partitions are created.
The remaining question is how to select these landmark points. Obviously, they should be representative enough to sketch the whole data distribution. To this end, we introduce the minimal principal angle which is defined between different stratum:
τ = min i 6=j
{ arccos
〈x, z〉 ‖x‖‖z‖ ∣∣∣∣ x ∈ Ci, z ∈ Cj} . 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-invariant kernel κ with κ(0) = r2, that is ‖φ(x)‖ = r for any x. With the partition strategy described above, for any k ∈ [K], we have
dk(ζk,βk)− d(ζ?,β?) ≤ U2M2c
2 + 2UM + U2M2r2 + U2r2 cos τ(2Θ−M2), where Θ = ∑ i,j∈[M ],i6=j 1ϕ(i)6=ϕ(j), and U is same with Theorem 1.
Proof sketch. Follow the construction process mentioned in appendix, we generate a data set D′k where |D′k| = |D| = M . According to our settings, the number of instances in |D′k| belong to the s-th stratum equals to |Cs|. Give the definition of dk(ζk,βk) and d′k(ζ′k,β′k) in appendix, we have d′k(ζ ′ k,β ′ k) = dk(ζk,βk) since Dk and D′k share the same margin mean and variance under the same hyperplane.
Denote α′k = [ζ ′ k;β ′ k], γ ′ k = [ζ ′ k − β′k]. By contrasting the definition of d′k(ζ′k,β′k) with that of d(ζ?,β?), we can find that the differences consists of three parts. The first part is Mc
2 (υ‖ζ′k‖2 + ‖β′k‖2 − υ‖ζ?‖2 − ‖β?‖2),
and the second part is
(θ + 1)1>M (β ′ k − β?) + (θ − 1)1>M (ζ′k − ζ?).
Note that both of above parts can be upper bounded by the infinity norm of α′k. The third part can be denoted as
gk(γ ′ k) =
1 2 γ′k > Q′kγ ′ k − 1 2 γ?>Qγ?.
With the boundness that −U2 ≤ γ?i γ?j , γ′kiγ ′ kj ≤ U 2, 0 ≤ υ ≤ 1, 0 ≤ θ ≤ 1, we have
gk(γ ′ k) ≤U2 ∑ i,j∈[M ] (κ(x′i (k) ,x′j (k) )− κ(xi,xj)) (4)
Upper bound κ(x′i (k) ,x′j (k) )−κ(xi,xj) by minimal principal angle and the law of cosines, we can easily find that gk(γ′k) ≤ U2M2r2 + U2r2 cos τ(2Θ −M2). 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 Dk. Note that 2Θ > M2 holds for any s ∈ [S] when |Cs| < 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:
z1 = arg max z∈D κ(z, z), zs = arg max z∈D/{z1,...,zs−1} SCs−1(z) (5)
where SCs(z) = κ(z, z) − K>z,sK−1s Kz,s is the Schur complement of a new candidate landmark zs+1 based on the landmarks {z1, ...,zs} which have been already selected, Kz,s = [κ(z, z1), ..., κ(z, zs)], Ks ∈ Rs×s is defined as [Ks]i,j = κ(zi, zj). In the process of solving zs, we actually seek the instance which maximize the determinant of kernel matrix construct by {z1, ...,zs}. It is obviously that the maximum determinant is achieved when φ(zs) is orthogonal to span{φ(z1), ..., φ(zs−1)}. Therefore, we can maximize the minimal principal angle by choosing the instance with maximum Schur complement.
It 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.

heading: 3.3 ACCELERATION FOR LINEAR KERNEL
text: 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 (xi, yi) as∇pi(w), we have
∇pi(w) = w + λ(yiw >xi + θ − 1)yixi1i∈I1 (1− θ)2 + λυ(yiw >xi − θ − 1)yixi1i∈I2 (1− θ)2
where I1 = {i | yiw>xi < 1− θ}, and I2 = {i | yiw>xi > 1 + θ}. Since the the objective function of ODM is differentiable, distributed SVRG (DSVRG) (Lee et al., 2017) can be exploited in this scenario. It generates a 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, so that an unbiased estimation of the gradient can be computed. In each iteration, all nodes are joined together to compute the full gradient first. Then each node performs the iterative update of SVRG in serial in a “round robin” fashion, i.e., let all nodes stay idle except one node performing a certain steps of iterative updates using its local auxiliary data and passing the solution to the next node. We show the process of solving DiODM by DSVRG algorithm in Algorithm 2.
Algorithm 2 Accelerated DiODM for linear kernel Input: Training data set D = {(xi, yi)}Mi=1 Parameters: Number of partitions K, number of stratums S, number of stages St, step size η, the number of iterations T . Output: Solution at St stage wSt
1: Get S landmark points by Eqn. (5) on D. 2: Sample instances without replacement to get partitions D1, . . . ,DK 3: Generate the auxiliary arrayR1, . . . ,Rk whereRi = {j|(xj , yj) ∈ Di} 4: s← 1. 5: for l = 0, 1, . . . , St − 1 do 6: The center node sends wl to each node. 7: for each node j = 1, 2, . . . ,K in parallel do 8: Compute hlj = ∑ i∈Dj ∇pi(w l)
9: send hlj to center. 10: end for 11: hl = 1M ∑K j=1 h l j 12: Initial the solutions wl+10 = w l 13: for t = 0, 1, 2, . . . , T − 1 do 14: Sample instances (xi, yi) from Ds where i ∈ Rs 15: wl+1t+1 = w l+1 t − η∇pi(wl+1t )−∇pi(wl) + hl) 16: Rs ← Rs\i 17: ifRs = ∅ then 18: send wl+1t+1 to node s+ 1. 19: s← s+ 1. 20: end if 21: end for 22: wl+1 = wl+1T 23: end for 24: return wSt

heading: 4 EXPERIMENTS
text: In this section, we evaluate the performance of our proposed algorithms by comparing with other QP solvers.

heading: 4.1 SETUP
text: We evaluate the performance of our proposed algorithms on seven real-world data sets.1 The statistics of these data sets are summarized in Table 1. All features are normalized into the interval [0, 1]. For each data set, eighty percent of instances are randomly selected as 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 is equipped with 16 Intel Xeon E5-2670 CPU cores and 64G RAM.
1https://www.csie.ntu.edu.tw/∼cjlin/libsvmtools/datasets/
DiODM is compared with three state-of-the-art distributed QP solvers, that is, Cascade approach (Ca-ODM) (Graf et al. (2004)), DiP approach (DiP-ODM) (Singh et al. (2017)) and DC approach (DC-ODM) (Hsieh et al. (2014)). We denote our proposed dual coordinate descent based algorithm as DiODM and accelerating algorithm as acc-DiODM. Besides, in evaluating the efficiency of acc-DiODM, two state-of-the-art gradient based methods are implementd, that is SVRG method (ODMsvrg) (Johnson & Zhang (2013)) and CSVRG method (ODMcsvrg) (Tan et al. (2019)).

heading: 4.2 RESULTS WITH LINEAR KERNEL
text: Figure 1 presents the time cost and test accuracy on data sets with linear kernel. In the Figure 1(a)(e), we show the training speedup ratio with cores increasing from 1 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 acc-DiODM show highly competitive performance compared with other methods. Specifically, accDiODM achieves better test accuracy and faster training speed than Ca-ODM, DPP-ODM and DCODM. DiODM achieves the better test accuracy on 5 data sets and just slightly worse than DC-ODM on skin-nonskin data set. On time cost, DiODM achieves faster training speed on all 6 data sets.

heading: 4.3 RESULTS WITH RBF KERNEL
text: Figure 2 presents 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 4 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.

heading: 4.4 COMPARISON WITH GRADIENT BASED METHODS
text: Figure 3 compares the training speed and generalization performance between our acceleration method and other gradient based methods. We observe that our method can get competitive test accuracy. Meanwhile, our method achieves over 5 times faster speed than other methods. This
indicates that our distributed acceleration method achieves great training speed while hold the generalization performance.

heading: 5 CONCLUSION
text: While lots of works have been proposed to 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 to limited bandwidth or user privacy.

heading: A APPENDIX
text: A.1 PRELIMINARIES
Given a labeled data set {(x1, y1), . . . , (xM , yM )}, the primal problem of ODM is
min w,ξi, i
p(w) = 1 2 ‖w‖2 + λ 2M ∑ i∈[M ] ξ2i + υ 2 i (1− θ)2 ,
s.t. 1− θ − ξi ≤ yiw>φ(xi) ≤ 1 + θ + i, ∀i ∈ [M ]. Denote X = [φ(x1), . . . , φ(xM )], Y = diag(y1, . . . , yM ), ξ = [ξ1; . . . ; ξM ], = [ 1; . . . ; M ], the above primal form can be rewritten as
min w,ξ,
p(w) = 1 2 ‖w‖2 + λ(‖ξ‖ 2 + υ‖ ‖2) 2M(1− θ)2 ,
s.t. (1− θ)1M − ξ ≤ YX>w ≤ (1 + θ)1M + , (6)
where 1M is the M -dimensional all one vector.
With Lagrange multipliers ζ,β ∈ RM+ for the two constraints respectively, the Lagrangian of Eqn. (6) leads to
L = 1 2 ‖w‖2 + λ(‖ξ‖ 2 + υ‖ ‖2) 2M(1− θ)2 − ζ>(YX>w − (1− θ)1M + ξ)
+ β>(YX>w − (1 + θ)1M − ), (7)
and the KKT conditions are
w = XY(ζ − β), ξ = M(1− θ) 2
λ ζ, =
M(1− θ)2
λυ β, (8)
ζi(yiw >φ(xi)− (1− θ) + ξi) = 0, βi(yiw>φ(xi)− (1 + θ)− i) = 0. (9)
Eqn. (8) is derived by setting the partial derivative of L w.r.t. {w, ξ, } to zero. Eqn. (9) is the complementary slackness conditions. Observe that yiw>φ(xi) < 1 − θ and yiw>φ(xi) > 1 + θ cannot hold simultaneously, therefore at least one of the two slack variables ξi and i is zero. According to Eqn. (8), we have ζiβi = 0 for any i ∈ [M ]. The following dual problem of ODM follows by substituting Eqn. (8) back into Eqn. (7):
min ζ,β∈RM+
d(ζ,β) = 1 2 (ζ − β)>Q(ζ − β) + Mc 2 (υ‖ζ‖2 + ‖β‖2) + (θ − 1)1>Mζ + (θ + 1)1>Mβ,
where Q = YX>XY and c = (1− θ)2/λυ is a constant. By denoting α = [ζ;β], above problem can be rewritten as a standard convex quadratic programming:
min α∈R2M+
f(α) = 1
2 α> [ Q +McυI −Q −Q Q +McI ] α+ [ (θ − 1)1M (θ + 1)1M ]> α.
Suppose the instances on the k-th partition are {(x(k)1 , y (k) 1 ), . . . , (x (k) m , y (k) m )}, then the dual problem of ODM on the k-th partition is
min ζk,βk∈Rm+
dk(ζk,βk) = 1
2 (ζk − βk)>Q(k)(ζk − βk)
+ mc
2 (υ‖ζk‖2 + ‖βk‖2) + (θ − 1)1>mζk + (θ + 1)1>mβk,
where Qk = YkXk>XkYk, Xk = [φ(x (k) 1 ), . . . , φ(x (k) m )], and Yk = diag(y (k) 1 , . . . , y (k) m ). Notice that the optimization variables ζk and βk are decoupled on each partition, by merging all the K problems together, we can get the formulation of DiODM:
min ζ,β∈RM+
d̃(ζ,β) = 1 2 (ζ − β)>Q̃(ζ − β) + mc 2 (υ‖ζ‖2 + ‖β‖2) + (θ − 1)1>Mζ + (θ + 1)1>Mβ,
where Q̃ = diag(Q1, . . . ,Qk) is a block diagonal matrix, ζ = [ζ1; . . . ; ζk], and β = [β1; . . . ;βk].
A.2 PROOF OF THEOREM 1
Theorem 1. Suppose the optimal solutions of ODM and DiODM are α? = [ζ?;β?] and α̃? = [ζ̃?; β̃?], respectively. The gaps between the optimal objective values and solutions satisfy
0 ≤ d(ζ̃?, β̃?)− d(ζ?,β?) ≤ U2(Q+M(M −m)c), (10)
‖α̃? −α?‖2 ≤ U 2
Mcυ (Q+M(M −m)c), (11) where U = max(‖ζ?‖∞, ‖β?‖∞, ‖ζ̃?‖∞, ‖β̃?‖∞), and Q = ∑ i,j:P (i)6=P (j) |[Q]ij |.
Proof. The left-hand side of Eqn. (10) is due to the optimality of ζ? and β?.
Without loss of generality, suppose the instances {(x1, y1), . . . , (xM , yM )} are ordered by partition index, i.e., the firstm instances are on the first partition, and the secondm instances are on the second partition, etc. According to the definition of d(ζ,β) and d̃(ζ,β), and by denoting γ = ζ − β, we have
d(ζ,β) = d̃(ζ,β) + 1 2 (ζ − β)>(Q− Q̃)(ζ − β) + (M −m)c 2 (υ‖ζ‖2 + ‖β‖2)
= d̃(ζ,β) + 1
2 ∑ i,j:P (i)6=P (j) γiγj [Q]ij + (M −m)c 2 (υ‖ζ‖2 + ‖β‖2).
In particular, the following holds:
d(ζ?,β?) = d̃(ζ?,β?) + 1
2 ∑ i,j:P (i)6=P (j) γ?i γ ? j [Q]ij + (M −m)c 2 (υ‖ζ?‖2 + ‖β?‖2), (12)
d(ζ̃?, β̃?) = d̃(ζ̃?, β̃?) + 1
2 ∑ i,j:P (i)6=P (j) γ̃?i γ̃ ? j [Q]ij + (M −m)c 2 (υ‖ζ̃?‖2 + ‖β̃?‖2). (13)
Notice that at least one of ζi and βi is zero, thus |γi| ≤ |ζi|+|βi| ≤ max(|ζi|, |βi|) = U . Subtracting Eqn. (12) from Eqn. (13) yields the right-hand side of Eqn. (10):
d(ζ̃?, β̃?)− d(ζ?,β?) ≤ 1 2 ∑ i,j:P (i) 6=P (j) (γ̃?i γ̃ ? j − γ?i γ?j )[Q]ij
+ (M −m)c
2 [υ(‖ζ̃?‖2 − ‖ζ?‖2) + (‖β̃?‖2 − ‖β?‖2)]
≤ 1 2 ∑ i,j:P (i) 6=P (j) |γ̃?i γ̃?j − γ?i γ?j | · |[Q]ij |+ (M −m)c 2 (υ‖ζ̃?‖2 + ‖β̃?‖2)
≤ U2Q+ U2M(M −m)c, where the first inequality follows from the optimality of ζ̃? and β̃?, and the third inequality is derived by the boundness of ζ,β,γ and υ ≤ 1. Since f(α) is a quadratic function, it can be expanded at α? as
f(α̃?) = f(α?) +∇f(α?)>(α̃? −α?) + (α̃? −α?)>∇2f(α?)(α̃? −α?) ≥ f(α?) + (α̃? −α?)>∇2f(α?)(α̃? −α?)
= f(α?) + (α̃? −α?)> [ Q +McυI −Q −Q Q +McI ] (α̃? −α?)
≥ f(α?) + (α̃? −α?)> [ McυI
McI
] (α̃? −α?)
≥ f(α?) +Mcυ‖α̃? −α?‖2, where the first inequality follows from the first order optimality condition, and the third inequality uses the fact υ ≤ 1. Thus ‖α̃? −α?‖2 can be upper bounded by
‖α̃? −α?‖2 ≤ 1 Mcυ (d(ζ̃?, β̃?)− d(ζ?,β?)) ≤ U 2 Mcυ (Q+M(M −m)c),
which shows that Eqn. (11) holds and concludes the proof.
A.3 PROOF OF THEOREM 2
Theorem 2. For shift-invariant kernel κ with κ(0) = r2, that is ‖φ(x)‖ = r for any x. With the partition strategy described above, for any k ∈ [K], we have
dk(ζk,βk)− d(ζ?,β?) ≤ U2M2c
2 + 2UM + U2M2r2
+ U2r2 cos τ(2Θ−M2) where Θ = ∑ i,j∈[M ],i6=j 1ϕ(xi) 6=ϕ(xj)
Proof. Construct a data set D′k based on partition Dk by repeating each instance K times which appeared in Dk, so that |D′k| = |D| = M . According to our settings, the number of instances in |D′k| belong to the s-th stratum equals to |Cs|. Denote D′k = {(x′i (k) , y′i (k) )}i∈[M ] and guarantee that ϕ(xi) = ϕ(x′i (k) ). Denote the dual form of ODM on D′k as
min ζ′k,β ′ k∈R M +
d′k(ζ ′ k,β ′ k) =
1 2 (ζ′k − β′k)>Q′k(ζ′k − β′k) + Mc 2 (υ‖ζ′k‖2 + ‖β′k‖2)
+ (θ − 1)1>Mζ′k + (θ + 1)1>Mβ′k,
where Q′k = Y ′ kX ′ k > X′kY ′ k, X ′ k = [φ(x ′ 1 (k) ), . . . , φ(x′m (k) )], and Y′k = diag(y ′ 1 (k) , . . . , y′m (k) ). Denote the primal form of ODM on D′k as
min w,ξi, i
p′k(w) = 1 2 ‖w‖2 + λ 2M ∑ i∈[M ] ξ′i 2 + υ ′i 2 (1− θ)2 ,
s.t. 1− θ − ξ′i ≤ y′iw>φ(x′i) ≤ 1 + θ + ′i, ∀i ∈ [M ].
For convenience, let k = 1 so that Dk = {(xi, yi)}i∈[m]. From the primal problem of ODM on Dk, we have
pk(wk) = 1
2 ‖wk‖2 +
λ
2m ∑ i∈[m] ξ2i + υ 2 i (1− θ)2 = 1 2 ‖wk‖2 + λ 2M ∑ i∈[m] K ξ2i + υ 2 i (1− θ)2
= 1
2 ‖wk‖2 +
λ
2M ∑ i∈[M ] ξ′i 2 + υ ′i 2 (1− θ)2 = p′k(wk),
We can infer that the optimal solution of ODM onDk andD′k are the same. Therefore, d′k(ζ′k,β′k) = dk(ζk,βk). According to the definition,
d′k(ζ ′ k,β ′ k)− d(ζ?,β?) =
1 2 (ζ′k − β′k)>Q′k(ζ′k − β′k)− 1 2 (ζ? − β?)>Q(ζ? − β?)
+ Mc
2 (υ‖ζ′k‖2 + ‖β′k‖2 − υ‖ζ?‖2 − ‖β?‖2)
+ (θ − 1)1>M (ζ′k − ζ?) + (θ + 1)1>M (β′k − β?)
= 1
2 ∑ i,j∈[M ] (γ′kiγ ′ kjy ′ i (k) y′j (k) κ(x′i (k) ,x′j (k) )− γ?i γ?j yiyjκ(xi,xj))
+ Mcυ
2 (‖ζ′k‖2 − ‖ζ?‖2) +
Mc
2 (‖β′k‖2 − ‖β?‖2)
+ (θ − 1)1>M (ζ′k − ζ?) + (θ + 1)1>M (β′k − β?) (14)
and−U2 ≤ γ?i γ?j , γ′kiγ ′ kj ≤ U 2, 0 ≤ υ ≤ 1, 0 ≤ θ ≤ 1. Then d′k(ζ′k,β′k)−d(ζ?,β?) can be upper bounded by
d′k(ζ ′ k,β ′ k)− d(ζ?,β?) ≤ U2 ∑ i,j∈[M ] (κ(x′i (k) ,x′j (k) )− κ(xi,xj)) + U2M2c 2 + 2UM (15)
Notice that κ(xi,xj) = 12 (‖φ(xi)‖ 2 + ‖φ(xj)‖2 − ‖φ(xi)− φ(xi)‖2). Sequentially,∑
i,j∈[M ]
(κ(x′i (k) ,x′j (k) )− κ(xi,xj))
= 1
2 ∑ i,j∈[M ] (‖φ(xi)− φ(xj)‖2 − ‖φ(x′i (k) )− φ(x′j (k) )‖2)
= 1
2 ∑ ϕ(xi)6=ϕ(xj) (‖φ(xi)− φ(xj)‖2 − ‖φ(x′i (k) )− φ(x′j (k) )‖2)
+ 1
2 ∑ ϕ(xi)=ϕ(xj) (‖φ(xi)− φ(xj)‖2 − ‖φ(x′i (k) )− φ(x′j (k) )‖2).
For the situation where ϕ(xi) 6= ϕ(xj), the maximal value of ‖φ(xi) − φ(xj)‖2 is 4r2, square of diameter of the ball. The minimal value of ‖φ(xi) − φ(xj)‖2 is 2r2(1 − cos τ) which can be computed by the law of cosines since the angle between φ(xi) and φ(xj) is greater than τ . According to the law of cosines, we can also upper bound ‖φ(xi) − φ(xj)‖2 by 2r2(1 − cos τ) when ϕ(xi) = ϕ(xj). It is obviously that ‖φ(xi)− φ(xj)‖2 ≥ 0, thus∑
i,j∈[M ]
(κ(x′i (k) ,x′j (k) )− κ(xi,xj)) ≤
1
2 ∑ ϕ(xi) 6=ϕ(xj) (4r2 − 2r2(1− cos τ))
+ 1
2 ∑ ϕ(xi)=ϕ(xj) 2r2(1− cos τ). (16)
Substitute Eqn. (16) into Eqn. (15), we can derive the bound
d′k(ζ ′ k,β ′ k)− d(ζ?,β?) ≤ U2 ∑ ϕ(xi) 6=ϕ(xj) ((2r2 − r2(1− cos τ)) + U 2M2c 2
+ ∑
ϕ(xi)=ϕ(xj)
r2(1− cos τ)) + 2UM
≤ U2r2Θ(1 + cos τ) + U2r2(M2 −Θ)(1− cos τ) + U 2M2c
2 + 2UM
= U2M2r2 + U2r2 cos τ(2Θ−M2) + U 2M2c
2 + 2UM

Review summaries:
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.   A Schur complement based strategy for partitioning for the data is presented.  For 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.  However, with non-linear kernels, the proposed methods improves over some baselines.

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. 

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.