Finite Sample Error Bounds for Ordinal Embedding

Ordinal embedding, also known as non-metric multidimensional scaling, aims to represent items as points in d-dimensional Euclidean space so that the distances between points agree as well as possible with a given set of ordinal comparisons such as item i is closer to item j than to item k. This classic problem is often used to quantify and/or visualize perceptual similarities. Recently, several authors have proposed a variety of algorithms for learning a metric embedding from ordinal information. There has also been some theoretical progress towards characterizing the consistency of ordinal embedding methods. For example, it has been shown that the correct embedding can be learned in limit as the number of items grows. However, a shortcoming of all prior work is the lack of prediction and embedding error bounds for problems involving a finite number of items. This talk addresses this problem, developing error bounds for ordinal embedding algorithms. The bounds explicitly show the dependence on the number of ordinal comparisons relative to the number of items and the dimension of the embedding.