Finite Sample Prediction and Recovery Bounds for Ordinal Embedding

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 $\mathbb{R}^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.

• Publication year

  2016

• Venue

  Neural Information Processing Systems

• Publication date

  2016-06-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1606.07081
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A Tight Bound of Hard Thresholding

  2016cited by this paper
• NEXT: A System for Real-World Development, Evaluation, and Application of Active Learning

  2015cited by this paper
• Preference Completion: Large-scale Collaborative Ranking from Pairwise Comparisons

  2015cited by this paper
• Some theory for ordinal embedding

  2015cited by this paper
• Sharp Time–Data Tradeoffs for Linear Inverse Problems

  2015cited by this paper
• An Introduction to Matrix Concentration Inequalities

  2015influential reference
• Local Ordinal Embedding

  2014cited by this paper
• Uniqueness of Ordinal Embedding

  2014cited by this paper
• Individualized rank aggregation using nuclear norm regularization

  2014cited by this paper
• Stochastic triplet embedding

  2012cited by this paper
• 1-Bit Matrix Completion

  2012cited by this paper
• Spectral Methods for Learning Multivariate Latent Tree Structure

  2011cited by this paper
• Low-dimensional embedding using adaptively selected ordinal data

  2011cited by this paper
• Learning Multi-modal Similarity

  2010cited by this paper
• Euclidean distance matrices: new characterization and boundary properties

  2009cited by this paper
• Generalized Non-metric Multidimensional Scaling

  2007cited by this paper
• Theory of classification : a survey of some recent advances

  2005cited by this paper
• Convex Optimization & Euclidean Distance Geometry

  2004cited by this paper
• Matrix analysis

  1985cited by this paper
• Nonmetric multidimensional scaling: A numerical method

  1964cited by this paper
• The analysis of proximities: Multidimensional scaling with an unknown distance function. II

  1962cited by this paper
• The analysis of proximities: Multidimensional scaling with an unknown distance function. I.

  1962cited by this paper

• LORE: Jointly Learning the Intrinsic Dimensionality and Relative Similarity Structure From Ordinal Data

  2026cites this paper
• Ordinal Embedding for Collaborative Filtering: A Unified Regularization for Enhanced Generalization and Interpretability

  2025cites this paper
• The Complexity of Finding Local Optima in Contrastive Learning

  2025cites this paper
• Uncovering the Computational Ingredients of Human-Like Representations in LLMs

  2025cites this paper
• People make mistakes: Obtaining accurate ground truth from continuous annotations of subjective constructs

  2024cites this paper
• Synthesis and perceptual scaling of high-resolution naturalistic images using Stable Diffusion

  2024cites this paper
• Metric Learning from Limited Pairwise Preference Comparisons

  2024cites this paper
• cblearn: Comparison-based Machine Learning in Python

  2024cites this paper
• Dimensions underlying the representational alignment of deep neural networks with humans

  2024cites this paper
• Representer Theorems for Metric and Preference Learning: Geometric Insights and Algorithms

  2023cites this paper
• Tight and fast generalization error bound of graph embedding in metric space

  2023cites this paper
• Theoretical Foundations of Ordinal Multidimensional Scaling, Including Internal and External Unfolding

  2023cites this paper
• Stability of Sequential Lateration and of Stress Minimization in the Presence of Noise

  2023cites this paper
• Dimension-Accuracy Tradeoffs in Contrastive Embeddings for Triplets, Terminals & Top-k Nearest Neighbors

  2023cites this paper
• Triplet Reconstruction and all other Phylogenetic CSPs are Approximation Resistant

  2022cites this paper
• Phylogenetic CSPs are Approximation Resistant

  2022cites this paper
• Estimating the perceived dimension of psychophysical stimuli using triplet accuracy and hypothesis testing

  2022cites this paper
• Recovering a Metric from Its Full Ordinal Information

  2022cites this paper
• Semantic Similarity of Social Functional Smiles and Laughter

  2022cites this paper
• One for All: Simultaneous Metric and Preference Learning over Multiple Users

  2022cites this paper
• On Position Embeddings in BERT O N P OSITION E MBEDDINGS IN BERT

  2021cites this paper
• Learning Ordinal Embedding from Sets

  2021cites this paper
• On Position Embeddings in BERT

  2021cites this paper
• Generalization Error Bound for Hyperbolic Ordinal Embedding

  2021influential citation
• Elliptical Ordinal Embedding

  2021cites this paper
