Comparing Few to Rank Many: Active Human Preference Learning Using Randomized Frank-Wolfe Method

We want to thank the reviewer for a positive review, and recognizing both benefits and shortcomings of our paper. Our rebuttal is below. We will incorporate all comments of the reviewer in the next version of our paper. If you have additional concerns, please reach out to us to discuss them.

We agree with the reviewer that LLM experiments would increase the appeal of the paper. However, we could not conduct them due to limited computational resources. To further support our claims and partially address your comment, we contacted Mukherjee et al. (2024) and implemented DopeWolfe on the Anthropic RLHF dataset in their paper. The plot of the experiment is at Anthropic plot. We observe that the ranking losses of DopeWolfe and Dope are comparable. This means that DopeWolfe beats all baselines in Mukherjee et al. (2024). However, in terms of the wall-clock time, DopeWolfe is about $4$x times faster than Dope ($6.046$ seconds on average versus $24.924$). See Section Additional Baselines of the rebuttal to Reviewer Z4RR for more details.

We want to thank the reviewer for acknowledging the contributions of our work and putting it in the context of prior works. Our rebuttal is below. We focus on major issues and will incorporate all comments of the reviewer in the next version of our paper. If you have additional concerns, please reach out to us to discuss them.

We Do Not Handle Multiple Lists

This is a writing issue. We sketch how to represent multiple lists in the last paragraph of Section 2. However, we failed to explicitly state that the algorithm remains unchanged when solving such problems. This is because it does not matter how the plausible subsets of items in DopeWolfe arise. They can be $K$-subsets of a single list or multiple.

In fact, we already conducted an experiment like this in our paper. The Nectar dataset in Section 6.1 has $30000$ lists, each with $7$ choices. For $K$-way comparisons, we optimize over $30000 {7 \choose K}$ subsets of items. This is what $K = 2$ and $K = 3$ in Figure 1 are. Even for $K = 2$, this is $630000$ subsets and two orders of magnitude more than in Mukherjee et al. (2024). We describe this in lines 949-953 (Appendix D.1).

Additional Baselines

To alleviate your concerns about the lack of comparison to Dope and baselines in Mukherjee et al. (2024), we contacted Mukherjee et al. (2024) and obtained their code. The code differs from their paper as follows:

• Dope is implemented using the Frank-Wolfe method where the linear maximization oracle (LMO) is a linear program.
• The Nectar experiment is on $500$ lists. The code crashes for $2000$ lists used in Mukherjee et al. (2024) and they did not resolve this issue before we submitted this rebuttal.

We implemented DopeWolfe in their code base as follows:

• LMO is solved greedily, as in (8), on 10% of randomly sampled subsets of items.
• Line search is implemented using golden-section search.

The plots for the Anthropic and Nectar experiments are at Anthropic plot and Nectar plot, respectively. We observe that the ranking losses of DopeWolfe and Dope are comparable. This means that DopeWolfe beats all baselines in Mukherjee et al. (2024). However, there is a difference in the wall-clock time:

• Anthropic: DopeWolfe is about $4$x times faster than Dope ($6.046$ seconds on average versus $24.924$).
• Nectar: DopeWolfe is about $3$x times faster than Dope ($0.571$ seconds on average versus $1.826$).

We want to thank the reviewer for a positive review that discusses both the new aspects of our work and potential shortcomings. Our rebuttal is below. We focus on major issues and will incorporate all comments of the reviewer in the next version of our paper. If you have additional concerns, please reach out to us to discuss them.

Empirical Concern in Claim 1

We acknowledge that the setting of real feedback is potentially more challenging because the optimized model is misspecified (unrealizable). However, we do not think that Figure 2 shows significantly worse results than Figure 1. First, note that the figures are plotted differently: all plots in Figure 1 are functions of a sample size for fixed $K$, while Figure 2 is a function of $K$ for a fixed sample size ($500$ in TREC-DL, for instance). Therefore, they are not comparable. Second, the corresponding experiments use different embeddings. Given all the differences, the relative difference in ranking losses of Uniform and DopeWolfe in the same plot is one natural metric. This is consistently 20% in Figure 2 and similar to many relative differences in Figure 1.

Theory Concern in Claim 2

