Learning RUMs: Reducing Mixture to Single Component via PCA
  We consider the problem of learning a mixture of Random Utility Models
(RUMs). Despite the success of RUMs in various domains and the versatility of
mixture RUMs to capture the heterogeneity in preferences, there has been only
limited progress in learning a mixture of RUMs from partial data such as
pairwise comparisons. In contrast, there have been significant advances in
terms of learning a single component RUM using pairwise comparisons. In this
paper, we aim to bridge this gap between mixture learning and single component
learning of RUM by developing a `reduction' procedure. We propose to utilize
PCA-based spectral clustering that simultaneously `de-noises' pairwise
comparison data. We prove that our algorithm manages to cluster the partial
data correctly (i.e., comparisons from the same RUM component are grouped in
the same cluster) with high probability even when data is generated from a
possibly {\em heterogeneous} mixture of well-separated {\em generic} RUMs. Both
the time and the sample complexities scale polynomially in model parameters
including the number of items. Two key features in the analysis are in
establishing (1) a meaningful upper bound on the sub-Gaussian norm for RUM
components embedded into the vector space of pairwise marginals and (2) the
robustness of PCA with missing values in the $L_{2, \infty}$ sense, which might
be of interest in their own right.
