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.

本文提出了一种基于地标的策略，称为Landmark Ordinal Embedding（LOE），来解决现有的序数嵌入问题，通过利用潜在嵌入的低维度来平衡统计效率和计算效率，并在Bradley-Terry-Luce噪声模型下说明了LOE的统计一致性，并通过对计算复杂度进行严格分析，证明LOE在项目数量增加时明显比传统序数嵌入方法更高效。同时，本文还提出了一种实用的方法，利用LOE来热启动更具统计效率但计算代价较高的现有方法。

地标序数嵌入