# A quasi-polynomial time algorithm for
Multi-Dimensional Scaling via LP hierarchies

Ainesh Bakshi
MIT  Vincent Cohen-Addad
Google Research  Samuel B. Hopkins
MIT  Rajesh Jayaram
Google Research  Silvio Lattanzi
Google Research

###### Abstract

Multi-dimensional Scaling (MDS) is a family of methods for embedding pair-wise
dissimilarities between $n$ objects into low-dimensional space. MDS is widely
used as a data visualization tool in the social and biological sciences,
statistics, and machine learning. We study the Kamada-Kawai formulation of
MDS: given a set of non-negative dissimilarities $\\{d_{i,j}\\}_{i,j\in[n]}$
over $n$ points, the goal is to find an embedding
$\\{x_{1},\dots,x_{n}\\}\subset\mathbbm{R}^{k}$ that minimizes

$\textsf{OPT}=\min_{x}\mathop{\mathbb{E}}_{i,j\in[n]}\left[\left(1-\frac{\|x_{i}-x_{j}\|}{d_{i,j}}\right)^{2}\right]$

Despite its popularity, our theoretical understanding of MDS is extremely
limited. Recently, Demaine, Hesterberg, Koehler, Lynch, and Urschel [DHK+21]
gave the first approximation algorithm with provable guarantees for Kamada-
Kawai, which achieves an embedding with cost $\textsf{OPT}+\varepsilon$ in
$n^{2}\cdot 2^{\tilde{\mathcal{O}}(k\Delta^{4}/\varepsilon^{2})}$ time, where
$\Delta$ is the aspect ratio of the input dissimilarities. In this work, we
give the first approximation algorithm for MDS with quasi-polynomial
dependency on $\Delta$: for target dimension $k$, we achieve a solution with
cost $\mathcal{O}(\textsf{OPT}^{\hskip
2.8903pt1/k}\cdot\log(\Delta/\varepsilon))+\varepsilon$ in time
$n^{\mathcal{O}(1)}\cdot
2^{\tilde{\mathcal{O}}(k^{2}(\log(\Delta)/\varepsilon)^{k/2+1})}$.

Our approach is based on a novel analysis of a conditioning-based rounding
scheme for the Sherali-Adams LP Hierarchy. Crucially, our analysis exploits
the geometry of low-dimensional Euclidean space, allowing us to avoid an
exponential dependence on the aspect ratio $\Delta$. We believe our geometry-
aware treatment of the Sherali-Adams Hierarchy is an important step towards
developing general-purpose techniques for efficient metric optimization
algorithms.

###### Contents

  1. 1 Introduction
    1. 1.1 Related Work
  2. 2 Preliminaries
  3. 3 Main Algorithm and Analysis
    1. 3.1 Analysis setup and pseudo-deviations
    2. 3.2 Bounding quantiles of pseudo-expected distances
    3. 3.3 Proof of Main Theorem
  4. 4 Proofs of Distance-Quantile Lemmas
    1. 4.1 Quantiles of pair-wise distances on the line – proof of Lemma 3.7
    2. 4.2 Translating between pseudo-expected distances and optimal quantiles
  5. 5 Remaining Proofs: Variance Reduction and Discretization
    1. 5.1 Variance Reduction via Conditioning
    2. 5.2 Discretization
  6. 6 Dimension Reduction for Kamada-Kawai
  7. 7 Implementation with poly(n)-size LP
  8. 8 Open Problems
  9. 9 Additional Related Work

##  1 Introduction

Given a set of pairwise dissimilarity scores $d_{ij}>0$ among $n$ objects, the
goal of multi-dimensional scaling (MDS) is to find a low-dimensional
embedding, denoted by vectors $x_{1},\ldots,x_{n}\in\mathbbm{R}^{k}$ such that
$d_{ij}\approx\|x_{i}-x_{j}\|$. MDS dates to at least the 1950s and has since
seen many uses: e.g., feature extraction for downstream machine learning
tasks, dimension reduction, data visualization (especially if $k=2$), and
graph drawing (if $d_{ij}$ is the shortest-path metric in a graph) – see the
extensive references in [Kru64, KW78, Tor52, dLH82, BG05, DIM01]. MDS is built
into several popular programming languages and packages, including Matlab, R,
and scikit-learn.

Unlike other dimension-reduction and data visualization methods, such as
principal component analysis (PCA), which have received extensive attention in
theoretical computer science, the input to MDS need not correspond to a
metric. Even in the special case where it does correspond to a high-
dimensional Euclidean metric – i.e. the setting where linear projection based
methods like Johnson-Lindenstrauss embeddings (JL) and PCA would apply – MDS
can discover non-linear embeddings of a high-dimensional metric into low
dimensions.

MDS in practice is typically performed via gradient descent or other local
search methods on one of a few objective functions. In this work, we study one
of the canonical objective functions, the Kamada-Kawai objective [KK+89]:

$\min_{x_{1},\ldots,x_{n}\in\mathbbm{R}^{k}}\hskip
7.22743pt\mathop{\mathbb{E}}_{i\neq
j\in[n]}\left[\left(1-\frac{\|x_{i}-x_{j}\|}{d_{ij}}\right)^{2}\right]\,.$

Kamada-Kawai measures the mean-squared distance between multiplicative
distortion and $1$. For normalization, note that placing all $x_{i}$ at the
same point gives objective value $1$, so for any input
$\\{d_{ij}\\}_{i,j\in[n]}$, the optimum value $\textsf{OPT}\in[0,1]$.

Kamada-Kawai is especially popular as a tool for force-directed graph drawing
in the social and medical sciences. For instance, the Kamada-Kawai objective
has been used to visualize the spread of obesity and the dynamics of smoking
in social networks [CF07, CF08], for mapping the structural core of the human
cerebral cortex [HCG+08] and identifying intellectual turning points in
theoretical physics [Che04].

Despite widespread use in practice, we are aware of only two works giving
algorithms with provable approximation guarantees for MDS. Bartal, Fandina,
and Neiman [BFN19] observe that many MDS objectives become convex
(semidefinite) programs if we ask to embed in $n$ dimensions – this is true in
particular for Kamada-Kawai. A simple Johnson-Lindenstrauss-style analysis
shows that randomly projecting an $n$-dimensional Kamada-Kawai solution,
obtained via semidefinite programming, to $k$ dimensions incurs an additive
$O(1/k)$ loss in objective value. Thus, we can obtain a solution with cost
$\textsf{OPT}+O(1/k)$ in polynomial time. But this algorithm lacks any
guarantee when $k$ is a small constant, e.g. $k=1,2,3$.

Demaine, Hesterberg, Koehler, Lynch, and Urschel give an algorithm that
retains provable guarantees for small $k$, at the expense of much slower
running time [DHK+21]. We associate an important parameter to
$\\{d_{ij}\\}_{i,j\in[n]}$: let

$\Delta=\frac{\max_{i,j\in[n]}d_{ij}}{\min_{i,j\in[n]}d_{ij}}$

measure the aspect ratio of the dissimilarities. [DHK+21] gives a PTAS for
small aspect ratio ($\Delta$).

######  Theorem 1.1 (PTAS for bounded aspect ratio [DHK+21]).

For every $\varepsilon>0$ there is an algorithm with running time
$n^{2}\cdot(\Delta/\varepsilon)^{\tilde{O}(k\cdot\Delta^{4}/\varepsilon^{2})}$
which gives an $\textsf{OPT}+\varepsilon$ approximation to Kamada-Kawai.

The algorithm of [DHK+21] is polynomial-time for $\Delta$ as large as
$\approx(\log n)^{1/4}$. For large-enough $\Delta$, [DHK+21] shows that the
additive PTAS becomes a multiplicative PTAS, at the additional cost of a
factor $\varepsilon^{-O(k)}$ in the exponent, by lower-bounding OPT. To prove
Theorem 1.1, [DHK+21] reduces the MDS problem to a generalized dense
constraint satisfaction problem (CSP), then uses a PTAS for such problems
[MS08a, YZ14, BRS11]. Concretely, [DHK+21] appeals to a by-now classical fact:

######  Fact 1.2 (See e.g. [MS08a]).

Let $\Omega$ be a finite set and $f_{ij}\hskip 3.61371pt:\hskip
3.61371pt\Omega\times\Omega\rightarrow[-M,M]$ be $\binom{n}{2}$ cost
functions. There is an algorithm with running time
$n^{2}|\Omega|^{O(M^{2}/\varepsilon^{2})}$ which returns
$x_{1},\ldots,x_{n}\in\Omega$ such that

$\operatorname*{\mathbb{E}}_{i,j\in[n]}f_{ij}(x_{i},x_{j})\leqslant\min_{x_{1}^{*},\ldots,x_{n}^{*}\in\Omega}\operatorname*{\mathbb{E}}_{i,j}f_{ij}(x_{i}^{*},x_{j}^{*})+\varepsilon\,.$

Modulo some details about discretizing $\mathbbm{R}^{k}$ into a finite set
$\Omega$, Fact 1.2 quickly implies Theorem 1.1 by taking
$f_{ij}=\left(1-\tfrac{\|x_{i}-x_{j}\|}{d_{ij}}\right)^{2}$. Furthermore, the
guarantees of Fact 1.2, in particular the exponential dependence on
$M^{2}/\varepsilon^{2}$, are widely believed to be tight for CSPs [JKR19,
MR16]. Thus, improving on Theorem 1.1 for Kamada-Kawai likely requires
exploiting MDS-specific structure, which is ignored by the reduction to CSPs.
We obtain significantly faster algorithms by exploiting the low-dimensional
metric structure of MDS.

#### Our results.

We give an almost-exponential improvement on the running time compared to
[DHK+21] with respect to $\Delta$, at the cost of a somewhat worse
approximation factor. Our algorithm remains polynomial-time for $\Delta$ as
large as $\exp((\log n)^{\Omega_{k}(1)})$, giving, as far as we know, the
first provable approximation guarantees for any polynomial-time MDS algorithm
when $\Delta$ is super-logarithmic in $n$. Roughly speaking, our algorithm
gives a $\textsf{OPT}^{1/k}\cdot\log(\Delta/\varepsilon)+\varepsilon$
approximation, meaning that the solution it outputs is comparable to the
algorithm of [DHK+21] whenever OPT is small; i.e.
$\textsf{OPT}\ll\varepsilon^{k}$. (Our approximation guarantee remains
$\sqrt{\textsf{OPT}}$ for $k=1$.)

######  Theorem 1.3 (Main theorem).

Given an instance of MDS under the Kamada-Kawai objective, with aspect ratio
$1\leqslant\Delta$, target dimension $k\in\mathbb{N}$, and target accuracy
$0<\varepsilon<1$, there exists an algorithm that outputs an embedding
$\left\\{\hat{x}_{i}\right\\}_{i\in[n]}$ such that with probability at least
$99/100$,

$\mathop{\mathbb{E}}_{i,j}\left[\left(1-\frac{\lVert\hat{x}_{i}-\hat{x}_{j}\rVert_{2}}{d_{i,j}}\right)^{2}\right]\leqslant\begin{cases}\vspace{0.05in}\mathcal{O}\left(\sqrt{\textsf{OPT}}\cdot\log(\Delta/\varepsilon)\right)+\varepsilon&\textrm{if
}k=1\\\
\vspace{0.05in}\mathcal{O}\left(\sqrt{\textsf{OPT}}\cdot\log(1/\varepsilon)\cdot\log(\Delta/\varepsilon)\right)+\varepsilon&\textrm{if
}k=2\\\ \mathcal{O}\left(\textsf{OPT}^{\hskip
2.8903pt1/k}\cdot\log(\Delta/\varepsilon)\right)+\varepsilon&\textrm{otherwise.}\end{cases}$

Further, the algorithm runs in
$\left(n\Delta/\varepsilon\right)^{\mathcal{O}\left(k\cdot\tau\right)}$ time,
where

$\tau=\begin{cases}\vspace{0.05in}\mathcal{O}\left(\left(\log\left(\log(\Delta)/\varepsilon\right)\log\left(\Delta/\varepsilon\right)\right)/\varepsilon\right)&\textrm{
if }k=1\\\
\vspace{0.05in}\mathcal{O}\left((\log^{2}\left(\log(\Delta)/\varepsilon\right)\log\left(\Delta/\varepsilon\right))/\varepsilon\right)&\textrm{
if }k=2\\\
\mathcal{O}\left(\left(k\log(\log(\Delta)/\varepsilon)\log(\Delta/\varepsilon)^{k/2}\right)/\varepsilon^{k/2}\right)&\textrm{
otherwise. }\end{cases}$

#### Our approach.

We formulate the MDS problem as a discrete optimization problem and consider
linear programming (LP) relaxation of this problem from the Sherali-Adams LP
hierarchy [SA90]. We use $\mathcal{O}\left(\tau\right)$ levels of the
hierarchy.

Our key innovation is a novel analysis of a conditioning-based rounding scheme
for Sherali-Adams. Interestingly, the same rounding scheme, applied to
$\mathrm{poly}(\Delta/\varepsilon)$ levels of Sherali-Adams [YZ14, BRS11], is
one way to obtain the algorithm of Fact 1.2, used as a subroutine in the
algorithm of [DHK+21]. Our geometry-aware analysis shows that the LP hierarchy
can exploit the low-dimensional metric structure of the variables
$x_{1},\ldots,x_{n}$ to obtain approximation guarantees with much smaller
linear programs than the generic analysis for CSPs would suggest. We give this
analysis, and the proof of our main theorem, in Section 3.

We hope that the convex-hierarchies approach to MDS opens the door to
approximation algorithms for other MDS objectives and even for metric
embedding problems more broadly. We suggest several open problems in Section
8.

######  Remark 1.4 (Sherali-Adams and smaller LP’s ).

We obtain Theorem 1.3 using $\mathcal{O}(\tau)$ levels of the Sherali-Adams
linear programming hierarchy, resulting in an LP of size
$(n\Delta/\varepsilon)^{\mathcal{O}\left(k\cdot\tau\right)}$. Using standard
techniques, we show that we can solve a significantly smaller LP to obtain the
same guarantee as above, resulting in a running time of
$n^{\mathcal{O}(1)}\left(\Delta/\varepsilon\right)^{\mathcal{O}\left(k\cdot\tau\right)}$
(see Section 7 for details).

###  1.1 Related Work

Multi-dimensional scaling has been studied since at least the 1950s. We refer
the reader to the survey [You13] and book [CC00] for review of its history and
applications. See also the recent book [AAB+21] for a perspective from applied
optimization. We discuss here some related works from the theoretical computer
science literature.

t-SNE and Friends. Another popular non-linear dimension reduction
technique/objective function, closely related to MDS, is t-SNE [VdMH08, HR02].
Notably Arora, Hu, and Kothari [AHK18] showed that the gradient-descent
algorithm used in practice for t-SNE performs well if the input exhibits some
clusterability properties. Other non-linear dimension reduction techniques
used in practice include the Isomap embedding [BS02], or Spectral embedding
methods [VL07]. We are not aware of any provable approximation algorithm for
these approaches.

Approximation Algorithms via LP Hierarchies. There is a vast literature on
approximation algorithms using LP hierarchies. Notable examples include works
on scheduling with communication delay [DKR+20], the matching polytope [MS09],
numerous works on CSPs and Dense-CSPs [BRS11, GS12], Bin Packing [KMN11], and
Correlation Clustering [CLN22].

Approximation Algorithms for Metric Embeddings with Additive or Multiplicative
Distortion Metric embeddings have been studied extensively for 30+ years in
theoretical computer science, with vast applications. See e.g. references in
the recent paper [SWW17]. Strong inapproximability results [MS08b] for
minimizing worst-case distortion
$\max_{i,j}\max({\|x_{i}-x_{j}\|/d_{ij},d_{ij}/\|x_{i}-x_{j}\|})$ led to some
efforts to design approximation algorithms for average-case notions of
distortion, among them MDS. Here “average-case” is in the sense that we take
the average over $i,j$ pairs, not that $d_{ij}$s are random. We are not aware
of works in this vein whose techniques apply directly to the Kamada-Kawai
problem we consider here, so we defer further discussion to Section 9.

##  2 Preliminaries

#### Notation.

