Poster
Landmark Ordinal Embedding
Nikhil Ghosh · Yuxin Chen · Yisong Yue

Tue Dec 10th 10:45 AM -- 12:45 PM @ East Exhibition Hall B + C #79
in Algorithms -- Similarity and Distance Learning »

In this paper, we aim to learn a low-dimensional Euclidean representation from a set of constraints of the form “item j is closer to item i than item k”. Existing approaches for this “ordinal embedding” problem require expensive optimization procedures, which cannot scale to handle increasingly larger datasets. To address this issue, we propose a landmark-based strategy, which we call Landmark Ordinal Embedding (LOE). Our approach trades off statistical efficiency for computational efficiency by exploiting the low-dimensionality of the latent embedding. We derive bounds establishing the statistical consistency of LOE under the popular Bradley- Terry-Luce noise model. Through a rigorous analysis of the computational complexity, we show that LOE is significantly more efficient than conventional ordinal embedding approaches as the number of items grows. We validate these characterizations empirically on both synthetic and real datasets. We also present a practical approach that achieves the “best of both worlds”, by using LOE to warm-start existing methods that are more statistically efficient but computationally expensive.

Keywords: Algorithms -> Similarity and Distance Learning · Algorithms -> Metric Learning; Algorithms -> Ranking and Preference Learning; Algorithms -> Representation Learning

Author Information

Nikhil Ghosh (UC Berkeley)
Yuxin Chen (UChicago)
Yisong Yue (Caltech)

More from the Same Authors