- Rating
- 2
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper revisits non-metric multidimensional scaling for noisy high-dimensional data. It recalls the continuum optimum of metric MDS for equal dissimilarities and proposes a finite-sample perturbation bound in energy distance. A three-cluster simulation motivates a quadratic versus quartic noise-dimension tolerance heuristic for metric and non-metric MDS. The practical contribution is a PyTorch stochastic implementation that computes within-batch distances and fits an isotonic transformation on the first batch of each epoch. Five datasets, including population-genomic and single-cell data, show favorable preservation of the input distance order; small-dataset comparisons report similar stress to SMACOF with shorter runtimes, and larger examples reach 70,000 points.
Critical strengths
- A useful scalable implementation of an established objective. Fitting the monotone transformation once per epoch makes non-metric MDS practical without constructing the full distance matrix when feature vectors are available (Section 6, pp. 5–6; Listing S1, pp. 17–18). Table 1 reports substantial speedups over SMACOF on the small datasets, and the Tasic/MNIST examples demonstrate a useful scale on a CPU laptop. Table S1 directly tests the isotonic-fit frequency approximation.
- The empirical motivation is coherent and interpretable. The noise experiment and Shepard diagrams explain why monotone distance transformations can help under concentration (Section 5, p. 5; Figures 3–5, pp. 7–9). Non-metric MDS improves over ordinary metric MDS across several reported global metrics, with particularly strong differences for the genomic dataset; the paper also acknowledges the local-structure tradeoff.
In the October 7 reviewer-side execution, full-size digits and blobs each completed three fresh seeds for both objectives, and all original cells of the 10,000-point high-dimensional notebook executed successfully. Three of four Table 1 stress entries matched to two decimals. Digits nonmetric .28 versus .29 was explained by reporting conventions: the same reference embedding gave .292201 under the notebook printout and .280473 under the author adjusted helper, close to the fresh SGD minibatch mean .280550. This is not evidence of degradation. SGD was faster than SMACOF on the tested machine, without establishing the paper's hardware-specific speed ratios.
Critical weaknesses
-
The theoretical statement needs a consistent normalization and a narrower interpretation. Equation 5 defines full expected squared residual S with S*=1−π²/12, while Appendix D's Eqs. 23 and 26 use half that objective but retain the full S*. For the main definition, the consistent identity is S[μ]−S*=2D_E²(μ,ρ*)+2∫g dμ. It yields D_E²≤π²/(24n)+2√Sδ+2δ², recovering the reported .843 linear coefficient. The printed 2√(2S) is instead about 1.192. Thus the advertised numerical estimate is repairable, but the symbolic proof must be aligned. This bound concerns a centered unlabeled marginal of a global minimizer; closeness to the disk distribution alone does not prove that labels or input correspondence are lost, nor does it certify the optimizer actually found. Figure 3 itself can preserve visible class structure within a disk-like layout.
-
The practical advantage remains insufficiently distinguished from the closest scalable alternatives. The shown comparisons against PCA, metric MDS, t-SNE and UMAP support those particular results; the paper acknowledges that the latter two emphasize local structure. The cited SQuadMDS uses relative quartet distances, so it is not simply the raw metric-MDS objective analyzed in the theorem. A matched quality/runtime comparison would directly assess the claimed advantage over an existing global method; no result favoring either method is presumed. The supplied notebooks also do not identify the exact table-generating state: dist_corrs defaults to 5,000 rather than the stated 500 evaluation points, and downstream cells treat the returned per-epoch loss array as a scalar. Data, seeds, evaluation sampling and the returned statistic need to be tied to a frozen run. These are identifiable lineage gaps, not an absence of code, runtime, or an isotonic-frequency ablation.
Execution also exposed a TypeError in main-notebook cell 18 from a commented-out keyword, missing processed Genomes/Tasic inputs, and historical hardcoded values in the robustness figure's second panel. Subsequent helper execution does not establish that the main notebook runs sequentially without repair. Complete MNIST and robustness results were not assessed at the October 7 evidence cutoff. These limitations are distinct from the positive completed checks and the explained stress convention.
Questions for authors
-
Concrete correction: Can Eq. 5, Theorem 1, Eq. 8 and Appendix D consistently use either the full objective or half of it? With the full definition, the identity and bound above recover .843. Please distinguish global-minimizer marginal convergence from a claim that class/input information is erased or that the actual local optimizer is covered.
-
Decisive practical comparison: How does the method compare with the cited SQuadMDS, respecting its relative-distance objective, under matched inputs and an explicit initialization/tuning/compute budget? Global quality and runtime are both relevant. This asks about one close scalable alternative, not every embedding method.
-
Exact experimental state: Which notebook/function version, evaluation subset, seeds and returned loss statistic generated Tables 1, 2 and S2? Please reconcile the scalar/array mismatch, the 500 versus 5,000 setting and the stated three-run means with per-run results. Please also provide the exact Genomes/Tasic preprocessing inputs and repair the non-executing notebook call. Table S1 already tests the first-batch-per-epoch approximation. The digits stress difference is explained by reporting conventions and does not indicate degradation.
-
Positioning within MDS: The paper already cites Neuc-MDS. Please make clear that its extension through indefinite bilinear forms addresses the output geometry and negative Gram eigenvalues, whereas the present method learns an ordinal transformation while retaining Euclidean output. These address different sources of distortion. Does the discussion of metric-MDS failure intend to include such generalized geometry, or only the Euclidean raw-stress objective actually analyzed? A clarification is appropriate; an unconditional Neuc-MDS benchmark or a claim that it already solves this noisy-data task is not supported.
4 comments
Thank you for correcting the stress normalization in the revised manuscript and for clarifying the perturbation bound. Could you please clarify two follow-up points?
- Does the per-epoch complexity in Section 6 include the cost of the dense Adam update to the full embedding table at each minibatch?
- In Figure 2, both metric and non-metric MDS use random initialization. Does the observed robustness gap persist when both methods are initialized from the same PCA embedding?
Follow-ups
Dear reviewer, thanks a lot for the great questions, especially the first one!!
Does the per-epoch complexity in Section 6 include the cost of the dense Adam update to the full embedding table at each minibatch?
No. The complexity reported in Section 6 does not include dense Adam steps, and we did not think about this cost before you asked. You are right -- Adam's steps are dense and update the entire embedding table, which adds complexity. We checked, and this additional runtime was negligible for all datasets in the paper (up to only 3% of epoch's runtime), but for very large sample sizes the cost of optimizer.step() can dominate.
Luckily, there is a very easy fix, namely to switch from Adam to SparseAdam and to set sparse=True when creating the Embedding object. This only affects two lines of our code. We ran preliminary experiments on several datasets now, and the resulting embeddings are almost not affected. We are going to switch to SparseAdam in the future, but as there is very little time left for the rebuttal period, will not rerun all the experiments now. Again, note that for datasets analyzed in the paper, almost nothing would change anyway.
We added an explicit statement about this to Section 6. Thanks again for flagging this!
In Figure 2, both metric and non-metric MDS use random initialization. Does the observed robustness gap persist when both methods are initialized from the same PCA embedding?
No. If initialized with PCA embedding, both MMDS and NMDS have nearly the same kNN accuracy as the PCA itself (see our Figure 3 for an example of how that looks). We used random initialization for this experiment specifically as a way to quantify robustness and to isolate the optimization from the initialization (we added a clarification to the text now). Of course even when starting with PCA initialization (as we do everywhere else in the paper), NMDS shows higher triplet accuracy, as reported in our tables and in Fig 3. Note also that this simulated dataset used in Fig 2 has 2D latent structure (centroids of three Gaussian blobs), which makes it particularly easy for PCA. Our real-world datasets such as 1000 Genomes are more complex, and one can see how NMDS embeddings show biologically relevant structure which is obscured in 2D PCA.
Thanks again for engaging! We are happy to answer any further follow-up questions!
Dear reviewer, there are only some hours left until the end of the discussion period, so please let us know if you have any remaining concerns!
Rebuttal
Dear reviewer, many thanks for your review! We address your comments in the following, and hope this will let you reconsider your score!
Thanks for spotting this. We fixed the normalization. We have now adopted the full objective throughout. This matches the average stress, i.e. the standard raw stress divided by n(n−1)/2. All our theoretical conclusions still hold with adapted constants. The final bound in Prop 2. now contains the term 2S⋆δ instead of 22S⋆δ.
Indeed, some cluster structure remains in the metric MDS embeddings in Figs. 3b, 4b. This is partly due to classical-MDS initialization. With random initialization, metric MDS typically fails to separate the classes (line 365). Moreover, the predicted overall disk shape with the thickened boundary carries no information about the data and could easily be over-interpreted by practioners.
While global optima and solutions of optimizers can differ, we find close agreement between them in terms of the embedding radius (Figs. 3b, 4b) and stress-1 (lines 367, 391). We now state explicitly in the Discussion (line 479) that the bound applies to the global optimum, and that our experiments confirm the effect for the scikit-learn implementation.
We opted not to include SQuadMDS into our benchmark because it lacks a convenient implementation: it is a custom unpackaged C++ code. More importantly, SQuadMDS is an implementation of metric MDS; it performs very similarly (in terms of stress-1 and other metrics) to our metric MDS implementation. You are right to mention that it normalizes the distances, but that's just an overall scaling to make optimization easier, and not an isotonic transformation. The focus of our paper is on non-metric MDS, which SQuadMDS does not implement!
As we write in our Discussion, SQuadMDS-hybrid combines t-SNE with metric MDS. Our work shows the greater robustness of non-metric MDS and makes it feasible on large datasets. Future work can thus include non-metric MDS in hybrid methods.
On a related note, we have added PaCMAP to all tables, based on a suggestion from another reviewer. It does not perform consistently better than t-SNE/UMAP in triplet accuracy (Table 2).
We really appreciate that the reviewer reran our analysis! Almost all our original code was manually written and the notebooks were partially out of sync. We have now used Claude Sonnet 5.5 to refactor the entire codebase, which allowed us to easily include additional metrics (kNN recall, kNN accuracy) and additional methods (PaCMAP), as requested by other reviewers. The entire analysis was rerun from scratch and the tables were regenerated. All regenerated results match the original code. We also fixed the typo in the text about 500 vs 5000 points, thanks!
Indeed, we agree that Neuc-MDS solves a different problem. We have clarified this in the text when mentioning Neuc-MDS.
We hope that these edits and additional evaluations will address your concerns!