# Learning Lines with Ordinal Constraints

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Apr 2020.

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

- [The Complexity of Finding Local Optima in Contrastive Learning](https://mlsanity.com/paper/2509.16898/) (2025)
- [Provable Accuracy Collapse in Embedding-Based Representations under Dimensionality Mismatch](https://mlsanity.com/paper/2605.03346/) (2026)
- [Optimal VC Dimension of Contrastive Learning with Margin](https://mlsanity.com/paper/2609.38834/) (2026)

## Abstract (arXiv)

We study the problem of finding a mapping f from a set of points into the real line, under ordinal triple constraints. An ordinal constraint for a triple of points (u,v,w) asserts that |f(u)-f(v)|<|f(u)-f(w)|. We present an approximation algorithm for the dense case of this problem. Given an instance that admits a solution that satisfies (1-varepsilon)-fraction of all constraints, our algorithm computes a solution that satisfies (1-O(varepsilon1/8))-fraction of all constraints, in time O(n7) + (1/varepsilon)^O(1/varepsilon1/8) n.