Throughout, we will write $\mathop{\mathbb{E}}_{i,j}\left[\cdot\right]$ to
denote $\mathop{\mathbb{E}}_{i,j\sim\binom{n}{2}}\left[\cdot\right]$, and take
a similar convention for $\max_{i,j},\min_{i,j}$ and so on. $\|\cdot\|$
denotes Euclidean norm on $\mathbbm{R}^{k}$. We write
$\mathcal{N}_{k,\Delta,\varepsilon}$ to denote an $\varepsilon$-cover /
$\varepsilon$-net of $[-\Delta,\Delta]^{\otimes k}$, i.e.
$[-\Delta,\Delta]^{\otimes k}\supseteq\mathcal{N}_{\Delta,k,\varepsilon}$ and
for any $v\in[-\Delta,\Delta]^{\otimes k}$, there exists a
$v^{\prime}\in\mathcal{N}_{\Delta,k,\varepsilon}$ such that $\lVert
v-v^{\prime}\rVert\leqslant\varepsilon$. It is standard, for instance via
greedily adding uncovered points to $\mathcal{N}_{k,\Delta,\varepsilon}$, that
such covers exist with
$\left\lvert\mathcal{N}_{k,\Delta,\varepsilon}\right\rvert\leqslant\left(c\Delta/\varepsilon\right)^{k}$,
for a fixed constant $c$, and that moreover one can have
$\min_{x,y\in\mathcal{N}_{k,\Delta,\varepsilon}}\|x-y\|>\varepsilon$. For a
finite set $S\subseteq\mathbbm{R}$, we write $\mathcal{Q}(S,\varepsilon)$ to
denote the value of the $\varepsilon$-th quantile/$\varepsilon|S|$-th least
element in $S$.

#### Sherali-Adams Linear Programming.

We review the local-distribution view of the Sherali-Adams linear programming
hierarchy. Let $\Omega$ be a finite set and $n\in\mathbbm{N}$. For
$t\in\mathbbm{N}$, the level-$t$ Sherali-Adams LP relaxation of $\Omega^{n}$
is as follows. (For a more formal account, see e.g. [BRS11].)

#### Variables and constraints.

For each $T\in\binom{n}{t}$, we have $|\Omega|^{t}$ non-negative variables,
$\mu_{T}(x)$ for $x\in\Omega^{t}$, collectively denoted $\mu_{T}$. For each
$T$, we constrain $\sum_{x}\mu_{T}(x)=1$ so that $\mu_{T}$ is a probability
distribution over $\Omega^{t}$. Then, for every $S,T\in\binom{n}{t}$, we add
linear constraints so that the distribution $\mu_{T}$ restricted to $S\cap T$
is identical to the distribution $\mu_{S}$ restricted to $S\cap T$. Overall,
we have $(|\Omega|n)^{O(t)}$ variables and constraints. We sometimes call the
collection of local distributions $\\{\mu_{T}\\}$ satisfying these constraints
a “degree-$t$ Sherali-Adams pseudo-distribution”.

#### Pseudo-expectation view.

If we have a Sherali-Adams solution which is clear from context, for any
function $f$ of at most $t$ variables out of $x_{1},\ldots,x_{n}$ (a.k.a.
“$t$-junta”), we write
$\operatorname{\tilde{\mathbb{E}}}f(x_{1},\ldots,x_{n})$ for
$\operatorname*{\mathbb{E}}_{x\sim\mu_{T}}f(x_{T})$, where $\mu_{T}$ is the
local distribution on the subset $T\subseteq[n]$ of variables on which $f$
depends. We can extend $\operatorname{\tilde{\mathbb{E}}}$ to a linear
operator on the linear span of $t$-juntas. Observe that
$\operatorname{\tilde{\mathbb{E}}}f$ is a linear function of the underlying LP
variables.

#### Conditioning.

We will frequently pass from a Sherali-Adams solution $\\{\mu_{T}\\}$ to a
conditional solution
$\\{\mu_{T}\,|\,x_{i_{1}}=a_{1},\ldots,x_{i_{t^{\prime}}}=a_{t^{\prime}}\\}$,
for $t^{\prime}<t$. We obtain the conditional local distribution on
$x_{j_{1}},\ldots,x_{j_{t-t^{\prime}}}$ by conditioning the local distribution
on $x_{j_{1}},\ldots,x_{j_{t-t^{\prime}}},x_{i_{1}},\ldots,x_{i_{t^{\prime}}}$
on the event $\\{x_{i_{1}}=a_{1},\ldots,x_{i_{t^{\prime}}}=a_{t^{\prime}}\\}$.

##  3 Main Algorithm and Analysis

Our goal is to set up a Sherali-Adams LP relaxation for the Kamada-Kawai
objective. The version of Sherali-Adams we use here works for discrete
assignment problems, while Kamada-Kawai asks us to assign $x_{1},\ldots,x_{n}$
to vectors in $\mathbbm{R}^{k}$, so we need to discretize $\mathbbm{R}^{k}$.
The following lemma shows that only an additive $\varepsilon$ is lost in the
objective value if we discretize to
$\mathcal{O}\left(\Delta/\varepsilon\right)^{k}$ points. We defer the proof to
Section 5.2.

######  Lemma 3.1 (Aspect ratio of the target space).

Let $\left\\{d_{i,j}\right\\}_{i,j\in[n]}$ satisfy $1\leqslant
d_{i,j}\leqslant\Delta$ for all $(i,j)\in\binom{n}{2}$ and let OPT be the
optimal Kamada-Kawai objective value with respect to $\mathbbm{R}^{k}$. For
$0<\varepsilon<1$, let $\mathcal{N}_{k,\Delta/\varepsilon,1}$ be a $1$-cover
of $[-\Delta/\varepsilon,\Delta/\varepsilon]^{k}$. There exists an embedding
$x_{1},\ldots,x_{n}\in\mathcal{N}_{k,\Delta/\varepsilon,1}$, such that for all
$(i,j)\in\binom{n}{2}$ we have:

$1\leqslant\|x_{i}-x_{j}\|_{2}\leqslant\mathcal{O}\left(\Delta/\varepsilon\right)\quad\text{
and }\quad\operatorname*{\mathbb{E}}_{i,j\in[n]}\left(1-\frac{\lVert
x_{i}-x_{j}\rVert}{d_{i,j}}\right)^{2}\leqslant\textsf{OPT}+\varepsilon\,.$

We are now ready to describe our algorithm. We follow a fairly standard
strategy for rounding Sherali-Adams relaxations: condition on the values of a
few randomly-chosen variables and output a simple function of the $1$-wise
local distributions on the remaining variables (in this case, simply their
expectations). This strategy can also be used to prove e.g. Fact 1.2. Our main
contribution is a new geometry-aware analysis of this rounding procedure which
obtains provable guarantees with $\approx\log(\Delta)/\varepsilon$ levels of
the Sherali-Adams hierarchy when embedding into the line or the plane.

######  Algorithm 3.2 (Efficient Kamada-Kawai).

Input: Nonnegative numbers $\mathcal{D}=\left\\{d_{i,j}\right\\}_{i,j\in[n]}$,
target dimension $k\in\mathbb{N}$, target accuracy $0<\varepsilon<1$.
Operation: 1. Let
$\tau=\begin{cases}\mathcal{O}\left(\left(\log\left(\log(\Delta)/\varepsilon\right)\log\left(\Delta/\varepsilon\right)\right)/\varepsilon\right)&\textrm{
if }k=1\\\
\mathcal{O}\left((\log^{2}\left(\log(\Delta)/\varepsilon\right)\log\left(\Delta/\varepsilon\right))/\varepsilon\right)&\textrm{
if }k=2\\\
\mathcal{O}\left(\left(k\log(\log(\Delta)/\varepsilon)\log(\Delta/\varepsilon)^{k/2}\right)/\varepsilon^{k/2}\right)&\textrm{
otherwise }\end{cases}$ Let $\mathcal{N}_{\Delta/\varepsilon,k,1}$ be an
$1$-net of $[-\Delta/\varepsilon,\Delta/\varepsilon]^{k}$. Let $\mu$ be a
degree-$(2\tau)$ Sherali-Adams pseudo-distribution over the domain
$\mathcal{N}_{k,\Delta/\varepsilon,1}$ optimizing
$\min_{\mu}\,\operatorname{\tilde{\mathbb{E}}}_{\mu}\operatorname*{\mathbb{E}}_{i,j\sim[n]}\left(1-\frac{\|x_{i}-x_{j}\|}{d_{ij}}\right)^{2}\,.$
2. Let $\mathcal{T}\subset[n]$ be a random subset of size $\tau$ and let
$\tilde{x}_{\mathcal{T}}$ be a draw from the local distribution
$\\{x_{\mathcal{T}}\\}$. Let $\mu_{\mathcal{T}}$ be the pseudo-distribution
obtained by conditioning $\mu$ on
$\zeta_{\mathcal{T}}:=\left\\{x_{j}=\tilde{x}_{j}\right\\}_{j\in\mathcal{T}}$.
Output: The embedding
$\left\\{\mathop{\tilde{\mathbb{E}}}_{\mu_{\mathcal{T}}}\left[x_{i}\right]\right\\}_{i\in[n]}$.

In what follows, we use pseudo-distribution to refer to any $n$-variable
Sherali-Adams pseudo-distribution over the domain
$\mathcal{N}_{k,\Delta/\varepsilon,1}$.

###  3.1 Analysis setup and pseudo-deviations

Our first key innovation is to track the following measure of the
fluctuations/uncertainty in the local distributions in our (conditioned)
pseudo-distribution.

######  Definition 3.3 (Pseudo-Deviation of an Embedding).

Given a pseudo-distribution $\mu$, we define the pseudo-deviation of each
point as follows:

$\mathop{\tilde{\mathbb{D}}}_{\mu}\left[x_{i}\right]=\mathop{\tilde{\mathbb{E}}}_{\mu}\left[\left\lVert
x_{i}-\mathop{\tilde{\mathbb{E}}}_{\mu}\left[x_{i}\right]\right\rVert_{2}\right].$

At a high level, we argue that

  1. (a)

if the conditional pseudo-deviations are small, i.e.
$\mathop{\tilde{\mathbb{D}}}_{\mu_{\mathcal{T}}}\left[x_{i}\right],\mathop{\tilde{\mathbb{D}}}_{\mu_{\mathcal{T}}}\left[x_{j}\right]\leqslant\delta\cdot
d_{ij}$, our rounding algorithm incurs cost that is a function of $\delta$,
and

  2. (b)

for most pairs $i,j$, the conditioned pseudo-distribution $\mu_{\mathcal{T}}$
satisfies
$\mathop{\tilde{\mathbb{D}}}_{\mu_{\mathcal{T}}}\left[x_{i}\right],\mathop{\tilde{\mathbb{D}}}_{\mu_{\mathcal{T}}}\left[x_{j}\right]\ll
d_{ij}$.

#### On the need for conditioning.

We show that the latter holds, despite the fact that for $\mu$ (as opposed to
$\mu_{\mathcal{T}}$), we could have
$\mathop{\tilde{\mathbb{D}}}_{\mu}\left[x_{i}\right]\approx\Delta$ for most
$i$. To see this, consider a one-dimensional instance where the optimal
embedding is to map half the points to roughly $-\Delta$ and half the points
to $\Delta$. In this example, the target embedding,
$\left\\{x_{i}\right\\}_{i\in[n]}$, can be partitioned into two clusters
$\mathcal{C}_{1},\mathcal{C}_{2}$, such that one gets mapped to $-\Delta$ and
another gets mapped to $\Delta$. Now, assume the pseudo-distribution $\mu$ is
the uniform distribution over
$(\mathcal{C}_{1}\to-\Delta,\mathcal{C}_{2}\to\Delta)$ and
$(\mathcal{C}_{1}\to\Delta,\mathcal{C}_{2}\to-\Delta)$. Such a pseudo-
distribution is valid since the cost remains unchanged. However, for each
$i\in[n]$, $\mathop{\tilde{\mathbb{D}}}_{\mu}\left[x_{i}\right]=2\Delta$ since
$\mathop{\tilde{\mathbb{E}}}_{\mu}\left[x_{i}\right]=0$ and $x_{i}$ is
$\pm\Delta$ with equal probability. However, observe that conditioning on the
location of a single $x_{i}$ precludes such a distribution over solutions.
With this intuition in mind, we show that that conditioning in step (2) of
Algorithm 3.2 reduces $\mathop{\tilde{\mathbb{D}}}\left[x_{i}\right]$ in
general.

#### Rounded cost to pseudo-deviations.

We capture (a) via the following simple fact, which we will apply with $X,Y$
being a joint sample from the conditional local distribution on $x_{i},x_{j}$.
Since we restrict attention to pairs of variables, we can freely translate
between distributions and pseudo-distributions.

######  Fact 3.4 (Pseudo-expected distances to pseudo-deviations, see proof in
Section 5).

Let $X,Y$ be vector-valued random variables and let $d>0$. Then

$\left(1-\frac{\|\operatorname{\tilde{\mathbb{E}}}X-\operatorname{\tilde{\mathbb{E}}}Y\|}{d}\right)^{2}\leqslant
2\operatorname{\tilde{\mathbb{E}}}\left(1-\frac{\|X-Y\|}{d}\right)^{2}+2\left(\frac{\operatorname{\tilde{\mathbb{E}}}\|X-\operatorname{\tilde{\mathbb{E}}}X\|+\operatorname{\tilde{\mathbb{E}}}\|Y-\operatorname{\tilde{\mathbb{E}}}Y\|}{d}\right)^{2}\,.$

In our setting, the left-hand side of 3.4 represents the cost of $x_{i},x_{j}$
in the rounded solution, while the right-hand side is the sum of two terms:
the contribution of the same pair to the Sherali-Adams objective function and
a term depending on the pseudo-deviations of $x_{i}$ and $x_{j}$, scaled by
the distance in the input space, i.e.
$(\mathop{\tilde{\mathbb{D}}}_{\mu_{\mathcal{T}}}\left[x_{i}\right]+\mathop{\tilde{\mathbb{D}}}_{\mu_{\mathcal{T}}}\left[x_{j}\right])/d_{ij}$.

#### Pseudo-deviations to quantiles.

To capture (b), we prove the following lemma, which says that
$\mathop{\tilde{\mathbb{D}}}_{\mu_{\mathcal{T}}}\left[x_{i}\right]^{2}$ can be
bounded in terms of the $\varepsilon$-th quantile of the set of numbers
$\left\\{\mathop{\tilde{\mathbb{E}}}_{\mu}\left[\|x_{i}-x_{j}\|^{2}\right]\right\\}_{j\in[n]}$,
which denote the pseudo-expected distances, as long as the number of points we
conditioned on is large enough.

######  Lemma 3.5 (Pseudodeviation Reduction via Quantiles).

Given $0<\varepsilon,\delta<0$, $1\leqslant\Delta$, let $\mu$ be a
degree-$\mathcal{O}\left(\log(1/\delta)/\varepsilon\right)$ pseudo-
distribution. Let $\mathcal{T}\subset[n]$ be a random subset of size
$\log(1/\delta)/\varepsilon$ and let $\tilde{x}_{\mathcal{T}}$ be a draw from
the local distribution $\\{x_{\mathcal{T}}\\}$. Let $\mu_{\mathcal{T}}$ be the
pseudo-distribution obtained by conditioning on
$\zeta_{\mathcal{T}}:=\left\\{x_{j}=\tilde{x}_{j}\right\\}_{j\in\mathcal{T}}$,
as in step (2) of Algorithm 3.2.

Then, for all $i\in[n]$, with probability at least $1-\delta$ over the choice
of $\mathcal{T}$,

$\mathop{\mathbb{E}}_{\tilde{x}_{\mathcal{T}}}\left[\mathop{\tilde{\mathbb{D}}}_{\mu_{\mathcal{T}}}\left[x_{i}\right]^{2}\right]\leqslant\mathcal{Q}\left(\left\\{\mathop{\tilde{\mathbb{E}}}_{\mu}\left[\lVert
x_{i}-x_{j}\rVert^{2}\right]\right\\}_{j\in[n]},\varepsilon\right)$

where $\mathcal{Q}\left(\mathcal{S},q\right)$ denotes the $q$-th quantile of
the ordered set $\mathcal{S}$.

###### Proof sketch – full proof deferred to Section 5.1.

Fix $i\in[n]$. Suppose that $j\in\mathcal{T}$. We have

