Dimension-accuracy Tradeoffs In Contrastive Embeddings For Triplets, Terminals & Top-k Nearest Neighbors

Abstract

Metric embeddings traditionally study how to map \(n\) items to a target metric space such that distance lengths are not heavily distorted; but what if we only care to preserve the relative order of the distances (and not their length)? In this paper, we are motivated by the following basic question: given triplet comparisons of the form ``item \(i\) is closer to item \(j\) than to item \(k\),'' can we find low-dimensional Euclidean representations for the \(n\) items that respect those distance comparisons? Such order-preserving embeddings naturally arise in important applications and have been studied since the 1950s, under the name of ordinal or non-metric embeddings. Our main results are: 1. Nearly-Tight Bounds on Triplet Dimension: We introduce the natural concept of triplet dimension of a dataset, and surprisingly, we show that in order for an ordinal embedding to be triplet-preserving, its dimension needs to grow as \(\frac n2\) in the worst case. This is optimal (up to consta

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keychatziafratis2023dimension

Related papers

• Low-dimensional Data Embedding Via Robust Ranking (2016)0.00
• Order-preserving Dimension Reduction For Multimodal Semantic Embedding (2024)2.26
• Improving Deep Binary Embedding Networks By Order-aware Reweighting Of Triplets (2018)8.60
• Metric Learning In An RKHS (2025)0.00
• Fast Training Of Triplet-based Deep Binary Embedding Networks (2016)14.62
• A Quadruplet Loss For Enforcing Semantically Coherent Embeddings In Multi-output Classification Problems (2020)6.77
• Variance & Greediness: A Comparative Study Of Metric-learning Losses (2026)0.00
• Tcdesc: Learning Topology Consistent Descriptors (2020)0.00