# Finite Sample Prediction and Recovery Bounds for Ordinal Embedding

arXiv: https://arxiv.org/abs/1606.07081 · HTML: https://mlsanity.com/paper/1606.07081/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Jun 2016.

## Built on by (most cited first, 12 of 12)

- [Dimensions underlying the representational alignment of deep neural networks with humans](https://mlsanity.com/paper/2406.19087/) (2024)
- [Generalization Error Bound for Hyperbolic Ordinal Embedding](https://mlsanity.com/paper/2105.10475/) (2021)
- [One for All: Simultaneous Metric and Preference Learning over Multiple Users](https://mlsanity.com/paper/2207.03609/) (2022)
- [Metric Learning from Limited Pairwise Preference Comparisons](https://mlsanity.com/paper/2403.19629/) (2024)
- [Evaluating Steering Techniques using Human Similarity Judgments](https://mlsanity.com/paper/2505.19333/) (2025)
- [Tight and fast generalization error bound of graph embedding in metric space](https://mlsanity.com/paper/2305.07971/) (2023)
- [The Complexity of Finding Local Optima in Contrastive Learning](https://mlsanity.com/paper/2509.16898/) (2025)
- [Uncovering the Computational Ingredients of Human-Like Representations in LLMs](https://mlsanity.com/paper/2510.01030/) (2025)
- [Elliptical Ordinal Embedding](https://mlsanity.com/paper/2105.10457/) (2021)
- [Representer Theorems for Metric and Preference Learning: Geometric Insights and Algorithms](https://mlsanity.com/paper/2304.03720/) (2023)
- [Synthesis and Perceptual Scaling of High Resolution Naturalistic Images Using Stable Diffusion](https://mlsanity.com/paper/2410.13034/) (2024)
- [LORE: Jointly Learning the Intrinsic Dimensionality and Relative Similarity Structure From Ordinal Data](https://mlsanity.com/paper/2602.04192/) (2026)

## Abstract (arXiv)

The goal of ordinal embedding is to represent items as points in a low-dimensional Euclidean space given a set of constraints in the form of distance comparisons like "item i is closer to item j than item k". Ordinal constraints like this often come from human judgments. To account for errors and variation in judgments, we consider the noisy situation in which the given constraints are independently corrupted by reversing the correct constraint with some probability. This paper makes several new contributions to this problem. First, we derive prediction error bounds for ordinal embedding with noise by exploiting the fact that the rank of a distance matrix of points in ℝd is at most d+2. These bounds characterize how well a learned embedding predicts new comparative judgments. Second, we investigate the special case of a known noise model and study the Maximum Likelihood estimator. Third, knowledge of the noise model enables us to relate prediction errors to embedding accuracy. This relationship is highly non-trivial since we show that the linear map corresponding to distance comparisons is non-invertible, but there exists a nonlinear map that is invertible. Fourth, two new algorithms for ordinal embedding are proposed and evaluated in experiments.