$\mathop{\tilde{\mathbb{E}}}_{\mu_{\mathcal{T}}}\left[\lVert
x_{i}-\mathop{\tilde{\mathbb{E}}}_{\mu_{\mathcal{T}}}\left[x_{i}\right]\rVert^{2}\right]\leqslant\mathop{\tilde{\mathbb{E}}}_{\mu_{\mathcal{T}}}\left[\lVert
x_{i}-\mathop{\tilde{\mathbb{E}}}_{\mu_{\mathcal{T}}}\left[x_{j}\right]\rVert^{2}\right]\leqslant\mathop{\tilde{\mathbb{E}}}_{\mu_{\mathcal{T}}}\left[\lVert
x_{i}-\tilde{x}_{j}\rVert^{2}\right].$

For the first inequality, we used that for any random vector $X$,
$\operatorname*{\mathbb{E}}\|X-v\|^{2}$ is minimized by choosing
$v=\operatorname*{\mathbb{E}}X$. By law of total expectation,
$\operatorname*{\mathbb{E}}_{\tilde{x}_{j}}\operatorname{\tilde{\mathbb{E}}}_{\mu_{\mathcal{T}}}\|x_{i}-\tilde{x}_{j}\|^{2}=\operatorname{\tilde{\mathbb{E}}}_{\mu}\|x_{i}-x_{j}\|^{2}$.
Finally, to obtain the statement about
$\mathcal{Q}\left(\left\\{\mathop{\tilde{\mathbb{E}}}_{\mu}\left[\lVert
x_{i}-x_{j}\rVert^{2}\right]\right\\}_{j\in[n]},\varepsilon\right)$, just note
that if $\mathcal{T}\gg 1/\varepsilon$ then it is likely to contain some $j$
among those with the $\varepsilon n$ smallest values
$\operatorname{\tilde{\mathbb{E}}}_{\mu}\|x_{i}-x_{j}\|^{2}$. ∎

Next, we develop tools to relate
$\mathcal{Q}\left(\left\\{\mathop{\tilde{\mathbb{E}}}_{\mu}\left[\lVert
x_{i}-x_{j}\rVert^{2}\right]\right\\}_{j\in[n]},\varepsilon\right)$ to
$\\{d_{ij}\\}$. Before turning to those tools, though, what do we do with
those $i,j$ where
$\mathop{\tilde{\mathbb{D}}}_{\mu_{\mathcal{T}}}\left[x_{i}\right],\mathop{\tilde{\mathbb{D}}}_{\mu_{\mathcal{T}}}\left[x_{j}\right]$
remains large even after conditioning?

#### Rounded cost on any small subset is small.

We show that no pair $i,j$ has a rounded cost greater than $O(1)$ plus its
contribution to the relaxed objective function, so if there aren’t too many
“bad” pairs like this, their contribution to the rounded cost isn’t large.
Formally, we show that the rounded cost on a small set of pairs can by bounded
by the size of the set and their contribution to OPT:

######  Lemma 3.6 (Rounded cost on a small set of pairs).

Let $\mathcal{T}\subset[n]$ be a subset of size $\tau$ and let
$\tilde{x}_{\mathcal{T}}\in\left([-\Delta,\Delta]^{\otimes
k}\right)^{|\mathcal{T}|}$ be a draw from the local distribution
$\\{x_{\mathcal{T}}\\}$. Let $\mu_{\mathcal{T}}$ be the pseudo-distribution
obtained in Algorithm 3.2, step (2). Let $\mathcal{S}\subseteq\binom{n}{2}$ be
any subset of pairs. Then,

$\mathop{\mathbb{E}}_{\tilde{x}_{\mathcal{T}}}\left[\sum_{(i,j)\in\mathcal{S}}\left(1-\frac{\lVert\mathop{\tilde{\mathbb{E}}}_{\mu}\left[x_{i}\right]-\mathop{\tilde{\mathbb{E}}}_{\mu}\left[x_{j}\right]\rVert}{d_{i,j}}\right)^{2}\right]\leqslant
4\cdot\lvert\mathcal{S}\rvert+4\textsf{OPT}\cdot\binom{n}{2}.$

###### Proof.

Using the fact that $(a+b)^{2}\leqslant 2(a^{2}+b^{2})$, we have

$\begin{split}\mathop{\mathbb{E}}_{\tilde{x}_{\mathcal{T}}}\left[\sum_{(i,j)\in\mathcal{S}}\left(1-\frac{\lVert\mathop{\tilde{\mathbb{E}}}_{\mu}\left[x_{i}\right]-\mathop{\tilde{\mathbb{E}}}_{\mu}\left[x_{j}\right]\rVert}{d_{i,j}}\right)^{2}\right]&\leqslant
2\sum_{(i,j)\in\mathcal{S}}1+2\mathop{\mathbb{E}}_{\tilde{x}_{\mathcal{T}}}\left[\sum_{(i,j)\in\mathcal{S}}\left(\frac{\lVert\mathop{\tilde{\mathbb{E}}}_{\mu_{\mathcal{T}}}\left[x_{i}-x_{j}\right]\rVert}{d_{i,j}}\right)^{2}\right]\\\
&\leqslant
2\cdot\left\lvert\mathcal{S}\right\rvert+2\sum_{(i,j)\in\mathcal{S}}\mathop{\mathbb{E}}_{\tilde{x}_{\mathcal{T}}}\left[\mathop{\tilde{\mathbb{E}}}_{\mu_{\mathcal{T}}}\left[\left(\frac{\lVert
x_{i}-x_{j}\rVert}{d_{i,j}}+1-1\right)^{2}\right]\right]\\\ &\leqslant
4\cdot\lvert\mathcal{S}\rvert+4\sum_{(i,j)\in\binom{n}{2}}\mathop{\tilde{\mathbb{E}}}_{\mu}\left[\left(\frac{\lVert
x_{i}-x_{j}\rVert}{d_{i,j}}-1\right)^{2}\right]\\\ &\leqslant
4\cdot\lvert\mathcal{S}\rvert+4\textsf{OPT}\cdot\binom{n}{2}\end{split}$

where the second inequality follows from Jensen’s inequality on the local
distributions in $\mu_{\mathcal{T}}$, the third uses law of total probability,
and the last inequality follows from the Sherali-Adams objective value being
smaller than OPT. ∎

###  3.2 Bounding quantiles of pseudo-expected distances

Lemma 3.5 shows that we can control
$\mathop{\tilde{\mathbb{D}}}_{\mu_{\mathcal{T}}}\left[x_{i}\right]$ using
quantiles of
$\\{\operatorname{\tilde{\mathbb{E}}}\|x_{i}-x_{j}\|\\}_{j\in[n]}$; now we
need to bound those quantiles. Our goal is to show that for most $i,j$,

$\mathcal{Q}\left(\\{\operatorname{\tilde{\mathbb{E}}}\|x_{i}-x_{\ell}\|\\}_{\ell\in[n]},\varepsilon\right),\mathcal{Q}\left(\\{\operatorname{\tilde{\mathbb{E}}}\|x_{j}-x_{\ell}\|\\}_{\ell\in[n]},\varepsilon\right)\ll
d_{ij}$

As a thought experiment, consider the case where instead of a pseudo-
distribution we had an actual set of points
$x_{1}^{*},\ldots,x_{n}^{*}\in\mathbbm{R}^{k}$, and instead of $d_{ij}$ we had
$\|x_{i}^{*}-x_{j}^{*}\|$, we could hope that quantiles of
$\mathcal{Q}(\\{\|x_{i}^{*}-x_{\ell}^{*}\|\\}_{j\in[n]},\varepsilon)\ll\|x_{i}^{*}-x_{j}^{*}\|$
for typical $\ell\in[n]$. Interestingly even in our setting, we can establish
a fact like this for sets of points
$x_{1}^{*},\ldots,x_{n}^{*}\in\mathbbm{R}^{k}$, and then show that most
$\operatorname{\tilde{\mathbb{E}}}\|x_{i}-x_{j}\|$ behave like a corresponding
$\|x_{i}^{*}-x_{j}^{*}\|$ for an optimal embedding
$x_{1}^{*},\ldots,x_{n}^{*}$.

#### Low-dimensional geometry and quantiles of pair-wise distances.

Consider the special case of n distinct points,
$\left\\{x_{1}^{*},x_{2}^{*},\ldots,x_{n}^{*}\right\\}$, on the discrete
interval $[-\Delta,\Delta]$. We derive the following geometric fact: ignoring
constant factors, for all but an $\varepsilon\cdot\log(\Delta)$-fraction of
pairs $(i,j)$, the intervals of radius $\varepsilon\cdot\lVert
x_{i}^{*}-x_{j}^{*}\rVert$ around $x_{i}^{*}$ and $x_{j}^{*}$ respectively
contain at least $\varepsilon n$ points (see Fig. 1 for a proof by picture).
This statement immediately implies that the $\varepsilon$-th quantiles of the
sets $\left\\{\lVert x_{i}^{*}-x_{k}^{*}\rVert\right\\}_{k\in[n]},\\{\lVert
x_{j}^{*}-x_{k}^{*}\rVert\\}_{k\in[n]}$, are at most $\varepsilon\cdot\lVert
x_{i}^{*}-x_{j}^{*}\rVert$.

We remark that, in general, discarding a $\Theta(\log\Delta)$ fraction of
pairs is necessary in the worst case. Consider the case of the line where
$x_{i}^{*}=2^{i}$; then for every pair $i<j$, we have
$2^{j-1}\leqslant\|x_{i}^{*}-x_{j}^{*}\|\leqslant 2^{j}$, thus there does not
exist even a single point $x_{k}^{*}$ such that
$\|x_{j}^{*}-x_{k}^{*}\|\leqslant(1/3)\cdot\|x_{i}^{*}-x_{j}^{*}\|$. We state
a generalized version of this geometric fact below and defer the proof to
Section 4.1:

######  Lemma 3.7 (Quantiles of distances in low-dimensional space).

Given $0<\eta,\delta<1$, and a set of $n$ points in the range
$[-\Delta,\Delta]^{\otimes k}$, denoted by
$\left\\{x_{i}^{*}\right\\}_{i\in[n]}$, for all but
$\mathcal{O}\left(\delta\log(\Delta)\cdot n^{2}\right)$ pairs, $(i,j)$ such
that $\lVert x_{i}^{*}-x_{j}^{*}\rVert\geqslant 1$, we have

$\mathcal{Q}\left(\left\\{\lVert
x_{i}^{*}-x_{k}^{*}\rVert\right\\}_{k\in[n]},\eta\right)+\mathcal{Q}\left(\left\\{\lVert
x_{j}^{*}-x_{k}^{*}\rVert\right\\}_{k\in[n]},\eta\right)\leqslant\mathcal{O}\left(\left(\frac{\eta}{\delta}\right)^{1/k}\right)\lVert
x_{i}^{*}-x_{j}^{*}\rVert.$

#### Quantiles of pseudo-expected distances to quantiles of an optimal
embedding.

Next, we translate between quantiles of pseudo-expected distances and
quantiles of distances in an optimal embedding. To start, the following
“glorified Markov” inequality shows that
$\operatorname{\tilde{\mathbb{E}}}\|x_{i}-x_{j}\|$ is close to
$\|x_{i}^{*}-x_{j}^{*}\|$ for some vectors $x_{1}^{*},\ldots,x_{n}^{*}$ and
most $i,j$ pairs. This lemma hinges on the fact that the cost of the solution
output by the LP is at most OPT, by the virtue of it being a relaxation. It
also crucially uses the fact that the Kamada-Kawai objective is an average
over pairs.

Figure 1: The figure shows that for two random points $x_{i},x_{j}$ on the
line, we have that there are $\epsilon n$ points around $x_{i}$ and $x_{j}$
that shrink by $\epsilon|x_{i}-x_{j}|$.

######  Lemma 3.8 (Relating OPT to distortion on typical distances).

Let $\left\\{x_{1}^{*},x_{2}^{*},\ldots,x_{n}^{*}\right\\}$ be some optimal
embedding of the points minimizing the Kamada-Kawai objective. Then, for any
$0<c<1/4$, with probability at least $1-(\textsf{OPT}/c)$, for a random pair
$i,j\sim[n]$,

$(1-2\sqrt{c})\lVert x^{*}_{i}-x^{*}_{j}\rVert^{2}\leqslant
d_{i,j}^{2}\leqslant(1+2\sqrt{c})\lVert x^{*}_{i}-x^{*}_{j}\rVert^{2}.$

Let $\mu$ be any pseudo-distribution that minimizes the objective
$\operatorname*{\mathbb{E}}_{i,j\in[n]}\left(1-\frac{\lVert
x_{i}-x_{j}\rVert}{d_{i,j}}\right)^{2}$. Then, with probability at least
$1-(\textsf{OPT}/c)$, for a random pair $i,j\sim[n]$,

$\left(1-2\sqrt{c}\right)\lVert
x_{i}^{*}-x_{j}^{*}\rVert\leqslant\mathop{\tilde{\mathbb{E}}}_{\mu}\left[\lVert
x_{i}-x_{j}\rVert\right]\leqslant\left(1+2\sqrt{c}\right)\lVert
x_{i}^{*}-x_{j}^{*}\rVert,$

and

$\left(1-2\sqrt{c}\right)d_{i,j}^{2}\leqslant\mathop{\tilde{\mathbb{E}}}_{\mu}\left[\lVert
x_{i}-x_{j}\rVert^{2}\right]\leqslant\left(2+2c\right)d_{i,j}^{2}.$

Observe, if Lemma 3.8 held for all the pairs, we would immediately be able to
translate between quantiles of pseudo-expected distances and quantiles of
distances corresponding to an optimal embedding. However, Lemma 3.8 holds only
for a $1-\textsf{OPT}$-fraction of pairs. Therefore, there could be a subset
of $\sqrt{\textsf{OPT}}n$ points such that for each one, their
$\sqrt{\textsf{OPT}}$-th quantiles do not shrink at all. Now, if either
endpoint of a pair (i,j) lands in this subset, we cannot obtain a non-trivial
bound on the corresponding quantiles. There can be at most
$\sqrt{\textsf{OPT}}n^{2}$ such pairs, and we can bound the cost on this
subset by invoking Lemma 3.6 again. In the following lemma, we show that this
is essentially the only thing that can go wrong and defer the proof to Section
4.2.

######  Lemma 3.9 (Translating between quantiles).

Let $\mu$ be a pseudo-distribution minimizing the objective in Algorithm 3.2
and let $\left\\{x_{i}^{*}\right\\}_{i\in[n]}$ be an optimal embedding. For
all but $(\sqrt{\textsf{OPT}}+\varepsilon)$-fraction of indices $i$,

$\mathcal{Q}\left(\left\\{\mathop{\tilde{\mathbb{E}}}_{\mu}\left[\lVert
x_{i}-x_{j}\rVert^{2}\right]\right\\}_{j\in[n]},\varepsilon\right)\leqslant
10\cdot\mathcal{Q}\left(\left\\{\lVert
x_{i}^{*}-x_{k}^{*}\rVert^{2}\right\\}_{k\in[n]},16\sqrt{\textsf{OPT}}+\varepsilon\right).$

###  3.3 Proof of Main Theorem

We are now ready to complete the proof of Theorem 1.3.

###### Proof of Theorem 1.3.

Our goal is to bound the objective value of the rounded solution:

$\mathop{\mathbb{E}}_{\tilde{x}_{\mathcal{T}}}\left[\mathop{\mathbb{E}}_{(i,j)\in\binom{n}{2}}\left[\left(1-\frac{\left\lVert\mathop{\tilde{\mathbb{E}}}_{\mu_{\mathcal{T}}}\left[x_{i}\right]-\mathop{\tilde{\mathbb{E}}}_{\mu_{\mathcal{T}}}\left[x_{j}\right]\right\rVert}{d_{i,j}}\right)^{2}\right]\right]$
(1)

in terms of OPT, the cost of an optimal embedding. Let
$\left\\{x_{i}^{*}\right\\}_{i\in[n]}$ be any embedding that obtains an
objective value of OPT.

Call a pair $(i,j)$ “good” (with respect to $\mathcal{T}$) if it satisfies the
following properties, where
$\varepsilon^{\prime}=16\sqrt{\textsf{OPT}}+\varepsilon$:

