Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams

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.