CaltechAUTHORS
  A Caltech Library Service

Landmark Ordinal Embedding

Ghosh, Nikhil and Chen, Yuxin and Yue, Yisong (2019) Landmark Ordinal Embedding. In: 33rd Conference on Neural Information Processing Systems. Neural Information Processing Systems Foundation, Inc. , Art. No. 9326. https://resolver.caltech.edu/CaltechAUTHORS:20200109-101416499

[img] PDF - Published Version
See Usage Policy.

755Kb
[img] PDF - Submitted Version
See Usage Policy.

3317Kb
[img] Archive (ZIP) - Supplemental Material
See Usage Policy.

3034Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20200109-101416499

Abstract

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.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
https://papers.nips.cc/paper/9326-landmark-ordinal-embeddingPublisherArticle
https://arxiv.org/abs/1910.12379arXivDiscussion Paper
ORCID:
AuthorORCID
Yue, Yisong0000-0001-9127-1989
Additional Information:© 2019 Neural Information Processing Systems Foundation, Inc. Nikhil Ghosh was supported in part by a Caltech Summer Undergraduate Research Fellowship. Yuxin Chen was supported in part by a Swiss NSF Early Mobility Postdoctoral Fellowship. This work was also supported in part by gifts from PIMCO and Bloomberg.
Funders:
Funding AgencyGrant Number
Caltech Summer Undergraduate Research Fellowship (SURF)UNSPECIFIED
Swiss National Science Foundation (SNSF)UNSPECIFIED
PIMCOUNSPECIFIED
Bloomberg Data ScienceUNSPECIFIED
Record Number:CaltechAUTHORS:20200109-101416499
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20200109-101416499
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:100591
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:09 Jan 2020 19:45
Last Modified:09 Jul 2020 21:53

Repository Staff Only: item control page