Comparing Few to Rank Many: Active Human Preference Learning Using Randomized Frank-Wolfe Method
Authors: Kiran Koshy Thekumparampil
Gaurush Hiranandani
Kousha Kalantari
Shoham Sabach
Branislav Kveton
Venue: ICML 2025 poster (2025)
Keywords: active learning
human preference learning
comparison feedback
optimal design
Frank-Wolfe method
Primary area: general_machine_learning->online_learning_active_learning_and_bandits
TL;DR: We propose an efficient active learning algorithm for learning human preferences from K-way comparison of a large number of choices.

Abstract: We study learning human preferences from limited comparison feedback, a core machine learning problem that is at the center of reinforcement learning from human feedback (RLHF). We formulate the problem as learning a Plackett-Luce (PL) model from a limited number of $K$-subset comparisons over a universe of $N$ items, where typically $K \ll N$. Our objective is to select the $K$-subsets such that all items can be ranked with minimal mistakes within the budget. We solve the problem using the D-optimal design, which minimizes the worst-case ranking loss under the estimated PL model. All known algorithms for this problem are computationally infeasible in our setting because we consider exponentially many subsets in $K$. To address this challenge, we propose a randomized Frank-Wolfe algorithm with memoization and sparse updates that has a low $O(N^2 + K^2)$ per-iteration complexity. We analyze it and demonstrate its empirical superiority on synthetic and open-source NLP datasets.

Comparing Few to Rank Many: Active Human Preference Learning Using Randomized Frank-Wolfe Method
Kiran Thekumparampil Gaurush Hiranandani
Kousha Kalantari
Shoham Sabach 13 Branislav Kveton +
Abstract
These real-world interactions are well-modeled by prefer- ence models studied in this work (Negahban et al., 2018). Finally, in reinforcement learning from human feedback (RLHFF) (Ouyang et al., 2022; Rafailov et al., 2023), human feedback is used to learn a reward model, which is then used to align a large-language model (L.LM) with human prefer- ences. In this case, the items are LLM responses and the relative feedback is used because it yields better alignment than absolute feedback (Christiano et al., 2017; Bai et al., 2022). A comparison of more than two responses has been investigated because it is practical and improves statistical efficiency (Zhu et al., 2023b; Mukherjee et al., 2024).
We study learning human preferences from lim- ited comparison feedback, a core machine learn- ing problem that is at the center of reinforcement learning from human feedback (RIHF). We for- mulate the problem as learning a Plackett-Luce (PL) model from a limited number of K-subset comparisons over universe of N items, where typically K < N. Our objective is to select the K-subsets such that all items can be ranked with minimal mistakes within the budget. We solve the problem using the D-optimal design, which minimizes the worst-case ranking loss under the estimated PI. model. All known algorithms for this problem are computationally infeasible in our setting because consider exponentially many subsets in K. To address this challenge, we pro- pose randomized
We formulate the problem as learning to rank N items, such as web pages or LLM responses, from a limited K K-way feedback. In general, K < N because humans cannot pro- vide high-quality preferential feedback of choices (Tversky & Kahneman, 1974). When K = 2, we get a relative feedback over two responses, known as the Bradley- Terry-Lurr (BTL) model (Bradley & Terry, 1952). When K 2 2, we get ranking feedback over K responses, known as the Plackett- (PL) model (Plackett, 1975; Luce, 2005). To learn high-quality preference models, we ask humans questions that maximize information gain. Such problems have long been studied in the field of optimal de- sign (Kiefer & Wolfowitz, 1960; Pukelsheim, 2006). An optimal design is a feedback collection policy that mini- mizes the uncertainty in the downstream learning task. This policy can be learned by iterative algorithms, such as the Frank-Wold (FW) method (Khachiyan, 1996). The main challenge of our setting is that these algorithms are im- practical when K < N, since we need to optimize over exponentially-man O((x)) K-subsets. In this work, we focus on solving large-scale optimal designs with trillions of potential choices for K K-way feedback. We make the following contributions:
large number
Wolfe algorithm with memoization and sparse updates that has a low O + K2) per-iteration complexity. We ana- lyze it and demonstrate its empirical superiority on synthetic and open-source NLP datasets.
1. Introduction
Learning to rank from human feedback is a fundamental machine learning problem. We consider the setting where a larger set of N items is ranked based on feedback on its K-subsets. This setting has various practical applications. In web search (Agichtein et al., 2006; Hofmann et al., 2013; 2016), the items are retrieved web pages for given query and they are rated by human annotators. Since this task is time consuming, the annotators typically label only a subset of the web pages (Hofmann et al., 2013; MS MARCO).
Online marketplaces display only handful of items from a catalogue of billions of items a user and the user's choice among them can be viewed as noisy ranking observation.
(1) We propose general optimal design framework for collecting human feedback to learn to rank N items from K-way feedback (Sections 2 and 3), where K < N. This generalizes known frameworks (Mukherjee et al., 2024; Mehta et al., 2023; Das et al., 2024) that assume K = N.
1 Amazon 'Typeface TTechnion' 4 'Adobe Research. Correspon- dence to: Kiran Thekumparampil Akkt@amazon.com
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
(2) We bound the prediction error and ranking loss of the PL model learned from human feedback (Section 3.3). Both

---

Comparing Few to Rank Many: Active Human Preference Learning Using Randomized Frank-Wolfe Method
decrease as the amount of feedback increases.
7T E Eies ((i) 1. For any positive-definite matrix A E Rdddd and vector x E IRd, let || Vz Az. We say that a square matrix M E Rd is PSD PD if it is positive semi-definite / positive definite.
(3) We propose novel algorithm DopeWolfe for solving our optimal design efficiently (Section 5). DopeWolfe fe has a low O + K²) per-iteration complexity. In contrast, the per-iteration complexity of the FW method is ((k))) We achieve this with the help of a randomized FW method (Zhao & Freund, 2023), combined with memoization and sparse operations.
We study the problem of learning to rank N items. An item k E [N] is represented by its feature vector 3hg X, where X' C Rd is the support of all feature vectors. The relevance of item A: is defined as x O.. where 0, E R is an unknown parameter, and we call it the mean reward. Linear models of relevance have a long history in learning to rank (Zong et al., 2016; Li et al., 2016). A standard way of applying them to modern machine learning problems is to set dig to the last hidden-layer embedding of the neural network (Riquelme et al., 2018). Our experiments in Section 6 are with such embeddings. Without loss of generality, we assume that the original order of the items is optimal, z] 0_ > 2 O2 for any < k.
(4) We provide a convergence analysis for DopeWolfe by generalizing the analysis of the randomized FW method be- yond Lipschitz smoothness (Kerdreux et al., 2018) to gen- eral class of logarithmically homogeneous self concordant barrier (LHSCB) objectives (Theorem 3 and Corollary 4).
(5) We empirically evaluate DopeWolfe on both synthetic and real-world problems (Section 6). We observe an order of magnitude reduction in sample size in our experiments on the Nectar dataset (Zhu et al., 2023a).
We interact with a human T times. In interaction & E (T), we select a K-subset of items Se E S and the human ranks all items in Se according to their preferences, where S is collection of all K K-subsets of [N]. Note that [S] (N)
Our real-world datasets cover reward modeling in RLHF and learning to rank. However, we stress that all our ex- periments are on linear models over frozen language model embeddings instead of fine-tuning LLMs. In this way, we stay faithful to the Plackett-Luce model that we study.
(k)
We represent the ranking as a permutation oz [K] - St. where (k)) is the item at position k. The probability that this permutation is generated is
Related work. There are two lines of related works: learn- ing to rank from human feedback and solving large-scale optimal designs. Mchta et al. (2023) and Das et al. (2024) learn to rank pairs of items from pairwise feedback. They optimize the maximum gap. Mukherjee et al. (2024) learn to rank lists of K items from K K-way feedback. They optimize both the maximum prediction error and ranking loss. We propose general framework for learning to rank N items from K- K-way feedback, where K 2 2 and N 2 K. This setting is more general than in the prior works. Our main algorithmic contribution is a randomized Frank-Wolf algo- rithm. It addresses a specific computational problem of our setting, solving a D-optimal design with ((())) ) variables for learning to rank. This distinguishes it from other recent works for solving large-scale optimal designs (Hendrych et al,, 2023; Ahipaşaoglu, 2015; Zhao & Freund, 2023). We review related works in more detail in Appendix A.
K
exp J (k)
0-]
p(a)) k= j=n explx T 1 0.]
II
(I)
In short, items with higher mean rewards are more preferred by humans and thus more likely to be ranked higher. This feedback model is known as Plackett-Luce (Plackett, 1975) and is the most popular approach to eliciting unknown hu- man preferences from ranking multiple options (Negahban et al., 2018).
Our goal is select the subsets such that we can learn the true order of the items. Specifically, after T interactions, we output a permutation â [N] + [N], where ō(k) is the index of the item at position k. The quality of the solution is measured by the ranking loss
This paper is organized as follows. Section introduces our ranking problem and Section presents our framework for collecting human feedback to rank N items using K-way feedback. We show the impracticality of the FW method in Section 4 and make it efficient in Section 5. Section 6 is devoted to experiments. We conclude in Section 7.
R(T) N(N - 1) j=
2
Σ
N
N Σ
1(00)> > o(k)), (2)
where N(N - 1)/2 is a normalizing factor that scales the loss to [0. 1]. Simply put, the ranking loss is the fraction of incorrectly ordered pairs of items in permutation o. It can also be viewed as the normalized Kendall tau rank distance (Kendall, 1948) between the optimal order of items and that according to â, multiplied by 2/(N - 1)). While other objectives are possible, such as the mean reciprocal rank (MRR) and normalized discounted cumulative gain (NDCG) (Manning et al., 2008), we focus on the ranking loss in (2)
2. Setting
We start with introducing notation. Let [n] (1, (1,..., n and Rd be a d-dimensional real vector space. Let A be the probability simplex over set S. For any distribution
2

---

Comparing Few to Rank Many: Active Human Preference Learning Using Randomized Frank-Wolfe Method
to simplify our presentation. For completeness, we report the NDCG in our experiments.
3.2. Active Learning
The problem of choosing the most informative subsets Sp for solving (3) was studied by Mukherjee et al. (2024) and can be summarized as follows. Let Cr) be the Hessian of Lr (0), which can be used to measure the uncertainty in the MLE A. Let 23,4 2 23 be the difference of feature vectors of items j and kt and 2 denote the set of all feature vector differences. Let zt.j.k = (i) (k)) In our notation, Zhu et al. (2023b) showed that high-probability bound on the prediction error, for any 2 E Z, is
To simplify exposition, and without loss of generality, we focus on ranking N items in single list. Our setting can be generalized to multiple lists as follows. Suppose that we want to rank multiple lists with ,,,...,N, NM items using K-way feedback. This can be viewed as ranking problem over (x)) + +.... (M**) subsets, where any K-subset of items from the M lists is included in S. Since our algorithm depends only on S (Section 5), it remains the same even in this more challenging setting. fact, we experiment with this setting in Section 6.2, where we learn rank 30 000 lists, each with items from K K-subsets of size K = 2 and K = 3. Even for K 2, this is 630 000 subsets and two orders of magnitude more than in prior works (Mukherjee
1a (0 - 0.)l - Ō Ö(Vā|==la 1),
(4)
where
C
T
K Σ
M 2K(K -1)
(5)
et al., 2024).
1)
(=1 k=j+1
3. Optimal Design for Learning To Rank
is lower bound on the Hessian, (T) ł M holds for any 0 E θ and a universal constant C' > 0.
In this section, we introduce our basic algorithm and analyze it. More specifically, we generalize Mukherjee et al. (2024) to ranking N items from K-way feedback, from ranking K items only. for any K < N. While these contributions are not surprising technically, they significantly expand the class of modeled and solved problems. The fundamental novel challenge is solving the optimal design in (7). Since |S] = (x) it has exponentially many variables in K. Therefore, it cannot be written out and solved using standard methods, such as CVXPY (Diamond & Boyd, 2016). We address this challenge separately in Section 5.
The minimization of max,ez || is equivalent to max- imizing log (M) (Kiefer & Wolfowitz, 1960). This maximization problem is known as the D-optimal design. Mukherjee al. (2024) formulated it using matrix notation as follows. Each subset S E S is represented by its matrix As (zj. (s))) where
(6) is the set of all pairs in S where the first entry has a lower index than the second one. The matrix As has d rows and K (K- - 1)/2 columns. Equipped with these matrices, the D-optimal design (Pukelsheim, 2006) is solved as
[l2(5) = k(, j.
3.1. Maximum I Likelihood Estimate
We note that the problem of learning from K-way feedback is identical to that in Zhu et al. (2023b). Therefore, we just summarize their solution. Suppose that the human interacts with T subsets {Se) (Section 2). We use the human
T. arg max g(TT), where HEAS
g = log det (V+), V== E Ex(S)AsA3
responses og on St to estimate 0,, Specifically, since the probability of og under 0. is (I), the negative log-likelihae likelhoooood of all feedback is
SES
T E A is a probability distribution over the subsets in S, A is the simplex of all such distributions, and (SS) denotes the probability of choosing the subset S under л. Note that we could have indexed x by an integer defined through a bijective mapping C : S - [(x] numbers. We do not do this to simplify presentation. The problem (7) is concave since log det is concave for PSD matrices and all π (5)) A are PSD by design. Moreover, its solution sparse (Kiefer & Wolfowitz, 1960). Therefore, fast convex optimization methods, such the Frank- method, can be used to solve it. After n. is computed, the human feedback is collected on sampled subsets S₁
T
K
explx
T (x))
from the subsets to natural
(r) =
log
(3)
Σ K
プラ= expl xx T 10
1=1 k=1
To estimate 6., we solve a maximum likelihood estimation (MLE) problem, i = arg min eee Lr) The problem is convex (Zhu et al., 2023b) and thus can be solved efficiently by standard methods for generalized linear models (GLMs) (Bishop, 2006). Finally, item ie 2T.6 f and sort the items in descending order of o. 0, which defines à in (2).
estimate the mean reward of
We go beyond prior works in two aspects. First, we learn to rank N 2 K items from K K-way feedback. This can be done by combining (7) and (3), and we analyze this approach in
3

