Research map / Learning theory and algorithms / Sample complexity
Hypothesis Testing for Generalized Thurstone Models
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.
Develops a minimax hypothesis test for whether pairwise comparison data follows a generalized Thurstone model with a given choice function F, deriving separation-based critical thresholds (tight for complete graphs), time-uniform error bounds, and lower bounds.
Problem
Testing whether observed pairwise comparison data is generated by a generalized Thurstone model (GTM) with a known choice function F, a composite hypothesis problem for which no rigorously analyzed test existed.
Approach
Defines a Frobenius-norm separation distance between a general pairwise comparison model and the GTM class, approximates it by the distance to the MLE-fitted weights, and uses a sample-split unbiased-type statistic T with Chebyshev and reverse-martingale arguments for error control.
Key results
- For complete graphs the critical threshold satisfies epsilon_c^2 = O(1/(nk)) upper bound and Omega(1/(nk)) lower bound, matching up to constants.
- On LMSYS top-n models, about 10% of samples exceed the threshold at n small, while about 60% exceed it at n=21, and a top-9 group fits Thurstone well.
- Empirical 95th-percentile scaled threshold gamma stabilizes roughly constant in n and k for complete graphs.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed GTM test on complete rather than sparse observation graphs | GTM hypothesis testing · Complete graph versus d-regular graph, single cycle, and toroidal grid | critical threshold ε_c: Complete graph: O\left(\dfrac{1}{\sqrt{nk}}\right) upper bound and \Omega\left(\dfrac{1}{\sqrt{nk}}\right) lower bound | Helped |
| Use a d-regular observation graph instead of a complete graph | GTM hypothesis testing · d-regular graph | critical threshold ε_c lower bound: \Omega\left(\dfrac{1}{\sqrt{n^2 k}}\right) | Hurt |
| Use a single-cycle observation graph instead of a complete graph | GTM hypothesis testing · Single cycle | critical threshold ε_c lower bound: \Omega\left(\dfrac{1}{\sqrt{n^2 k}}\right) | Hurt |
| Use a toroidal-grid observation graph instead of a complete graph | GTM hypothesis testing · Toroidal grid | critical threshold ε_c lower bound: \Omega\left(\dfrac{1}{\sqrt{n^{7/4} k}}\right) | Hurt |
| Apply BTL and Thurstone models to larger groups of leaderboard models | Proposed GTM test · LMSYS chatbot leaderboard | samples above threshold: 10% to around 60% | Hurt |
| Fit the Thurstone model to top-9 batches rather than larger groups | Thurstone model · LMSYS chatbot leaderboard | fit to the model: top-9 | Helped |
Surprising findings
- The test remains valid for disconnected observation graphs even though parameter estimation is infeasible in that case.
Limitations
- Analysis assumes bounded dynamic range of pairwise probabilities and strong log-concavity of F on a bounded interval.
- Lower bounds for general graphs are not tight except for complete graphs and k-scaling; gaps remain for cycles and toroidal grids.
- Restricted to pairwise comparisons with fixed, a priori observation graph and independent data.
Experimental setup
Datasets: LMSYS chatbot arena pairwise comparisons synthetic GTM data
Benchmarks: LMSYS chatbot arena leaderboard comparisons
Metrics: scaled test statistic k*T/n 95th percentile threshold fraction of samples above threshold
Baselines: spectral method for BTL model
Builds on: Generalized Thurstone models Bradley-Terry-Luce model Ingster-Suslina method Hanson-Wright inequality
Closest papers by meaning
- Parameter Estimation for Generalized Thurstone Choice Models (ICML 2016 · similarity 0.90)
- Testing and Estimation of Contextual Generalized Thurstone Models (NeurIPS 2026 · similarity 0.89)
- A Unified Confidence Sequence for Generalized Linear Models, with Applications to Bandits (NeurIPS 2024 · similarity 0.83)
- Entropy testing and its application to testing Bayesian networks (NeurIPS 2024 · similarity 0.83)
- Binary Hypothesis Testing for Softmax Models and Leverage Score Models (ICML 2025 · similarity 0.82)
- Asymptotically Log-Optimal Bayes-Assisted Confidence Sequences for Bounded Means (NeurIPS 2026 · similarity 0.82)
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.