$d_{ij}$ is close to $\|x_{i}^{*}-x_{j}^{*}\|$:
$\displaystyle\qquad\left(1-0.1\right)\lVert
x_{i}^{*}-x_{j}^{*}\rVert_{2}\leqslant
d_{i,j}\leqslant\left(1+0.1\right)\lVert x_{i}^{*}-x_{j}^{*}\rVert_{2}$ (2)
pseudo-deviations bounded by quantiles:
$\displaystyle\qquad\mathop{\mathbb{E}}_{\tilde{x}_{\mathcal{T}}}\left[\mathop{\tilde{\mathbb{D}}}_{\mu_{\mathcal{T}}}\left[x_{i}\right]^{2}\right]\leqslant
10\cdot\mathcal{Q}\left(\left\\{\lVert
x_{i}^{*}-x_{k}^{*}\rVert^{2}\right\\}_{k\in[n]},\varepsilon^{\prime}\right)\text{
and the same for $j$}\,,$ (3) $x^{*}$ quantiles are small:
$\displaystyle\qquad\frac{\mathcal{Q}\left(\left\\{\lVert
x_{i}^{*}-x_{k}^{*}\rVert^{2}\right\\}_{k\in[n]},\varepsilon^{\prime}\right)}{\lVert
x_{i}^{*}-x_{j}^{*}\rVert^{2}}+\frac{\mathcal{Q}\left(\left\\{\lVert
x_{j}^{*}-x_{k}^{*}\rVert^{2}\right\\}_{k\in[n]},\varepsilon^{\prime}\right)}{\lVert
x_{i}^{*}-x_{j}^{*}\rVert^{2}}\leqslant 1.$ (4)

If $(i,j)$ is not good, then we say it is “bad”.

We put together the lemmas from the previous sections to prove the following
claim at the end of this section:

######  Claim 3.10.

With probability at least $0.99$ over $\mathcal{T}$, if
$|\mathcal{T}|\gg\log(1/\varepsilon)/\varepsilon$, there are at most
$\mathcal{O}\left(\sqrt{\textsf{OPT}}+\varepsilon\right)\cdot\log\Delta\cdot\binom{n}{2}$
bad pairs.

From now on, condition $\mathcal{T}$ on the event that Claim 3.10 applies.
Using Lemma 3.6 on the bad pairs, their contribution to the rounded cost, in
expectation over $\tilde{x}_{\mathcal{T}}$, is at most

$\operatorname*{\mathbb{E}}_{\tilde{x}_{\mathcal{T}}}\operatorname*{\mathbb{E}}_{i,j\sim[n]}1((i,j)\text{
bad})\cdot\left(1-\frac{\|\mathop{\tilde{\mathbb{E}}}_{\mu_{\mathcal{T}}}\left[x_{i}-x_{j}\right]\|}{d_{ij}}\right)^{2}\leqslant\mathcal{O}\left(\sqrt{\textsf{OPT}}+\varepsilon\right)\cdot\log\Delta\,.$

So, we can turn to the good pairs.

Observe, for any pair $(i,j)$, and any $\tilde{x}_{\mathcal{T}}$, we have by
Fact 3.4,

$\left(1-\frac{\left\lVert\mathop{\tilde{\mathbb{E}}}_{\mu_{\mathcal{T}}}\left[x_{i}\right]-\mathop{\tilde{\mathbb{E}}}_{\mu_{\mathcal{T}}}\left[x_{j}\right]\right\rVert}{d_{i,j}}\right)^{2}\leqslant
2\mathop{\tilde{\mathbb{E}}}_{\mu_{\mathcal{T}}}\left[\left(1-\frac{\lVert
x_{i}-x_{j}\rVert}{d_{i,j}}\right)^{2}\right]+2\left(\frac{\mathop{\tilde{\mathbb{D}}}_{\mu_{\mathcal{T}}}\left[x_{i}\right]+\mathop{\tilde{\mathbb{D}}}_{\mu_{\mathcal{T}}}\left[x_{j}\right]}{d_{i,j}}\right)^{2}$
(5)

The first term on the right-hand side is the pair’s contribution to the LP
objective. The second term we bound for good $(i,j)$, on average over
$\tilde{x}_{\mathcal{T}}$:

$\displaystyle\operatorname*{\mathbb{E}}_{\tilde{x}_{\mathcal{T}}}\left(\frac{\mathop{\tilde{\mathbb{D}}}_{\mu_{\mathcal{T}}}\left[x_{i}\right]+\mathop{\tilde{\mathbb{D}}}_{\mu_{\mathcal{T}}}\left[x_{j}\right]}{d_{i,j}}\right)^{2}$
$\displaystyle\quad\leqslant\mathcal{O}\left(1\right)\cdot\frac{\mathcal{Q}\left(\left\\{\lVert
x_{i}^{*}-x_{k}^{*}\rVert^{2}\right\\}_{k\in[n]},16\sqrt{\textsf{OPT}}+\varepsilon\right)+\mathcal{Q}\left(\left\\{\lVert
x_{j}^{*}-x_{k}^{*}\rVert^{2}\right\\}_{k\in[n]},16\sqrt{\textsf{OPT}}+\varepsilon\right)}{\|x_{i}^{*}-x_{j}^{*}\|^{2}}$

At the end of this section, we use Lemma 3.7 to prove the following Claim:

######  Claim 3.11.

For $k>2$,

$\displaystyle\operatorname*{\mathbb{E}}_{i,j\sim[n]}\left[1((i,j)\text{
good})\cdot\frac{\mathcal{Q}\left(\left\\{\lVert
x_{i}^{*}-x_{k}^{*}\rVert^{2}\right\\}_{k\in[n]},16\sqrt{\textsf{OPT}}+\varepsilon\right)+\mathcal{Q}\left(\left\\{\lVert
x_{j}^{*}-x_{k}^{*}\rVert^{2}\right\\}_{k\in[n]},16\sqrt{\textsf{OPT}}+\varepsilon\right)}{\|x_{i}^{*}-x_{j}^{*}\|^{2}}\right]$
$\displaystyle\leqslant\mathcal{O}\left(\left(\textsf{OPT}^{1/k}+\varepsilon^{2/k}\right)\cdot\log\left(\Delta\right)\right)\,.$

and, for $k=1,2$, the same inequality holds with the right-hand side replaced
with
$\mathcal{O}\left(\left(\sqrt{\textsf{OPT}}+\varepsilon\right)\cdot\log\Delta\right)$
and
$\mathcal{O}\left(\left(\sqrt{\textsf{OPT}}+\varepsilon\right)\cdot\log(1/\varepsilon)\cdot\log\Delta\right)$,
respectively.

All together, for $k>2$ we obtain for the good pairs

$\operatorname*{\mathbb{E}}_{\tilde{x}_{\mathcal{T}}}\operatorname*{\mathbb{E}}_{i,j\sim[n]}1((i,j)\text{
good})\cdot\left(1-\frac{\|\mathop{\tilde{\mathbb{E}}}_{\mu_{\mathcal{T}}}\left[x_{i}-x_{j}\right]\|}{d_{ij}}\right)^{2}\leqslant
2\textsf{OPT}+\mathcal{O}\left(\left(\textsf{OPT}^{1/k}+\varepsilon^{2/k}\right)\cdot\log\Delta\right)\,.$

and the analogous claim for $k=1,2$. To obtain the theorem statement when
$k>2$, we rescale $\varepsilon\leftarrow(\varepsilon/\log(\Delta))^{k/2}$ (and
analogously for $k=1,2$). This gives us an algorithm using an LP of size
$(n\Delta)^{\mathcal{O}(k^{2}\log(\log\Delta/\varepsilon)\cdot(\log\Delta)^{k/2}/\varepsilon^{k/2})}$.
We discuss in Section 7 how to prune this LP while maintaining the same
guarantees. ∎

#### Proofs of Claims

We turn to the proofs of Claims 3.10 and 3.11.

###### Proof of Claim 3.10.

All but $\mathcal{O}\left(\textsf{OPT}\right)n^{2}$ pairs $(i,j)$ satisfy Eq.
2, by Lemma 3.8. Combining Lemma 3.5 and Lemma 3.9 shows that Eq. 3 holds for
all but $\mathcal{O}\left(\sqrt{\textsf{OPT}}+\varepsilon\right)n^{2}$ pairs,
with probability at least $0.99$ over $\mathcal{T}$, as long as
$|\mathcal{T}|\gg\log(1/\varepsilon)/\varepsilon$. And, applying Lemma 3.7
with $\delta=\Theta(\sqrt{\textsf{OPT}}+\varepsilon)$, we get that Eq. 4 holds
for all but
$\mathcal{O}\left(\sqrt{\textsf{OPT}}+\varepsilon\right)\cdot\log\Delta\cdot
n^{2}$ pairs $i,j$. ∎

###### Proof of Claim 3.11.

Let $\mathcal{I}$ be the set of pairs such Eq. 4 holds. It will be enough to
prove the claim with $1((i,j)\text{ good})$ replaced with
$1((i,j)\in\mathcal{I})$. For any $\delta>0$, applying Lemma 3.7 with $\delta$
and $\eta=\varepsilon^{\prime}=16\sqrt{\textsf{OPT}}+\varepsilon$ yields

$\begin{split}&{\mathop{\mathbf{Pr}}_{i,j\sim[n]}}\left[\frac{\mathcal{Q}\left(\left\\{\lVert
x_{i}^{*}-x_{k}^{*}\rVert^{2}\right\\}_{k\in[n]},\varepsilon^{\prime}\right)+\mathcal{Q}\left(\left\\{\lVert
x_{j}^{*}-x_{k}^{*}\rVert^{2}\right\\}_{k\in[n]},\varepsilon^{\prime}\right)}{\lVert
x_{i}^{*}-x_{j}^{*}\rVert^{2}}>\left(\frac{c(\sqrt{\textsf{OPT}}+\varepsilon)}{\delta}\right)^{2/k}\right]\leqslant\mathcal{O}\left(\delta\log(\Delta)\right).\end{split}$
(6)

for some fixed constant $c$. First, suppose $k>2$. For a non-negative random
variable $x$ such that $x\leqslant 1$ with probability $1$,
$\mathop{\mathbb{E}}\left[x\right]=\int_{0}^{1}\text{{Pr}}\left[x>t\right]dt$,
so using Eq. 6,

$\begin{split}&\mathop{\mathbb{E}}_{i,j\sim[n]}\left[1((i,j)\in\mathcal{I})\frac{\mathcal{Q}\left(\left\\{\lVert
x_{i}^{*}-x_{k}^{*}\rVert^{2}\right\\}_{k\in[n]},\varepsilon^{\prime}\right)+\mathcal{Q}\left(\left\\{\lVert
x_{j}^{*}-x_{k}^{*}\rVert^{2}\right\\}_{k\in[n]},\varepsilon^{\prime}\right)}{\lVert
x_{i}^{*}-x_{j}^{*}\rVert^{2}}\right]\\\
&=\mathop{\text{\huge$\int_{\text{\normalsize$\scriptstyle\kern-2.45004pt0$}}^{\text{\normalsize$\scriptstyle
1$}}$}}\nolimits{\mathop{\mathbf{Pr}}_{i,j\sim[n]}}\left[\frac{\mathcal{Q}\left(\left\\{\lVert
x_{i}^{*}-x_{k}^{*}\rVert^{2}\right\\}_{k\in[n]},\varepsilon^{\prime}\right)+\mathcal{Q}\left(\left\\{\lVert
x_{j}^{*}-x_{k}^{*}\rVert^{2}\right\\}_{k\in[n]},\varepsilon^{\prime}\right)}{\lVert
x_{i}^{*}-x_{j}^{*}\rVert^{2}}>t\right]dt\\\
&\leqslant\mathcal{O}\left(\varepsilon^{\prime}\cdot\log(\Delta)\right)\cdot\int_{(\varepsilon^{\prime})^{2/k}}^{1}\frac{dt}{t^{k/2}}+\int_{0}^{(\varepsilon^{\prime})^{2/k}}1\cdot
dt\leqslant\mathcal{O}\left(\left(\textsf{OPT}^{1/k}+\varepsilon^{2/k}\right)\cdot\log\left(\Delta\right)\right).\end{split}$
(7)

Turning to the case that $k=1$, we can use the same calculation as Eq. 7, but
now when we integrate $\int_{0}^{1}dt/t^{1/2}$ we get
$\mathcal{O}\left(1\right)$. When $k=2$, the integral
$\int_{\varepsilon}^{1}dt/t$ gives $\mathcal{O}\left(\log
1/\varepsilon\right)$. ∎

##  4 Proofs of Distance-Quantile Lemmas

In this section, we prove Lemma 3.7 through Lemma 3.9, beginning with the
simplest, Lemma 3.8.

###### Proof of Lemma 3.8.

By definition, we have

$\frac{1}{n^{2}}\sum_{i,j\in[n]}\left(1-\frac{\lVert
x^{*}_{i}-x^{*}_{j}\rVert}{d_{i,j}}\right)^{2}=\textsf{OPT}$

Then, by Markov’s inequality, for any constant $c\geqslant 1$,

${\mathop{\mathbf{Pr}}_{i,j\sim[n]}}\left[\left(1-\frac{\lVert
x_{i}^{*}-x_{j}^{*}\rVert}{d_{i,j}}\right)^{2}\geqslant
c\right]\leqslant\frac{\textsf{OPT}}{c}$ (8)

Therefore, with probability at least $1-(\textsf{OPT}/c)$, for a random pair
$i,j\sim[n]$,

$\left(1-\sqrt{c}\right)d_{i,j}\leqslant\lVert
x_{i}^{*}-x_{j}^{*}\rVert\leqslant\left(1+\sqrt{c}\right)d_{i,j},$ (9)

and squaring both sides yields the first claim. Further, Eq. 9 implies

$\left(1-2\sqrt{c}\right)\lVert x_{i}^{*}-x_{j}^{*}\rVert\leqslant
d_{i,j}\leqslant\left(1+2\sqrt{c}\right)\lVert x_{i}^{*}-x_{j}^{*}\rVert.$

Next, recall the pseudo-distribution $\mu$ satisfies

$\mathop{\tilde{\mathbb{E}}}_{\mu}\left[\frac{1}{n^{2}}\sum_{i,j\in[n]}\left(1-\frac{\lVert
x_{i}-x_{j}\rVert}{d_{i,j}}\right)^{2}\right]\leqslant\textsf{OPT},$

Again by Markov’s, with probability at least $1-\textsf{OPT}/c$, for a random
pair $i,j\sim[n]$,

$\mathop{\tilde{\mathbb{E}}}_{\mu}\left[\left(1-\frac{\lVert
x_{i}-x_{j}\rVert}{d_{i,j}}\right)^{2}\right]\leqslant c$ (10)

Next, observe, for any $(i,j)$ satisfying Eq. 10,

$\begin{split}\mathop{\tilde{\mathbb{E}}}_{\mu}\left[\left(\frac{\lVert
x_{i}-x_{j}\rVert}{d_{i,j}}\right)^{2}\right]\leqslant
2\left(\mathop{\tilde{\mathbb{E}}}_{\mu}\left[1\right]+\mathop{\tilde{\mathbb{E}}}_{\mu}\left[\left(1-\frac{\lVert
x_{i}-x_{j}\rVert}{d_{i,j}}\right)^{2}\right]\right)\leqslant
2+2c.\end{split}$ (11)

Further, it follows from Jensen’s inequality (going to local distributons and
back) that

$\frac{1}{n^{2}}\sum_{i,j\in[n]}\left(1-\frac{\mathop{\tilde{\mathbb{E}}}_{\mu}\left[\lVert
x_{i}-x_{j}\rVert\right]}{d_{i,j}}\right)^{2}\leqslant\mathop{\tilde{\mathbb{E}}}_{\mu}\left[\frac{1}{n^{2}}\sum_{i,j\in[n]}\left(1-\frac{\lVert
x_{i}-x_{j}\rVert}{d_{i,j}}\right)^{2}\right]\leqslant\textsf{OPT},$

and thus with probability at least $1-\textsf{OPT}/c$, for a random pair
$i,j\sim[n]$,

$\left(1-\sqrt{c}\right)d_{i,j}\leqslant\mathop{\tilde{\mathbb{E}}}_{\mu}\left[\lVert
x_{i}-x_{j}\rVert\right]\leqslant\left(1+\sqrt{c}\right)d_{i,j}.$

Further, this implies

