Paper ID: 1327
Title: Controlling the distance to a Kemeny consensus without computing it

Review #1
=====
Summary of the paper (Summarize the main claims/contributions of the paper.): N.A.

Clarity - Justification: N.A.

Significance - Justification: N.A.

Detailed comments. (Explain the basis for your ratings while providing constructive feedback.): Finding Kemeny consensus is NP-hard. This paper, by utilizing the geometric properties of the Kemeny embedding, proposes a theorem that bounds the Kendal distance of a given ranking to the Kemeny consensus. The bound is tight and the corresponding algorithm is quadratic w.r.t. the items to be ranked and linear w.r.t. the number of rankings. I am inclined to accept this paper, given its novel use of the Kemeny embedding.   Below are more comments/questions.  It is known that Kendall and Spearman distances have the following relation (due to Diaconis), 1/\sqrt{n} D_k <= D_s <= 2 D_k. Since (1) the bound is also tight and (2) the minimum of the sum of Spearman can be obtained by Borda count, why would one use the proposed approach, given the fact that the alternative is much more efficient? Moreover, since both bounds are tight, I think it should be easy (and interesting) to establish some relationship.  Line 128. What is the quantity after sigma?  Reference. If abbreviation of an author’s name is used, please be consistent: Diaconis, P. vs. Diaconis, Persi. 

=====

Review #2
=====
Summary of the paper (Summarize the main claims/contributions of the paper.): The authors studied the problem of rank aggregation with Kemény criterion. Their main result is an upper bound for the distance between the Kemény optimal ranking and an arbitrary ranking without computing the optimal ranking. The upper bound is based on a very nice geometrical interpretation of the Kemény problem. The upper bound is given in terms of the angle between the vector representation of the permutation of interest and the average of the vector representation of the data. The theoretical findings are supported by experiments on synthetic and real world datasets. 

Clarity - Justification: The paper is mainly easy-to-follow and well-written. But it should be polished at some places, see comments.

Significance - Justification: The upper bound presented in the paper seems to be an interesting result and this result potentially attracts significant research attention from the machine learning community. 

Detailed comments. (Explain the basis for your ratings while providing constructive feedback.): In Theorem 1, it might be more consistent to write \ge instead of >. Because if the data \mathcal{D}_N consists of the replicates of a single ranking, then this Theorem will not be true.    Regarding Table 1: some voting rules which was included in the test are randomized, such as QuickSort, Pick a perm. How was k_min computed for them. Was their inner randomization taken into account?  What is R in line 411? Is it the radius of S? Then R = \sqrt{\frac{n(n-1)}{2}}. Is this true?  In the experiments, the tightness of the bound was tested experimentally. It would be interesting to compute the  worst-case tightness of the bound. Do the authors have any idea how this could be done?   Regarding the experiments:  -- The Plackett-Luce ranking aggregation does mean fitting a model and then sort the items based on their skill parameters? -- The experiments are carried out only for very small n \le 5. Of course the Kemény problem is NP-hard thus n cannot be too big. But I think this results does not tell too much about the tightness of the bound. It would be more interesting to investigate the worst case behaviour of the bound. Or to analyse this bound along with some method under some probabilistic assumption.     Minor comments:  It is written more than once that ``the proof is straightforward and left to the reader''. This is not a textbook. I think such a phrase should not be used in a conference paper.  Line 775: 4 -> Figure 4

=====

Review #3
=====
Summary of the paper (Summarize the main claims/contributions of the paper.): The paper presents a tractable upper bound of the Kemeny distance (the number of pairwise mismatches between two permutations or orderings) between a permutation and the Kemeny consensus of a set of ordering data which is NP-hard to find. The upper bound is based on geometry of Kemeny embeddings proposed by Zwicker 2008 et al. Basically it says that if the angle between the permutation and the mean Kemeny embeddings of ordering dataset is small enough, then the Kemeny distance between the permutation and the Kemeny consensus of data is upper bounded by the quantity given in Theorem 1. Such a result gives a new geometric way to understand the ranking data, which up to my knowledge has never appeared in machine learning literature. Potentially it might be helpful to inspire new algorithms based on such an observation.  

Clarity - Justification: The idea is well presented and the logic flow is clear.

Significance - Justification: The introduction of Zwicker's geometric perspective on Kemeny aggregation has not appeared in machine learning society up to my knowledge. The provable upper bound via mean Kemeny embedding is novel and shows an example of its potential applications which might lead to new algorithms in machine learning. In this sense, the paper presents a novel idea which is substantially distinct to existing methods. 

Detailed comments. (Explain the basis for your ratings while providing constructive feedback.): Can you extend Kemeny embedding to partial orders? Partial orders, like pairwise comparison data with incomplete pairs, are ubiquitous for crowdsourced ranking. Current version of Kemeny embedding is for complete order only. It there an extension to partial orders? It would be good to comment on this. 

=====