• Comparison-based centrality measures

  2021cites this paper
• Optimal Clustering in Stable Instances Using Combinations of Exact and Noisy Ordinal Queries

  2021cites this paper
• Two Simple Ways to Learn Individual Fairness Metrics from Data

  2020cites this paper
• Improved Confidence Bounds for the Linear Logistic Model and Applications to Linear Bandits

  2020cites this paper
• Greedy <inline-formula><tex-math notation="LaTeX">$k$</tex-math></inline-formula>-Center From Noisy Distance Samples

  2020cites this paper
• Improved Confidence Bounds for the Linear Logistic Model and Applications to Bandits

  2020cites this paper
• Near-Optimal Comparison Based Clustering

  2020influential citation
• Simultaneous Preference and Metric Learning from Paired Comparisons

  2020cites this paper
• Statistical and Computational Rates in Graph Logistic Regression

  2020cites this paper
• City-SAFE: Estimating Urban Safety Perception

  2019cites this paper
• Generating Labels for Regression of Subjective Constructs using Triplet Embeddings

  2019influential citation
• Convergence rates for ordinal embedding

  2019cites this paper
• Bluetooth Based Indoor Localization Using Triplet Embeddings

  2019influential citation
• Learning to Search Efficiently Using Comparisons

  2019cites this paper
• Comparison-Based Framework for Psychophysics: Lab versus Crowdsourcing

  2019cites this paper
• Seeker: Real-Time Interactive Search

  2019cites this paper
• Learning Nearest Neighbor Graphs from Noisy Distance Samples

  2019cites this paper
• Scaling Up Ordinal Embedding: A Landmark Approach

  2019influential citation
• Uncertainty Estimates for Ordinal Embeddings

  2019cites this paper
• Optimal estimation in high-dimensional and nonparametric models

  2019cites this paper
• Estimation of perceptual scales using ordinal embedding

  2019cites this paper
• Landmark Ordinal Embedding

  2019influential citation
• Active Ordinal Querying for Tuplewise Similarity Learning

  2019cites this paper
• Scalable and Efficient Comparison-based Search without Features

  2019cites this paper
• Fast Stochastic Ordinal Embedding With Variance Reduction and Adaptive Step Size

  2019cites this paper
• Large scale representation learning from triplet comparisons

  2019cites this paper
• Efficient Data Analytics on Augmented Similarity Triplets

  2019cites this paper
• Diversity and Novelty: Measurement, Learning and Optimization

  2019cites this paper
• Insights into Ordinal Embedding Algorithms: A Systematic Evaluation

  2019influential citation
• Large scale ordinal embedding: training neural networks with structure-free inputs

  2019cites this paper
• On the estimation of latent distances using graph distances

  2018cites this paper
• Contrastive Learning from Pairwise Measurements

  2018influential citation
• Foundations of Comparison-Based Hierarchical Clustering

  2018influential citation
• Boosting for Comparison-Based Learning

  2018influential citation
• Fusing Annotations with Majority Vote Triplet Embeddings

  2018cites this paper
• The Landscape of Non-Convex Quadratic Feasibility

  2018cites this paper
• Optimal link prediction with matrix logistic regression

  2018cites this paper
• As you like it: Localization via paired comparisons

  2018cites this paper
• Robust Ordinal Embedding from Contaminated Relative Comparisons

  2018influential citation
• Less but Better: Generalization Enhancement of Ordinal Embedding via Distributional Margin

  2018cites this paper
• Adaptive Hierarchical Clustering Using Ordinal Queries

  2017influential citation
• Learning Low-Dimensional Metrics

  2017cites this paper
• Ranking ideas for diversity and quality

  2017cites this paper
• Comparison-Based Nearest Neighbor Search

  2017cites this paper
• Machine learning in a setting of ordinal distance information

  2017influential citation
• NEXT: A system to easily connect crowdsourcing and adaptive data collection

  2017cites this paper
• Stochastic Non-convex Ordinal Embedding with Stabilized Barzilai-Borwein Step Size

  2017cites this paper
• Kernel functions based on triplet comparisons

  2016cites this paper
• Ordinal Embedding with a Latent Factor Model

  2016cites this paper
• Lens Depth Function and k-Relative Neighborhood Graph: Versatile Tools for Ordinal Data Analysis

  2016influential citation
• Generalization Error Bounds for Graph Embedding Using Negative Sampling: Linear vs Hyperbolic

  year unknowninfluential citation