Hypothesis Testing for Generalized Thurstone Models

AI summary

Overview

Research area: theoretical machine learning and statistics, specifically ranking from pairwise comparisons and hypothesis testing for generalized Thurstone models (GTMs).
Technical level: Advanced.
Scope: This paper develops a minimax hypothesis testing framework to decide whether pairwise comparison data is generated by a GTM (\mathcal{T}_F) for a given choice function (F), with graph-dependent bounds on the critical threshold.

What This Paper Is About

Pairwise comparison data, such as wins and losses or preference judgments, is often modeled by GTMs, where the probability that agent (i) is preferred over agent (j) is (F(w_i - w_j)) for latent utilities (w). Existing work mostly estimates GTM parameters or quantifies uncertainty, but does not rigorously test whether the data actually comes from a given GTM. This paper asks whether one can test (H_0): data comes from some GTM (\mathcal{T}_F) against (H_1): data comes from a pairwise comparison model that is not (\mathcal{T}_F), with a quantified separation from the GTM class.

Key Contributions

1. The paper frames the problem as a minimax composite hypothesis test and introduces a tractable separation distance to the class of all (\mathcal{T}_F) models, approximated in Theorem 3.1 by the distance to the best maximum-likelihood GTM fit.
2. It derives upper and lower bounds on the critical threshold for testing, depending on the topology of the observation graph, with tight results for complete graphs.
3. It proposes a hypothesis test based on the separation distance, establishes time-uniform type I and type II error probability bounds using reverse martingale techniques, and derives minimax lower bounds using information-theoretic methods.
4. It provides auxiliary results, including (\ell^2)-error bounds for parameter estimation in general pairwise comparison models (Theorem 3.3) and time-uniform confidence intervals under the null hypothesis (Proposition 3.8), and validates the theory on synthetic and real-world datasets.

Main Findings

• Complete graph threshold: For complete observation graphs, the critical threshold scales as (\Theta((nk)^{-1/2})), where (n) is the number of agents and (k) is the number of comparisons per pair. The upper bound is (O(1/\sqrt{nk})) and the lower bound is (\Omega(1/\sqrt{nk})).
• Graph-dependent bounds: Table 1 gives upper bounds of (O(1/\sqrt{nk})) for complete, (d)-regular, single cycle, and toroidal grid graphs. Lower bounds are (\Omega(1/\sqrt{nk})) for complete graphs, (\Omega(1/\sqrt{n^2 k})) for (d)-regular and single cycle graphs, and (\Omega(1/\sqrt{n^{7/4} k})) for toroidal grids.
• Tightness: The upper and lower bounds match for complete graphs, showing minimax optimal scaling up to constants. They also match in terms of (k) for other graph classes.
• Separation distance: Theorem 3.1 shows that the separation distance to (\mathcal{T}F) models is within constants of (|P - \mathsf{F}(w^*)|{\mathrm{F}}), where (w^*) is the maximum-likelihood GTM approximation in Equation 8.
• Test statistic: The proposed test splits the data, estimates (\hat{w}) on the first half, and computes a statistic (T) on the second half. (T) is an estimator of the squared Frobenius distance (|P - \mathsf{F}(w^*)|_{\mathrm{F}}^2). The test chooses (H_1) if (T > \gamma n/k) for

Authors’ abstract

In this work, we develop a hypothesis testing framework to determine whether pairwise comparison data is generated by an underlying \emph{generalized Thurstone model} $\mathcal{T}_F$ for a given choice function $F$. While prior work has predominantly focused on parameter estimation and uncertainty quantification for such models, we address the fundamental problem of minimax hypothesis testing for $\mathcal{T}_F$ models. We formulate this testing problem by introducing a notion of separation distance between general pairwise comparison models and the class of $\mathcal{T}_F$ models. We then derive upper and lower bounds on the critical threshold for testing that depend on the topology of the observation graph. For the special case of complete observation graphs, this threshold scales as $Θ((nk)^{-1/2})$, where $n$ is the number of agents and $k$ is the number of comparisons per pair. Furthermore, we propose a hypothesis test based on our separation distance, construct confidence intervals, establish time-uniform bounds on the probabilities of type I and II errors using reverse martingale techniques, and derive minimax lower bounds using information-theoretic methods. Finally, we validate our results through experiments on synthetic and real-world datasets.