Venue: UAI 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area of AI or moderate to high impact on more than one area of AI, with good to excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations. 
review_content: Q1 Summary and contributions: 1. This paper theoretically shows that knowing all label comparisons does not result in improvement to the sample complexity in the passive learning regime.

2. A new active query approach based on label neighborhood graph is proposed for active learning with label comparisons.

3. This paper shows that label-comparison-based query approach can improve the query complexity from both theoretical and empirical perspectives.
Q3 Main strengths: 1. The problem studied in this paper is very interesting. As the authors mentioned, query from all classes is difficult even impossible when the number of classes is large, yet querying the label comparisons is a very natural alternative strategy in real-world tasks.

2. This paper shows that although learning from label comparisons does not benefit the sample complexity in the passive learning, label-comparison-based query can improve the query complexity in active learning setting from both theoretical and empirical perspectives.
Q4 Main weakness: 1. Empirical analysis on passive learning with label comparisons could be conducted to support the results in Section 4.

2. For active tournament algorithm, a label pair would be selected if the current model is "sufficiently" confident. How does the confidence be measured? 

3. In figure 3, it seems that when d=7, the gap between the sparsity levels of empirical neighborhood graph and true neighborhood graph is larger. Figure 4 only shows the results with d=5. What about the accuracy comparison when d=7? 
Q5 Detailed comments to the authors: This paper considers the active learning setting in which label pairs (instead of max labels) are queried for manual annotation. The authors offer an approach based on label neighborhood graph and shows it improves the query complexity compared with regular active learning from both theoretical and empirical perspectives. The studied problem is very interesting and the proposed approach is technically sound. 

As I mentioned in Q4, more empirical analyses, including the performance comparison in passive learning and comparisons with varied d, could be further conducted. 

Q2(4) Quality of experiments (Optional): 3: Good: The experimental evaluation is adequate, and the results convincingly support the main claims.
Q7 Justification for your score: The authors proposed a new active learning approach based on label comparisons and showed it improves the query complexity compared with regular active learning from both theoretical and empirical perspectives. The query setting studied in this paper is realistic. The proposed approach is technically sound.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., lack of novelty, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: Q1 Summary and contributions: The paper studies an active learning setting where annotators are meant to provide pairwise label comparisons. It is quite reasonable to assume this is cognitively less demanding compared to providing all labels and asking the annotators to provide the argmax.
Q3 Main strengths: It’s great to see a combination of theoretical and experimental evaluation and also good that the latter supports the former. Also there are both synthetic and real data and they seem to follow the same trend. 
Q4 Main weakness: My main concern is the actionability of the results and their significance. Basically the takeaway message is that in passive learning setting  there are cases for which having all the class comparisons for a data point does not necessarily yield an advantage over receiving the argmax. On the contrary, in active learning setting in some cases comparisons are more effective than argmax. My main question is the following: I have a classification problem in hand that I require labels for. How do I use the current finding to choose what’s the best way forward? I create a neighbourhood graph and check it’s sparsity? Or there are other guidelines?
Q5 Detailed comments to the authors: - The evaluation has a theoretical part and an experimental part. The proofs for technical part are included. There is not much details on the experimental part though. They wouldn’t be reproducible given the level of details currently given.
- The Introduction and related work are quite clearly written, but the rest is very hard to follow. Figures are not necessarily close to their description. Algorithms are referenced in the text as a whole, without a line by line clear cut descriptions. Some proofs include few definitions within them, which makes it very hard to follow. 

The work needs to be motivated better. The use cases of the findings need to be outlined better. What happens if labels are required? It would strengthen the message of the paper is some systematic guidelines were generated from the findings that address all applicable scenarios.
Q2(4) Quality of experiments (Optional): 3: Good: The experimental evaluation is adequate, and the results convincingly support the main claims.
Q7 Justification for your score: While there are some original ideas, I struggle to see how this can be used in practice. Clarifying that would be a huge help for the significance and a good improvement overall.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate to high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations. 
review_content: Q1 Summary and contributions: This paper considers the active learning setting where human annotators are provided with label comparisons instead of an overall ground-truth label. Their first result shows that in the PAC setting knowing all ${k \choose 2}$ combinations has the same complexity as knowing the $\argmax$ of the labels. They also prove the sample complexity for the pool-based active learning setting. They propose a new graph-based active algorithm NbrGraphSGD(G) and evaluate it empirically.
Q3 Main strengths: 1) They show in Theorem 4.3 that in the 1D setting the $\arg\max$ oracle has the same complexity as the label comparison oracle. Similarly, they show in Theorem 5.2 for the active pool-based setting, that the sample complexity of label comparison is actually smaller than the lower bound for the sample complexity for the $\arg\max$ oracle. Again the result only holds for $d=1$.

2) They propose a new graph-based active learning algorithm NbrGraphSGD(G) that uses this label comparison by building neighborhood graphs.

3) They experiment in synthetic and real-dataset against a few benchmarks.
Q4 Main weakness: 1) Their first main result entirely depends on the 1-dimensional case. It is not clear to me what will happen in a large, or sparse dimensional setting. We surely do not hope that even in these large dimensions the most informative samples lie close to the decision boundary. Some comment on this will be helpful.

2) I am not sure that the discussion after Definition 2 for the pool-based setting is true: *Every active learning algorithm that uses argmax queries can always be simulated using comparison queries*. What happens to a core-set based approach (Sener and Savarese, 2017). In that case, choosing samples from your unlabelled pool that maximally covers it using minimum samples and asking for their label comparisons will take far more sample complexity than just choosing samples based on their uncertainty score.
Q5 Detailed comments to the authors: See 1), 2) from Q4.

3) What does the $O^{\tilde}$ hide in the result of Theorem 5.2. Also, is Algorithm 2 (used for proving Theorem 5.2) only hold for $d=1$? If yes, then how do you use it for NbrGraphSGD(G)? The NbrGraphSGD requires the neighborhood graph $G$ as input, and do you use Algorithm 2 to construct it? 

4) The baselines chosen for the experimental setting seem to be inadequate. For the pool-based setting, a lot of recent advances have been made for active learning algorithms. At least for the real-dataset, I suggest experimenting against BALD, Coreset, Badge, etc. Note that in section 6 you state that $h$ can also be a neural network. So I do not see any reason not to test against Badge?


Q2(4) Quality of experiments (Optional): 2: Fair: The experimental evaluation is weak: important baselines are missing, or the results do not adequately support the main claims.
Q7 Justification for your score: Refer to Q3, Q4, Q5. If the authors answer my queries sufficiently in Q4, Q5, I am willing to raise my scores.
review_title: null

Meta-review: Meta Review: Generally, the idea of querying the label comparisons to is an interesting and natural choice to enable active learning in real-world tasks. Both theoretical analyses and empirical studies have been reported in this paper. The whole paper is well organized and easy to follow.

The expeirmental studies performed in this paper can be improved, such as considering performance comparison in passive learning, the inclusion of more SOTA baselines, etc.
Decision: Accept (Poster)