Minimax-Optimal Inference and Rank-Breaking from Plackett-Luce Partial Rankings

A statistical estimation and rank-aggregation methodology (introduced by Bruce Hajek, Sewoong Oh, and Jiaming Xu in 2014) for inferring latent item parameters $\theta^* \in \Theta_b = \{\theta \in [-b,b]^n : \langle \theta, \mathbf{1}\rangle = 0\}$ under the Plackett–Luce (PL) random utility model ($U_i = \theta_i^* + Z_i$ with i.i.d. standard Gumbel noise $f(z) = e^{-(z+e^{-z})}$, equivalently sequential Luce choice $\mathbb{P}[\sigma_j \mid S_j] = \prod_{\ell=1}^{k_j-1} e^{\theta^*_{\sigma_j(\ell)}} / \sum_{r=\ell}^{k_j} e^{\theta^*_{\sigma_j(r)}}$) from $m$ partial rankings of subsets $S_j \subseteq [n]$ of size $k_j$. By coupling observed rankings to an oracle revealing exact Gumbel utilities $U_i$ and applying the multivariate van Trees Bayesian Cramér–Rao inequality with product prior $\mu_0(t) = (1+\cos(\pi t))/2$ ($I(\mu_0)=\pi^2$) and Gumbel location Fisher information $I(f)=1$, Theorem 1 establishes the non-asymptotic minimax lower bound $\inf_{\hat{\theta}}\sup_{\theta^*\in\Theta_b}\mathbb{E}[\|\hat{\theta}-\theta^*\|_2^2] \ge \frac{(n-1)^2}{2\sum_{j=1}^m k_j + 2n\pi^2/b^2}$. Theorem 2 proves that the constrained Plackett–Luce Maximum Likelihood Estimator $\hat{\theta}_{\mathrm{ML}} = \arg\max_{\theta\in\Theta_b}\mathcal{L}_{\mathrm{PL}}(\theta)$ achieves $\|\hat{\theta}_{\mathrm{ML}} - \theta^*\|_2 \le \frac{C e^{4b}\sqrt{n\log n + \frac{k_{\max}}{k_{\min}}\log^2 n}}{\sqrt{m k_{\mathrm{ave}}}}$ via strongly convex Hessian lower bounds $\lambda_2(H(\theta)) \ge \frac{1}{2e^{4b}} \lambda_2(L)$ on the hypergraph Laplacian $L = \sum_{j=1}^m \frac{1}{k_j}\sum_{i<i'\in S_j}(e_i-e_{i'})(e_i-e_{i'})^\top$ (Lemmas 1–2, Claim 1). Furthermore, comparing *Random Independence-Preserving Breaking* ($\lfloor k_j/2\rfloor$ disjoint pairs per ranking, Theorem 3) against *Full Breaking* (all $\binom{k_j}{2}$ pairs weighted by $1/(k_j-1)$ in the composite pairwise log-likelihood $\mathcal{L}_{\mathrm{FB}}(\theta)$, Definition 5, Equation 2, Theorem 4) proves that Full Breaking achieves the minimax-optimal $1/\sqrt{m k_{\mathrm{ave}}}$ rate despite dependent pairwise comparisons.