$\left(1-2\sqrt{c}\right)\lVert
x_{i}^{*}-x_{j}^{*}\rVert\leqslant\mathop{\tilde{\mathbb{E}}}_{\mu}\left[\lVert
x_{i}-x_{j}\rVert\right]\leqslant\left(1+2\sqrt{c}\right)\lVert
x_{i}^{*}-x_{j}^{*}\rVert,$

which yields the second claim. We can complete the proof by observing that

$\begin{split}\mathop{\tilde{\mathbb{E}}}_{\mu}\left[\left(\frac{\lVert
x_{i}-x_{j}\rVert}{d_{i,j}}\right)^{2}\right]\geqslant\left(\frac{\mathop{\tilde{\mathbb{E}}}_{\mu}\left[\lVert
x_{i}-x_{j}\rVert\right]}{d_{i,j}}\right)^{2}\geqslant\left(\frac{1}{1+\sqrt{c}}\right)^{2}\geqslant
1-2\sqrt{c}.\end{split}$

∎

###  4.1 Quantiles of pair-wise distances on the line – proof of Lemma 3.7

In this section, we show that quantiles of distances between points on the
line are well-behaved.

###### Proof of Lemma 3.7.

We begin by partitioning the pair-wise distances that are at least $1$ into
geometrically increasing level sets in the range $[1,2\Delta]$ as follows: let
$\left\\{\mathcal{P}_{0},\mathcal{P}_{1},\ldots\mathcal{P}_{\log(\Delta)}\right\\}$
be a partition of $\mathcal{S}_{1}\times\mathcal{S}_{2}$ such that for each
$T\in[-1,\log(\Delta)]$,

$\mathcal{P}_{T}=\left\\{(i,j)\hskip 7.22743pt\big{|}\hskip 7.22743pt\lVert
x_{i}^{*}-x_{j}^{*}\rVert\in(2^{T},2^{T+1}],i,j\in[n]\right\\}.$ (12)

Next, for each $T\in[0,\log(\Delta)]$, we fix a $(2^{T}/2)$-cover, denoted by
$\mathcal{N}_{k,\Delta,2^{T}}$. Thus,
$\min_{x,y\in\mathcal{N}_{k,\Delta,2^{T}}}\|x-y\|>2^{T}/2$, and for any
$x\in[-\Delta,\Delta]^{\otimes k}$
$\min_{z\in\mathcal{N}_{k,\Delta,2^{T}}}\|x-z\|\leqslant 2^{T}/2$. We now
partition the space $[-\Delta,\Delta]^{\otimes k}$ by mapping each
$x\in[-\Delta,\Delta]^{\otimes k}$ to its nearest
$z\in\mathcal{N}_{k,\Delta,2^{T}}$, breaking ties arbitrarily. Let
$\mathcal{G}_{T}$ denote this partition, and note that each cluster
$S\in\mathcal{G}_{T}$ has diameter at most $2^{T}$. It follows that all
distances at scale $\mathcal{P}_{T}$ arise from points $x_{i}^{*},x_{j}^{*}$
that lie in distinct clusters of $\mathcal{G}_{T}$. Similarly, we define a
finer partition of $\mathcal{G}_{T}$, constructed via a smaller
$\varepsilon$-cover with $\varepsilon=\eta\cdot 2^{T}/\delta$, which we denote
by $\mathcal{F}_{\eta,T}$. For each
$\mathcal{B}\in\mathcal{F}_{\eta,T}\cup\mathcal{G}_{T}$ let
$\mathcal{C}(\mathcal{B})$ denote the number of points such that $i\in[n]$ and
$x_{i}^{*}\in\mathcal{B}$. If for any cluster
$\mathcal{B}\in\mathcal{F}_{\eta,T}$, i.e. the finer partition,
$\mathcal{C}(\mathcal{B})\leqslant\mathcal{O}\left(\eta^{k}n\right)$, we
discard all pairs $(i,j)\in\mathcal{P}_{T}$ that involve any $x_{i}^{*}$ such
that $x_{i}^{*}\in\mathcal{B}$ or $x_{j}^{*}\in\mathcal{B}$.

Observe, for the remaining pairs $(i,j)\in\mathcal{P}_{T}$, we know that
$x_{i}^{*}$ and $x_{j}^{*}$ land in distinct finer clusters from
$\mathcal{F}_{\eta,T}$ that each have at least $c\eta^{k}n$ points (for a
fixed constant $c$) $x^{*}_{k}$ such that $\lVert
x_{i}^{*}-x_{k}^{*}\rVert,\lVert
x_{j}^{*}-x_{k}^{*}\rVert\leqslant\frac{2\eta}{\delta}\lVert
x_{i}^{*}-x_{j}^{*}\rVert$. Therefore,

$\mathcal{Q}\left(\left\\{\left\lVert
x_{i}^{*}-x_{k}^{*}\right\rVert\right\\}_{k\in[n]},c\eta^{k}\right)+\mathcal{Q}\left(\left\\{\left\lVert
x_{j}^{*}-x_{k}^{*}\right\rVert\right\\}_{k\in[n]},c\eta^{k}\right)\leqslant\left(\frac{4\eta}{\delta}\right)\left\lVert
x_{i}^{*}-x_{j}^{*}\right\rVert,$ (13)

where the inequality follows from recalling that $(i,j)\in\mathcal{P}_{T}$.

It remains to show that the above procedure discarded at most
$\mathcal{O}\left(\delta^{k}n^{2}\right)$ pairs. Recall,
$\mathcal{G}_{T}=\left\\{\mathcal{B}_{\ell}\right\\}_{\ell\in[\lvert\mathcal{N}_{k,\Delta,2^{T}}\rvert]}$
is the set of clusters with diameter $2^{T}$ that cover
$[-\Delta,\Delta]^{\otimes k}$. Further, note that for each
$\mathcal{B}_{\ell}\in\mathcal{G}_{T}$, by the separation property of the
cover and the doubling dimension of $\mathbbm{R}^{k}$, we have that at most
$\left(c^{\prime}\delta/\eta\right)^{k}$ clusters in $\mathcal{F}_{\eta,T}$
intersect (and cover) $\mathcal{B}_{\ell}$, for a fixed constant $c^{\prime}$.

For a fixed cluster $\mathcal{B}_{\ell}\in\mathcal{G}_{T}$, we consider the
number of pairs $(i,j)$ dropped because either $x_{i}^{*}$ or $x_{j}^{*}$ lies
in a sub-cluster $\mathcal{S}\in\mathcal{F}_{\eta^{k},T}$ intersecting
$\mathcal{B}_{\ell}$ with at most $c\eta^{k}n$ points; call such a cluster
$\mathcal{S}$ light. Next, observe that any $x_{i}^{*}$ in a light sub-
cluster, for every distance $(x_{i}^{*},x_{j}^{*})$ in $\mathcal{P}_{T}$ the
point $x_{j}^{*}$ can be in one of at most $\mathcal{O}\left(2^{k}\right)$
clusters $\mathcal{B}_{\ell}\in\mathcal{G}_{T}$ since the ball of radius
$2^{2T+1}$ around $x_{i}^{*}$ is covered by $\mathcal{O}\left(2^{k}\right)$
clusters in $\mathcal{G}_{T}$ of radius $2^{T}/2$ (by the separation property
of the cover). Therefore, the total number of such pairs is at most
$\sum_{z\in[\mathcal{O}(2^{k})]}\mathcal{C}\left(\mathcal{B}_{\ell_{z}}\right)$.
Therefore, the total number of pairs dropped for a fixed cluster
$\mathcal{B}_{\ell}$ is at most

$\underbrace{\mathcal{O}\left(\frac{\delta}{\eta}\right)^{k}}_{\textrm{number
of light
clusters}}\cdot\underbrace{\mathcal{O}\left(\eta^{k}n\right)}_{\textrm{
$x_{i}^{*}$ in light clusters
}}\cdot\underbrace{\sum_{z\in[\mathcal{O}(2^{k})]}\mathcal{C}\left(\mathcal{B}_{\ell_{z}}\right)}_{\textrm{number
of $x_{j}^{*}$s in any neighboring cluster }}.$

Summing over all $\ell\in\lvert\mathcal{N}_{k,\Delta,\varepsilon}\rvert$, the
total number of such pairs dropped can be bounded as follows:

$\mathcal{O}\left(\delta^{k}\cdot
2^{k}n^{2}\right)\leqslant\mathcal{O}\left(\delta^{k}n^{2}\right)$

Summing over the $\log(\Delta)$ levels, and substituting
$\eta\leftarrow\eta^{1/k}$ and $\delta\leftarrow\delta^{1/k}$ concludes the
proof.

∎

###  4.2 Translating between pseudo-expected distances and optimal quantiles

In this section, we show that we can bound the pseudo-deviation of each
indeterminate in terms of the quantiles of the pair-wise distances in the
optimal embedding corresponding to that indeterminate. However, in this
translation, we lose a $\sqrt{\textsf{OPT}}$ factor, since we can only relate
the $\sqrt{\textsf{OPT}}$-th quantiles of the pseudo-expected distances to the
distances in an optimal embedding.

###### Proof of Lemma 3.9.

For each $i\in[n]$, let $\varepsilon_{i}$ be such that

$\mathcal{Q}\left(\left\\{\mathop{\tilde{\mathbb{E}}}_{\mu}\left[\lVert
x_{i}-x_{k}\rVert^{2}\right]\right\\}_{k\in[n]},\varepsilon\right)\leqslant
10\cdot\mathcal{Q}\left(\left\\{\lVert
x_{i}^{*}-x_{k}^{*}\rVert^{2}\right\\}_{k\in[n]},\varepsilon+\varepsilon_{i}\right).$

It follows from Lemma 3.8, with $c=1/16$ that

$\frac{1}{n}\sum_{i\in[n]}{\varepsilon_{i}}\leqslant 16\cdot\textsf{OPT},$
(14)

since each $\varepsilon_{i}$ contributes at least $\varepsilon_{i}\cdot n$
pairs such that $(i,k)$ does not satisfy

$\left(1-0.75\right)\lVert
x_{i}^{*}-x_{k}^{*}\rVert^{2}_{2}\leqslant\mathop{\tilde{\mathbb{E}}}_{\mu}\left[\lVert
x_{i}-x_{k}\rVert_{2}^{2}\right]\leqslant 2.5\lVert
x_{i}^{*}-x_{k}^{*}\rVert_{2}^{2},$

and we know that there are at most $16\textsf{OPT}\cdot n^{2}$ such pairs.
Thus applying Markov’s to (14),

${\mathop{\mathbf{Pr}}_{i\sim[n]}}\left[\varepsilon_{i}>16\sqrt{\textsf{OPT}}\right]\leqslant\sqrt{\textsf{OPT}}.$
(15)

Therefore, for all but $\sqrt{\textsf{OPT}}$-fraction of points, we have

$\mathcal{Q}\left(\left\\{\mathop{\tilde{\mathbb{E}}}_{\mu}\left[\lVert
x_{i}-x_{k}\rVert^{2}\right]\right\\}_{k\in[n]},\varepsilon\right)\leqslant
10\cdot\mathcal{Q}\left(\left\\{\lVert
x_{i}^{*}-x_{k}^{*}\rVert^{2}\right\\}_{k\in[n]},16\sqrt{\textsf{OPT}}+\varepsilon\right).$
(16)

Let $\mathcal{B}_{2}$ be the set of points that do not satisfy Eq. 16.
Observe,
$\lvert\mathcal{B}_{1}+\mathcal{B}_{2}\rvert\leqslant\mathcal{O}\left(\sqrt{\textsf{OPT}}+\varepsilon\right)n^{2}$,
which concludes the proof. ∎

##  5 Remaining Proofs: Variance Reduction and Discretization

First we prove the simple Fact 3.4, then we turn to the remaining key lemmas:
the discretization Lemma 3.1 and the variance-reduction Lemma 3.5.

###### Proof of Fact 3.4.

We have

$\begin{split}\left(1-\frac{\left\lVert\operatorname*{\mathbb{E}}X-\operatorname*{\mathbb{E}}Y\right\rVert}{d}\right)^{2}&=\left(1-\frac{\left\lVert\operatorname*{\mathbb{E}}X-\operatorname*{\mathbb{E}}Y\right\rVert+\operatorname*{\mathbb{E}}\|X-Y\|-\operatorname*{\mathbb{E}}\|X-Y\|}{d}\right)^{2}\\\
&\leqslant
2\left(1-\frac{\operatorname*{\mathbb{E}}\|X-Y\|}{d}\right)^{2}+2\left(\frac{\left\lVert\operatorname*{\mathbb{E}}X-\operatorname*{\mathbb{E}}Y\right\rVert-\operatorname*{\mathbb{E}}\|X-Y\|}{d}\right)^{2}\\\
&\leqslant
2\operatorname*{\mathbb{E}}\left(1-\frac{\|X-Y\|}{d}\right)^{2}+2\left(\frac{\left\lVert\operatorname*{\mathbb{E}}X-\operatorname*{\mathbb{E}}Y\right\rVert-\operatorname*{\mathbb{E}}\|X-Y\|}{d}\right)^{2}\\\
\end{split}$ (17)

where we used the inequality $(a+b)^{2}\leqslant 2(a^{2}+b^{2})$ and Jensen’s
inequality. For the last term above, we have

$\displaystyle\|\operatorname*{\mathbb{E}}X-\operatorname*{\mathbb{E}}Y\|$
$\displaystyle=\operatorname*{\mathbb{E}}\|(\operatorname*{\mathbb{E}}X-\operatorname*{\mathbb{E}}Y)+(X-Y)-(X-Y)\|$
$\displaystyle\leqslant\operatorname*{\mathbb{E}}\|X-\operatorname*{\mathbb{E}}X\|+\operatorname*{\mathbb{E}}\|Y-\operatorname*{\mathbb{E}}Y\|+\operatorname*{\mathbb{E}}\|X-Y\|$

and so therefore

$\|\operatorname*{\mathbb{E}}X-\operatorname*{\mathbb{E}}Y\|-\operatorname*{\mathbb{E}}\|X-Y\|\leqslant\operatorname*{\mathbb{E}}\|X-\operatorname*{\mathbb{E}}X\|+\operatorname*{\mathbb{E}}\|Y-\operatorname*{\mathbb{E}}Y\|\,.$

A similar argument shows

$\operatorname*{\mathbb{E}}\|X-Y\|-\|\operatorname*{\mathbb{E}}X-\operatorname*{\mathbb{E}}Y\|\leqslant\operatorname*{\mathbb{E}}\|X-\operatorname*{\mathbb{E}}X\|+\operatorname*{\mathbb{E}}\|Y-\operatorname*{\mathbb{E}}Y\|$

which completes the proof. ∎

###  5.1 Variance Reduction via Conditioning

In this section, we show that the pseudo-deviation of the variables $x_{i}$ is
related to the $\varepsilon$-th quantile of pseudo-expected distances. In
particular, we provide a proof of Lemma 3.5.

We begin by showing that conditioning on a subset of points reduces the
pseudo-deviation of any point to the distance between this point and the
closest conditioned point. Formally,

######  Lemma 5.1 (Pseudo-Deviation to Closest Conditioning).

Let $\mathcal{T}\subset[n]$ be any arbitrary subset of size $\tau\in[n]$, and
let $\mu$ be a degree-$2\tau$ pseudo-distribution over the vector-valued
indeterminate $x\in\mathbb{R}^{n}$. Let
$\tilde{x}_{\mathcal{T}}\in\mathcal{N}_{k,\Delta/\varepsilon,1}^{\lvert\mathcal{T}\rvert}$
be a draw from the local distribution $\left\\{x_{\mathcal{T}}\right\\}$ and
$\mu_{\mathcal{T}}$ be the pseudo-distribution obtained by conditioning on the
event
$\zeta_{\mathcal{T}}:=\left\\{x_{j}=\tilde{x}_{j}\right\\}_{j\in\mathcal{T}}$.
Then, for all $i\in[n]$,

$\mathop{\mathbb{E}}_{\tilde{x}_{\mathcal{T}}}\left[\mathop{\tilde{\mathbb{D}}}_{\mu_{\mathcal{T}}}\left[x_{i}\right]^{2}\right]\leqslant
2\cdot\min_{j\in\mathcal{T}}\mathop{\tilde{\mathbb{E}}}_{\mu}\left[\left\lVert
x_{i}-x_{j}\right\rVert^{2}\right].$

###### Proof.

