# Learning sparse mixtures of rankings from noisy information

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Nov 2018.

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

- [Robust Voting Rules from Algorithmic Robust Statistics](https://mlsanity.com/paper/2112.06380/) (2021)

## Abstract (arXiv)

We study the problem of learning an unknown mixture of k rankings over n elements, given access to noisy samples drawn from the unknown mixture. We consider a range of different noise models, including natural variants of the "heat kernel" noise framework and the Mallows model. For each of these noise models we give an algorithm which, under mild assumptions, learns the unknown mixture to high accuracy and runs in nO(log k) time. The best previous algorithms for closely related problems have running times which are exponential in k.