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 \mathbb{R}^k$ that minimizes \[ \text{OPT} =
\min_{x} \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
(arXiv:2109.11505) gave the first approximation algorithm with provable
guarantees for Kamada-Kawai, which achieves an embedding with cost $\text{OPT}
+\epsilon$ in $n^2 \cdot 2^{\tilde{\mathcal{O}}(k \Delta^4 / \epsilon^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}(\text{OPT}^{ \hspace{0.04in}1/k } \cdot \log(\Delta/\epsilon)
)+ \epsilon$ in time $n^{ \mathcal{O}(1)} \cdot 2^{\tilde{\mathcal{O}}( k^2
(\log(\Delta)/\epsilon)^{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.

我们研究了多维缩放（Multi-dimensional Scaling，MDS）的 Kamada-Kawai 公式，提出了一种基于 Sherali-Adams 线性规划层次的近似算法，该算法实现了在目标维度下成本和时间复杂度之间的平衡，为高效度量优化算法的开发奠定了基础。

通过 LP 分层的多维度尺度算法的准多项式时间算法

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

It has been shown that for a general-valued constraint language $\Gamma$ the
following statements are equivalent: (1) any instance of
$\operatorname{VCSP}(\Gamma)$ can be solved to optimality using a constant
level of the Sherali-Adams LP hierarchy; (2) any instance of
$\operatorname{VCSP}(\Gamma)$ can be solved to optimality using the third level
of the Sherali-Adams LP hierarchy; (3) the support of $\Gamma$ satisfies the
"bounded width condition", i.e., it contains weak near-unanimity operations of
all arities.
We show that if the support of $\Gamma$ violates the bounded width condition
then not only is $\operatorname{VCSP}(\Gamma)$ not solved by a constant level
of the Sherali-Adams LP hierarchy but it is also not solved by $\Omega(n)$
levels of the Lasserre SDP hierarchy (also known as the sum-of-squares SDP
hierarchy). For $\Gamma$ corresponding to linear equations in an Abelian group,
this result follows from existing work on inapproximability of Max-CSPs. By a
breakthrough result of Lee, Raghavendra, and Steurer [STOC'15], our result
implies that for any $\Gamma$ whose support violates the bounded width
condition no SDP relaxation of polynomial-size solves
$\operatorname{VCSP}(\Gamma)$.
We establish our result by proving that various reductions preserve exact
solvability by the Lasserre SDP hierarchy (up to a constant factor in the level
of the hierarchy). Our results hold for general-valued constraint languages,
i.e., sets of functions on a fixed finite domain that take on rational or
infinite values, and thus also hold in notable special cases of
$\{0,\infty\}$-valued languages (CSPs), $\{0,1\}$-valued languages
(Min-CSPs/Max-CSPs), and $\mathbb{Q}$-valued languages (finite-valued CSPs).

通过证明各种规约保持 Lasserre SDP 层次的精确可解性，我们展示了支持破坏有限宽度条件的一般值约束语言不能被静态程序快速求解。