Research map / Learning theory and algorithms / Sample complexity
Minimax Rate for Learning From Pairwise Comparisons in the BTL Model
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace unweighted least squares on log-ratios with weighted least squares using empirically estimated variances (WLSM) | BTL weight estimation · Simulations on 2D grid, 3D grid, Erdos-Renyi graphs | sine(W_hat, w): gains of only a few percent | Helped |
| Use eigenvector-based estimator (Negahban et al.) instead of least-squares-based WLSM | BTL weight estimation · Line graph with complete bipartite gadget (Figure 2) | |W3 - W5| estimation difference: WLSM outperforms by about an order of magnitude | Hurt |
| Use eigenvector-based estimator instead of least-squares methods on 3D grid | BTL weight estimation · 3D grid | sine(W_hat, w) | No clear effect |
Closest papers by meaning
- A Simple and Adaptive Learning Rate for FTRL in Online Learning with Minimax Regret of $\Theta(T^{2/3})$ and its Application to Best-of-Both-Worlds (NeurIPS 2024 · similarity 0.85)
- Hypothesis Testing for Generalized Thurstone Models (ICML 2025 · similarity 0.84)
- Comparing Few to Rank Many: Active Human Preference Learning Using Randomized Frank-Wolfe Method (ICML 2025 · similarity 0.84)
- Binary Hypothesis Testing for Softmax Models and Leverage Score Models (ICML 2025 · similarity 0.84)
- Generalizing while preserving monotonicity in comparison-based preference learning models (NeurIPS 2025 · similarity 0.84)
- Preference-based Reinforcement Learning beyond Pairwise Comparisons: Benefits of Multiple Options (NeurIPS 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.