Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: 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.
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_review: The problem seems quite similar to the standard SVMs and a new distributed solver for the problem looks not significantly new.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: 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.

 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.
main_review: strengths:
1.  Result in theorem 1 seems useful as the bound depends on m.
2. Result in theorem 2 is indeed helpful in motivating the intuitive landmark selection strategy.
3. Improvements in fig2 seem encouraging.

Critical comments:
1. 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. 

2. The tree structured based parallel strategy has limited novelty as such ideas are popular among parallel methods.

3. 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.

4. 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.

5. Since the solver runs with entire data too, and the problem is convex, convergence is anyway guaranteed.

6. 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.

7. Section 3.3 is repetition of Lee et.al, 17 and hence can go into background/related work.

8. 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. 

9. Since acc-DiODM is Lee et.al.'17, the section 4.2 may be postponed to appendix.

10. It is not clear what  the baselines in figure 3 are. Again this makes evaluation of simulations section difficult.

11. 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_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.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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. 
main_review: 
Strengths:
Overall, 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. 

Weaknesses:

Despite many strengths, there are a few issues with the paper as I explain below:

(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. 

(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?  

(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. 

(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? 









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.
review_title: null

final_score: rating: 8: accept, good paper
review_content: 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.
main_review: Pros
1.	The paper proposes a novel partition strategy for training kernel method in distributed scenario, leading to nearly ten times speedup.
2.	The paper is thorough and accomplished. Both linear and nonlinear kernels are fully considered. Both theoretical analyses and empirical studies are clearly presented.
3.	The experiments are conducted on data sets obtained from public repositories and necessary links to the readers are given.

Questions during rebuttal period: 
Many 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?

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.
The 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.
review_title: null

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