Since $\mu$ has degree at least $2\tau$, any pseudo-distribution over $\tau$
variables can be treated as a true local distribution. Then, for any fixed
$j\in\mathcal{T}$,

$\begin{split}\mathop{\mathbb{E}}_{\tilde{x}_{\mathcal{T}}}\left[\mathop{\tilde{\mathbb{D}}}_{\mu_{\mathcal{T}}}\left[x_{i}\right]^{2}\right]&=\mathop{\mathbb{E}}_{\tilde{x}_{\mathcal{T}}}\left[\left(\mathop{\tilde{\mathbb{E}}}_{\mu}\left[\left\lVert
x_{i}-\mathop{\tilde{\mathbb{E}}}_{\mu}\left[x_{i}|\zeta_{\mathcal{T}}\right]\right\rVert\Big{|}\zeta_{\mathcal{T}}\right]\right)^{2}\right]\\\
&=\mathop{\mathbb{E}}_{\tilde{x}_{\mathcal{T}}}\left[\left(\mathop{\tilde{\mathbb{E}}}_{\mu}\left[\left\lVert
x_{i}-x_{j}+\left(x_{j}-\mathop{\tilde{\mathbb{E}}}_{\mu}\left[x_{i}|\zeta_{\mathcal{T}}\right]\right)\right\rVert\Big{|}\zeta_{\tau}\right]\right)^{2}\right]\\\
&\leqslant
2\mathop{\mathbb{E}}_{\tilde{x}_{\mathcal{T}}}\left[\left(\mathop{\tilde{\mathbb{E}}}_{\mu}\left[\left\lVert
x_{i}-x_{j}\right\rVert\Big{|}\zeta_{\mathcal{T}}\right]\right)^{2}\right]+2\mathop{\mathbb{E}}_{\tilde{x}_{\mathcal{T}}}\left[\left(\mathop{\tilde{\mathbb{E}}}_{\mu}\left[\left\lVert
x_{j}-\mathop{\tilde{\mathbb{E}}}_{\mu}\left[x_{i}|\zeta_{\mathcal{T}}\right]\right\rVert\Big{|}\zeta_{\mathcal{T}}\right]\right)^{2}\right]\\\
&\leqslant
2\mathop{\mathbb{E}}_{\tilde{x}_{\mathcal{T}}}\left[\mathop{\tilde{\mathbb{E}}}_{\mu}\left[\left\lVert
x_{i}-x_{j}\right\rVert^{2}\Big{|}\zeta_{\mathcal{T}}\right]\right]+2\mathop{\mathbb{E}}_{\tilde{x}_{\mathcal{T}}}\left[\left(\mathop{\tilde{\mathbb{E}}}_{\mu}\left[\left\lVert\mathop{\tilde{\mathbb{E}}}_{\mu}\left[x_{j}-x_{i}|\zeta_{\mathcal{T}}\right]\right\rVert\Big{|}\zeta_{\mathcal{T}}\right]\right)^{2}\right]\\\
&\leqslant 2\mathop{\tilde{\mathbb{E}}}_{\mu}\left[\lVert
x_{i}-x_{j}\rVert^{2}\right]+2\mathop{\mathbb{E}}_{\tilde{x_{\mathcal{T}}}}\left[\left(\mathop{\tilde{\mathbb{E}}}_{\mu}\left[\lVert
x_{j}-x_{i}\rVert|\zeta_{\mathcal{T}}\right]\right)^{2}\right]\\\ &\leqslant
4\mathop{\tilde{\mathbb{E}}}_{\mu}\left[\lVert
x_{i}-x_{j}\rVert^{2}\right],\end{split}$ (18)

where the first inequality follows from triangle inequality, the second
follows from Jensen’s inequality, combined with the law of conditional
expectation. Repeating the above inequality for all $j\in\mathcal{T}$, and
taking the minimum yields the claim. ∎

We can now complete the proof of Lemma 3.5.

###### Proof of Lemma 3.5.

Let $\zeta_{i,\mathcal{T}}$ be the event that the set $\mathcal{T}$ contains
$j$ such that

$\mathop{\tilde{\mathbb{E}}}\left[\lVert
x_{i}-x_{j}\rVert^{2}\right]\leqslant\mathcal{Q}\left(\left\\{\mathop{\tilde{\mathbb{E}}}\left[\lVert
x_{i}-x_{j}\rVert^{2}\right]\right\\}_{j\in[n]},\varepsilon\right).$

Then,

$\begin{split}\mathop{\mathbb{E}}_{\zeta_{\mathcal{T}}}\left[\mathop{\tilde{\mathbb{D}}}_{\mu_{\mathcal{T}}}\left[x_{i}\right]^{2}\right]&=\mathop{\mathbb{E}}_{\zeta_{\mathcal{T}}}\left[\mathop{\tilde{\mathbb{D}}}_{\mu_{\mathcal{T}}}\left[x_{i}\right]^{2}\left(\mathop{\mathbb{1}}\left[\zeta_{i,\mathcal{T}}\right]+1-\mathop{\mathbb{1}}\left[\zeta_{i,\mathcal{T}}\right]\right)\right]\\\
&\leqslant
2\left(\min_{j\in\mathcal{T}}\mathop{\tilde{\mathbb{E}}}_{\mu}\left[\lVert
x_{i}-x_{j}\rVert^{2}\right]\right)\cdot\mathop{\mathbb{1}}\left[\zeta_{i,\mathcal{T}}\right]+\mathop{\mathbb{E}}_{\zeta_{\mathcal{T}}}\left[\left(1-\mathop{\mathbb{1}}\left[\zeta_{i,\mathcal{T}}\right]\right)\mathop{\tilde{\mathbb{D}}}_{\mu_{\mathcal{T}}}\left[x_{i}\right]\right]\\\
&\leqslant
2\mathcal{Q}\left(\left\\{\mathop{\tilde{\mathbb{E}}}_{\mu}\left[\lVert
x_{i}-x_{j}\rVert^{2}\right]\right\\}_{j\in[n]},\varepsilon\right)\cdot\mathop{\mathbb{1}}\left[\zeta_{i,\mathcal{T}}\right]+\left(1-\mathop{\mathbb{1}}\left[\zeta_{i,\mathcal{T}}\right]\right)\cdot\mathop{\tilde{\mathbb{D}}}_{\mu_{\mathcal{T}}}\left[x_{i}\right]\end{split}$
(19)

where the first inequality uses Lemma 5.1 and the second uses that when
$\mathop{\mathbb{1}}\left[\zeta_{i,\mathcal{T}}\right]=1$,

$\min_{j\in\mathcal{T}}\mathop{\mathbb{E}}_{\mu}\left[\lVert
x_{i}-x_{j}\rVert^{2}\right]\leqslant\mathcal{Q}\left(\left\\{\mathop{\mathbb{E}}_{\mu}\left[\lVert
x_{i}-x_{j}\rVert^{2}\right]\right\\}_{j\in[n]},\varepsilon\right).$

Next, observe

$\mathbf{Pr}\left[\zeta_{i\mathcal{T}}=0\right]\leqslant\left(1-\varepsilon\right)^{\tau}\leqslant\mathcal{O}\left(\delta\right).$
(20)

Conditioning on the event that $\zeta_{i\mathcal{T}}=1$, it follows from
Equation (19) that with probability at least $1-\delta$ over the choice of
$\mathcal{T}$,

$\mathop{\mathbb{E}}_{\tilde{x}_{\mathcal{T}}}\left[\mathop{\tilde{\mathbb{D}}}_{\mu_{\mathcal{T}}}\left[x_{i}\right]^{2}\right]\leqslant\mathcal{Q}\left(\left\\{\mathop{\tilde{\mathbb{E}}}_{\mu}\left[\lVert
x_{i}-x_{j}\rVert^{2}\right]\right\\}_{j\in[n]},\varepsilon\right),$

which concludes the proof.

∎

###  5.2 Discretization

###### Proof of Lemma 3.1.

Let $\left\\{x_{i}^{*}\right\\}_{i\in[n]}$ be an embedding with cost OPT.
First, using Jensen’s inequality:

$\begin{split}1\geqslant\textsf{OPT}&=\mathop{\mathbb{E}}_{i,j}\left[\left(1-\frac{\|x_{i}^{*}-x_{j}^{*}\|}{d_{i,j}}\right)^{2}\right]\\\
&\geqslant
1-2\mathop{\mathbb{E}}_{i,j}\left[\frac{\|x_{i}^{*}-x_{j}^{*}\|}{d_{i,j}}\right]+\left(\mathop{\mathbb{E}}_{i,j}\left[\frac{\|x_{i}^{*}-x_{j}^{*}\|}{d_{i,j}}\right]\right)^{2}\\\
\end{split}$ (21)

which implies that

$\mathop{\mathbb{E}}_{i,j}\left[\frac{\|x_{i}^{*}-x_{j}^{*}\|}{\Delta}\right]\leqslant\mathop{\mathbb{E}}_{i,j}\left[\frac{\|x_{i}^{*}-x_{j}^{*}\|}{d_{i,j}}\right]\leqslant
2$ (22)

and therefore
$\mathop{\mathbb{E}}_{i,j}\left[\|x_{i}^{*}-x_{j}^{*}\|\right]\leqslant
2\Delta$. Letting $c\in\\{x_{i}^{*}\\}_{i\in[n]}$ be the center of
$\\{x_{i}^{*}\\}_{i\in[n]}$, i.e. a point such that

$c=\arg\min_{i\in[n]}\sum_{j\in[n]}\|x_{i}^{*}-x_{j}^{*}\|$

It follows for such a choice of $c$ that
$\mathop{\mathbb{E}}_{i\sim[n]}\left[\|c-x_{i}^{*}\|\right]\leqslant 2\Delta$.
Now define the modified point set $\\{x_{i}\\}_{i\in[n]}$ as the image of the
projection of $\\{x_{i}^{*}\\}_{i\in[n]}$ onto the metric ball
$\mathcal{B}\left(c,\frac{10}{\varepsilon}\Delta\right)$. By Markov’s
inequality, we have $\left\lvert
X^{*}\cap\mathcal{B}\left(c,\frac{10}{\varepsilon}\Delta\right)\right\rvert\geqslant(1-\frac{\varepsilon}{5})n$.
Thus, assuming $\varepsilon$ is smaller than some constant, we have

$\left|\left\\{(i,j)\;:\;\|x_{i}^{*}-x_{j}^{*}\|\neq\|x_{i}-x_{j}\|\right\\}\right|\leqslant\frac{\varepsilon^{2}}{25}n^{2}+\frac{\varepsilon}{5}n^{2}\leqslant\frac{\varepsilon}{4}n^{2}$

Moreover, since the mapping
$X^{*}\mapsto\mathcal{B}\left(c,\frac{10}{\varepsilon}\Delta\right)$ was a
contraction, for each such above pair $i,j$ we have:

$\left(1-\frac{\|x_{i}-x_{j}\|}{d_{i,j}}\right)^{2}-\left(1-\frac{\|x_{i}^{*}-x_{j}^{*}\|}{d_{i,j}}\right)^{2}\leqslant
1$

from which if follows that $\frac{1}{n^{2}}\sum_{i,j}\left(1-\frac{\lVert
x_{i}-x_{j}\rVert}{d_{i,j}}\right)^{2}\leqslant\textsf{OPT}+\varepsilon/4$.
Next, we fix an $\varepsilon$-net $\mathcal{N}$ over
$\mathcal{B}\left(c,\frac{10}{\varepsilon}\Delta\right)$; by standard volume
arguments, such nets exist with size
$|\mathcal{N}|\leqslant\mathcal{O}\left((\frac{\Delta}{\varepsilon})^{k}\right)$.
We then map each point $x_{i}$ to the nearest net point in $\mathcal{N}$, and
let $\\{y_{i}\\}_{i\in[n]}$ be the resulting mapping. For all
$i,j\in\binom{n}{2}$, we have

$\begin{split}\left|\left(1-\frac{\|x_{i}-x_{j}\|}{d_{i,j}}\right)^{2}-\left(1-\frac{\|y_{i}-y_{j}\|}{d_{i,j}}\right)^{2}\right|&\leqslant\left|\left(1-\frac{\|x_{i}-x_{j}\|}{d_{i,j}}\right)^{2}-\left(1-\frac{\|x_{i}-x_{j}\|}{d_{i,j}}\pm\varepsilon\right)^{2}\right|\\\
&\leqslant
2\varepsilon\left(1-\frac{\|x_{i}-x_{j}\|}{d_{i,j}}\right)^{2}+\varepsilon^{2}\end{split}$

Thus

$\begin{split}\frac{1}{n^{2}}\sum_{i,j}\left(1-\frac{\lVert
y_{i}-y_{j}\rVert}{d_{i,j}}\right)^{2}&\leqslant\frac{1}{n^{2}}\sum_{i,j}(1+2\varepsilon)\left(1-\frac{\lVert
x_{i}-x_{j}\rVert}{d_{i,j}}\right)^{2}+\varepsilon^{2}\\\
&\leqslant(1+2\varepsilon)\left(\textsf{OPT}+\varepsilon/4\right)+\varepsilon^{2}\leqslant\textsf{OPT}+3\varepsilon\end{split}$

which completes the proof with $\\{y_{i}\\}_{i\in[n]}$ being the desired
mapping after a rescaling of $\varepsilon$. ∎

##  6 Dimension Reduction for Kamada-Kawai

######  Lemma 6.1 (Dimension Reduction for Kamada-Kawai).

Let $\\{d_{i,j}\\}_{i\neq j\in[n]}$ be positive, and for $k\in\mathbbm{N}$ let

$\textsf{OPT}_{k}=\min_{x_{1},\ldots,x_{n}\in\mathbbm{R}^{k}}\frac{1}{n^{2}}\sum_{i\neq
j\in[n]}\left(1-\frac{\|x_{i}-x_{j}\|}{d_{i,j}}\right)^{2}\,.$

For every $\varepsilon>0$ and $k$,

$\textsf{OPT}_{1/\varepsilon}\leqslant\textsf{OPT}_{k}+\mathcal{O}\left(\varepsilon\right)\,.$

###### Proof.

Since $\textsf{OPT}_{k}$ is monotonically non-increasing in $k$, if
$k\leqslant 1/\varepsilon$ then the statement is trivial. So we can assume
$k>1/\varepsilon$. Let $S\in\mathbbm{R}^{1/\varepsilon\times k}$ be a matrix
consisting of independent mean zero variance $\varepsilon$ Gaussian entries
(i.e. $S_{i,j}\sim\mathcal{N}(0,\varepsilon)$). It is standard that
$\mathop{\mathbb{E}}\left[\|Sx\|^{2}\right]=\|x\|^{2}$ for any vector
$x\in\mathbbm{R}^{k}$. Let $x_{1},\ldots,x_{n}\in\mathbbm{R}^{k}$ witness the
value of $\textsf{OPT}_{k}$. We analyze

$\textsf{OPT}_{1/\varepsilon}\leqslant\mathop{\mathbb{E}}_{S}\left[\,\frac{1}{n^{2}}\sum_{i\neq
j}\left(1-\frac{\|Sx_{i}-Sx_{j}\|}{d_{i,j}}\right)^{2}\right]=\frac{1}{n^{2}}\sum_{i\neq
j}1-2\frac{\mathop{\mathbb{E}}_{S}\left[\|Sx_{i}-Sx_{j}\|\right]}{d_{i,j}}+\frac{\|x_{i}-x_{j}\|^{2}}{d_{i,j}^{2}}\,.$

By Lemma 6.2, we have
$\mathop{\mathbb{E}}_{S}\left[\|Sx_{i}-Sx_{j}\|\right]\geqslant\|x_{i}-x_{j}\|(1-O(\varepsilon))$.
Therefore, we get

$\textsf{OPT}_{1/\varepsilon}\leqslant\textsf{OPT}_{k}+\mathcal{O}\left(\epsilon\right)\cdot\frac{1}{n^{2}}\sum_{i\neq
j}\frac{\|x_{i}-x_{j}\|}{d_{i,j}}\,.$ (23)

To bound the last term, we observe that by Jensen’s inequality,

$\begin{split}1\geqslant\textsf{OPT}_{k}&=\mathop{\mathbb{E}}_{i,j}\left[\left(1-\frac{\lVert
x_{i}-x_{j}\rVert}{d_{i,j}}\right)^{2}\right]\\\ &\geqslant
1+\left(\mathop{\mathbb{E}}_{i,j}\left[\frac{\lVert
x_{i}-x_{j}\rVert}{d_{i,j}}\right]\right)^{2}-2\mathop{\mathbb{E}}_{i,j}\left[\frac{\lVert
x_{i}-x_{j}\rVert}{d_{i,j}}\right]\end{split}$

