Sampling from ranking models via a hit and run approach

Music City Center 

The Mallows permutation model is a prominent model for ranking data, which are prevalent in diverse fields such as recommender systems, psychology, and electoral studies. This model specifies a family of non-uniform probability distributions on permutations, defined via a distance metric on permutations. We focus on two common choices: the L1 distance (Spearman's footrule) and the L2 distance (Spearman's rank correlation). Despite their popularity, these models present a significant computational challenge due to the intractability of their normalizing constants, hindering off-the-shelf sampling and inference methods. We develop and analyze hit and run Markov chain Monte Carlo algorithms for sampling from these Mallows models. For both models, we establish order log(n) mixing time upper bounds, providing the first theoretical guarantees for efficient sampling. The convergence analysis employs novel couplings for permutations with one-sided restrictions and leverages the path coupling technique. These advancements enable efficient Monte Carlo maximum likelihood estimation, facilitating scalable inference for ranking data with statistical guarantees.

Mallows permutation model

ranking data

hit and run algorithm

Markov chain Monte Carlo

mixing time

scalable inference 

IMS