Thank you for understanding the computational feasibility perspective that we tried to convey in the last two paragraphs of Section 5. We reiterate that DopeWolfe was designed to address the concern that the naive implementation of Dope is infeasible even for small problems (Section 4).

Ensuring Assumption 1 During MLE

We can ensure $\|\|\hat{\theta}\|\|_2 \leq 1$ during MLE as follows. First, note that $\Theta = \\{\theta \in \mathbb{R}^d: \|\|\theta\|\|_2 \leq 1\\}$ is a convex set. Second, the MLE in (3) is a convex optimization problem. Therefore, we can minimize (3) on $\Theta$ using gradient descent with a projection step to $\Theta$.

Additive $d$ in Proposition 2

The additive $d$ in Mukherjee et al. (2024) arises at the end of the proof of Theorem 6 (Appendix A.6), because a high-probability upper bound on the model parameter error is $O(d + \log(1 / \delta))$. See their Lemma 9 (Appendix B) for the statement and proof of the bound.

We want to thank the reviewer for detailed feedback, and recognizing that we solved the problem that we set out to solve well. Our rebuttal is below. We focus on major issues and will incorporate all comments of the reviewer in the next version of our paper. If you have additional concerns, please reach out to us to discuss them.

Practical Motivation

$K$-wise comparisons naturally arise in many large-scale systems. For instance, online marketplaces frequently display a handful of items selected from a catalogue of billions of items to a user, and the user’s choice among those items can be viewed as a noisy ranking observation. These real-world interactions are well-modeled by the Plackett–Luce model used in our work (Negahban et al., 2018; Buchholz et al., 2022).

Recent developments in reinforcement learning with human feedback (RLHF) also suggest that relative feedback can yield better alignment than absolute feedback (Christiano et al., 2017; Bai et al., 2022). It has also been shown that comparisons on longer lists ($K > 2$) can improve downstream reward models (Zhu et al., 2023b; Liu et al., 2024). This is one motivation for collecting the Nectar dataset used in Mukherjee et al. (2024).

Absolute Versus Relative Feedback

We acknowledge the concern that repeated $K$-wise comparisons may become costly. However, it is known that absolute feedback has its shortcomings as well (Shah et al., 2014). First, annotators often exhibit variable calibration when assigning absolute scores, making cross-annotator aggregation difficult. Second, comparison of items is often more natural and faster for humans. Finally, often we only have access to proxy signals (ad clicks or video watch time), which have an approximately monotonic relation to the real preference. A relative comparison requires only ordering rather than judging the precise value, mitigating calibration and proxy issues. Ultimately, whether the absolute or relative feedback is used is a design choice, and we believe that both should be studied.

Data and Setup Concerns

We would like to clarify that our Nectar experiment is not small scale. The dataset has $30000$ lists, each with $7$ choices. For $K$-way comparisons, we optimize over $30000 {7 \choose K}$ subsets of items. Even for $K = 2$, this is $630000$ subsets and two orders of magnitude more than in Mukherjee et al. (2024). We describe this in lines 949-953 (Appendix D.1).

Additional Baselines

To alleviate your concerns about the lack of comparison to Dope and baselines in Mukherjee et al. (2024), we contacted Mukherjee et al. (2024) and obtained their code. The code differs from their paper as follows:

• Dope is implemented using the Frank-Wolfe method where the linear maximization oracle (LMO) is a linear program.
• The Nectar experiment is on $500$ lists. The code crashes for $2000$ lists used in Mukherjee et al. (2024) and they did not resolve this issue before we submitted this rebuttal.

We implemented DopeWolfe in their code base as follows:

• LMO is solved greedily, as in (8), on 10% of randomly sampled subsets of items.
• Line search is implemented using golden-section search.

The plots for the Anthropic and Nectar experiments are at Anthropic plot and Nectar plot, respectively. We observe that the ranking losses of DopeWolfe and Dope are comparable. This means that DopeWolfe beats all baselines in Mukherjee et al. (2024). However, there is a difference in the wall-clock time:

• Anthropic: DopeWolfe is about $4$x times faster than Dope ($6.046$ seconds on average versus $24.924$).
• Nectar: DopeWolfe is about $3$x times faster than Dope ($0.571$ seconds on average versus $1.826$).

Note that both Anthropic and Nectar are well-established RLHF datasets.