Title: Efficiently Learning Mixtures of Mallows Models,
Abstract: 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.