Rearranging, we have

$\left(\mathop{\mathbb{E}}_{i,j}\left[\frac{\lVert
x_{i}-x_{j}\rVert}{d_{i,j}}\right]\right)\leqslant 2,$

and substituting back into Eq. 23 completes the proof. ∎

######  Lemma 6.2 (Sketching dimension for expected euclidean norm).

Let $S\in\mathbbm{R}^{k\times n}$ be a matrix consisting of i.i.d. Gaussian
entries drawn from $\mathcal{N}(0,1/k)$. Then for any vector
$x\in\mathbbm{R}^{n}$, we have

$\mathop{\mathbb{E}}_{S}\left[\left\lVert
Sx\right\rVert\right]=\left(1\pm\mathcal{O}\left(\frac{1}{k}\right)\right)\lVert
x\rVert.$

###### Proof.

By scaling, it will suffice to prove the result for unit vectors $x$. In this
case, the value $\|Sx\|$ is distributed as the square root of a chi-squared
variable with $k$ degrees of freedom, which is also known as a chi-
distribution with $k$ degrees of freedom. It is known that
$\mathbb{E}[\|Sx\|]=\sqrt{\frac{2}{k}}\cdot\frac{\Gamma(\frac{k+1}{2})}{\Gamma(\frac{k}{2})}$
(see e.g. Appendix E, p.972 of [Goo10]). Setting $m=k+1$, we have

$\mathbb{E}[\|Sx\|]=\sqrt{\frac{2}{m-1}}\cdot\frac{\Gamma(m/2)}{\Gamma((m-1)/2)}$
(24)

By the the Legendre Duplication Formula [Wei19], we can write

$\Gamma((m-1)/2)=\sqrt{\pi}\cdot 2^{2-m}\cdot\frac{\Gamma(m-1)}{\Gamma(m/2)}$
(25)

Plugging Eq. 25 into Eq. 24 yields

$\mathbb{E}[\|Sx\|]=\sqrt{\frac{2}{\pi(m-1)}}\cdot
2^{m-2}\frac{(\Gamma(m/2))^{2}}{\Gamma(m-1)}$

We can then apply Stirling’s approximation
$\Gamma(z)=\sqrt{2\pi}(z-1)^{z-1+1/2}e^{-(z-1)}(1+O(1/z))$ to approximate the
Gamma functions above, which yields

$\begin{split}\mathbb{E}[\|Sx\|]&=\sqrt{\frac{2}{\pi(m-1)}}\cdot
2^{m-2}\cdot\frac{\left(\sqrt{2\pi}(\frac{m}{2}-1)^{\frac{m}{2}-1+\frac{1}{2}}e^{-(\frac{m}{2}-1)}\cdot\left(1+O\left(\frac{1}{m}\right)\right)\right)^{2}}{\sqrt{2\pi}(m-2)^{m-2+\frac{1}{2}}e^{-(m-2)}\cdot\left(1+O\left(\frac{1}{m}\right)\right)}\\\
&=2\sqrt{\frac{1}{(m-1)}}\cdot
2^{m-2}\cdot\frac{(\frac{m}{2}-1)^{m-1}e^{-(m-2)}\cdot\left(1+O\left(\frac{1}{m}\right)\right)}{2^{m-1}(m-2)^{-1/2}(\frac{m}{2}-1)^{m-1}e^{-(m-2)}\cdot\left(1+O\left(\frac{1}{m}\right)\right)}\\\
&=\frac{1}{\sqrt{m-1}}\cdot\sqrt{m-2}\cdot\left(1+O\left(\frac{1}{m}\right)\right)\\\
&=\frac{1}{\sqrt{m-1}}\cdot\sqrt{m-1}\cdot\left(1-\frac{1}{m-1}\right)^{1/2}\cdot\left(1+O\left(\frac{1}{m}\right)\right)\\\
&=1\pm O\left(\frac{1}{k}\right)\\\ \end{split}$

Where in the last line we used that $(1-x)^{1/2}=(1-\Theta(x))$ for
sufficiently small $x\in[0,1]$.

∎

##  7 Implementation with poly(n)-size LP

In this section we show that our algorithm can be implemented with a linear
program of size
$n^{2}\cdot\left(\Delta\right)^{\tilde{\mathcal{O}}\left(k^{2}\log(\Delta)^{k/2}/\varepsilon^{k/2}\right)}$,
resulting in a running time of
$n^{\mathcal{O}(1)}\left(\Delta\right)^{\tilde{\mathcal{O}}\left(k^{2}\log(\Delta)^{k/2}/\varepsilon^{k/2}\right)}$.

#### Subsets of the Sherali-Adams LP.

We can define an LP analogous to the Sherali-Adams LP (see Section 2) for any
subset $\mathcal{S}\subseteq\binom{n}{t}$, as opposed to all subsets of size
$t$. We can introduce variables corresponding to local distributions $\mu_{T}$
only for $T\in\mathcal{S}$ and add the consistency constraints such that the
marginal distribution on the intersection of any pair
$T_{1},T_{2}\in\mathcal{S}$ is the same. It is easy to verify that this LP has
at most $|\Omega|^{O(t)}\cdot|\mathcal{S}|^{2}$ variables and constraints.

######  Corollary 7.1 (Sparsifying the Sherali-Adams LP).

Given an instance of MDS with aspect ratio $\Delta$, target dimension $k$, and
target accuracy $\varepsilon$, the relaxation and rounding introduced in
Algorithm 3.2 can be implemented in
$n^{\mathcal{O}(1)}\left(\Delta/\varepsilon\right)^{\mathcal{O}(\tau)}$ time,
where

$\tau=\begin{cases}\mathcal{O}\left(\left(\log\left(\log(\Delta)/\varepsilon\right)\log\left(\Delta/\varepsilon\right)\right)/\varepsilon\right)&\textrm{
if }k=1\\\
\mathcal{O}\left((\log^{2}\left(\log(\Delta)/\varepsilon\right)\log\left(\Delta/\varepsilon\right))/\varepsilon\right)&\textrm{
if }k=2\\\
\mathcal{O}\left(\left(k\log(\log(\Delta)/\varepsilon)\log(\Delta/\varepsilon)^{k/2}\right)/\varepsilon^{k/2}\right)&\textrm{
otherwise.}\end{cases}$

The approximation guarantees remain identical to Theorem 1.3.

###### Proof.

Let $\mathcal{S}_{0}\subset\binom{n}{\tau-2}$ be a subset of size
$\mathcal{O}\left(n/\varepsilon\right)$, where each element is picked
uniformly at random. We augment each tuple in $\mathcal{S}_{0}$ of size
$\tau-2$ by adding all pairs:

$\mathcal{S}=\left\\{T\cup\left\\{i,j\right\\}\textrm{ for
}T\in\mathcal{S}_{0}\textrm{ and }i,j\in[n]\right\\}.$

We can now write down an LP relaxation analogous to Sherali-Adams, where we
define variables $\mu_{T}(x)$ for each $T\in\mathcal{S}$ and consistency
constraints for the intersection of every pair $T_{1},T_{2}\in\mathcal{S}$.
Observe, for the complete Sherali-Adams hierarchy we can condition on $x_{T}$
corresponding to any set $T\in\binom{n}{\tau}$ of size $\tau$ and Algorithm
3.2 conditions on a uniformly random set of size $\tau$.

In our modified LP, we can condition on $x_{T}$ corresponding to any set
$T\in\mathcal{S}_{0}$ and the resulting conditioned pseudo-distribution
$\mu_{T}$ would corresponding to a level-$2$ Sherali-Adams program. The bulk
of our analysis remains unchanged except for the proof of Lemma 3.5. It
suffices to show that for the sparse set $\mathcal{S}$, conditioning on a
random $T$ still hits an index in the $\varepsilon$-th quantile of every pair,
and thus reduces the variance.

To this end, we show that $T$ intersects with any subset of size $\varepsilon
n$ with non-trivial probability. Let $Q\subset[n]$ be a fixed subset of size
$\varepsilon\cdot n$. Then, using standard concentration bounds for Bernoulli
random variables,

$\begin{split}&{\mathop{\mathbf{Pr}}_{\mathcal{S}_{0}}}\left[\left\lvert{\mathop{\mathbf{Pr}}_{T\sim\mathcal{S}_{0}}}\left[T\cap
Q\neq\phi\right]-\mathop{\mathbb{E}}\left[{\mathop{\mathbf{Pr}}_{T\sim\mathcal{S}_{0}}}\left[T\cap
Q\neq\phi\right]\right]\right\rvert\geqslant\varepsilon\right]\\\
&={\mathop{\mathbf{Pr}}_{\mathcal{S}_{0}}}\left[\left\lvert{\mathop{\mathbf{Pr}}_{T\sim\mathcal{S}_{0}}}\left[T\cap
Q\neq\phi\right]-{\mathop{\mathbf{Pr}}_{T\sim\binom{n}{\tau-2}}}\left[T\cap
Q\neq\phi\right]\right\rvert\geqslant\varepsilon\right]\\\
&\leqslant\delta\end{split}$

whenever $\mathcal{S}_{0}\geqslant\log(1/\delta)/\varepsilon^{2}$. Recall,
there are $\binom{n}{\varepsilon n}\leqslant 2^{\mathcal{O}\left(\varepsilon
n\right)}$ sets $Q$ of size $\varepsilon n$. Union bounding over the choice of
$Q$, setting $\mathcal{S}_{0}$ to have $\mathcal{O}\left(n/\varepsilon\right)$
random sets of size $\tau-2$ suffices to recover the quantile statements.
Therefore, the running time is now

$\lvert\mathcal{S}\rvert^{\mathcal{O}(1)}\cdot\lvert\Omega\rvert^{\mathcal{O}(\tau)}=n^{\mathcal{O}(1)}\cdot\left(\Delta/\varepsilon\right)^{\mathcal{O}(k\cdot\tau)},$

which concludes the proof. ∎

##  8 Open Problems

Our work gives, as far as we know, the first polynomial-time approximation
algorithm for any MDS-style objective function with provable approximation
guarantees when $\Delta$ is super-logarithmic in $n$. We hope that the idea of
using convex programming hierarchies to Kamada-Kawai opens the door to further
progress on related optimization-based formulations of dimension reduction,
MDS, and metric embedding. To this end, we offer a non-exhaustive list of some
open problems, focusing on MDS-style objectives.

#### Improved algorithms for Kamada-Kawai.

The only hardness of approximation we are aware of for the Kamada-Kawai
objective is the result of [DHK+21] showing that an FPTAS is not possible
unless $P=NP$. But this does not rule out, say, constant-factor approximation:

######  Problem 8.1.

Design a constant-factor approximation algorithm for the Kamada-Kawai function
which is polynomial time for superlogarithmic aspect ratio.

#### Weighted least squares.

A wider range of MDS-style objectives (many available in R, scikit-learn,
Matlab, etc.) is captured via the following generalization of Kamada-Kawai. A
weighted least-squares instance is specified by dissimilarities
$\\{d_{ij}\\}_{i,j\in[n]}$ as well as nonnegative weights
$\\{w_{ij}\\}_{i,j\in[n]}$. The objective function is now

$\min_{x_{1},\ldots,x_{n}\in\mathbbm{R}^{k}}\operatorname*{\mathbb{E}}_{i\neq
j}w_{ij}\left(1-\frac{\|x_{i}-x_{j}\|}{d_{ij}}\right)^{2}=\min_{x_{1},\ldots,x_{n}\in\mathbbm{R}^{k}}\operatorname*{\mathbb{E}}_{i\neq
j}\frac{w_{ij}}{d_{ij}^{2}}(d_{ij}-\|x_{i}-x_{j}\|)^{2}\,.$

Setting all $w_{ij}=1$ recovers the Kamada-Kawai objective; other choices lead
to other popular MDS objectives. For instance, $w_{ij}=d_{ij}$ is “Sammon
mapping” and $w_{ij}=d_{ij}^{2}$ is “raw stress”. By analogy to CSPs, it’s
natural to associate a parameter to the weights measuring their density: let
$W=\max w_{ij}/\operatorname*{\mathbb{E}}w_{ij}$. The algorithm of [DHK+21]
extends to an additive PTAS for weighted MDS, with running time exponential in
$W$.

######  Problem 8.2.

Provide nontrivial polynomial-time approximation guarantees for weighted
least-squares when $\Delta$ is superlogarithmic.

#### Krustal Stress-1 and Stress-2.

Another common objective function for MDS is Kruskal’s “Stress-$1$”, given by

$\text{Stress-$1$}(x_{1},\ldots,x_{n})=\frac{\operatorname*{\mathbb{E}}_{i\neq
j}(d_{ij}-\|x_{i}-x_{j}\|)^{2}}{\operatorname*{\mathbb{E}}_{i\neq
j}\|x_{i}-x_{j}\|^{2}}\,.$

Stress-$1$ is qualitatively different from the objectives we discussed already
because of the normalization by $\|x_{i}-x_{j}\|$, meaning that the objective
value penalizes contracting pairs somewhat more than the weighted least-
squares objective. A local-search routine for minimizing Stress-1 is the
default implementation in Matlab’s built-in mdscale, and is also available in
scikit-learn. Stress-$2$ is yet another variant:

$\text{Stress-$2$}(x_{1},\ldots,x_{n})=\frac{\left(\operatorname*{\mathbb{E}}_{i\neq
j}(d_{ij}-\|x_{i}-x_{j}\|)^{2}\right)^{2}}{\operatorname*{\mathbb{E}}_{i\neq
j}\|x_{i}-x_{j}\|^{4}}\,.$

######  Problem 8.3.

Provide a nontrivial polynomial-time approximation algorithm for Kruskal
Stress-$1$ or Stress-$2$.

##  9 Additional Related Work

We review some additional related work in the broad area of metric embeddings.
For embedding into $\mathbbm{R}^{k}$ the multiplicative distortion of a pair
of input points $i,j$ with input distance $d_{ij}$ and output distance
$d^{\prime}_{ij}$, would be
$\max\left(d^{\prime}_{ij}/d_{ij},d_{ij}/d^{\prime}_{ij}\right),$ and the
additive distortion, for some objective norm $p$,
$\operatorname*{\mathbb{E}}_{i,j}||d^{\prime}_{ij}-d_{ij}||^{p}.$

In this context, we distinguish two lines of works: (1) on absolute
distortion, where the goal is to show a bound $X$ such that for any input the
distortion is at most $X$; versus (2) on relative or “data-dependent”
distortion, where the goal is to algorithmically compute an embedding that for
any input is as close to the best embedding as possible for that input.

In the first line of work, the classic results of Bartal [Bar96] and
Fakcharoenphol, Rao and Talwar [FRT04] show that one can probabilistically
embed any metric space into a tree with polylogarithmic distortion. For the
case of embedding into Euclidean spaces and minimizing the multiplicative
distortion, we refer to the work of Matousek [Mat90, Mat96]. For embedding
ultrametrics into Euclidean spaces while minimizing the multiplicative
distortion, Onak and Sidiropoulos [OS08] provide a
polylog$\Delta$-approximation where (see also [BCIS06]).

Additionally, there has been a line of work studying various notions of
average-distortion when the mapping is constrained to be either non-
contracting or non-expanding. For instance, Rabinovich [Rab08] considers
embedding an arbitrary $n$-point metric $(X,d_{X})$ into the line, where the
average distance is defined as $\frac{\mathbb{E}_{x,y\in
X}[d_{X}(x,y)]}{\mathbb{E}_{x,y\in X}[|f(x)-f(y)|]}$ subject to the constraint
that the embedding $f:X\to\mathbbm{R}$ is non-expanding; the authors also
consider the multiplicative inverse of this objective taken over non-
contracting embeddings, and argue that the former is a more natural variant
due to the phenomenon of concentration of measure. Notice that these
objectives capture a notion of how the average distance must decrease when
mapping to a lower dimensional metric space, rather than measuring the average
distortion that a pair of points incurs under this mapping (which is the goal
of MDS). A related objective, studied in [LMN05, BFN19]), which is closer to
the spirit of MDS, is $\mathbb{E}[|x-y|/d(x,y)]$ taken over non-contracting
embeddings.

