Research map / Learning theory and algorithms / Sample complexity

Ranking with Multiple Oracles: From Weak to Strong Stochastic Transitivity

ICML 2025 · Learning theory and algorithms › Sample complexity · approach: Sample complexity of ranking and selection

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 RMO-WST and RMO-SST, active algorithms that rank N items from multiple noisy pairwise oracles under weak and strong stochastic transitivity, with instance-dependent sample complexity bounds and a WST lower bound.

Problem

Efficiently recovering a full ranking of items from pairwise preference feedback provided by multiple oracles with heterogeneous accuracy, under weak (WST) or strong (SST) stochastic transitivity, with as few comparisons as possible.

Approach

Bi-level design: a high-level Probe-Max that repeatedly finds the maximal remaining item via transitive closure, and a low-level Compare/Try-Compare routine that adaptively allocates queries and eliminates less accurate oracles per pair, yielding hardness based on the multi-oracle harmonic-style measure H_ij rather than average-oracle hardness.

Key results

• RMO-WST achieves sample complexity eO(N * sum_i H_{σ^-1(i),σ^-1(i-1)}) and a matching WST lower bound eΩ(N^2 H_{σ^-1(1),σ^-1(2)}) is proved, answering an open question of Lou et al. (2022).
• RMO-SST achieves eO(sum_i H_i log log H_i + log(N/δ)), improving the best known SST bound of Saad et al. (2023) by a log N factor.
• In simulations, RMO-WST consistently uses fewer samples than the Probe-Max baseline across N up to 64 and M in {2,4,6} oracles.

Measured effects reported in the paper

Limitations

• Monotonicity/consistency assumption may not hold in general
• Experiments assume only one oracle is accurate; overhead if oracles have uniform accuracy
• Instance-dependent lower bound for WST remains open

Experimental setup

Benchmarks: simulated ranking environment with N in {2,...,64} items and M in {2,4,6} oracles

Metrics: sample complexity

Baselines: Probe-Max (Lou et al., 2022) with uniform random oracle choice Binary-Search (Saad et al., 2023) Iterative-Insertion-Ranking (Ren et al., 2019)

Builds on: Probe-Sort / Probe-Rank (Lou et al., 2022) Compare routine of Saad et al. (2023) Iterative-Insertion-Ranking (Ren et al., 2019)

Closest papers by meaning

• On Sample Complexity Upper and Lower Bounds for Exact Ranking from Noisy Comparisons (NeurIPS 2019 · similarity 0.90)
• Active Ranking without Strong Stochastic Transitivity (NeurIPS 2022 · similarity 0.89)
• Maxing and Ranking with Few Assumptions (NeurIPS 2017 · similarity 0.88)
• Beyond Kemeny Medians: Consensus Ranking Distributions. Definition, Properties and Statistical Learning (NeurIPS 2026 · similarity 0.85)
• Active Ranking and Matchmaking, with Perfect Matchings (ICML 2024 · similarity 0.85)
• Sampling for Beyond-Worst-Case Online Ranking (AAAI 2024 · similarity 0.85)