Metric Learning from Limited Pairwise Preference Comparisons
Zhi Wang Geelon So Ramya Korlakai Vinayak
We study metric learning from preference comparisons under the ideal point
model, in which a user prefers an item over another if it is closer to their
latent ideal item. These items are embedded into $\mathbb{R}^d$ equipped with
an unknown Mahalanobis distance shared across users. While recent work shows
that it is possible to simultaneously recover the metric and ideal items given
$\mathcal{O}(d)$ pairwise comparisons per user, in practice we often have a
limited budget of $o(d)$ comparisons. We study whether the metric can still be
recovered, even though it is known that learning individual ideal items is now
no longer possible. We show that in general, $o(d)$ comparisons reveals no
information about the metric, even with infinitely many users. However, when
comparisons are made over items that exhibit low-dimensional structure, each
user can contribute to learning the metric restricted to a low-dimensional
subspace so that the metric can be jointly identified. We present a
divide-and-conquer approach that achieves this, and provide theoretical
recovery guarantees and empirical validation.