  This work concerns learning probabilistic models for ranking data in a
heterogeneous population. The specific problem we study is learning the
parameters of a Mallows Mixture Model. Despite being widely studied, current
heuristics for this problem do not have theoretical guarantees and can get
stuck in bad local optima. We present the first polynomial time algorithm which
provably learns the parameters of a mixture of two Mallows models. A key
component of our algorithm is a novel use of tensor decomposition techniques to
learn the top-k prefix in both the rankings. Before this work, even the
question of identifiability in the case of a mixture of two Mallows models was
unresolved.