---

Comparing Few to Rank Many: Active Human Preference Learning Using Randomized Frank-Wolfe Method
Section 3.3. Second, (7) cannot be solved efficiently because S is exponentially large in K. To address this challenge, we propose a randomized Frank-Wolfe algorithm in Section 5.
The bound in Proposition is O(de/T), which is standard for a squared prediction error in linear models with d param- eters and sample size T. The dependencies on N K and (1/6) are due to bounding predictions errors of ( item pairs, from relative K K-way feedback with probability at least -
3.3. Generalization Analysis
In this section, we analyze active learning by the D-optimal design for ranking N 2 K items from K-way feedback. We start with proving that the differences in estimated item relevance under Ô converge to those under 0. as the sample size increases. The proof is under two assumptions that are not essential and only avoid rounding. We also assume that the parameter and feature vectors are bounded, as in Mukherjee al. (2024), which allows derive C in (5).
Now we derive an upper bound on the ranking loss R(T). Proposition 2. Let the feedback be collected according to T. in (7). Then the ranking loss is bounded as
N
N
(3) CKkI + d
R(T) S N(N Σ exp k=j+1
Assumption 1. For all & E [N], ||axll2 S 1. In addition, ||0xl12 5 1 and ||0]|2 S 1.
where > 0 is a universal constant from the concentration analysis in Lemma 9 in Mukherjee et al. (2024).
We can ensure that ||0112 S. 1 when optimizing (3) because @ -= {0 Rd: ||0||a S 1] is convex set and (3) is con- vex function. As a result, this can be done using gradient descent with a projection step to θ.
Proof. We build on Theorem of Mukherjee et al. (2024). Specifically, the key step in their proof is that
IP x 0 S 2 - expl
+
Our first claim is proved below.
holds for any set of K items S and items (j, I1,(S) in it. Our claim follows from noting that IP (ā(j) > akk)
Proposition 1. Let K be even and N/ K be an integer. Let the feedback be collected according to n, in (7), Then with probability at least 5,
P a < xx 0) and then applying the above bound.
Proposition 2 says that the ranking loss decreases exponen- tially with sample size T and squared gaps; and increases with the number of features d and K. The dependence on T. gaps, and d' is similar to prior works on fixed-budget best-arm identification in GLMs (Theorem 2 of Azizi et al. (2022)). Therefore, although we do not prove a lower bound, our bound is likely near-optimal.
N
N
= N2 log (N
(2]n(0. -0) B))² =
T
A=2+1
where
Zj,k- Tzj Tk.
Proof. We build on Theorem 5 of Mukherjee et al. (2024), which says that for any collection& of K -ubbeets,
3.4. Comparison to Clustering-based Approaches
Σ (6)00-00) =ō -0)0--00((0 =0(K'0
(&dd log(1 (1/0)
max SES
In this section we argue that optimal design works better for data selection than clustering- methods such as DBSCAN and m-medoids (see Appendix D. for details). As we saw in Sections 3.2 and 3.3, optimal design aims to minimize the worst-case estimation error along any direc- tion (4). The G-Optimal Design objective directly targets minimizing this upper-bound in the worst case through the objective h(T) = max, || where M depends on т. Then, by the Welffr-Wolfooitz theorem (Kiefer & Wol- fowitz, 1960; Mukherjee et al., 2024), maximizing h(xT) is equivalent to minimizing our D-Optimal Design objective (()) = log det (7).
T
(S))
holds with probability at least - 5. To reuse this result, we design collection C such that any item pair appears in at least one S E C. Then any (z]_e bounded. Let = {[E)/<(2N/K] be partition of [N] into sets with consecutive item indices, each of size K/2. Then C can be designed follows. The first 2N/K K 1 sets in C contain items 1 combined with any other set I \ 41, the next 2. K- - sets in C contain items I2 combined with any other set Z') \\ Iz. and so on. Clearly, the size of C is at most 4 2 and all (zJ_ و))² are covered. Thus
0))² would be
In contrast, clustering based data selection methods aim to maximize data coverage by first clustering to minimize the total intra-cluster variance and then selecting center- s/medoids from these clusters. Thus, when the original data distribution is unbalanced, clustering methods can miss potentially useful directions with fewer data points.
N Σ
(0. -0))
4N2 K2
&& log(1/0)
T
1=j-1
This concludes the proof.
LI
4

---

Comparing Few to Rank Many: Active Human Preference Learning Using Randomized Frank-Wolfe Method
Algorithm I Frank-Wolfe method for solving the D-optimal
Algorithm 2 DopeWolfe: A randomized FW method for solving the D-optimal design in (7).
design in (7).
Input: #steps Tod, initial iterate To E A
Input: sampling size R. #steps Tod, initial subset So E S, regularization 7, and line-search tolerance anol Let S be the collection of all KCsubsett of [N]
for f 1= ... Tod-1 do
Compute gradient: G2 = (T((
LMO: मे E arg max (G,; m)
Set æjA = Ij 2g. V(j, E [l2([N]) and no ES
TEAS
// Update iterate (Aigorithm 4)
Line search: ar E arg max g((1 - a) me aa. #1) oE(0.1]
3 Set Vimhv = Update Aso - ?), 1 - 7)
for t = 0, 1,,,,,,.,,Toa Toa-1 do
Iterate update: T(+1 = (1 - an) गe + aq Tt
// Randomized LMO
return Toa
5 Sample R2 Uniform( (R _ S [ R})
{G]( PartialGrad N, R2, Vi {zga))
S, E arg max SER. (5)
4. Frank-Wolfe Method for Optimal Design
// Line search (Algorithm 4)
The Trank-Wolfe (FW) method has been traditionally uti- 8 lized as a scalable algorithm for solving D-optimal designs
a = GoldenSearch( AA,, atol)
// Update iterate (Algorithm 4)
#++1 = (1 a.)) - me + 04 es.
(Khachiyan, 1996; Zhao & Freund, 2023). When applied
"
Viny UpdateInverse(V/M) at)
to (7), we obtain Algorithm 1. Each iteration of the method comprises three steps. First, we compute the gradient G, the current iterate (Line of Algorithm 1). Second, we find the distribution म. that maximizes the linear functional defined by G. (Line 3 of Algorithm 1) using a linear maxi- mization oracle (LMO). Finally, we update the iterate with a convex combination of the current iterate T,, and R. with a step size at, which is set to maximize g((1 ((l--a)-zz 7 a #t) (Line 4 of Algorithm 1) using linear search. It is known that this method converges the maximizer of (7) (Zhao & Freund, 2023).
11 return TTad
Sub-routine PartialGrad (N, Viny {z
for (j. E [Ia(( do
// Pair gradients
Dj.t 33,e Viav žjzh
for S E R, do L G(S) E(jA)enn(s) Dz.k
16
return {G(S))SER.
The FW method is efficient when the LMO can be imple- mented efficiently. In our problem (7) on simplex A the LMO can be written
gradients at time. This reduced the per-iteration compu- tational complexity of the FW method to 10t = 13 8/155. This is again impractical.
म ES,, where
(8)
The line search can also be computationally costly because it requires objective calculations at many feasible iterates and each such calculation involves computing the log det of a d x d matrix, which requires (dd)) operations in most practical implementations. In Section 5, we address these and other limitations through a new algorithm DopeWolfe, e, which has a better per-iteration complexity in terms of N, K, and d. Zhao (2023) proposed an away step variant of the FW method that has a superior empirical convergence rate for solving optimal designs. This method would face the same computation challenge as the FW method. We discuss this in detail in Appendix A.
S. = arg max GS),), - = St}. SES
Simply put, R is a distribution where all probability mass is put on set S,, which has the largest corresponding partial derivative maxses GS) Note that this implies that line search with es, can only increase the number of non-zere elements in the iterate मे by most one. So, after i steps, the number of non-zero elements in 7. is at most plus the number of non-zero elements in mo- This is one reason why the FW method is often preferred over gradient descent.
While the LMO in (8) seems simple, it requires computing the gradient with respect an (*) -dimensioon vector and finding its maximum entry. When N >> K, this means that the computational complexity is exponential in K. As an example, in our experiments (Section 6), the FW method runs out of memory when N = 100 and K = 10 because the full gradient is a 10 dime-diimlii vector. Even under conservative estimates, this requires 68 TB of RAM for a float32 precision, which is out of reach for most practition- ers. We tried parallelization and could compute 10 partial
5. DopeWolfe: Randomized Trank-Wolfs Method for Optimal Design
We propose and analyze our algorithm for solving the D- optimal design in (7) next. We call it DopeWolfe and show its pseudo-code in Algorithm 2. The pseudo-code for some sub-routines is in Appendix. DopeWolfe is a fast random- ized variant of the FW method that incorporates compu-
5

---

Let Letr= = (K) < d. Then A is rank-r matrix since As E _dxr Assuming access to V= the log-determinant of (10) can be computed using that of an update is derived in Appendix C. This reduces the overall from Comparing Few to Rank Many: Active Human Preference Learning Using Randomized Frank-Wolfe Method
tationally efficient memoization, and low-rank and sparse operations. In the rest of the section, we describe the build- ing blocks of the algorithm and show how they address the scaling concerns identified in Section 4.
we note that the update can be written as
- - + aAsAg.
(10)
5.1. Randomized LMO and Cached Derivatives
matrix. This
The computational complexity of the LMO in Section 4 is O(( ((x)) because the maximization step is over an exponen- tially large S in (8). We utilize a randomized variant of the FW method (Kerdreux et al., 2018) to reduce it to (R) by restricting the maximization to an R-subset R₂ chosen uniformly at random from S (Lines and 7 of Algorithm 2).
line search complexity to O( + rd²) O(dP a in Section 4.
Both the partial derivative and objective value computation require the inverse of V4 DopeWolfe initializes the matrix by Vinn (Line 3 of Algorithm 2) and then updates it (Line 10 of Algorithm 2) using UpdateInverse. The computational complexity of naively inverting a d d matrix is Odd)). We note though that V₂ is updated by a low-rank matrix in (10). Therefore, we can compute the inverse of Va by using the inverse of an r x matrix (Algorithm 4 in Appendix). As a result, the inverse computational complexity is reduced from (dd) to O(r3 + rdf).
St E arg max Gs( where SER,
R₂- Uniform {R C S| [R] R)).
This implies that we only need to compute R partial gradi- ents G[( = 8g(5s) for the subsets S E R4,
(S)
Next we show how the partial gradients can be computed efficiently. Recall the definitions of ( and V from (7). Since the gradient of log (U)) is U-1 for a PSD matrix U. the partial derivative at any S can be written as
Finally, we address how DopeWolfe maintains and stores the iterate n; in exponentially-mann dimensions (x) When N >>>>> K > 1, it becomes both computationally and space costly. Since DopeWolfe is initialized with a one-hot vector and its updates are sparse (Lines 2 and 9 of Algorithm 2), we store ne as a sparse vector and update it using sparse operations. This reduces the complexity of maintaining Te to its number of non-zero elements, which is at most & + 1 after iterations. We discuss this in detail in Appendix C.
ag(T))
(S) = (AsAS, = Σ
3g Vo a Zgkk
(9)
(I))
Dj.k
where Dj, = V Simply put, all partial deriva- tives are sums of (K) terms chosen from the (2) terms in (Dy.) (Dj.)tjaa ((.t)ees In DopeWolfe, we leverage this struc- ture in sub-routine PartialGrad, which first computes and caches all D (Line 14 in Algorithm 2), and then combines them to obtain partial derivatives for all S E R2 (Line 16 in Algorithm 2). Assuming that V is known, this reduces the overall LMO complexity from (( (K) df) in Section 4 to O (2) d + n((5 R())). We parallelize these computations in our code.
5.3. Convergence Rate of Randomized FW Method
We analyze the convergence rate of DopeWolfe next. Since DopeWolfe is a randomized FW method, we know that it converges to the maximizer of (7) if g was Lipschitz smooth (Kerdreux al., 2018). However, g does not satisfy this con- dition because of the logarithm in its definition. To provide guarantees, we prove a more general result, that random- ized FW method (A (Algorithm 3 in Appendix) converges for problems of the form
5.2. Line Search with Low-Rank and Sparse Updates
We noted earlier that line search (Line 4 of Algorithm 1) is computationally costly. In Dopewolfe. e. we replace it with sub-routine GoldenSearch (Line 8 of Algorithm 2), which is provided in Algorithm 4 in Appendix. This sub-routine solves a one-dimensional unimodal maximization problem using the colden-section search (Kiefer, 1953). The golden- section search reduces the search space by multiplicative factor of yp known the golden ratio, per iteration. As result, it is guaranteed to return the maximizer up to an error Osol after 1 + (Oto) iterations.
min F(y) min s(A(v)), yEy
(11)
yEY
where y is the convex hull of set of Ñ vectors, A A:y: IC is linear operator, IC regular cone, and f in)((C)) + R is searithmicclly-homogeeee (LHSCB) (Zhao & Freund, 2023).
self-concordant barrier
Theorem 3. If the initial iterate yo maps to domain of f. i.e. A(yn) E iK), then Randomized FW method (Algo- rithm 3) which samples R elements from V for computing the randomized LMO achieves an E sub-optimal solution to the problem (11) after Tew = Ommxx N /R); 11 itera- tions, i.e. F( ) - mingey F(y) S E.
We also noted earlier that a naive computation of the objec- tive value in line search has a complexity of (d3)) Here
6

---

Comparing Few to Rank Many: Active Human Preference Learning Using Randomized Frank-Wolfe Method
This result extends the convergence analysis of a random- ized FW method for Lipschitz smooth objectives to prob- lems of the form (11). As corollary of Theorem 3, we provide the convergence rate for DopeWolfe.
Anthropic Dataset
0.40
Uniform
0.35
Dope
Mean Ranking Loss
DopeWolfe
Corollary 4. For full-rank Vag 7 - O, and small enough avol- DopeWolfe (Algorithm 2) outputs an E sub-optimal solution to the D-optimal design problem (7) after Tod = (1max(1 (x)/R) (R)]=R)))) iterations, i.e. m g(xx) (Tg(( S.
0.30
0.25
0.20
0.15
We provide the proofs of these statements in Appendix B. Note that Corollary 4 needs V=,, to be full-rank; otherwise the objective might not be well-defined. In practice, this can be guaranteed by regularizing the matrix as Va + Ilax with a small 7 > 0. Finally, aggregating the complexities of all steps of DopeWolfe, we observe that its per-iteration complexity is (((2) d² R(²)) (r² + rd²) log, (Atsa) Toa), eliminating any (x) and d dependence.
0.10
100
200
300
400
500
600
700
800 900 1000
Sample Size (T)
Nectar Dataset
2.5
Uniform
Mean Ranking Loss
2.0
Dope DopeWolfe
1.5
Note that DopeWolfe without a randomized LMO would have the per-iteration complexity of O(()) (5) (r" rdd) log,p (Araa) Tad) and the iteration complexity of ()= (Zhao& & Freund, 2023). As result, in theory, the randomized LMO has a better per-iteration complex- ity while increasing the worst-case iteration complexity to O (())/())) Note that this is desirable because the FW method is impractical even for small instances of our prob- lems, as discussed in Section 4. We do not observe empir- ically (Section 6) that the convergence rate of DopeWolfe is exponentially worse, bounded in Corollary 4. Similar observations have been made in prior works, where the em- pirical convergence rate of the randomized FW method is much hetter than the theoretical upper bound when applied to Lipschitz smooth problems (Kerdreux et al., 2018, Figure 1). Therefore, we conjecture that Theorem 3 is not tight for most problems and defer further study to future work.
1.0
0.5
0.0
100
200
300
400
500
600
700 800 900 1000
Sample Size (T)
Figure I. Mcan ranking loss of DopeWolfe, Dope, and Uniform on the Antropic and Nectar problems in Mukherjee et al. (2024).
provement over the original implementation of Mukherjee et al. (2024), which solves the linear maximization problem in (8) using linear programming. Morcover, we replace the line search in Algorithm 1 with the golden-section search in Algorithm 2. We also compare to a baseline that chooses subsets of items uniformly at random. While simple, is known to be competitive in real-world problems where fea- ture vectors may cover the feature space close to uniformly (Ash et al., 2019; Yuan al., 2020; Ash et al., 2021; Ren et al., 2021). We call it Uniform. DopeWolfe is run with 10% of randomly sampled subsets of items.
6. Experiments
We evaluate the performance of DopeWolfe in three experi- ments. In Section 6.1, we compare it to Dope (Mukherjee et al., 2024) on the same datasets and in the same setting. This is the closest related work. The main difference in our algorithm is that it can be applied to larger problems. We evaluate DopeWolfe such problems with synthetic feed- back in Section 6.2 and with real feedback in Section 6.3. The main evaluation metric is the mean ranking loss in (2). We also report NDCG in Appendix.
We vary the sample size from T = 100 to T = 1 000, and report our results in Figure 1. We observe that the ranking losses of DopeWolfe and Dope are similar, while those of Uniform are much worse. We note major difference in the run times of DopeWolfe and Dope, Although we imple- ment Dope more efficiently than Mukherjee et al. (2024), DopeWolfe is more than three times faster on the Anthropic dataset (6.184 seconds on average versus 20.149 147) and more than two times faster on the Nectar dataset (0.411 seconds on average versus 0.960). This is despite the fact that our method designed for much larger problems.
6.1. Comparison to Dope
In the first experiment, we compare to Dope (Mukherjee et al., 2024) on both Anthropic (Zhu et al., 2023a) and Nec- tar (Bai et al., 2022) datasets in their work. We implement Dope using Algorithm 1. This is major computational im-
7

---

Comparing Few to Rank Many: Active Human Preference Learning Using Randomized Prank-Wold Method
Moan Ranking Less for K 2 on BEIR-COVID Dataset
Nean Ranking Less for K znn TREC-OL Dataset
Moan Ranking Loss for K 2 on NECTAR Dateset
Dipewalli
Mean Bankingg Loke
DESCAV Nedooda
DESCAN Medoica
DESCAV
Noan Ranking
1
Moan Ranking
Sample Size
Samale Size (T)
Sample Size
(a) BEIR-COVID, K = 2
(b) TREC-DL, K 2
(c) NECTAR, K
=
Ranking BEIR.COVID
Ranking TREC-OL Dataset
Ranking
NECTAR
Dec coooee
Dopewailc
Decomate DescaN
Maan Bankinng Loos
Nean Banking
Nesveda
Noan Manking
Medo
Samule Size IT) (d) HEIR-COVID, K 3
Samale Size (T)
Samule Size (T)
TREC-DL, K
(f) NECTAR, K
Figure 2. Mean ranking loss on three datasets with synthetic feedback. Medoids fails on the Nectar dataset due to excessive memory requirements, TB and TB RAM, respectively.
6.2. Synthetic Feedback
Mean Ranking Loss on BEIR-COVID Dataset
023
Uniform
Our second experiment is on problems where Dope cannot be implemented efficiently. We experiment with two text retrieval datasets, SEIR-COVID and TREC Deep Learn- ing (TREC-DL)². and Nectar (Bai al., 2022) dataset. In the first two datasets, we experiment with single lists of N = 100 items. In the Nectar dataset, we choose 30 000 lists, each with 7 items, and learn to rank of these lists simul- tancously, as described in the last paragraph in Section 2. Even for K = 2, this means 30 000 (2) = 630 000 subsets of items to choose from, which is two orders of magnitude more than in Section 6.1.
DopeWolfa
Mean Ranking Loss
0.20
0.3-
0.5-
060
10
(a) Ranking loss on BEIR-COVID with real feedback.
The feature vectors of the items are their (00-dimensional BERT embeddings. The parameters of the Plackett-L.uc model are learned from data and the feedback is sampled according to (1) with those parameters. We consider three baselines: Uniform, which was already introduced in Sec- tion 6.1; DBSCAN (Ester al., 1996), which is a clustering baseline; and Medoids, which is another clustering baseline, We describe the baselines in more detail in Appendix D.1. All results are averaged over 100 random runs.
Mean Ranking Loss on TREC-DL Dataset
000-
Uniform
DopeWolfe
Mean Ranking Loss
0.05
acca
8:3
We vary the sample size from T = 100 to T = 1 000, and report results for K E (2.3) in Figure 2. We observe the following trends. First, DopeWolfe fe has the lowest ranking loss. Some improvements are of an order of magnitude. In particular, for K 2 on the Nectar dataset, the ranking loss of DopeWolfe at T 100 is lower than that of all
861
(b) Ranking loss on TREC-DL DL with real feedback.
Figure 3. Mean ranking loss on two datasets with real feedback.
hntps://huggingface hhtp://huuggingfa....oddassss//a www.aanssss//Beeeeeeee..o
8

---

Comparing Few to Rank Many: Active Human Preference Learning Using Randomized Frank-Wolfe Method
baselines at T = 1 000. Second, both DBSCAN and Medoids perform relatively poorly because they often do not even outperform Uniform. We also note that the ranking losses of all methods decrease as T and K increase. The former is expected because the methods benefit from more feedback. The latter is also expected because each unit of feedback contains more information, due to ranking more items. For completeness, we report NDCG in Figure 4 (Appendix D.1) and results for K 4 in Figure 5 (Appendix D.I). We also compare the run times of DopeWolfe and DESCAN in Appendix D.3.
variables, exponentially many in K.
To address this challenge, we propose DopeWolfe for solv- ing our optimal design problem. DopeWolfe is random- ized FW method that uses memoization and sparse updates to improve the per-iteration complexity of the FW method from ((())) ) to O(N + K²). Furthermore, we provide convergence analysis for DopeWolfe by generalizing the analysis of the randomized FW method beyond Lipschitz smoothness to general class of logarithmically homoge- neous self-concordant barrier objectives. Finally, we em- pirically demonstrate the computational and statistical effi- ciency of our framework on both synthetic and real-world datasets, with large N and moderate K.
6.3. Real Feedback
The third experiment is more realistic variant of the exper- iment in Section 6.2. There are three main differences. First, we use real feedback instead of simulated feedback. The real feedback is more challenging since the optimized model may be and likely is misspecified. Second, we use more rep- resentative .021-dimensional BGE-M3 embeddings (Chen al., 2024) to ensure that the features are sufficiently rich to learn the true ranking order under real feedback. Finally, we explore wider range of feedback with K E (2, ...,, 10). Note that large N and moderate K make this experiment an extremely large-scale ranking problem. Particularly, for N 100 and K = 10, there are 17 trillion subsets of items for eliciting feedback. Therefore, it essentially impossible to run prior optimal design methods (Mukherjee al., 2024) or the Frank- Wolfe method (Zhao & Freund, 2023). We omit DBSCAN and Medoids baselines due to the same scale issues. We provide more details in Appendix D.2.
Limitations. Our work can be viewed as learning to rank N items from relative K-way feedback. A natural question to ask is if this can be done using absolute feedback. In our opinion, absolute feedback has three major shortcomings. First, annotators often exhibit variable calibration when as- signing absolute scores, making cooss-annotaoor aggregation difficult. Second, comparing items is typically more natural and faster for humans. Finally, often we only have access to proxy signals (ad clicks or video watch time), which have 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.
We have an offline active learning problem, in sense that DopeWolfe selects K-subsets of items to elicit feedback on before receiving any feedback. The most natural way of making it online would be to update item embeddings after receiving feedback.
We plot all results as a function of K and report them in Fig- ure 3. We observe the following trends. First, Dopewolfe has the lowest ranking loss in all settings. Second, the rank- ing losses of both methods decrease as K increases. This is expected because each unit of feedback contains more information, due to ranking more items. While Figures 2 and 3 are not comparable, they can be compared by looking at relative differences in the ranking losses of Uniform and DopeWolfe. This is consistently 20% in Figure and sim- ilar to many relative differences in Figure 2. We conclude the despite the more challenging settings, the improvements due to DopeWolfe can be of similar magnitude. For com- pleteness, we report NDCG in Figure 6 (Appendix D.2).
Future work. Our work can be extended in multiple direc- tions. First, we only studied one particular human feedback model, K-way ranking, popularized by RLHF (Ouyang et al., 2022) and DPO (Rafailov et al., 2023). Second, the (dd2) dependence in Proposition 1 is suboptimal. It can be reduced to O(d) by avoiding the Cauchy-Schwarr in- equality in (4). Finally, we want to conduct more realistic experiments on high-dimensional LLM embeddings used in the reward modeling phase of RLHF (Sun et al., 2023).
7. Conclusions
Impact Statement
We study learning to rank N items from K-way ranking feedback under a limited feedback budget. We develop an D-optimal design framework for eliciting K K-way feedback by generalizing Mukherjee et al. (2024) and prove that it is statistically efficient in minimizing the ranking loss. We also show that the classic methods for solving this problem are infeasible in our setting because they optimize over 0 K
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
9

---

Comparing Few to Rank Many: Active Human Preference Learning Using Randomized Frank-Wolfe Method
References
Casper, S., Davies, X., Shi, C., Gilbert, T. K., Scheurer, J., Rando, J., Freedman, R., Korbak, T.,, Lindner, D., Freire, P., et al. Open problems and fundamental limitations of reinforcement learning from human feedback. arXiv preprint arXiv:2307. 15217, 2023.
Abdi, H. and Williams, L. J. Principal component analysis. Wiley interdisciplinary reviews: computational statistics, 2(4))433-4455 440)44334499, 2010.
Agichtein, E., Brill, E., Dumais, S., and Ragno, R. Learn- ing user interaction models for predicting web search result preferences. In Proceedings of the 29th Annual International ACM SIGIR Conference. pp. 3-10, 2006.
Chen, J., Xiao, S., Zhang, P., Luo, K., Lian, D., and Liu, Z. Bge m3-embedding: Multi-lingual, multi- functionality, multi multi-granularity text embeddings through weff-knowledge distillation, 2024.
Ahipaşaoğlu. S. D. first-order algorithm for the a-optimal experimental design problem: mathematical program- ming approach. Statistics and Computing, 20155
Christiano, P., Leike, J., Brown, T., Martic, M., Legg, S., and Amodei, D. Deep reinforcement learning from hu- man preferences. Advances in Neural Information Processing Systems 30, 2017.
Ash, J., Goel, S., Krishnamurthy, A., and Kakade, S. Gone fishing: Neural active learning with fisher embeddings. Advances in Neural Information Processing Systems, 34, 2021.
Das, N., Chakraborty, S., Pacchiano, A., and Chowdhury, S. R. Active preference optimization for sample efficient RLHF. CoRR, abs/2402.10500, 2024. URL https:
//axxiv.org/abstt. /200.
Ash, J. T., Zhang, C., Krishnamurthy, A., Langford, J., and Agarwal, A. Deep batch active learning by di- verse, uncertain gradient lower bounds. arXiv preprint 1XXv::9906.06611, 2019.
Diamond, S. and Boyd, S. CVXPY: A Python-embeddee modeling language for convex optimization. Journal of Machine Learning Research, 17(83):1-5, 2016.
Ester, M., Kriegel, H.-P., Sander, J., Xu, X., et al. A density- based algorithm for discovering clusters large spatial databases with noise. In KDD, volume 96, pp. 221-231, 1996.
Audibert, J.-Y., Bubeck, S., and Munos, R. Best arm iden- tification in multi- aeme bandits. In Proceedings of the 23rd Annual Conference on Learning Theory, pp. 41-53, 2010.
Fedorov, V. V. Theory of optimal experiments. Elsevier, 2013.
Azizi, M. J., Kveton, B., and Ghavamzadeh, M. Fixed- budget best-arm identification structured bandits. In Proceedings of the 31st International Joint Conference Artificial Intelligence, 2022.
Guttman, Enlargement methods for computing the in- verse matrix. The annals of mathematical statistics, pp. 336-343, 1946.
Bai, Y., Jones, A., Ndousse, K., Askell, A., Chen, A., Das- Sarma, N., Drain, D., Fort, S., Ganguli, D., Henighan, T., et al. Training helpful and harmless assistant with rein- forcement learning from human feedback. arXiv preprint arXiv:2204.05886 058622 2022.
Hendrych, D., Besançon, M., and Pokutta, S. Solving the optimal experiment design problem with mixed-inteed integer convex methods. arXiv preprint 2312 1200, 2023.
Hiranandani, G., Singh, H., Gupta, P., Burhanuddin, I. A.. Wen, Z., and Kveton, B. Cascading linear submodular bandits: Accounting for position bias and diversity in online learning to rank. In Proceedings of the 35th Con- ference on Uncertainty in Artificial Intelligence, 2019.
Barzilai, J. and Borwein, M. Two-point step size gradient methods. IMA journal of numerical analysis, 8(1):141- 148, 1988.
Hofmann, K., Whiteson, S., and de Rijke, M. Fidelity, soundness, and efficiency of interleaved comparison methods. ACM Transactions on Information Systems, 31(4):1-43, 2013.
Bishop, C. Pattern Recognition and Machine Learning. Springer, New York, NY, 2006.
Bradley, R. A. and Terry, M. Rank analysis of incom- plete block designs: I. the method of paired comparisons. Biometrika, 39(3-4):324-345, 1952.
Hofmann, K., Li, I.., and Radlinski, F. Online evaluation for information retrieval. Foundations and Trends in Information Retrieval, 2016.
Bubeck, S., Munos, R., and Stoltz, G. Pure exploration in multi-armed bandits problems. In Proceedings of the 20th International Conference on Algorithmic Learning Theory, pp. 23-37, 2009.
Jaggi, M. Revisiting frank-wolfe: Projection- sparse convex optimization. International conference on ma- chine learning, pp. 427-435. PMLR, 2013.
10

---

Comparing Few to Rank Many: Active Human Preference Learning Using Randomized Frank-Wolfe Method
Jin, Y., Yang, Z., and Wang, Z. Is pessimism provably efficient for offline rI? In International Conference on Machine Learning, pp. 5084-5096. PMLR, 2021.
Mehta, V., Das, V., Neopane, O., Dai, Y., Bogunovic, I., Schneider, J., and Neiswanger, W. Sample efficient reinforcement learning from human feedback via ac- tive exploration. CoRR, abs/2312.002677, 2023. URL https: http:///axvvvvv.oeoeee wtt.:///////..........o
Kang, Y., Shi, D., Liu, J., He, L., and Wang, D. Beyond reward: Offline preference-guice policy optimization. arXiv preprint arXiv:2305. 16217,1111 2023.
MS MARCO.
MS MARCO https:/mniccsott.ggguu..oommmmms 2016.
Dataset,
Kendall, M. G. Rank correlation methods. Griffin, 1948.
Mukherjee, S., Lalitha, A., Kalantari, K., Deshmukh, A., Liu, G., Ma, Y., and Kveton, B. Optimal design for human preference elicitation, In Advances in Neural Information Processing Systems 37, 2024.
Kerdreux, T., Pedregosa, F., and d' Aspremont, A. Frank- wolfe with subsampling oracle. In International Con- ference on Machine Learning, pp. 2591-2600. PMLR, 2018.
Negahban, S., Oh, S., Thekumparampil, K. K., and Xu, J. Learning from comparisons and choices. The Journal of Machine Learning Research, 19(1):1478- 1572, 2018.
Khachiyan, I.. G. Rounding of polytopes in the real num- ber model of computation. Mathematics of Operations Research, 21 21)333007-3 1996.
Nesterov, Y. Introductory Lectures Convex Optimiza- tion: A Basic Course. Springer Publishing Company, Incorporated, I edition, 2014.
Khetan, A. and Oh, S. Data-driven rank breaking for effi- cient rank aggregation. In International Conference on Machine Learning, pp. 89-98. PMLR, 2016.
Ouyang. I.,, Wu, J., Jiang, X., Almeida, D., Wainwright, C., Mishkin, P., Zhang, C., Agarwal, S., Slama, K., Ray, A.. Schulman, J., Hilton, J., Kelton, F., Miller, L., Simens, M., Askell, A., Welinder, P., Christiano, P., Leike, J., and Lowe, R. Training language models to follow instructions with human feedback. In Advances in Neural Information Processing Systems 35, 2022.
Kiefer, J. Sequential minimax search for maximum. Pro- ceedings of the American mathematical society, 4(3): 502-506, 1953.
Kiefer, and Wolfowitz, The equivalence of two ex- tremum problems. Canadian Journal of Mathematics, 12: 363-366, 1960.
Pan, Y.. Tsang, I. W., Chen, W., Niu, G., and Sugiyama, M. Fast and robust rank aggregation against model misspeci- fication. Journal of Machine Learning Research, 23(23): 1-35, 2022.
Kveton, B., Szepesvari, C., Wen, Z., and Ashkan, A. Cas- cading bandits: Learning to rank in the cascade model. In Proceedings of the 32nd International Conference on Machine Learning, 2015.
Plackett, R. L. The analysis of permutations. Journal of the Royal Statistical Society: Series C (Applied Statistics), 24(2):193-202, 1975.
Lagree, P., Vernade, C., and Cappe, O. Multiple-play bandits in the position-based model. In Advances in Neural In- formation Processing Systems 29, pp. 1597-1605, 2016.
Pozrikidis, C. An introduction to grids, graphs, and net- works. Oxford University Press, USA, 2014.
Lattimore, T. and Szepesvari, C. Bandit Algorithms. Cam- bridge University Press, 2019.
Pukelsheim, F. Optimal Design of Experiments. Society for Industrial and Applied Mathematics, 2006.
Li, S., Wang, B., Zhang, S., and Chen, W. Contextual combinatorial cascading bandits. In Proceedings of the 33rd International Conference on Machine Learning, pp. 2016.
Radlinski. F., Kleinberg, R., and Joachims, T. Learning diverse rankings with multi-armed bandits. In Proceed- ings of the 25th International Conference Machine Learning, pp. 784-791, 2008
Luce, R. D. Individual Choice Behavior: A Theoretical Analysis. Dover Publications, 2005.
Rafailov, R., Sharma, A., Mitchell, E., Manning, C., Ermon, S., and Finn, C. Direct preference optimization: Your language model is secretly a reward model. In Advances in Neural Information Processing Systems 36, 2023.
Manning, C., Raghavan P., and Schutze, H. Introduction to Information Retrieval. Cambridge University Press, 2008.
McInnes, L., Healy, J., and Melville, J. Umap: Uniform manifold approximation and projection for dimension 2018.
Reimers, N. and Gurevych, I. Sentence-bert. Sentence embeddings using siamese bert-networks. In Proceed- ings of the 2019 Conference on Empirical Methods in
reduction. arXiv preprint

---

Comparing Few to Rank Many: Active Human Preference Learning Using Randomized Frank-Wolfe Method
Natural Language Processing. Association for Compu- tational Linguistics, 11 2019. URL http://arxiv.
Zanette, A. When is realizability sufficient for off-policy reinforcement learning? In International Conference on Machine Learning, pp. 40637-40668, PMLR, 2023.
httgabbs/990..33
Ren, P., Xiao, Y., Chang, X., Huang, P.-Y., Li, Z., Gupta, B. B., Chen, X., and Wang, X. A survey of deep active learning. ACM Computing Surveys (CSUR), 54(9):1-40, 2021.
Zhao, An away-step frank- wolfe method for minimizing logaritmiiaaly--ommgeeecoss barriers. arXiv preprint arXiv:2305. 2023.
Zhao, R. and Freund, R. M. Analysis of the frank-wolfe method for convex composite optimization involving a logarbmmicalj--homgeeeou barrier. Mathematical pro- gramming, 199(1): 123-163, 2023.
Riquelme, C., Tucker, G., and Snoek, J. Deep Bayesian ban- dits showdown: An empirical comparison of Bayesian deep networks for Thompson sampling. In Proceedings of the 6th International Conference on Learning Repre- sentations, 2018.
Zhu, B., Frick, E., Wu, T., Zhu, H.,, and Jiao, J. Starling- 7b: Improving IIm helpfulness & harmlessness with rlaif, November 2023a.
Saha, A. and Gopalan, A. Active ranking with subset- wise preferences. In Proceedings of the 22nd Interna- tional Conference on Artificial Intelligence and Statisties, 2019a.
Zhu, B.. Jiao, J., and Jordan, M. Principled reinforce- ment learning with human feedback from pairwise or K K-wise comparisons. CoRR, abs/2301.11270, 2023b. URL https::////cmmm http///axxxvvvroee abs 2301 11270.
Saha, A. and Gopalan, A. PAC battling bandits in the Plackett-Luce model. In Proceedings of the 30th Inter- national Conference on Algorithmic Learning Theory, 2019b.
Zong, S., Ni, H., Sung. K., Ke, N. R., Wen, Z., and Kveton, B. Cascading bandits for large-scale recommendation problems. Proceedings of the 32nd Conference on Uncertainty Artificial Intelligence, 2016.
Sun, W., Yan, L., Ma, X., Ren, P., Yin, D., and Ren, Z. Is chatgpt good at search? investigating large language mod- els as re-ranking agent. arXiv preprint 20X4522304.09542, 2023.
Szorenyi, B., Busa-Fekete, R., Paul, A.. and Hullermeier, E. Online rank elicitation for Plackett- Luce: A dueling bandits approach. In Advances in Neural Information Processing Systems 28, 2015.
Tennenholtz, G., Chow, Y., Hsu, C.-W., Shani, L., Liang, E., and Boutilier, C. Embedding aligned language models. arXiv preprini arXiv:2406.0000 00024, 2024.
Tversky, A. and Kahneman, D. Judgment under uncertainty: Heuristics and biases. Science, 185(4157)1114--1131
1974.
Woodbury, M. A. Inverting modified matrices. Department of Statistics, Princeton University, 1950.
Xu, T., Wang, Y., Zou, S., and Liang, Y. Provably effi- cient offline reinforcement learning with trajectory-wise reward. arXiv preprint arXiv:2206.06426, 2022.
Yang, J. and Tan, V. Minimax optimal fixed-budget best arm identification in linear bandits. In Advances in Neural Information Processing Systems 35, 2022.
Yuan, M., Lin, H.-T., and Boyd-Graber, Cold-start ac- tive learning through self supervueee language modeling. arXiv preprint M:Xiv:2000.095355 2020.
12

---

Comparing Few to Rank Many: Active Human Preference Learning Using Randomized Frank-Wolfe Method
A. Related Work
Three recent papers studied a similar setting. Mehta et al. (2023) and Das et al. (2024) learn to rank pairs of items from pairwise feedback. Mukherjee et al. (2024) learn to rank lists of K items from K K-way feedback in (I). We propose a general framework for learning to rank N items from K-way feedback, where K 2 2 and N 2 K. Therefore, our setting is more general than in prior works. Our setting is also related to other bandit settings as follows. Due to the sample budget, it is reminiscent of fixed-budget best arm identification (BAI) (Bubeck et al., 2009; Audibert et al., 2010; Azizi et al., 2022; Yang & Tan, 2022). The main difference is that we do not want to identify the best arm. We want to estimate the mean rewards of N items to sort them. Online learning to rank has also been studied extensively (Radlinski et al., 2008; Kveton et al., 2015; Zong et al., 2016; Li et al., 2016; Lagree et al., 2016; Hiranandani et al., 2019). We do not minimize cumulative regret or try to identify the best arm.
We discuss related work on Frank-Wolfe (FW) methods next. The use of FW method for solving standard optimal design problem (for linear and logistic regression) is not new. In fact, it can be traced even up to 1990s (Khachiyan, 1996). Ahipaşaoğlu (2015) presents two first-order Frank-Wolfe algorithms with rigorous time-complexity analyses for the A- optimal experimental design. Hendrych et al. (2023) optimize an experimental design by the Frank-Wolfe algorithm within a mixed-integer convex optimization framework. Zhao & Freund (2023) introduce a generalized Frank-Wole method for composite optimization with a logarithmically-Dne hooooolcooooooooouuuu self-concordant barrier (LHSCB). None of these works focus on ranking problems. Please see Zhao & Freund (2023) for comprehensive literature review. Recently Zhao (2023) proposed and analyzed Away-step variant of the FW (AFW) method for LHSCB problems. Just like in the case of Lipschitz smooth problems, AFW achieves better empirical performance than standard FW method. However, we would like to highlight that AFW is also infeasible for our problem since it has higher per-iteration cost than the standard FW method which is already infeasible. Additionally, their implementation (Zhao, 2023, Sec 6.2-6.3) nitializes Ty with a uniform distribution, which can also be a practical challenge for us since π is O(N*) dimensional. This is the reason we do not compare against this algorithm. Our randomized Frank-Wolfe algorithm addresses this specific computational challenge variables.
when solving for a D-optimal design for learning to rank with O (N)
While other works have learning rank with ranking feedback, motivated by learning preference models in RLHF (Rafailov et al., 2023; Kang et al., 2023; Casper et al., 2023), our work is unique in applying optimal designs to collect human feedback for learning to rank. Tennenholtz et al. (2024) show the benefits of using an optimal design of a state-dependent action set to improve an embedding- aligned guided language agent's 's efficiency. Additionally, Khetan & Oh (2016) and Pan et al. (2022) provide optimal rank aank-brekinn estimators for efficient rank aggregation under different user homogeneity assumptions. Our work stands out by integrating optimal design with randomized Frank- Wolfe method in the context of ranking a large list of N items through K- www ranking feedback.
In offline RL, the agent directly observes the past history of interactions. Note that these actions can be suboptimal and there can be issues of data coverage and distribution shifts. Therefore in recent years pessimism under offline RL has gained traction (Jin et al., 2021; Xu et al., 2022; Zanette, 2023). In contrast to these works, we study offline K-wise preference ranking under PL and BTL models for pure exploration setting. We do not use any pessimism but use optimal design (Pukelsheim, 2006; Fedorov, 2013) to ensure diversity among the data collected. If the action set is infinite, then approximately optimal designs can sometimes be found efficiently (Lattimore & Szepesvari, 2019). (Sun et al., 2023) investigated generative LLMs, such as ChatGPT and GPT-4, for relevance ranking in IR and found that properly instructed LLMs can deliver competitive, even superior results to state-of-the-at supervised methods on popular IR benchmarks. We note that our approach can further be used in such settings to enhance the performance.
There are also related works in the bandit community. Saha & Gopalan (2019a) proposed non-contextual algorithms. That is, they do not have access to features of the items and hence the relevance (Plackett-Luce score) of each item is estimated independently of other items. The paper studies two feedback models: the winner out of K items and top-m ranked items out of K for m < K. The performance metric a ranking loss. We differ from this work by having a contextual algorithm, which parameterizes the relevance of an item as a linear function of its feature. Szorenyi et al. (2015) also proposed non-contextual algorithms. The paper studies dueling feedback. The performance metrics are the best item and a ranking loss. We differ from this work by having contextual algorithm and more general feedback than ducling (K > 2). Saha & Gopalan (2019b) also proposed non-contextual algorithms. The paper studies two feedback models: the winner out of K items and top-m ranked items out of K for m < K. The performance metric is the best item. We differ from this work by having a contextual algorithm and different performance metric.
The most naive approach to solving our problem is uniform sampling. That is Tuniform (S) -(x)
VA
S. Its
13

---

Comparing Few to Rank Many: Active Human Preference Learning Using Randomized Frank-Wolfe Method
convergence rate depends on the distribution of feature vectors and be significantly worse than that of DopeWolfe. To this, consider K 2 and N > d. Let æ1 (1,0,0). For & > let 2g (0, 1) for even k and 2 (0, 0, 1) for odd k. In this case, only N 1 feature vector differences out of N(N - 1)/2 have non-zero entry in the first dimension. Therefore, the minimum eigenvalue of V grows at the rate of ((T/N) in expectation, unlike (TT/d) in the D-optimal design. The implication for the bounds is that one in Proposition is replaced with and the only d in Proposition is replaced with N.
B. Theoretical convergence rate analyses
This section provides the theoretical convergence rate analysis of DopeWolfe (Algorithm 2). We do this by first proving more general result for the broad class of LHSCB problems (11). Then we will provide the convergence rate of DopeWolfe as corollary of this result.
B.1. Generic Randomized FW method for solving the LHSCB problem
In this section we analyze the convergence of the generic randomize FW method (Algorithm 3) for minimizing composition of 6-LHSCB functions and affine transformations. More precisely, we recall the studied optimization problem
min Fly) = min / (A(y)), yEy
(12)
yEy
where } is the convex hull of set V of Ñ vectors O cV))(V)), A y - K. is a linear operator, AC is a cone, and f: (KC) - R is b-oggaribmiccllyy-mmoeeeene self-concordant barrier (LHSCB) (Zhao & Freund, 2023). Next we define the LHSCB function.
Definition 5. We say that function f is B-logarithmically homogenous self-concordant barrier (LHSCB) if
1. f + IR is a convex mapping with regular cone K. m (closed, convex, pointed and with non-empty interior in)(K)) as its domain,
2. f is 0-logarithmicaly homogenous, i.e. f(tu) = f(u) 0 log &, for all int(K) and >> 0 for some 2
3. f is self-concordant, i.e. fu)(V, v, ul[ < 4(c, 42 (u)o)) for all u E int(K)) and v E R where D3 (u)) is the third order derivative of f at u in the direction v and 4² (u)( is the Hessian of f at u, and
4. f is barrier, i.e. fly) + too for any (ux)k20 S int(KC and - E bd(K)), where bd(IC) is the boundary of K.
From the above assumption it is clear that problem (12) is convex problem.
Algorithm 3 Randomized Frank-Wolfe Method for LHSCB Problem (12)
Input: yo such that A(3o) int(K)), sample size Rt for t 0, 1, ..... Tew do Sample (S N) subsets uniformly random from V: R4 Uniform S ||| R1))
Compute v2 arg min (VF (we), v) // Randomizes LMO
VER,
Compute dg = arg min F(#; + a(1 -x)) // Line Search
Update F:+1 = v, + (v, 2z))
In Algorithm 3, we provide the generic randomize FW method for solving problem (12). Before providing its convergence rate we state known property of LHSCBB functions. It is know that IHSCBB functions satisfy the following approximate second-order upper bound. We define, for given positive semi-definite matrix M, the weighted norm || V Mu. Proposition 6 ((Zaao Freund, 2023; Nesterov, 2014)). Let f K. - be LHSCB. Then,
f()) < f(v) (Vf(u), v u) w(ll w ullv>s(u)), Vu (nt)
(13)
14

