# Efficiently Learning Mixtures of Mallows Models

arXiv: https://arxiv.org/abs/1808.05731 · HTML: https://mlsanity.com/paper/1808.05731/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Aug 2018.

## Built on by (most cited first, 13 of 13)

- [Learning Multimodal Rewards from Rankings](https://mlsanity.com/paper/2109.12750/) (2021)
- [Mapping Social Choice Theory to RLHF](https://mlsanity.com/paper/2404.13038/) (2024)
- [Learning a Latent Simplex in Input-Sparsity Time](https://mlsanity.com/paper/2105.08005/) (2021)
- [On the identifiability of mixtures of ranking models](https://mlsanity.com/paper/2201.13132/) (2022)
- [Perfect Sampling from Pairwise Comparisons](https://mlsanity.com/paper/2211.12868/) (2022)
- [Statistical Depth Functions for Ranking Distributions: Definitions, Statistical Learning and Applications](https://mlsanity.com/paper/2201.08105/) (2022)
- [Efficient Algorithms for Sparse Moment Problems without Separation](https://mlsanity.com/paper/2207.13008/) (2022)
- [Subset Selection Based On Multiple Rankings in the Presence of Bias: Effectiveness of Fairness Constraints for Multiwinner Voting Score Functions](https://mlsanity.com/paper/2306.09835/) (2023)
- [Representative Ranking for Deliberation in the Public Sphere](https://mlsanity.com/paper/2503.18962/) (2025)
- [Robust Voting Rules from Algorithmic Robust Statistics](https://mlsanity.com/paper/2112.06380/) (2021)
- [Mallows Model with Learned Distance Metrics: Sampling and Maximum Likelihood Estimation](https://mlsanity.com/paper/2507.08108/) (2025)
- [Generalized Top-k Mallows Model for Ranked Choices](https://mlsanity.com/paper/2510.22040/) (2025)
- [MoPLEx: Estimating Plackett-Luce Mixture Models for Multi-Objective Alignment](https://mlsanity.com/paper/2608.25200/) (2026)

## Abstract (arXiv)

Mixtures of Mallows models are a popular generative model for ranking data coming from a heterogeneous population. They have a variety of applications including social choice, recommendation systems and natural language processing. Here we give the first polynomial time algorithm for provably learning the parameters of a mixture of Mallows models with any constant number of components. Prior to our work, only the two component case had been settled. Our analysis revolves around a determinantal identity of Zagier which was proven in the context of mathematical physics, which we use to show polynomial identifiability and ultimately to construct test functions to peel off one component at a time. To complement our upper bounds, we show information-theoretic lower bounds on the sample complexity as well as lower bounds against restricted families of algorithms that make only local queries. Together, these results demonstrate various impediments to improving the dependence on the number of components. They also motivate the study of learning mixtures of Mallows models from the perspective of beyond worst-case analysis. In this direction, we show that when the scaling parameters of the Mallows models have separation, there are much faster learning algorithms.