Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: The paper develops a method to learn a binary classifier based only on pairwise comparison data. For example, the classifier learns to classify pictures of people as "adult" versus "child" based on pairwise comparisons of the form "person C is older than person X". The authors derive their method based on an empirical risk minimization argument. The authors test their methods on four standard data sets (three MNIST variants and one more). They compare to some baselines including binary biased, noisy unbiased, and RankPruning. They try 4 different variations of their method. The Pcomp-Teacher model performs especially well.

The paper develops some interesting ideas, but the main problem is that the authors say that their pairwise comparison (Pcomp) classification is novel, but it is not. For example, see this blog post: https://blog.ml.cmu.edu/2019/03/29/building-machine-learning-models-via-comparisons/

And this paper:

Noise-tolerant interactive learning using pairwise comparisons.
Yichong Xu, Hongyang Zhang, Kyle Miller, Aarti Singh, Artur W Dubrawski. NIPS'17: Proceedings of the 31st International Conference on Neural Information Processing Systems December 2017 Pages 2428–2437
https://dl.acm.org/doi/10.5555/3294996.3295004

As the blog post points out, learning to rank is very related and there are hundreds of papers on learning to rank.

Usually pairwise comparisons are motivated as easier for people to do (lower cost labels to obtain). For example, it's easier to tell if one person is older than another than to guess the age of a person. The authors motivate pairwise comparison differently. They say it is better for privacy. Why are pairwise comparisons better for privacy? Given enough pairwise comparisons, the original order can be uncovered, so there are limits to the privacy advantage that the authors don't discuss. In general, the privacy motivation needs to be more clear.

Pairwise can sometimes be harder to judge than pointwise, for example which of two pictures of a cat is "more" cat than the other? Or which of two laptop computers is "more cat-like" than the other?

The authors must get some small amount of pointwise data, or they have some assumption that I missed, like the base label frequencies are known. For example, what if we try to learn a dog/cat classifier using pairwise comparisons that are 100% cats? How can the classifier possibly know that all the images are cats without *some* pointwise labels? All we know from pairwise comparisons is which cat is the most and least dog-like. There is no way to know how to draw the line without some pointwise labels or other modeling assumption. The blog post above discusses this.
review_title: problem is not novel

final_score: rating: 7: Good paper, accept
review_content: Authors addressed the problem of 'Pcomp', a weakly supervised binary classification setting where the dataset only includes pairs of unlabeled data with an indicator of which one is more likely to be positive than the other (unlike pointwise labeled data in classical binary classification). The setting could be useful in privacy-preserving applications.

Authors proposed a generative model for pairwise data comparison, for which unbiased risk estimators could be obtained, and this crucially helps them to obtain a theoretical bound on the empirical risk minimizer.

I have a slight concern about the practicability of the assumed comparison model (Sec 3) which only provides examples like (+1+1), (+1,-1), (-1,-1)? The theoretical proof does not go through without unbiased risk estimators, which in this is obtainable because of Thm 1 and 2, but these are very specific to the above assumption on the generative model? But I think it is an okay assumption and the bare minimum for any practical purpose.
  
Also, can you comment on the tightness of the current bound say Thm. 4 in terms of n (for this specific generative model).

Overall I found the paper is easy to understand and well structured. 

Two interesting follow-up questions:
- It would interesting if the authors can add some comments about the possibility of extending the work to a multiclass classification setting.
- Another interesting direction could be to understand the performance limits for the case where instead of two the learner is allowed to see the relative class probabilities of a larger subset of items. Is the current method directly extendable to such a setting and how do we expect to see the estimation error bound varying with the subsetsize?
review_title: Well motivated problem formulation with theoretical performance guarantees and extensive simulation results -- vote for accept.

final_score: rating: 5: Marginally below acceptance threshold
review_content: Summary of the paper: 
The paper studies binary classification with pairwise comparisons as the supervision. Instead of the traditional pointwise supervision, the paper assumes only access to pairs of examples $x,x'$ where we believe that $p(y=1|x)\geq p(y=1|x')$. The authors considers two kinds of methods. The first one considers x, x' be sampled from two different distributions, and uses the method from Unlabeled-Unlabeled (UU) classification to obtain an unbiased risk estimator. The second one is the RankPruning method, where a fraction of data with highest confidence is selected and is used to derive a URE on the selected samples. The paper proposes to add a moving-average regularization to RankPruning. The authors performed experiments on 2-class versions of standard benchmark datasets. In general RankPruning with regularization performs the best in most cases, but the first method is also competitive.

Review: 
The paper studies an important problem of learning classification from pairwise comparisons. I have some doubts though:
	a) The paper assumes a generative process of the pairs: Generally, it assumes a rejecting sampling process. If we sample $(x,x')$ with $y=-1,y'=+1$, then we reject it; otherwise we keep it. Why is this correct? Do we have data supporting this process? I may suggest other models: E.g., return $(x',x)$ if $y=-1,y'=+1$, and $(x,x')$ otherwise. Is this also plausible? How can we test what generation method is used?
	b) Another bigger problem is that the method ignores the PAIR nature of the problem; the method basically ignores the pairs and just treat list of $x, x'$ as from different distributions. We naturally loses the information that $p(y=1|x)\geq p(y=1|x')$. Is this a good method? Can we use other methods to utilize the pair information, such as siamese networks? How does the performance compare?
	c) In general the paper lacks a bit novelty - the first method is an adaptation of UU estimator, and the second method is just adding a regularization to RankPruning.

Minor Comments:
	a) Second paragraph in Sec 3 - the paragraph is a bit unclear to me. Can you state the generation process formally?
	b) Classification with pairwise comparisons is also considered in these works:
	Xu, Y., Zhang, H., Miller, K., Singh, A., and Dubrawski, A. Noise-tolerant interactive learning from pairwise comparisons with near-minimal label complexity. NIPS2017.
	D. M. Kane, S. Lovett, S. Moran, and J. Zhang. Active classification with comparison queries. FOCS 2017.
Both papers use a small amount of labeled data; but they considers the pair information.
review_title: Is the proposed method good enough?

Meta-review: This paper has been evaluated  by three expert reviewers, two of whom recommended rejection and one acceptance. Two of the three reviews are particularly detailed and thorough. Both point out a few points of conceptual issues that leave the reader confused. These key issues have not been addressed sufficiently in the rebuttal to result in changing the reviewers' assessments. One major concern is lacking novelty of the work as presented, which limits its current utility to the ICLR audience. I recommend a rejection.
Decision: Reject