Summary
This paper considers the setting of learning an ordering between items according to some scoring rule. The assumption is that this ordering is determined by a contextual scoring rule, determined from the features of each item. Such contextual structure can aid in more rapidly learning an ordering, and generalizing to out of sample items. This ordering is learned from asking pairwise preferences to an oracle, reducing uncertainty about the total order. Since there are a large number of possible comparisons to be asked, active learning is deployed to only query labels for a subset of comparisons. A theoretical argument is made about the optimal balance between aleatoric and epistemic uncertainty to target in adaptive selecting queries, motivating the GURO adaptive sampling strategy and variants. The performance of GURO is demonstrated in several empirical experiments on simulated data and data collected (offline) from real humans.
Strengths
I believe this paper is excellent - it is *clearly* written, has a great flow, and theoretical and empirical arguments are tied together nicely to motivate the problem setting, establish the problem fundamentals, convey mathematical intuition about uncertainty reduction, and justify active selection. There is also a robust set of experiments demonstrating GURO (and variants) in practice against baselines, along with explanatory discussion and implementation details. To my knowledge the analysis and algorithmic ideas here are *original*, and this is a *high quality* submission. Although not the centerpiece of this work, in an age where RLHF and efficiently learning from human preferences is paramount in training large models and ranking queries, work in active preference learning and the contributions made here are *significant*. There is also a robust and thorough appendix providing details and theoretical proofs (disclaimer: I have read the main paper in careful detail, but only skimmed the appendix). Overall, this is elegant, interesting, and impactful work (both theoretically and empirically).
Weaknesses
I do not have any explicit weaknesses to list. Instead, I have a list of comments and questions below that I would like the authors to address. However I feel confident that these can be addressed during the rebuttal phase.
One comment is that there is no discussion (unless I missed it) about computational complexity stating and comparing the big-O computational complexity of GURO, its variants, and other selection methods. This would be an interesting and strengthening addition to this work.
Questions
- I think the statement "Moreover, the set we want to order is often larger than the set of items observed during training—we may want to rank new X-rays in relation to previous ones. This cannot be solved using per-item scores alone." should be clarified. If one knew absolute scores for all items (regardless if they are observed in training), isn't it trivial to compute an ordering? Or did the authors mean that pairwise responses collected during training could not generalize outside of training, without example features to predict from? [Edit: this does seem to be clarified in Section 2, but should be made more clear in the introduction]
- I find the sentence "However, as we show in Section 4, learning this map to recover a complete ordering is distinct from the general preference learning setting, and existing algorithms lack theoretical justification for this application" to be vague and should be clarified. What exactly is the "general preference learning setting", versus learning a map to recover complete orderings? What does "this application" refer to? Which of these two settings are you concerned with here?
- I'm confused by line 159. Why can one lower bound $\Delta_{ij}$ by a factor depending on the index difference $\lvert i -j \rvert$? Aren't the indices arbitrary, and agnostic to the underlying geometry of the feature space? Does this mean that a simple index permutation would drastically change this $\Delta$ quantity?
- in line 166, should the dependence not be on $\theta_T$ rather than $\theta_*$?. See line 157 which uses $\theta_T$. line 169 also jumps back to $\theta_T$
- line 189 is missing an important point: by definition the entirety of $\mathcal{I}$ is unavailable, only $\mathcal{I}_D$ is available to select from. This should be commented on.
- I think line 198 is too vague: "As θt converges to θ∗, this pair becomes representative of the maximizer of (4) provided there is no major systematic discrepancy between ID and I." Can you comment more on what constitutes acceptable vs unacceptable discrepancies between I and I_D? This does bring up a problematic point: what if $I_D$ is not sufficiently representative of $I$? Line 215 starts to hint at this discussion but I think it needs to be elaborated on, ideally more formally
- in GURO Hybrid, how are these $\zeta_i$ parameters actually learned? Is it just a joint MLE on $\theta$ and $\zeta_i$? In this case, what prevents the model from learning an arbitrary $\theta$ (i.e., $\theta = 0$) and just using the full expressivity of $\zeta_i$? Is there some sort of regularization in practice?
- for completeness, can you include a figure in the Appendix showing the experiment in Fig 1b, but just plotting $R_{I_D}$ instead of the difference? It would be good to know how each algorithm does in an absolute sense on $I_D$
- figure 2 would benefit from a log y scale - it is very difficult to discern between methods
Minor:
- line 147 uses the notation $\widehat{H}$ instead of $\widetilde{H}$. I assume this is a typo
- missing left parentheses in line 5 of GURO algorithm
- the word BayesGURO in Algorithm 1 should also probably be colored green to show the association to (7) and (11)
- be careful with red and green as distinguishing colors for readers with color vision deficiency
- fix quotes on line 258