---

Comparing
Few to Rank Many: Active Human Preference Learning Using Randomized Prank-Wolf Method
where
w(a) a 1m(1 -a-Ia(1 a), a<l
(14)
D0C,
1 1 a.
Note that the w is convex and non-negative in (-o0, 1).
Now we are ready to provide the convergence rate of Algorithm 3. For the sake of clarity, we restate Theorem 3 with more details below. This proof is inspired from the proof techniques developed in (Kerdreux al., 2018; Zhao & Freund, 2023).
Theorem 7. Let the initial iterate yo maps to domain of f. i.e. A(vo) E int((K), and óu = F( - minyey Fly), then Randomized FW method (Algorithm 3) which uniformly samples R elements from V for computing the randomized LMO a each step outputs an E sub-optimal solution to the 0- L-HSCBB problem (11) in expectation. after
TFW = 5.3
N N (ōn 0) max In (10.6 20 o0)
+
12 R
0² max
{ le
max
1
N 10.6
0]}
(15)
R
R
00
R
iterations, ie.. [F[F((]eW) - minzey F(y)= S.
Proof. First notice that since A is linear mapping, the update rule in Algorithm can be re-written as
Dr arg min (VF(y.). v) = arg min (A (V.((A(()))) v) arg min (Vf(((())) VER,
(16)
vE
vER,
and
0g arg min F((1 ((1--ay a)y: + av) arg min S(A((1 a)ye + av)). 0E
(17)
oE[0.1]
Above also follows from the well-known affine invariance property of FW method (Jaggi, 2013), Next using Proposition 6 we get
F((1 - a)ye + avr) = f(A((1 a) a) avi))
f(A(N) + (Vf(A(())))))))))))VVV)))))))))) A((1 a)y, + av;)) + w[I[A((1 a)u, + aav))lle FV))) aVV 91)) wwalllA(ue )))lv=)(((m)))
Let G, -(Vf(A()))) A(v 91) and D₁ || w)l We also assume that 2i arg min vev(VS(A(A)) ) u) is the output of the LMO if we run regular deterministic FW method (general version of Algorithm 1) at iteration f. Note that we can also define this LMO output as ey E arg min (AA())((())))) v) since y = conv(V) and a minimizier of linear functional on a closed convex polytope is one of its vertices. Using this definition of of we also define G; = - f(Amm))) )), A(u; - yt)) and DI = ||A(tt () Then taking the minimum w.r.t. a on both sides of the above inequality yields
F()-11) min F((1 a)v ov)) S F(y) min |-aG; w(aD)))
(18)
aE(0,1]
aE(U,1]
and by taking expectation conditioned on the randomness of y/2 we get
E[F(y++1) [v] < F(y:) E min aE[0.1]
[-aGi+-(aal) w(DD:)) 1v]]
-
(19)
Notice that when a 0 we obviously have that - -aG; + w.) = 0 since ((0) 0. Therefore, minaejo.ul-aG, + w(aD;)] < O. Note that, in contrast to regular FW method (Algorithm 1) where G. is always negative, for the worst case sampling of RR, the quantity Ge can be positive. Therefore, choosing the a dynamically is necessary to ensure non-increasing objective values in randomized FW (Kerdreux et al., 2018). Next, we upper bound the above inequality as
[[F((++1)1 [v]] < F(y) + (1 Prob(ef E v.)) 0 Prob(u E V.) min [-aGt + w(()))) aE(o.1]
F()) + (R/N) min [-aGt + w(a)))) aE(o.1]
(20)
Now notice that the above "descent lemma" inequality is similar to (Zhao & Freund, 2023, Inequality 2.7), except for the conditional expectation on the LHS and the discount factor (R/š)= & 1 on second term which corresponds to the minimum decrease in objective value. Therefore, rest of the proof follow similar arguments as (?)Theorem 2J2hao202aasalyss..
15

