Abstract
In this paper, we aim to learn a low-dimensional Euclidean representationfrom 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 expensiveoptimization procedures, which cannot scale to handle increasingly largerdatasets. To address this issue, we propose a landmark-based strategy, which wecall Landmark Ordinal Embedding (LOE). Our approach trades off statisticalefficiency for computational efficiency by exploiting the low-dimensionality ofthe latent embedding. We derive bounds establishing the statistical consistencyof LOE under the popular Bradley-Terry-Luce noise model. Through a rigorousanalysis of the computational complexity, we show that LOE is significantlymore efficient than conventional ordinal embedding approaches as the number ofitems grows. We validate these characterizations empirically on both syntheticand real datasets. We also present a practical approach that achieves the "bestof both worlds", by using LOE to warm-start existing methods that are morestatistically efficient but computationally expensive.