Minimax-optimal Inference from Partial Rankings
Authors: Bruce Hajek, Sewoong Oh, Jiaming Xu
NeurIPS 2014 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | 2.5 Numerical experiments Suppose there are n = 1024 items and θ is uniformly distributed over [ b, b]. We first generate d full rankings over 1024 items according to the PL model with parameter θ . Then for each fixed k {512, 256, . . . , 2}, we break every full ranking σ into n/k partial rankings over subsets of size k as follows: Let {Sj}n/k j=1 denote a partition of [n] generated uniformly at random such that Sj Sj = for j = j and |Sj| = k for all j; generate {σj}n/k j=1 such that σj is the partial ranking over set Sj consistent with σ. In this way, in total we get m = dn/k k-way comparisons which are all independently generated from the PL model. We apply the minorization-maximization (MM) algorithm proposed in [7] to compute the ML estimator bθML based on the k-way comparisons and the estimator bθFB based on the pairwise comparisons induced by the FB. The estimation error is measured by the rescaled mean square error (MSE) defined by log2 mk n2 bθ θ 2 2 . We run the simulation with b = 2 and d = 16, 64. The results are depicted in Fig. 1. We also plot the Cram er-Rao (CR) limit given by log2 1 1 l 1 as per Theorem 2. The oracle lower bound in Theorem 1 implies that the rescaled MSE is at least 0. We can see that the rescaled MSE of the ML estimator bθML is close to the CR limit and approaches the oracle lower bound as k becomes large, suggesting the ML estimator is minimax-optimal. Furthermore, the rescaled MSE of bθFB under FB is approximately twice larger than the CR limit, suggesting that the FB is minimax-optimal up to a constant factor. |
| Researcher Affiliation | Academia | Bruce Hajek UIUC b-hajek@illinois.edu Sewoong Oh UIUC swoh@illinois.edu Jiaming Xu UIUC jxu18@illinois.edu |
| Pseudocode | No | The information is insufficient. The paper does not contain any structured pseudocode or algorithm blocks. |
| Open Source Code | No | The information is insufficient. The paper does not provide any concrete access to source code (e.g., a specific repository link, explicit code release statement, or code in supplementary materials) for the methodology described. |
| Open Datasets | No | The information is insufficient. The paper mentions the 'Netflix challenge dataset' as an example but states that for their rigorous study, they 'assume that users provide partial rankings over subsets of items generated according to the popular Plackett Luce (PL) model', indicating they generated synthetic data for their experiments, not used a publicly accessible dataset. There is no link, DOI, or formal citation for a dataset used in their experiments. |
| Dataset Splits | No | The information is insufficient. The paper describes generating synthetic data for numerical experiments (e.g., 'generate d full rankings', 'break every full ranking into n/k partial rankings') but does not specify any train/validation/test dataset splits, percentages, or methodology for data partitioning for reproducibility. |
| Hardware Specification | No | The information is insufficient. The paper describes running numerical simulations but does not provide any specific hardware details such as GPU/CPU models, processor types, or memory amounts used for the experiments. |
| Software Dependencies | No | The information is insufficient. The paper mentions using the 'minorization-maximization (MM) algorithm proposed in [7]' but does not provide specific software details like programming languages with versions, library names with version numbers, or solver versions needed to replicate the experiment environment. |
| Experiment Setup | Yes | Suppose there are n = 1024 items and θ is uniformly distributed over [ b, b]. We first generate d full rankings over 1024 items according to the PL model with parameter θ . Then for each fixed k {512, 256, . . . , 2}, we break every full ranking σ into n/k partial rankings over subsets of size k as follows: [...] We run the simulation with b = 2 and d = 16, 64. |