---

Comparing Few to Rank Many: Active Human Preference Learning Using Randomized Frank-Wolfe Method
This proves that randomized FW method convergence the the minimizer of the LHSCB problem in ((N) (M)/R))=)) steps.. Compared to regular FW method, randomized version increases the iteration complexity by a factor of R/R. We see similar increase in iteration complexity even for convex problems with bounded Lipschitz smoothness (Kerdreux et al., 2018). In the next section we specialize this result to provide convergence rate guarantee for DopeWolfe (Algorithm 2).
B.2. Theoretical analysis of DopeWolfe
Again for the sake of clarity we first restate Corollary 4 providing the iteration complexirt of DopeWolfe (Algorithm 4) with more details and then provide its proof.
Corollary& 8 (of Theorem 7). Let Va be full-raan, 7 0, R S (k), Olzol be small enough and d ms g(m) g (TT)) then DopeWolfe (Algoritimm 2) which uniformly samples R subsets from S for computing the randomized LMO at each step, outputs an sub-optimal solution to the D-optimal design problem (7) in expectation, after
Tod 5.3
K (ōo d) max { In (10.6 60)) K R
12
K df max le
max
10.6 K
}.0]]
(21)
60 R
iterations, iee ms ( - E[g(TT.a)) S.
Proof. Let 84 be the regular cone of all PSD matrices of dimension x d. Then we notice that the maximization problem in the D-optimal design (7) can be written as a special case of the minimization problem (12) by setting F = = y/ = n, K = S f = log det $ + R, A = Eses A5S)AAAS : π + $4. and = S (N = ())) It known that f = log det is an LHSCB function (Definition 5) with 0 = d (Zhao & Freund, 2023). Moreover, A maps to S because As is PSD for all S S.
This equivalence implies that when Ctol + and y 0, running DopeWolfe (Algorithm 2) is equivalent to running randomized FW method (Algorithm 3) for the above specialization. Please see Section 5 for description of how various sub-routines of Algorithm 2 implements varioius steps of Algorithm 3. Finally, we can satisfy the condition yo int(K)) if Va, is full rank since V= E iSt Then the the iteration complexity of DopeWolfe directly follows from Theorem 7. O
Note that above theorem requires that atll is small enough, but since GoldenSearch is an exponentially fast algorithm, Osoi can reach machine precision in a very few steps. For example in our implementation we set Ohaol 10-16 and this is achieved in 76 steps of GoldenSearch.
C. Additional algorithmic details and sub-routines for DopeWolfe
In this section, provide additional details for DopeWolfe (Algorithm 2). We begin by providing the complete pseudocode for the three undefined sub-routines of DopeWolfe (UpdateInverse, GoldenSearch, UpdateLogDet) in Algorithm 4. Next we provide explanation for various algorithmic choices made in DopeWolfe.
C.1. Low-rank update for the log det objective
As mentioned in Section 5.2 computing objective function values involves computing the log det of a d x d matrix which has a worst case complexity of O(d)). However, we simplify this computation by noting that V22 is only updated with the
r (k) rank matrix As A (for some 5). Since As E I xd
R this is a low-rank matrix when < d, which allows us to simplify the relevant change in objective function value after the convex combination with step size a as follows. For the sake of simplicity, we denote Vine =V=) (V=)-1/(1 - a) and À vaAs. Then,
g((1 - a) ग a es) (T))
log det ((1 a) + aAsAA) log (va)
log det ((1 - (Iaxd + AA Friny VV)) log VV))
d dog(( a) + del (Iaxa + AA FrlN)
= d log(1 - a) + log dee (I, + A Pinv A).
(22)
where the third equality follows from the facts that log det (BC) = log det(B) + log det(C") and log det(cBuxdl) = doog(c) + log det(()) (), and the third equality follows from the Weinstein-Aronszajy identity log det (I BC) = log (It
16

---

Comparing Few to Rank Many: Active Human Preference Learning Using Randomized Wolle Method
Algorithm 4 Sub-routines required for Algorithm 2
Sub-routine Invere (1 (Viny, A, a
Set
(2), Vinv
Vinv /1 a), and A VaA
Vi Vinv Viny L Lxxr + A vinr (
A V'vv
return Viay
Sub-routine GoldenSearch (V (Ving, AA, atol)
Set و - (v5 1)/2, 02 = 0,0% ag Initialize:
ag aa + tapp ad au + anp
Vidd UpdateLogDet (V ae)
V UpdateLogDett("1 (Viny A, ad)
10
while @u - 0b 2 acco do
OG anp
if Vild > Vid then
12
ab. ad. Vld. a = ad, ace Vll aa + anp yil UpdateLogDet(
14
ac)
15
else
Oa. Ocg Vld ag = aes ad, Vld aa + unip yld UpdateLogDet (Vnv, A, 0.))
16
return (a. + aab//2
Sub-routine UpdateLogDet /inv A, a:)
Set r = -k), Vinv Vinv /(1 a), and A = VaA
29
21 Via d'log(1 - a) + lolo det [Ixrr + Vini A
return V
22
CB) (Pozrikidis, 2014). GoldenSearch sub-routine (Line 5 of Algorithm 4) in turn uses the UpdateLogDet sub-routine (Line 19 of Algorithm 4) which implements (22) assuming the access V--1, Since (22) computes log det of an r matrix reduce complexity of computing change in objective function values from (dd²) to O rd²). Note that one can further reduce the total complexity of GoldenSearch from O(log, (o + rd?)) to (1o + + + rd²) by computing eigenvalues { of A3, V As, once and then computing the change in objective function values as dloo(11 a) + Σ log(1 + ad;), however this approach may be numerically less stable.
C.2. Low-rank inverse update
Here we expand on how DopeWolfe computes the inverse of the x d matrix Vs, used in PartialGrad (Line 12 of Algorithm 2) and UpdateLogDet (Line 19 of Algorithm 4) sub-routines. Naively implementing every iteration incurs cost of (dd) every iteration. Instead, UpdateInverse sub-routine (Line of Algorithm 4) is used in DopeWolfe to iteratively update the matrix vinv storing the inverse as follows
Vinv ((1 (11 + (aAsA)
((Vinv) AAT)
(23)
Pinv - Finv Ā(I A Vinv A Fine
where we used the notations from Section 5.2 and the second equality used the Woodburry matrix inversion identity (Guttman, 1946; Woodbury, 1950) with r = (K). When r & d, this update rule improves the complexity of finding the inverse Or rd)). Similarly Viav is also initialized using the same UpdateInverse sub-routine (Line of
17

---

Comparing Few to Rank Many: Active Human Preference Learning Using Randomized Frank-Woll Method
Algorithm 2) because (for y 1):
VoTe (As_, + IIxxd)
(7laad + (1 As A / 7)) UpdateInverse (Lxx: As / (1-7), -))1-1)
(24)
Therefore even initialization only costs O(r + rdf) compute.
C.3. Sparse iterate update
Finally we discuss how we store and update the large (x) dimensional iterate Tr (Line of Algorithm 2). If we initialize DepeWolfe with sparse To and if Tod << (x) then its iterates are sparse since the update rule T++11 = (1-o)) -T tett ess consists of the one-hot probability vector es,- This implies that maintaining %e as (x) dimensional dense vector is unnecessary and expensive. Therefore, DopeWolfe maintains it as sparse vector =!(*p) (scipy (scipy.sparse.................ee www.ssaae.cc... pytparse.ccc.araae csc_array')
of size (x) This begs the question how DopeWolfe maps a subset E S to an index of ग. (sp) DopeWolfe answers this by
using the combinadics number system of order K* which defines bijective mapping, Cx S > [[x]], from the collection (ep) (1 (1-a,)- -..aa--- (op) + +o e (sp) (x()))) where (S.( is the basis vector for the (x(S)) (St)-th dimension. These modifications improves the worst case complexity of updating and maintaining n, after t iterations from (( (x) to only O(t).
of subsets of size K to integers. Therefore our update rule in terms of ,,, (sp) translates to 7441
[sp]
D. A Additional Experimental Details and Results
In this section we provide additional experimental details and results that were omitted from Section 6.
We experiment with (a) BEIR-COVID", (b) Trec Deep Learning (TREC-DL) and (c) NECTAR" datasets. These are question- antioering datasets, where the task is to rank answers or passages by relevance to the question. Each question in BEIR-COVID and TREC-DL has hundred potential answers. Each question in NECTAR has seven potential answers. All the following experiments are conducted on 3.5 GHz 3rd generation Intel Xeon Scalable processors with 128 vCPUs and ITB RAM. Code for our experiments is available at https: /tttttb.tuu/ggggg/gg///.tg.....t com/ www.//tkiiaan/opeoo.......
D.I. Synthetic Feedback Setup
In this section we provide additional experimental details and results that were omitted from Section 6.2.
We first compute di4-eiimesional dense BERT embeddings (Reimers & Gurevych, 2019) for each question and answer, and then reduce the embedding dimensions to 10 by fitting UMAP (McInnes et al., 2018) on the answers in a dataset. The same UMAP transformation is applicd to questions to get 10-dimensional embedding of the questions. Let q and a be the projected embeddings question and an answer it. Then, we consider the outer product vec(ga") as the feature vector of the question -enssion-answerr pair. Its length is d 100. We choose a random 6* IR 100 generate feedback in (1).
The output of DopeWolfe is a distribution over all K-subsets of the original set of N items. To show the efficacy of DopeWolfe, we compare it with the following baselines:
1. Uniform: This approach chooses K-subsets at random with equal probability.
2. DBSCAN: We apply DBSCAN clustering (Ester et al., 1996) over features of all K-subsets, each of which is a concatenation of the features of the items in it. DBSCAN has a distance syper-parametent that has a major impact on the clustering. To select it, we evaluate several clustering e {10-5, 10-4 ....., 1}. and choose the one that results in the fewest clusters; and then define uniform distribution over the cluster centers. This can be viewed as the sparsest distribution of core samples centroids.
hnttp:://scipy.orr
'https: stttps:///ent http://///eewwwiiiieeeeeee http://www...e..e///m/maaatttoee number_ saaibber_systee system. ee "hunss//huggingffcee.c
18

---

Comparing Few to Rank Many: Active Human Preference Learning Using Randomized Frank-Wolfe Method
3. m-medoids: We set to the size of the support of the distribution from DopeWolfe. Then, we run the m-medoids algorithm over the same features in DBSCAN. Finally, we select K-subsets associated with (centroids) at random with equal probabilities. Note that this approach has extra information in terms of m which other methods do not have.
We consider 1 random question in BEIR-COVILE and TREC-DL DL datasets. The number of 2-way subsets and 3-way subsets for one question with hundred answers are (2)) = 4950 and (?gn) = 161700, respectively. We consider random 30,000 questions in NECTAR dataset. The number of way subsets and 3-way subsets, where each question has seven answers, are 30000(2 = 630000 and () = 1050000, respectively. Given a sample size T. we fit a PL ranking model. m-medoids fails for the NECTAR dataset due to excessive memory requirements (2 TB and 8 TB of RAM, respectively).
In Figure 4, we show the mean NDCG metric (higher is better) for the experiment in Section 6.2 for K 2,3 on the three datasets. The observations are consistent with Section 6.2, where DopeWolfe achieves better ranking performance than baselines.
Meen RDCG for K 2 on BEIR-COVID Dataset
Mean NDCG for K 2 on TREC-OL Dataset
Nean NDCG for K 2 on NECTAR Datsset
Uppees
Leaferrs
Lniierrs
pasco
ERFUCAM
Hoan NDCG
Mour NDCC
Sample Size
Sample Size (T)
Sample Size (T)
(a) BEIR-COVID, K = 2
(b) TREC-DI, K = 2
(c) NECTAR, K =
Mean NDCG for K 3 on BEIR-COVID Dataset
Mean NDCG for K 3 on TREC- OL Dataget
Nean NDCG for K 3 on NECTAR Dataset
DESIOA
Uewnn HDCG
Modo do
Mean NBCG
Heddets
40
20
26 Sample Size (T)
Sample Size
Sample Size ITS (f) NECTAR, K K==3
(d) BEIR-COVID, K =
(e) TREC-DI, K 3
Figure 4. Mean NDCG metric (higher is better) on BEIR-COVID, TREC-DL and NECTAR datasets with synthetic feedback.
We next show the ranking loss (2) (lower is better) and NDCG metric (higher is better) for K = 4 for BEIR-COVID and TREC-DL datasets in Figure 5 for the synthetic setup (Section 6.2. Note that, for NECTAR dataset, since the number of answers for each question are only seven, the number of possible subsets are same for = 3 and K = 4; thus, we ignore NECTAR dataset for K = 4. We again observe that DopeWolfe achieves better performance than baselines on the ranking
task.
D.2. Real Feedback Setup
In this section, we provide more details on the experimental choices for the experiment with real feedback (Section 6.3).
We use real feedback from TREC-DL and BEIR-COVID datasets. Each question in TREC-DL and BEIR-COVID datasets has 100 potential answers. The answers are ranked. When a learning algorithm queries a subset of K answers, the feedback is their ranked order in the dataset. We vary K a fixed value of T and observe how the metrics change.
Similarly to Section 6.2, we evaluate the feedback elicitation methods by assessing the downstream performance of the learned PL model. Specifically, we compare DopeWolfe to Uniform sampling for feedback elicitation. DBSCAN and m-medoids are excluded from this comparison due to their inability to scale effectively for this problem size.
For both BEIR-COVID and TREC-DL datasets, since the feedback is real, we use more representative 1024 dimensional BGE-M3 embedding (Chen al., 2024) ensure that the features are rich and reasonable enough capture the true
'htps://tinyurll wwtp:/ywwwwooooociiiiiiiiieeeeee meniiiii---aa----mmdiiiii
19

---

Comparing Few to Rank Many: Active Human Preference Learning Using Randomized Frank-Wolf Method
Mean Ranking Loss for K on BER-COVID Dataset
Mean NDCG for K on BEIR-COVID Dataset
Dopot/alt::
DESCAN
DBSCAN
Noon Ranking
Sample Size (T)
Sample Size
(a) BEIR-COVID, K = 4
(b) BEIR-COVID, K = 4
Ranking TREC-DL Dataset
Mean NDCG TREC-DL Dataset
DooeWW St
Dopertall::
Nean Banking Lous
Mean HOCG
6.30
Sample Size IT)
Samsle Size (
(c) TREC-DL, K
(d) TREC-DL, K
Figure 5. BEIR-COVID and TREC-DL ELC--DLGG datasets with synthetic feedback: Mean KDtau and NDCG metric on Datasets for K = 4. On average, DopeWolfe achieves better performance than Uniform sampling and DBSCAN.
Table 1. Run time comparison: DopeWolfe vs DBSCAN.
Method
Time in Seconds
DopeWolfe at 1000 iterations
1646.70
DBSCAN (c 10-5)
37.52
DBSCAN (E 10-4)
37.46
DBSCAN (e = 10-3)
39.63
DBSCAN (e 10-2)
69.28
DBSCAN (c = 1101)
1346.28
DBSCAN (E ===]
3397.21
ranking (realizable ranking problem). We then apply Principal Component Analysis (PCA) (Abdi & Williams, 2010) so that the feature matrix is full rank. We end up with 98 and 78 features for BEIR-COVID and TREC-DL datasets, respectively.
We then run DopeWolfe on the datasets by setting 7 = 10 6 atol = 10
10-16 16 and R = min( ( ((x) 10a) and initializing 1. We find that the DopeWolfe converges in 200 iterations for
with a uniformly chosen single subset, i.e. nnz(#.) BEIR-COVID and in 1500 iterations for TREC-DI. Since the feedback is real and does not change whenever we sample new waw subset for feedback, distribution obtained through DopeWolfe. Note that due to significant amount of ranking ties in the BEIR-COVID dataset, we use the MLE for the pairwise rank breaking of the observations (Negahban et al., 2018, Equation 39, Page 25) instead of the K-wise MLE (3). We found that choosing only top-25 K-way subsets for BEIR-COVID works well, possibly due to the simpler nature of the problem as a consequence of the ties. For TREC-DL dataset, we choose top-500 K K-way subsets. Lastly, we run the Plackett-Luce model's maximum likelihood estimation process using gradient descent with Barzilai-Borwedd stepsize rule (Barzilai & Borwein, 1988) with min and max stepsize clip values of 10 and 100/103 for NEER-COVVD/TRECAAA which converges in 200/1000 iterations for BEIR-COVID/TREC-DL. All the reported metrics provide mean and standard error over over 10 trials
pick the top K-way subsets that have the highest probability mass in the sampling
The ranking loss (2) results for this experiment is shown in Figure 3. We also show NDCG@ @ 10 for this experiment in Figure 6. We choose NDCG@ 10 to show the accuracy at the top of the ranking. In the NDCG computation, we use linear gain function for
and an exponential gain with temperature 0.1 for TREC-DL with the aim of differentiating its very close score values. We see that DopeWolfe performs better than the baselines for the ranking tasks in both datasets.
20

---

Comparing Few to Rank Many: Active Human Preference Learning Using Randomized Frank-Wolf Method
Mean NDCG@10 on BEIR-COVID Dataset
Mean NDCG@10 on TREC-DL Dataset
Uniform
DopeWolte
1.993
Mean NDCG@10
91000
Dniform
19645
DapeWWlle
K
(a) BEIR-COVID
(b) TREC-DL
Figure 6. BEIR-COVED CEVIRCCVVDDAAA and TREC-DL datasets with real feedback: Models learned through ranking feedback collected on DopeWolfe samples achieve higher NDCG@ 10 than the ones learned on Uniformly selected samples.
D.3. Practical Run Time Comparison
We now compare the run time of Dopewolfe with DBSCAN. Although the running times for DopeWolfe and DBSCAN are not directly comparable due to different deciding parameters- Dopewoffe relies on the number of Frank-Wolfe iterations, while DBSCAN depends on the distance threshold (t). We chose DBSCAN as a baseline clustering algorithm, because does not require input parameter specifying distribution sparsity (e.g., m-medoids requiring m), and it provides cluster centers actual data points.
Nonetheless, in Table 1, we present run-time comparisons for DopeWolfe with 1000 Frank-Wolfe iterations and DBSCAN with distance thresholds varying between [10-5,.... 1], as explained in Section 6.2 for the BEIR-COVID dataset with K = 3, corresponding to 161,700 possible subsets. We observe that DBSCAN takes twice the time of our proposed method for c 1. The total run-time for the DBSCAN- Although we used 1000 iterations in all our experiments, convergence is typically achieved in around 100 iterations, yielding similar performance, which only takes 164.67 seconds. This demonstrates that proposed method not only achieves superior performance but also is computationally efficient.
baseline is 4927.38 seconds; whereas ours is only 1646.70 70 seconds.
D.4. Additional baseline
The closest related work from the bandit baselines in Appendix A is Saha & Gopalan (2019a) and compare it in the following experiments. Since both of their algorithms perform comparably, we implemented simpler Beat-the-Pivot (for TR feedback) as follows:
1. We give Beat-the-Pivot the optimal pivot (best item). This simplifies our implementation while giving Beat-the-Pivot slight advantage.
2. We divide all items into groups of size K and add the pivot each group.
3. We go over the groups in a round robin and get ranking feedback on them. For each item in each group, we estimate the fraction of times that it beats the pivot.
4. We sort the items by the fraction of times that they beat the pivot in descending order. This yields the final ranked list.
We report our results in the synthetic feedback setting (Section 6.2) in Tables 2 andd 3.
We observe that Beat-the-Pivor performs worse than any of our current baselines (compare to Figure 1 on page 7 and Figure 3 in Appendix). This is because the approach is not contextual. Specifically, since the relevance of each item is estimated independently, Beat-the-Pivor is less statistically efficient than the methods that utilize features. Due to this shortcoming, we also do not run experiments on the NECTAR dataset, which has 30k separate lists. Even with a total of 1000 samples, the number of samples allotted a list could be 0 and non-contextual algorithms cannot share information across lists.
21

---

Comparing Few to Rank Many: Active Human Preference Learning Using Randomized Frank-Waod Wolfe Method
100
200
300
400
500
600
700
800
900
1000
BEIR-COVID
083 0.01
1077 + 0.01
0.75 + 0.01
0.73 + 0.1
0.71
+ 0.1
0.69 + 0.01
0.67 + 0.01
0.67 +: 0.01
0.6 + 0.01
0.33 0.01
TREC-DL
0.9 0.01
0.99 +: 0.01
0.96 0.01
0.97 + 001
0.7
001
0.96
0:11
0.96
0,01
0:35 001
0.6 + 0.01
0.96 0.01
TREC
0.98
0.01
0.6
0.94
0.3
000
Table Mean ranking loss of heat-the-Pivot.
BEIR-COVID
0.1
0.00
0:21
2: 0.00
0.21
+ 0.00
0.21 + 0.00
0.21
0.0
0.21
= 0.00
0.21 = 0.00
0.22 2 0.00
0.1
+ 0000
0:11
0.00
BEIR COVID
0.21
0.00
0.21
+: 0.00
0:21
0.00
0.22 + 0.00
0.21
0.00
0.22
4: 0.00
0.22 4 0.00
0.22
0.00
0.22
+ 0.00
0.22
0.00
TREC
0.00
0.21
0.00
0.21
0.00
0.21
0.00
0.21
0.00
0.00
0.21
1 0.00
0.00
Table NDCG Beat-the-Pivot.
22


Reviews:
[{"review_id": "qjBoA4cWGf", "reviewer": "Reviewer_Z4RR", "summary": "This paper proposes an algorithm to rank N items from K-way comparisons (K<<N), formulated through a D-optimal design objective. The authors develop “DopeWolfe,” a randomized Frank-Wolfe variant with sparse and low-rank updates to avoid high complexity of naive approaches. They prove a sublinear convergence rate for this randomized method under a logarithmically-homogeneous self-concordant barrier analysis. Empirical results on both synthetic and real IR datasets suggest that the proposed design framework improves ranking accuracy compared to uniform sampling or clustering-based methods.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n### **Practical Motivation**\n\n$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](https://arxiv.org/pdf/2205.06024)).\n\nRecent developments in reinforcement learning with human feedback (RLHF) also suggest that relative feedback can yield better alignment than absolute feedback ([Christiano et al., 2017](https://arxiv.org/abs/1706.03741); [Bai et al., 2022](https://arxiv.org/abs/2204.05862)). 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](https://arxiv.org/abs/2402.01878)). This is one motivation for collecting the Nectar dataset used in Mukherjee et al. (2024).\n\n### **Absolute Versus Relative Feedback**\n\nWe 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](https://arxiv.org/abs/1406.6618)). 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.\n\n### **Data and Setup Concerns**\n\nWe 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).\n\n### **Additional Baselines**\n\nTo 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:\n\n* Dope is implemented using the Frank-Wolfe method where the linear maximization oracle (LMO) is a linear program.\n* 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.\n\nWe implemented DopeWolfe in their code base as follows:\n\n* LMO is solved greedily, as in (8), on 10% of randomly sampled subsets of items.\n* Line search is implemented using golden-section search.\n\nThe plots for the Anthropic and Nectar experiments are at [Anthropic plot](https://anonymous.4open.science/r/DopeWolfe-ICML-anon-1AD6/DopeWolfe_Anthropic_ICML_rebuttal.png) and [Nectar plot](https://anonymous.4open.science/r/DopeWolfe-ICML-anon-1AD6/DopeWolfe_Nectar_ICML_rebuttal.png), 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:\n\n* **Anthropic:** DopeWolfe is about $4$x times faster than Dope ($6.046$ seconds on average versus $24.924$).\n* **Nectar:** DopeWolfe is about $3$x times faster than Dope ($0.571$ seconds on average versus $1.826$).\n\nNote that both Anthropic and Nectar are well-established RLHF datasets.", "claims_and_evidence": "Claims are supported by theoretical analysis.", "methods_and_evaluation_criteria": "A key assumption in the paper is that a global ranking over N items can be inferred solely by issuing multiple K-ranking queries—i.e., repeatedly asking annotators to compare small subsets of items. However, this setup becomes questionable when N is large and the total number of queries T times K exceeds N. In real-world systems, it may be more natural and cost-effective to collect absolute (or per-item) feedback for high-dimensional or large-scale ranking tasks, rather than repeated sampling of the same few items in multiple queries. The results in the experiment gets small ranking error when T times K exceeds.", "theoretical_claims": "The theorems appear consistent with known self-concordance analyses.", "experimental_designs_or_analyses": "**Data/Setup Concerns.** The paper’s experiments primarily center on two information-retrieval datasets, each with N=100≫K=2. While these retrieval tasks do involve preference judgments, they may not accurately reflect the complexities of human-generated comparisons found in large-scale response-based RLHF settings, where user preferences can be more nuanced or subjective. Moreover, for the LLM-alignment dataset, the paper mentions N=7 items across multiple lists—a rather small scale. In such a scenario, it seems more prior baselines (e.g., DOPE) could be applied and compared, since the problem size is not computationally prohibitive.\n\n**Baselines.** On the “real data” setting, the paper omits the two baselines in synthetic setting, even though K remains small. Also, including baselines that is “smarter” than uniform sampling yet still computationally manageable would be more convincing. For instance, iterating through all data in random order and pairing. \n\n**Hyperparameter Analysis.** More tuning or ablation studies on key hyperparameters will be helpful.", "relation_to_broader_scientific_literature": "The paper situates itself in the broader context of RLHF and preference-based ranking. Its approach to active preference learning for \nK-wise feedback is connected to D-optimal design, a classic concept in statistics but still underexplored in RLHF or large-scale ranking tasks. It generalizes prior active ranking work (some of which focuses on pairwise or small-scale scenarios) to the more general Plackett-Luce model for K-way comparisons. The use of a randomized Frank-Wolfe variant for log-determinant objectives extends earlier results on Lipschitz smooth objectives, bridging a gap in the continuous optimization literature.", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "The problem setting is interesting but may not be very practical. The proposed algorithm nicely solve the problem and theoretical analysis is provided. But more real-world experiments are needed to support practical use.", "other_comments_or_suggestions": "Line 358 right column has a reference error (??)", "questions_for_authors": "In practice, K-way queries might arrive in a sequential setting with noisy or incomplete feedback. How could DopeWolfe incorporate incremental updates as partial responses come in?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8lOFMQAW3K", "reviewer": "Reviewer_4hjz", "summary": "This paper focuses on the problem of RL using human ranking feedback. In particular, the goal is to learn the ranking of N items using K-way ranking feedback. To solve such a problem in an active learning fashion, the learner needs to first compute a design via Frank-Wolfe (FW), sample queries according to the design, estimate utility for each item, and estimate the ranking.\n\nPrevious work by Mukherjee et al. (2024) solved the problem where N=K. This paper extends Mukherjee et al. (2024) to the case when N>>K. The key challenge in this extension is that the FW gradient has a dimension of (choose N K), which is computationally challenging for modern computers.\n\nThere are 2 contributions: (1) analyzing the ranking loss by extending Mukherjee et al. (2024) to show that the original method from Mukherjee et al. (2024) is still valid for the case when N>>K if ignoring the computation challenge; (2) proposes a computationally efficient method, called \"DopeWolfe\" by integrating randomized FW (Kerdreux et al., 2018) and golden-section search method (Kiefer, 1953) to approximately solve FW and reduce the computation with a factor of (choose N K) to (choose N 2). Also, the authors prove that after O(max(1, (choose N K)/R)/ε) iterations, the error is upper bounded by ε.\n\nThe authors tested the proposed method vs 3 baseline methods on 3 real-world datasets. In the first experiment, the human preference vector, θ, is randomly sampled, and human feedback is simulated accordingly. In the second experiment, there is no ground truth θ (which makes the proposed method using the PL model misspecified), and the human feedback is taken from the dataset. The result shows that the proposed method with the MLE estimator achieves the lowest ranking loss.\n\n## update after rebuttal\nI appreciate the authors' Rebuttal in addressing my concerns. I have adjusted my score accordingly.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n### **Empirical Concern in Claim 1**\n\nWe 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.\n\n### **Theory Concern in Claim 2**\n\nThank 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).\n\n### **Ensuring Assumption 1 During MLE**\n\nWe 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$.\n\n### **Additive $d$ in Proposition 2**\n\nThe 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.", "claims_and_evidence": "* Claim 1: Mukherjee et al. (2024) is valid for the case of N>>K when ignoring the computation challenge.\n    * This is theoretically justified by bounding the ranking loss in Sec.3.3 and empirically justified in experiments to show that the pipeline achieved higher performance than others.\n    * I have one concern about the empirical result. In the result in Sec.6.1 (using synthetic feedback), the proposed method significantly outperformed baselines (Fig.1). However, in the result in Sec.6.2 (using real feedback), the advantage of the proposed method, in comparison to the baseline is less than 0.1 for mean ranking loss (Fig.2). It might be helpful to justify this by explaining that this difference can be significant in real-world systems.\n\n* Claim 2: when extending Mukherjee et al. (2024) to the case of N>>K, the FW is computationally challenging due to the computation complexity factor (choose N K). The proposed method resolves this by getting rid of the (choose N K).\n    * This is theoretically justified by analyzing the computation complexity in Sec.5.1 and 5.2, by showing e.g., (choose N K) is reduced to (choose N 2). This is also empirically justified in experiments to show that the proposed method is able to solve the FW while vanilla FW won't work.\n    * I have one concern about the theoretical result. Cor.4 shows that to solve the proposed algorithm to reach small error ε, it would need O(max(1, (choose N K)/R)/ε) iterations. So essentially, in each iteration, the proposed method is able to get rid of the (choose N K), but the overall optimization still needs (choose N K) iterations. I understand that there is no free lunch, and the empirical result seems to be working well, but it might be helpful for the authors to clarify this.", "methods_and_evaluation_criteria": "Yes. The empirical study is based on 3 real-world datasets about text retrieval and LLM alignment. The synthetic-feedback experiment randomly selects θ, which makes sense because the problem is too complicated to identify the θ from the dataset. The real-feedback experiment directly uses human feedback and benchmarking the ranking loss, which makes sense.", "theoretical_claims": "I didn't check the proofs. Prop.1 adapts from Thm.5 of Mukherjee et al. (2024), and Prop.2 adapts from Thm.6 of Mukherjee et al. (2024).\n\nOne concern is that Assumption 1 assumes that ||θhat||_2<=1. I am wondering how this can be ensured during the MLE?", "experimental_designs_or_analyses": "The experiment design and analysis make sense.", "relation_to_broader_scientific_literature": "The result can be useful for learning human preferences from ranking feedback for modern AI systems, such as LLMs, if the set of prompts is fixed and known, as demonstrated by the empirical result.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "This paper is well written, with good theoretical and empirical justification. The technical contribution is not so \"surprising\" as it integrates several existing FW variations to solve an optimal design problem computationally efficiently. But the extension is well-motivated and the proposed method performed empirically better than baselines. So I think it is a good contribution.", "other_comments_or_suggestions": "Typo in Sec.6.1: `form sampling (see ??)`", "questions_for_authors": "In Prop.2. I am curious why there is the extra additive d in the exponent. I checked that it also appears in Thm.6 in Mukherjee et al. (2024) (https://arxiv.org/pdf/2404.13895). Mukherjee et al. (2024) said that `This dependence is similar to Theorem 2 of Azizi et al. [6] for fixed-budget best-arm identification in", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Uuz6zDAnPl", "reviewer": "Reviewer_GkKM", "summary": "This paper investigates how to select the optimal data points to learn the ground-truth reward model in RLHF. Specifically, compared to previous work [1], this paper extends the result from learning the ranking of $K$ actions from $K$-way feedback to learning the ranking of $N\\geq K$ actions from $K$-way feedback.\n\n[1] Mukherjee, Subhojyoti, et al. \"Optimal design for human preference elicitation.\" Advances in Neural Information Processing Systems 37 (2024): 90132-90159.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n### **We Do Not Handle Multiple Lists**\n\nThis 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.\n\nIn 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).\n\n### **Additional Baselines**\n\nTo 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:\n\n* Dope is implemented using the Frank-Wolfe method where the linear maximization oracle (LMO) is a linear program.\n* 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.\n\nWe implemented DopeWolfe in their code base as follows:\n\n* LMO is solved greedily, as in (8), on 10% of randomly sampled subsets of items.\n* Line search is implemented using golden-section search.\n\nThe plots for the Anthropic and Nectar experiments are at [Anthropic plot](https://anonymous.4open.science/r/DopeWolfe-ICML-anon-1AD6/DopeWolfe_Anthropic_ICML_rebuttal.png) and [Nectar plot](https://anonymous.4open.science/r/DopeWolfe-ICML-anon-1AD6/DopeWolfe_Nectar_ICML_rebuttal.png), 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:\n\n* **Anthropic:** DopeWolfe is about $4$x times faster than Dope ($6.046$ seconds on average versus $24.924$).\n* **Nectar:** DopeWolfe is about $3$x times faster than Dope ($0.571$ seconds on average versus $1.826$).", "claims_and_evidence": "Yes. The proof sketch is clear and convincing to me.", "methods_and_evaluation_criteria": "The synthetic feedback and real feedback seem to be reasonable.", "theoretical_claims": "I checked the proof sketch in the main text but did not go through the proof in the appendix. The proof seemed to make sense according to the proof sketch in the main text.", "experimental_designs_or_analyses": "I've checked Section 6 and it sounds reasonable to me.", "relation_to_broader_scientific_literature": "This paper could complement previous papers about how to compute the ground-truth reward from a dataset of rankings, such as [2]. Specifically, the previous paper considers how to compute the reward form a given dataset, while this paper focuses on how to collect the data to make the computation efficient.\n\n[2] Zhu, Banghua, Michael Jordan, and Jiantao Jiao. \"Principled reinforcement learning with human feedback from pairwise or k-wise comparisons.\" International Conference on Machine Learning. PMLR, 2023.", "essential_references_not_discussed": "I do not find any essential references not discussed.", "other_strengths_and_weaknesses": "Compared to [1], this paper does not include the scenario when multiple lists exist.\n\n[1] Mukherjee, Subhojyoti, et al. \"Optimal design for human preference elicitation.\" Advances in Neural Information Processing Systems 37 (2024): 90132-90159.", "other_comments_or_suggestions": "There is a missing reference on lines 358-359.", "questions_for_authors": "Compared to [1], may you also compare the baselines including Dope, Avg Design, Clustered Design, and APO? Additionally, I would appreciate a comparison in the Anthropic dataset [3] used in [1].\n\nI would raise the score if the authors could provide additional experiments.\n\n[1] Mukherjee, Subhojyoti, et al. \"Optimal design for human preference elicitation.\" Advances in Neural Information Processing Systems 37 (2024): 90132-90159.\n\n[3] Bai, Yuntao, et al. \"Training a helpful and harmless assistant with reinforcement learning from human feedback.\" arXiv preprint arXiv:2204.05862 (2022).", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "y1pKTm2QAc", "reviewer": "Reviewer_Q6wK", "summary": "This paper considers an N-item-ranking problem with K-way comparisons, where K<<N. The goal is to determine the optimal K-subset selection strategy to minimize the worst-case ranking error. Previous approaches to this problem are computationally infeasible due to the exponentially large number to consider. To address this, the authors propose an improved Frank-Wolfe algorithm that incorporates randomization, memorization, and sparse updates, making the computation tractable.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\nWe 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](https://anonymous.4open.science/r/DopeWolfe-ICML-anon-1AD6/DopeWolfe_Anthropic_ICML_rebuttal.png). 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.", "claims_and_evidence": "The claims in the paper are thoroughly supported at both the theoretical and experimental levels.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "No mistakes were found in the proofs.", "experimental_designs_or_analyses": "The experiments include two small-scale text retrieval datasets and one LLM alignment dataset, along with multiple baselines, both synthetic and real feedback settings. The appendix also provides additional ablation experiments and runtime comparisons. I believe the experimental setup is thorough and reliable.", "relation_to_broader_scientific_literature": "The key contribution is related to the K-way feedback selection strategy in N-item ranking problems, which is highly relevant to RLHF and LLM alignment.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "**Strengths:**  \n- The paper is well-written, with a clear and rigorous logical structure. Despite the extensive mathematical theory, it remains easy to follow.  \n- The theoretical section is very thorough, with both theoretical and experimental evidence supporting the claims, making the results highly credible.  \n- The problem addressed by the paper is highly meaningful, and DopeWolfe makes the previously intractable algorithm with exponential computational complexity practically usable.  \n\n**Weaknesses:**  \n- If the paper included experiments on RLHF fine-tuning with LLMs, it would enhance the practical applicability and make the paper's findings more convincing.", "other_comments_or_suggestions": "- page 15, line 3, missing citation.\n- page 7, section 6.1, line 5, missing reference.", "questions_for_authors": "I have no questions.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: In the context of active object ranking, this study addresses the problem of ranking $ N $ objects based on $ K $-way feedback. In each interaction, the learner presents a subset of $ K $ objects from the $ N $ total objects, which the user then orders. After $ T $ interactions, a ranking of the $ N $ items is generated, and its effectiveness is evaluated using ranking loss. The main contributions of this paper are: (i) an elegant formulation based on D-optimal design, and (ii) an efficient solution with convergence guarantees, supported by empirical validation through a variant of the randomized Frank-Wolfe algorithm.

Reviewers have noted that the paper is well-written (although there are a few typos). The primary concern raised by the reviewers is the absence of empirical comparisons with additional benchmarks and baselines. However, the authors effectively addressed these concerns during the rebuttal phase by conducting additional experiments. 

In a revised version, I suggest including the authors' comments addressing the reviewers' concerns. Specifically, the experiments conducted on additional benchmarks and baselines (especially Dope) are informative. It would also be beneficial to discuss the overall complexity of the algorithm: while the per-iteration complexity is indeed low, the number of iterations required to ensure convergence is exponential in $ K $.
Decision: Accept (poster)