REVIEW 3 major objections 4 minor 7 references
Additive Approximation Schemes for Low-Dimensional Embeddings
T0 review · 3 major / 4 minor · reviewed 2026-08-04 · deepseek-v4-flash
Pith's one-line read The paper claims that k-Euclidean Metric Violation — fitting a k-dimensional Euclidean metric to arbitrary pairwise distances under squared error — admits the first polynomial-time additive approximation scheme, returning an embedding whose
desk verdict Genuinely new and likely salvageable, but Lemma 5.10's entropy bound is incompatible with the algorithm's own grid, and fixing it reintroduces B into the conditioning set—so the claimed polynomial runtime is not established as written. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is a pseudo-distribution from a convex-hierarchy relaxation, rounded by global correlation rounding: condition on values of a few coordinates sampled from the local distribution, then draw all remaining coordinates independently from their one-point marginals. The paper proves the objective's Lipschitz part (d_ij‖x_i−x_j‖) and quadratic part (⟨x_i,x_j⟩) are each 'potential-aligned' with an average-entropy potential and an average-variance potential; a combined-potential lemma bounds how many conditionings suffice to make the rounded expectation match the pseudo-expectation within ε. A truncation step replaces each variable by a bounded version, which is what keeps the
What would settle it
Search over small n and k=2 for a distance matrix D and an embedding with k-EMV objective at most 2 E_{ij} d_ij^2 but with every candidate anchor a satisfying (1/n)Σ_i‖x_i−x_a‖^2 > 6 E_{ij} d_ij^2; such an example would falsify Lemma 5.8 and collapse the anchoring step. Equivalently, on a small instance where the exact optimum is known by brute force, the algorithm should return objective at most OPT + ε E d^2 with high probability; a single violation would falsify the main theorem.
Extended reading notes
Core claim
Central claim is Theorem 5.4: for any input distance matrix D with B-bit entries, any target dimension k, and any 0<ε<1, an algorithm running in B^{O(k^2 log(k/ε)/ε^4)}·poly(n) time returns, with probability at least 0.99, an embedding in R^k whose k-EMV objective is at most OPT_EMV + ε·E_{ij} d_ij^2. The proof rounds a high-level convex-hierarchy relaxation (an LP/SDP pseudo-distribution) by first conditioning on a small anchor set and then sampling every remaining point independently from its one-point marginal. The new analysis shows the rounding error splits into a linear Lipschitz term and a quadratic covariance term, each controlled by a separate potential, so the number of conditionin
Load-bearing premise
The load-bearing premise is Lemma 5.8: every embedding with objective value at most twice the average squared input distance has some anchor point such that the average squared distance from all points to that anchor is at most six times the average squared input distance; if this fails for k>1, the variance and entropy potentials that make the rounding finite are not bounded.
Editorial extensions
If this is right
- For fixed k and ε the running time is polynomial in n and B, replacing the earlier double-exponential dependence on the bit length B with a fixed polynomial degree.
- The weighted version gives an additive approximation scheme for multidimensional scaling with partial or weighted pairwise data when the underlying weight graph is dense and regular, with an explicit dependence on density and distance magnitudes.
- For entrywise ℓ_p low-rank approximation with even p>2, the technique yields a quasi-polynomial-time additive scheme with no bit-complexity assumptions, a guarantee not previously available even in subexponential time.
- The paper states that the same rounding algorithms are likely to yield PTASs with different discretization schemes, though such a result would require new analytical ideas.
Reading between the lines
- If the anchor lemma extends with dimension-independent constants and the B^{poly} factor can be made polylogarithmic, a full PTAS for k-EMV would follow directly from the same conditioning structure.
- The truncation-before-rounding move is transferable to other continuous optimization problems where the objective splits into Lipschitz terms and polynomial terms but variables lie in an unbounded domain; the same potential-alignment argument would apply whenever a single conditioning step controls the variance.
- One testable extrapolation: on synthetic low-dimensional embeddings corrupted by large global shifts or a few outliers, the algorithm's output should retain additive error ε·E d^2 because the first anchoring step kills global translations; measuring this empirically for small n and k=1 would probe the anchor lemma directly.
- The ℓ_p result is confined to even integers because the proof expands (A_ij−u_i v_j)^p into monomials; getting odd p>2 will likely require non-monomial potentials beyond variance and entropy.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes an additive approximation scheme for the k-Euclidean Metric Violation problem (k-EMV). Given pairwise distances D with B-bit entries, it claims to output an embedding in R^k whose k-EMV value is at most OPT_EMV + epsilon times the average squared input distance, in time (nB)^{poly(k,1/epsilon)} (stated as B^{poly} times poly(n) in Theorem 1.1). The approach combines a Sherali-Adams / Sum-of-Squares relaxation, a geometric discretization onto a grid, an anchoring step that conditions on a single point, and a global-correlation-rounding analysis showing that the objective terms are potential-aligned. The paper also claims extensions to weighted k-EMV under regularity assumptions and to entrywise ell_p low-rank approximation for even p > 2.
Significance. If correct, the main result would be the first polynomial-time additive approximation scheme for k-EMV and would settle the long-standing open question for k=1, since the additive error epsilon*E d^2 implies a (1+epsilon)-approximation when combined with the trivial bound OPT <= E d^2. The potential-aligned framework is a conceptually interesting extension of Barak-Raghavendra-Steurer correlation rounding to continuous low-dimensional embedding problems. The paper gives detailed proofs and does not rely on fitted parameters or circular reasoning. However, a load-bearing grid-scaling error in Lemma 5.10 currently invalidates the claimed poly(n) runtime for the central theorem. The manuscript needs a significant technical repair before its main contribution can be accepted.
major comments (3)
- [§5.2, Lemma 5.10 vs. Algorithm 5.5] The entropy bound in Lemma 5.10 uses the wrong grid spacing. The proof bounds H(tilde x_i) by dividing the support width 2C*sqrt(E||x_i - E x_i||^2) by a denominator sqrt(epsilon/k * E_{i,j} d_{ij}^2). But Algorithm 5.5 defines Sigma = {0} union {epsilon*sqrt(1/k)(1+epsilon)^t}, whose minimum spacing is epsilon/sqrt(k), independent of E d^2. On the stated grid, the number of reachable values in the truncation ball is Omega(C*sqrt(E d^2)*sqrt(k)/epsilon), and E d^2 can be Theta(2^{2B}) when min d_ij = 1 and max d_ij = 2^B. Thus the correct bound is O(kB), not O(k log(Ck/epsilon)). Consequently Lemma 5.11 gives |T| = Omega(kB/epsilon^4), the Sherali-Adams degree acquires B, and the algorithm's search/solution time has n^{Omega(B)} factors; the poly(n) runtime of Theorem 5.4 is not established. This is fixable by using a distance-normalized grid with spacing epsilon*sqrt(E d^2/k), but that
- [§5.2, Lemma 5.6, Eq. (8)] The display 'OPTDEMV <= E(dij - ||xhat_i - xhat_j||)^2 = E(dij - ||xhat_i - xhat_j|| ± ||x_i - x_j||)^2 = OPT_EMV + epsilon E d^2 + ...' is not a valid identity. The first and third expressions are not equal, and the ± notation obscures the dependence on the optimal solution x. At best this should be an upper bound obtained by adding and subtracting ||x_i - x_j|| and applying triangle/Cauchy-Schwarz. The subsequent 16epsilon bound may be recoverable, but the proof as written contains a real algebraic gap in a load-bearing discretization lemma.
- [§5.3, Theorem 5.12 vs. Theorem 1.2] The weighted runtime stated in the body is inconsistent with the claimed Theorem 1.2. Theorem 5.12 claims time (n*Delta)^{O(k^2 log(Delta*k/(epsilon*delta))/(epsilon^2*delta^11))}; since Delta = 2^B can encode B bits, this is at least n^{Omega(k^2 B)} even for fixed epsilon and delta, so it is not of the form (n*2^B)^{poly(k,epsilon^{-1},delta^{-1})} promised in Theorem 1.2. The degree appearing in the final proof of Theorem 5.12 also contains log Delta. Unless the intended runtime is genuinely quasi-polynomial in n for growing B, the statement and proof need to be reconciled.
minor comments (4)
- [§5.2, Lemma 5.6 / Fact 5.7] The presentation of the low-diameter solution argument is hard to follow: 'all but an epsilon^2/Delta^4-fraction of pairs' and 'good points at least 1-epsilon/Delta^2' do not align dimensionally, and the sentence claiming 'there are only epsilon/Delta^2 n^2 many pairs' should be stated in terms of bad pairs/incidences. This is fixable but should be rewritten.
- [§5.2, Algorithm 5.5 and Definition 3.4] The notation mu_T is overloaded: in Definition 3.4 it denotes the conditioned pseudo-distribution, while in Algorithm 5.5 step (b) it denotes the local distribution on T and then the conditioned distribution. This makes the algorithm ambiguous.
- [§5.1, Lemma 5.10] The expression 'x_i(T)' in the definition of tilde x_i appears to be a typo for x_i. Also, the statement 'all points in Sigma^k differ by at least sqrt(epsilon/k * E d^2)' should read 'differ by at least epsilon/sqrt(k)' for the actual Algorithm 5.5 grid; this is the same issue as the first major comment.
- [Appendix A] The speedup via [GS12a] is presented as a sketch. It should specify the number of rounds ell, the volume/measure condition needed for Theorem A.3, and precisely how the randomized SEED procedure satisfies the deterministic/framework hypotheses. As written, Appendix A is not self-contained enough to verify the claimed B^{poly}*poly(n) runtime.
Circularity Check
No significant circularity: the k-EMV guarantee is derived directly from the LP relaxation and rounding analysis; self-citations are contextual and not load-bearing.
full rationale
The derivation chain is self-contained. Theorem 5.4 is obtained by (i) discretizing the objective to a grid (Lemma 5.6), (ii) proving an anchoring bound that justifies the LP constraint E_i||x_i||^2 ≤ 6E d^2 (Lemma 5.8), (iii) solving the Sherali-Adams relaxation, and (iv) bounding the independent-rounding error via potential-aligned functions (Lemmas 5.1, 4.3, 4.4, 5.10, 5.11). No parameter is fitted to OPT or to the final embedding; the search over anchors and conditioning sets is an enumeration over candidates, and the output is evaluated directly on the target objective. The only self-citations—[BCHJL25] for context/anchoring and [BLMT24] for a standard SoS fact—are not used to force the conclusion: [BCHJL25] is explicitly said not to extend to k-EMV, and the SoS fact is a standard quadratic-module statement. The grid-spacing issue raised by the reviewer concerns whether the stated entropy bound and n^{poly(k,1/ε)} runtime follow from the algorithm as written; that is a correctness/runtime question, not an identity between inputs and outputs, so it does not constitute circularity under the defined patterns.
Assumptions & free parameters
assumptions (9)
- standard math Sherali-Adams relaxation is a valid relaxation and can be solved in (n|Sigma|)^O(t) time
- standard math Pinsker's inequality TV^2 <= I
- standard math Variance reduction Fact 3.2
- standard math Quadratic inequalities admit SoS proofs
- standard math Expander decomposition theorem of [GT14] (Theorem 5.16)
- standard math Fast local rounding solver of [GS12a] (Theorem A.3)
- domain assumption Input distances are B-bit nonnegative numbers
- domain assumption Weight matrix is delta-n-regular with weights in [0,1]
- domain assumption p is an even integer for the LRA result
Cite this review
Pith. "Pith review of Additive Approximation Schemes for Low-Dimensional Embeddings." pith.science (2026). https://pith.science/paper/OLLLOZCT
@misc{pith2026250909652,
author = {Pith},
title = {Pith review of: Additive Approximation Schemes for Low-Dimensional Embeddings},
year = {2026},
howpublished = {\url{https://pith.science/paper/OLLLOZCT}},
note = {Machine review of arXiv:2509.09652}
}
abstract
We consider the task of fitting low-dimensional embeddings to high-dimensional data. In particular, we study the $k$-Euclidean Metric Violation problem ($\textsf{$k$-EMV}$), where the input is $D \in \mathbb{R}^{\binom{n}{2}}_{\geq 0}$ and the goal is to find the closest vector $X \in \mathbb{M}_{k}$, where $\mathbb{M}_k \subset \mathbb{R}^{\binom{n}{2}}_{\geq 0}$ is the set of all $k$-dimensional Euclidean metrics on $n$ points, and closeness is formulated as the following optimization problem, where $\| \cdot \|$ is the entry-wise $\ell_2$ norm: \[ \textsf{OPT}_{\textrm{EMV}} = \min_{X \in \mathbb{M}_{k} } \Vert D - X \Vert_2^2\,.\] Cayton and Dasgupta [CD'06] showed that this problem is NP-Hard, even when $k=1$. Dhamdhere [Dha'04] obtained a $O(\log(n))$-approximation for $\textsf{$1$-EMV}$ and leaves finding a PTAS for it as an open question (reiterated recently by Lee [Lee'25]). Although $\textsf{$k$-EMV}$ has been studied in the statistics community for over 70 years, under the name "multi-dimensional scaling", there are no known efficient approximation algorithms for $k > 1$, to the best of our knowledge. We provide the first polynomial-time additive approximation scheme for $\textsf{$k$-EMV}$. In particular, we obtain an embedding with objective value $\textsf{OPT}_{\textrm{EMV}} + \varepsilon \Vert D\Vert_2^2$ in $(n\cdot B)^{\mathsf{poly}(k, \varepsilon^{-1})}$ time, where each entry in $D$ can be represented by $B$ bits. We believe our algorithm is a crucial first step towards obtaining a PTAS for $\textsf{$k$-EMV}$. Our key technical contribution is a new analysis of correlation rounding for Sherali-Adams / Sum-of-Squares relaxations, tailored to low-dimensional embeddings. We also show that our techniques allow us to obtain additive approximation schemes for two related problems: a weighted variant of $\textsf{$k$-EMV}$ and $\ell_p$ low-rank approximation for $p>2$.
Reference graph
Works this paper leans on
-
[1]
Let S(0)⊆[N] be the initial solution fragment and y(0)←x S(0) be the induced solution on those coordinates
-
[2]
(b) If i< ℓ read more of the solution by setting S(i+ 1)←SEED(y(i)) and y(i+1)←x S(i+1)
Fori∈[ℓ]: (a) Fail if FEASIBLE(y(i))asserts infeasible. (b) If i< ℓ read more of the solution by setting S(i+ 1)←SEED(y(i)) and y(i+1)←x S(i+1)
-
[3]
Note that the algorithm as stated in Algorithm 5.5 reads the entire solution in enumerating over all possible seed sets of size k2 log(k/ε)/ε 4
Perform rounding using onlyS(ℓ)andy(ℓ). Note that the algorithm as stated in Algorithm 5.5 reads the entire solution in enumerating over all possible seed sets of size k2 log(k/ε)/ε 4. However, we note that this brute force method of determining the correct seed set is unnecessary, and we will overview later in this section how a good seed set can be samp...
-
[4]
Let S1 be a subset of size k2 log(k/ε)/ε 4 where i is sampled proportional to Ej∼[n] d2 ij and letS 2 be a uniformly random subset of sizek 2 log(k/ε)/ε 4
-
[5]
Read the distribution of all (2k2 log(k/ε)/ε 4 + 2)-sized subsets including S1 ∪S 2, and ensure that they are consistent on the local distribution of S1 ∪S 2 and that the LP constraints in Algorithm 5.5 are satisfied
-
[6]
Sample an assignment to the xi ∈S 1 ∪S 2 from the local distribution and condi- tion on the assignment
-
[7]
We now return to the proof of Theorem A.1
Using only the prior local distributions viewed in step 2, assign all other vari- ables by sampling them independently from their marginal distributions. We now return to the proof of Theorem A.1. Proof of Theorem A.1. We will explain how to view the rounding algorithm in Section 5 as a local rounding algorithm and then apply Theorem A.3. First, we note t...
Reviewed August 4, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.