# Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 51 references that are in the map.
- First posted on arXiv 29 Nov 2023.

## Builds on (most cited first, 7 of 7)

- [Minimum-Distortion Embedding](https://mlsanity.com/paper/2103.02559/) (2021)
- [Correlation Clustering with Sherali-Adams](https://mlsanity.com/paper/2207.10889/) (2022)
- [Multidimensional Scaling: Approximation and Complexity](https://mlsanity.com/paper/2109.11505/) (2021)
- [On Efficient Low Distortion Ultrametric Embedding](https://mlsanity.com/paper/2008.06700/) (2020)
- [Fitting Distances by Tree Metrics Minimizing the Total Error within a Constant Factor](https://mlsanity.com/paper/2110.02807/) (2021)
- [Scheduling with Communication Delays via LP Hierarchies and Clustering](https://mlsanity.com/paper/2004.09682/) (2020)
- [Metric embedding with outliers](https://mlsanity.com/paper/1508.03600/) (2015)

## Abstract (arXiv)

Metric embeddings are a widely used method in algorithm design, where generally a ``complex'' metric is embedded into a simpler, lower-dimensional one. Historically, the theoretical computer science community has focused on bi-Lipschitz embeddings, which guarantee that every pairwise distance is approximately preserved. In contrast, alternative embedding objectives that are commonly used in practice avoid bi-Lipschitz distortion; yet these approaches have received comparatively less study in theory. In this paper, we focus on Multi-dimensional Scaling (MDS), where we are given a set of non-negative dissimilarities di,ji,j∈ [n] over n points, and the goal is to find an embedding x1,dots,xn subset Rk that minimizes textrmOPT=minxmathbbEi,j∈ [n]left(1-frac|xi - xj|di,jright)2. Despite its popularity, our theoretical understanding of MDS is extremely limited. Recently, Demaine et. al. (arXiv:2109.11505) gave the first approximation algorithm with provable guarantees for this objective, which achieves an embedding in constant dimensional Euclidean space with cost textrmOPT +ε in n2· 2^textrmpoly(Delta/ε) time, where Delta is the aspect ratio of the input dissimilarities. For metrics that admit low-cost embeddings, Delta scales polynomially in n. In this work, we give the first approximation algorithm for MDS with quasi-polynomial dependency on Delta: for constant dimensional Euclidean space, we achieve a solution with cost O(log Delta)· textrmOPTOmega(1)+ε in time nO(1) · 2poly((log(Delta)/ε)). Our algorithms are based on a novel geometry-aware analysis of a conditional rounding of the Sherali-Adams LP Hierarchy, allowing us to avoid exponential dependency on the aspect ratio, which would typically result from this rounding.