#### “Data”-dependent embeddings

In this paper, we are concerned with the second line of work. Strong
inapproximability results for max-distortion in the mid 2000s (e.g. [MS08b])
have led to some efforts to design approximation algorithms for average-case
notions of distortion, among them MDS. Here “average-case” is in the sense
that we take the average over $i,j$ pairs, not that $d_{ij}$s are random. For
the additive distortion and the problem of embedding into the line (i.e.: the
$d^{\prime}$ distance should come from a line metric), the problem is NP-Hard
[HIL98, Iva00] and Hastad et al. [HIL98] showed provided a 2-approximation
algorithm that was later improved by Badoiu to the plane under the
$\ell_{1}$-metric [Bad03]. Dhamdhere [Dha04] considered the problem of
embedding into a line metric in a non-contractive way to minimize additive
distortion and presented an $\mathcal{O}(\log n)$ approximation. In the
context where the objective is the multiplicative distortion [SBD+19] provides
an $O(\sqrt{n})$-approximation to the problem and [BCIS05] later provided an
$O(\Delta^{3/4})$-approximation.

There have been few provable bounds on approximating average-case distortion
style objectives for dimensionality-reduction problems. Bartal, Fandina and
Neiman [BFN19] give provable approximation guarantees for a several variants
of multi-dimensional scaling, the closest of which to our setting, i.e. the
Kamada-Kawai objective, is the objective

$\mathop{\mathbb{E}}_{i\neq
j\in[n]}\left[\left(1-\max\left(\frac{\|x_{i}-x_{j}\|}{d_{i,j}},\frac{d_{i,j}}{\|x_{i}-x_{j}\|}\right)\right)^{2}\right].$

They first employ an embedding of the $d_{i,j}$’s into high dimensional
Euclidean space $\mathbbm{R}^{n}$ by solving the standard semi-definite
program. Next, they apply Johnson-Lindenstrauss (JL) projections to reduce the
dimension from $n$ to any target dimension $k$. The main contribution of
[BFN19] is in the moment based analysis of JL. However, it is easy to see that
JL will result unavoidably result in fixed additive error that is a function
only of $k$; Specifically, the authors obtain an additive $O(1/\sqrt{k})$
approximation to several objectives, including the aforementioned. However,
since $\textsf{OPT}\in[0,1]$, this guarantee is non-vacuous only for target
dimension larger than $1/\varepsilon^{2}$, regardless of running time.
Additionally, their result requires the initial distances $\\{d_{i,j}\\}$ to
be a metric—something that we do not assume. In contrast, our results give
non-trivial approximations for any $k$, for which the additive $\varepsilon$
error can be made arbitrarily small at the cost of increasing the runtime of
the algorithm.

The literature on embeddings into tree metrics or ultrametric is also very
rich. Motivated by biology applications, researchers have studied
reconstruction of phylogenies as a tree or ultrametric embedding problem:
given pairwise dissimilarities between $n$ elements, the goal is to fit the
elements to a tree or ultrametric while minimizing the maximum additive
distortion or the sum over all pairs of elements of the additive distortion.
Farach-Colton, Kannan and Warnow [FKW95] showed that for the ultrametric case
an optimal solution can be found in $\Theta(|S|^{2})$ time (see also [CKL20,
CdJdVL21] for when the input is Euclidean). For embedding into a tree,
Agarwala, Bafna, Farach-Colton, Paterson and Thorup [ABF+99] provided a
constant factor approximation and showed the problem is APX-Hard. If the input
distances have at most $k$ distinct values, then Harb, Kannan and McGregor
[HKM05] showed a factor $\mathcal{O}(\min\\{n,k\log n\\}^{1/p})$
approximation. The best bounds known for the ultrametric variant of the
problem are due to Cohen-Addad et al. [CDK+21] and Ailon and Charikar [AC11].
This has also been considered in the context of stochastic inputs (see Farach-
Colton and Kannan [FK99], Mossel and Roch [MR05], Henzinger, King, Warnow
[HKW99] and the references therein).

## Acknowledgements

We thank Moses Charikar, Piotr Indyk, and Robert Kleinberg for helpful
conversations. SBH was funded by NSF CAREER award no. 2238080 and MLA@CSAIL.
AB was funded by the Foundations of Data Science Institute, NSF award no.
2023505.

## References

  * [AAB+21] Akshay Agrawal, Alnur Ali, Stephen Boyd, et al.  Minimum-distortion embedding.  Foundations and Trends® in Machine Learning, 14(3):211–378, 2021.
  * [ABF+99] Richa Agarwala, Vineet Bafna, Martin Farach, Mike Paterson, and Mikkel Thorup.  On the approximability of numerical taxonomy (fitting distances by tree metrics).  SIAM J. Comput., 28(3):1073–1085, 1999.  Announced at SODA 1996.
  * [AC11] Nir Ailon and Moses Charikar.  Fitting tree metrics: Hierarchical clustering and phylogeny.  SIAM J. Comput., 40(5):1275–1291, 2011.  Announced at FOCS 2005.
  * [AHK18] Sanjeev Arora, Wei Hu, and Pravesh K. Kothari.  An analysis of the t-sne algorithm for data visualization.  In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet, editors, Conference On Learning Theory, COLT 2018, Stockholm, Sweden, 6-9 July 2018, volume 75 of Proceedings of Machine Learning Research, pages 1455–1462. PMLR, 2018.
  * [Bad03] Mihai Badoiu.  Approximation algorithm for embedding metrics into a two-dimensional space.  In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 12-14, 2003, Baltimore, Maryland, USA, pages 434–443. ACM/SIAM, 2003.
  * [Bar96] Yair Bartal.  Probabilistic approximations of metric spaces and its algorithmic applications.  In FOCS, pages 184–193, 1996.
  * [BCIS05] Mihai Bǎdoiu, Julia Chuzhoy, Piotr Indyk, and Anastasios Sidiropoulos.  Low-distortion embeddings of general metrics into the line.  In Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, pages 225–233, 2005.
  * [BCIS06] Mihai Bǎdoiu, Julia Chuzhoy, Piotr Indyk, and Anastasios Sidiropoulos.  Embedding ultrametrics into low-dimensional spaces.  In Proceedings of the twenty-second annual symposium on Computational geometry, pages 187–196, 2006.
  * [BFN19] Yair Bartal, Nova Fandina, and Ofer Neiman.  Dimensionality reduction: theoretical perspective on practical measures.  Advances in Neural Information Processing Systems, 32, 2019.
  * [BG05] Ingwer Borg and Patrick JF Groenen.  Modern multidimensional scaling: Theory and applications.  Springer Science & Business Media, 2005.
  * [BRS11] Boaz Barak, Prasad Raghavendra, and David Steurer.  Rounding semidefinite programming hierarchies via global correlation.  In 2011 ieee 52nd annual symposium on foundations of computer science, pages 472–481. IEEE, 2011.
  * [BS02] Mukund Balasubramanian and Eric L Schwartz.  The isomap algorithm and topological stability.  Science, 295(5552):7–7, 2002.
  * [CC00] Trevor F Cox and Michael AA Cox.  Multidimensional scaling.  CRC press, 2000.
  * [CdJdVL21] Vincent Cohen-Addad, Rémi de Joannis de Verclos, and Guillaume Lagarde.  Improving ultrametrics embeddings through coresets.  In ICML, 2021.
  * [CDK+21] Vincent Cohen-Addad, Debarati Das, Evangelos Kipouridis, Nikos Parotsidis, and Mikkel Thorup.  Fitting distances by tree metrics minimizing the total error within a constant factor.  In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7-10, 2022, pages 468–479. IEEE, 2021.
  * [CF07] Nicholas A Christakis and James H Fowler.  The spread of obesity in a large social network over 32 years.  New England journal of medicine, 357(4):370–379, 2007.
  * [CF08] Nicholas A Christakis and James H Fowler.  The collective dynamics of smoking in a large social network.  New England journal of medicine, 358(21):2249–2258, 2008.
  * [Che04] Chaomei Chen.  Searching for intellectual turning points: Progressive knowledge domain visualization.  Proceedings of the National Academy of Sciences, 101(suppl_1):5303–5310, 2004.
  * [CKL20] Vincent Cohen-Addad, Karthik C. S., and Guillaume Lagarde.  On efficient low distortion ultrametric embedding.  In ICML, volume 119, pages 2078–2088, 2020.
  * [CLN22] Vincent Cohen-Addad, Euiwoong Lee, and Alantha Newman.  Correlation clustering with sherali-adams.  In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022, pages 651–661. IEEE, 2022.
  * [Dha04] Kedar Dhamdhere.  Approximating additive distortion of embeddings into line metrics.  In APPROX-RANDOM, pages 96–104, 2004.
  * [DHK+21] Erik Demaine, Adam Hesterberg, Frederic Koehler, Jayson Lynch, and John Urschel.  Multidimensional scaling: Approximation and complexity.  In International Conference on Machine Learning, pages 2568–2578. PMLR, 2021.
  * [DIM01] DIMACS.  Working group on algorithms for multidimensional scaling i.  http://dimacs.rutgers.edu/archive/SpecialYears/2001_Data/Algorithms/program.html, 2001\.  Accessed: 2023-11-08.
  * [DKR+20] Sami Davies, Janardhan Kulkarni, Thomas Rothvoss, Jakub Tarnawski, and Yihao Zhang.  Scheduling with communication delays via lp hierarchies and clustering.  In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 822–833. IEEE, 2020.
  * [dLH82] Jan de Leeuw and Willem Heiser.  13 theory of multidimensional scaling.  Handbook of statistics, 2:285–316, 1982.
  * [FK99] Martin Farach and Sampath Kannan.  Efficient algorithms for inverting evolution.  J. ACM, 46(4):437–449, 1999.  Announced at STOC 1996.
  * [FKW95] Martin Farach, Sampath Kannan, and Tandy J. Warnow.  A robust model for finding optimal evolutionary trees.  Algorithmica, 13(1/2):155–179, 1995.  Announced at STOC 1993.
  * [FRT04] Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar.  A tight bound on approximating arbitrary metrics by tree metrics.  J. Comput. Syst. Sci., 69(3):485–497, 2004.  Announced at STOC 2003.
  * [Goo10] Jan W Gooch.  Encyclopedic dictionary of polymers, volume 1.  Springer Science & Business Media, 2010.
  * [GS12] Venkatesan Guruswami and Ali Kemal Sinop.  Faster SDP hierarchy solvers for local rounding algorithms.  In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 197–206. IEEE Computer Society, 2012.
  * [HCG+08] Patric Hagmann, Leila Cammoun, Xavier Gigandet, Reto Meuli, Christopher J Honey, Van J Wedeen, and Olaf Sporns.  Mapping the structural core of human cerebral cortex.  PLoS biology, 6(7):e159, 2008.
  * [HIL98] Johan Håstad, Lars Ivansson, and Jens Lagergren.  Fitting points on the real line and its application to rh mapping.  In Algorithms—ESA’98: 6th Annual European Symposium Venice, Italy, August 24–26, 1998 Proceedings 6, pages 465–476. Springer, 1998.
  * [HKM05] Boulos Harb, Sampath Kannan, and Andrew McGregor.  Approximating the best-fit tree under l${}_{\mbox{p}}$ norms.  In APPROX-RANDOM, pages 123–133, 2005.
  * [HKW99] Monika Rauch Henzinger, Valerie King, and Tandy J. Warnow.  Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology.  Algorithmica, 24(1):1–13, 1999.  Announced at SODA 1996.
  * [HR02] Geoffrey E Hinton and Sam Roweis.  Stochastic neighbor embedding.  Advances in neural information processing systems, 15, 2002.
  * [Iva00] Lars Ivansson.  Computational aspects of radiation hybrid mapping.  PhD thesis, Numerisk analys och datalogi, 2000.
  * [JKR19] Vishesh Jain, Frederic Koehler, and Andrej Risteski.  Mean-field approximation, convex hierarchies, and the optimality of correlation rounding: a unified perspective.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 1226–1236, 2019.
  * [KK+89] Tomihisa Kamada, Satoru Kawai, et al.  An algorithm for drawing general undirected graphs.  Information processing letters, 31(1):7–15, 1989.
  * [KMN11] Anna R Karlin, Claire Mathieu, and C Thach Nguyen.  Integrality gaps of linear and semi-definite programming relaxations for knapsack.  In Integer Programming and Combinatoral Optimization: 15th International Conference, IPCO 2011, New York, NY, USA, June 15-17, 2011. Proceedings 15, pages 301–314. Springer, 2011.
  * [Kru64] Joseph B Kruskal.  Nonmetric multidimensional scaling: a numerical method.  Psychometrika, 29(2):115–129, 1964.
  * [KW78] Joseph B Kruskal and Myron Wish.  Multidimensional scaling.  Sage, 1978.
  * [LMN05] James R Lee, Manor Mendel, and Assaf Naor.  Metric structures in l1: dimension, snowflakes, and average distortion.  European Journal of Combinatorics, 26(8):1180–1190, 2005.
  * [Mat90] Jiří Matoušek.  Bi-lipschitz embeddings into low-dimensional euclidean spaces.  Commentationes Mathematicae Universitatis Carolinae, 31(3):589–600, 1990.
  * [Mat96] Jiří Matoušek.  On the distortion required for embedding finite metric spaces into normed spaces.  Israel Journal of Mathematics, 93(1):333–344, 1996.
  * [MR05] Elchanan Mossel and Sébastien Roch.  Learning nonsingular phylogenies and hidden markov models.  In STOC, pages 366–375, 2005.
  * [MR16] Pasin Manurangsi and Prasad Raghavendra.  A birthday repetition theorem and complexity of approximating dense csps.  arXiv preprint arXiv:1607.02986, 2016.
  * [MS08a] Claire Mathieu and Warren Schudy.  Yet another algorithm for dense max cut: go greedy.  In SODA, volume 8, pages 176–182, 2008.
  * [MS08b] Jirí Matousek and Anastasios Sidiropoulos.  Inapproximability for metric embeddings into r^d.  In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA, pages 405–413. IEEE Computer Society, 2008.
  * [MS09] Claire Mathieu and Alistair Sinclair.  Sherali-adams relaxations of the matching polytope.  In Michael Mitzenmacher, editor, Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, pages 293–302. ACM, 2009.
  * [OS08] Krzysztof Onak and Anastasios Sidiropoulos.  Circular partitions with applications to visualization and embeddings.  In Proceedings of the twenty-fourth annual symposium on Computational geometry, pages 28–37, 2008.
  * [Rab08] Yuri Rabinovich.  On average distortion of embedding metrics into the line.  Discrete & Computational Geometry, 39(4):720–733, 2008.
  * [SA90] Hanif D Sherali and Warren P Adams.  A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems.  SIAM Journal on Discrete Mathematics, 3(3):411–430, 1990.
  * [SBD+19] Anastasios Sidiropoulos, Mihai Badoiu, Kedar Dhamdhere, Anupam Gupta, Piotr Indyk, Yuri Rabinovich, Harald Racke, and R. Ravi.  Approximation algorithms for low-distortion embeddings into low-dimensional spaces.  SIAM Journal on Discrete Mathematics, 33(1):454–473, 2019.
  * [SWW17] Anastasios Sidiropoulos, Dingkang Wang, and Yusu Wang.  Metric embeddings with outliers.  In SODA, pages 670–689, 2017.
  * [Tor52] Warren S Torgerson.  Multidimensional scaling: I. theory and method.  Psychometrika, 17(4):401–419, 1952.
  * [VdMH08] Laurens Van der Maaten and Geoffrey Hinton.  Visualizing data using t-sne.  Journal of machine learning research, 9(11), 2008.
  * [VL07] Ulrike Von Luxburg.  A tutorial on spectral clustering.  Statistics and computing, 17:395–416, 2007.
  * [Wei19] Eric W Weisstein.  Legendre duplication formula.  From MathWorld. http://mathworld. wolfram. com/LegendreDuplicationFormula. html, 2019.
  * [You13] Forrest W Young.  Multidimensional scaling: History, theory, and applications.  Psychology Press, 2013.
  * [YZ14] Yuichi Yoshida and Yuan Zhou.  Approximation schemes via sherali-adams hierarchy for dense constraint satisfaction problems and assignment problems.  In Proceedings of the 5th conference on Innovations in theoretical computer science, pages 423–438, 2014.