Research map / Learning theory and algorithms / Prediction and decision losses

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

ICML 2025 · Learning theory and algorithms › Prediction and decision losses · approach: Ranking models from comparisons

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes DopeWolfe, a randomized Frank-Wolfe method that solves a D-optimal design over all K-subsets for active learning of Plackett-Luce rankings from K-way human feedback, avoiding the exponential cost of the full linear maximization oracle.

Problem

Learning human preference rankings of N items from limited K-way comparison feedback (K << N) requires choosing informative K-subsets, but the D-optimal design over all C(N,K) subsets is exponentially costly to solve exactly.

Approach

Solve the D-optimal design of Plackett-Luce feedback with Frank-Wolfe whose linear maximization oracle is restricted to a uniformly random subcollection of R subsets per iteration, combined with cached pair gradients, golden-section line search, and low-rank inverse/logdet updates; the analysis extends randomized FW to log-homogeneous self-concordant barrier objectives.

Key results

• On synthetic feedback, DopeWolfe achieves lower ranking loss than Uniform, DBSCAN and m-medoids across K=2,3 and T=100 to 1000 on BEIR-COVID, TREC-DL and NECTAR, with reported order-of-magnitude sample reductions on NECTAR.
• On BEIR-COVID with K=3 (161,700 subsets), DopeWolfe with 1000 FW iterations ran in 1646.70 s versus 4927.38 s total for the DBSCAN sweep; about 100 iterations took 164.67 s.
• On real feedback with N=100 and K up to 10 (about 17 trillion subsets), DopeWolfe using 10^5 sampled subsets outperforms Uniform sampling in ranking loss.

Measured effects reported in the paper

Surprising findings

• Randomizing the linear maximization oracle slows the theoretical convergence by a factor of N-choose-K over R, yet the authors observe no such degradation in practice.
• DBSCAN is equal to or worse than uniform sampling in several synthetic setups.

Limitations

• Ranking loss upper bound has an O(d^2) dependence that is suboptimal, noted by the authors.
• Experiments use simulated feedback from a PL model on real datasets; real-world human noise is not studied, and real feedback experiments use noiseless fixed rankings.
• Theoretical convergence of randomized FW is slower by a factor C(N,K)/R, with no degradation observed only empirically.

Experimental setup

Datasets: BEIR-COVID TREC-DL NECTAR

Benchmarks: BEIR-COVID TREC-DL NECTAR

Metrics: ranking loss (Kendall tau distance) NDCG run time

Baselines: Uniform sampling DBSCAN m-medoids

Builds on: Frank-Wolfe method Plackett-Luce model D-optimal design randomized Frank-Wolfe

Closest papers by meaning

• Preference-based Reinforcement Learning beyond Pairwise Comparisons: Benefits of Multiple Options (NeurIPS 2025 · similarity 0.88)
• A Minimaximalist Approach to Reinforcement Learning from Human Feedback (ICML 2024 · similarity 0.88)
• Comparing Comparisons: Informative and Easy Human Feedback with Distinguishability Queries (ICML 2025 · similarity 0.87)
• Bayesian Optimization from Human Feedback: Near-Optimal Regret Bounds (ICML 2025 · similarity 0.87)
• Capturing Individual Human Preferences with Reward Features (NeurIPS 2025 · similarity 0.87)
• Making RL with Preference-based Feedback Efficient via Randomization (ICLR 2024 · similarity 0.87)