acceptodds
Under review as a conference paper at ICLR 2027

Fast non-metric MDS for noisy high-dimensional data

Abstract

Multidimensional scaling (MDS) constructs low-dimensional embeddings that approximate pairwise distances in a high-dimensional dataset. MDS exists in several flavors, with metric MDS approximating distances directly and non-metric MDS additionally optimizing for an arbitrary monotonic transformation of the high-dimensional distances. Empirically, metric MDS is known to suffer from the curse of dimensionality. Here we extend prior theoretical results for metric MDS on fully uninformative data to a more general case of finite, high-dimensional data with concentrated distances. We show that the metric MDS embeddings of such datasets stay distributionally close to the data-independent limit case. We then show that non-metric MDS is more robust to high-dimensional noise and can yield informative embeddings of such data. While existing implementations of non-metric MDS are slow, we develop a fast implementation using stochastic gradient descent in PyTorch. Using our implementation, we conduct an empirical study using multiple simulated and real-world datasets, including population-genomic and scRNA-seq data, and show that non-metric MDS can strongly outperform other methods in terms of global structure preservation.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
dimensionality reduction, visualization, multidimensional scaling, MDS, high-dimensional data, distance concentration

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_PdyHOpenReview ↗
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
  1. 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.
  2. 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
  1. 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.

  2. 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
  1. 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.

  2. 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.

  3. 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.

  4. 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

Dear reviewer, many thanks for your review! We address your comments in the following, and hope this will let you reconsider your score!

The theoretical statement needs a consistent normalization

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)/2n(n-1)/2. All our theoretical conclusions still hold with adapted constants. The final bound in Prop 2. now contains the term 2S⋆ δ2\sqrt{S^\star}\,\delta instead of 22S⋆ δ2\sqrt{2S^\star}\,\delta.

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.

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.

The practical advantage remains insufficiently distinguished from the closest scalable alternatives.
[...]
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.

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).

The supplied notebooks also do not identify the exact table-generating state.

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!

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.

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!

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?

  1. Does the per-epoch complexity in Section 6 include the cost of the dense Adam update to the full embedding table at each minibatch?
  2. 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?
AuthorsOpenReview ↗

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 O(nb)O(nb) 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 O(n2/b)O(n^2 / b) 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!

Reviewer_7SYCOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2(+1)
Read review
Paper summary

The paper data in which a handful of dimensions carry the signal and thousands of others are pure noise, as is common in genomics and single-cell data. In this regime all pairwise distances become nearly equal, and metric MDS, which must reproduce those distances fails in reproducing the underlying structure. The paper explains this phenomenon by a 1992 result that holds in the infinite-sample limit and extends it to finite samples whose distances are only approximately equal. It then argues that non-metric MDS, which preserves only the ordering of the distances rather than their values, is far less affected (although no new theory is provided for non-metric MDS, which is supported empirically only): in simulation, the number of noise dimensions that can be tolerated grows with the fourth power of the clusters separation, rather than with its square. Since existing non-metric MDS code requires the full distance matrix, the authors implement a mini-batch version in PyTorch, scale it to 70,000 points, and show on five datasets that it preserves global structure better than PCA, metric MDS, t-SNE and UMAP, as measured by three global-structure scores: triplet accuracy and the Spearman and Pearson correlations between distances.

Critical strengths

The disk result from the 1990s held only in the infinite-sample limit. The paper extends it to finite samples with only approximately equal distances and checks the extension in simulation. The use of Claude and ChatGPT for the proofs is declared openly, including where the tools failed.

A D² versus D⁴ scaling law, the only new result about non-metric MDS. At a given separation between groups, non-metric MDS tolerates more noise dimensions before the groups merge: with groups separated by 10 and unit noise, metric MDS breaks down at a few hundred dimensions, non-metric MDS roughly two orders later. The simulations confirm the predicted slopes, also with varied cluster sizes and noise types.

Critical weaknesses

Limited novelty, and “fast” is not established. The theory is about metric MDS; the case for non-metric MDS is empirical only, resting on a heuristic argument and simulations. The main practical contribution is the implementation, called “fast” in the title, the abstract and elsewhere, but the only timing comparison is with SMACOF. The implementation is currently CPU only.

Wording stronger than the evidence. Figure 3b is described as metric MDS that “could barely separate the classes”, but it shows three well-separated wedges; the failure reported for random initialisation is not shown. The Discussion states: “metric MDS remains close to a meaningless circular embedding”, yet on Genomes it reaches a triplet accuracy of 0.85, above t-SNE and UMAP.

Limited comparison with existing methods and prior work. On global structure, methods designed for it are absent (e.g. PaCMAP), as are the hybrid methods the paper itself cites as future applications (SQuadMDS-hybrid, DREAMS). On local structure there is no measurement in the benchmark: the paper states that t-SNE and UMAP would win on kNN recall and kNN accuracy without reporting either. The claim that no scalable implementation of non-metric MDS exists is made without discussing scalable ordinal embedding, which addresses the closely related problem of embedding from ordinal comparisons of distances (Anderton & Aslam, ICML 2019; Ghosh et al., NeurIPS 2019).

Questions for authors

Could the authors perform a comparison with PaCMAP and at least one of the hybrid methods cited in the Discussion, and report kNN recall and kNN accuracy for all methods in Table 2? On prior work. The paper states that no scalable implementation of non-metric MDS exists; how does the method relate to scalable ordinal embedding (Anderton & Aslam, ICML 2019; Ghosh et al., NeurIPS 2019)? On “fast”. What evidence supports “fast” beyond the comparison with SMACOF? Could the authors report runtimes, on the same hardware, for all methods in Table 2 and for those requested above (PaCMAP and at least one of the hybrid methods cited in the Discussion)?

2 comments

Dear reviewer, many thanks for your review! We address your comments in the following, and hope this will let you reconsider your score!

Limited novelty [...] The theory is about metric MDS; the case for non-metric MDS is empirical only, resting on a heuristic argument and simulations.

The theory is about metric MDS, but our perturbation results here are novel and motivate the use of non-metric MDS. Furthermore, while our argument on robustness of non-metric MDS is indeed heuristic, it does predict specific power-law exponents which we confirmed in simulations! This is also entirely novel.

The main practical contribution is the implementation, called “fast” in the title, the abstract and elsewhere, but the only timing comparison is with SMACOF.

We have included runtimes for all methods in Table S6. Of course PCA and also neighbor-embedding methods are all much faster than our non-metric MDS. But we do not think this is a relevant comparison here. When we say "fast'', what we mean is that our implementation is much faster than existing implementations (SMACOF). Our implementation actually allows to discuss non-metric MDS embeddings of Tasic and MNIST for the first time! We believe this is an interesting result.

That said, to make our title more precise, we have now replaced "fast'' with "stochastic''. We hope this addresses your concern.

Wording stronger than the evidence. Figure 3b is described as metric MDS that “could barely separate the classes”, but it shows three well-separated wedges; the failure reported for random initialisation is not shown. The Discussion states: “metric MDS remains close to a meaningless circular embedding”, yet on Genomes it reaches a triplet accuracy of 0.85, above t-SNE and UMAP.

Fair enough. We reformulated the first quote as "metric MDS produced only a weak class separation'' and removed "meaningless'' from the second quote. We also added a supplementary figure showing the failure on random initialization (Figure S3).

Limited comparison with existing methods and prior work. On global structure, methods designed for it are absent (e.g. PaCMAP), as are the hybrid methods the paper itself cites as future applications (SQuadMDS-hybrid, DREAMS).

We have added PaCMAP to all tables. In all global metrics, it performs consistently worse than non-metric MDS and also not consistently better than t-SNE/UMAP (Tables 2, S2, S3).

We opted not to include SQuadMDS-hybrid and DREAMS into our benchmark because those methods lack convenient implementations. The former is a custom unpackaged C++ code. The latter is an unpackaged fork of openTSNE which leads to conflicts with openTSNE itself; also, its API is broken in the latest GitHub version. To be sure, we ran DREAMS on Digits: it gave triplet accuracy 0.77, close to t-SNE's 0.75 and much worse than 0.85 of non-metric MDS.

Perhaps more importantly, both SQuadMDS-hybrid and DREAMS combine t-SNE with a global method (PCA or 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 local structure there is no measurement in the benchmark: the paper states that t-SNE and UMAP would win on kNN recall and kNN accuracy without reporting either.

We have added both as Tables S4 and S5. As expected, t-SNE and UMAP win there.

The claim that no scalable implementation of non-metric MDS exists is made without discussing scalable ordinal embedding, which addresses the closely related problem of embedding from ordinal comparisons of distances (Anderton & Aslam, ICML 2019; Ghosh et al., NeurIPS 2019).

Thank you for raising this point! These methods share some similarity to non-metric MDS but are quite different in that they only received a set of triplet comparisons as input, rather than the full distance matrix. We added the following text to the Related Work section:

Non-metric MDS is closely related to ordinal embeddings, which learn an embedding from a set of triplet comparisons such as ``$j$ is closer to $i$ than to $k$''. There are several landmark-based methods that provide approximate implementations suitable for large sample sizes \citep{anderton2019scaling, ghosh2019landmark}. Non-metric MDS also uses only the rank order of the high-dimensional distances, but over all pairs, and not just over a subset of triplets. Therefore we do not include ordinal embeddings into our benchmark comparison.

Another reason why we did not add these methods to the benchmark (at least for now), is that they do not seem to have a convenient packaged implementation. One paper's Github has code in MATLAB, the other only has incomplete C++ code without usage instructions.

We hope that our edits and additional evaluations will address all your concerns!

Thanks very much. My concerns have been correctly addressed. Therefore I have decided to raise my score to 3.

Reviewer_BHuwOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates the behavior of metric multidimensional scaling under high-dimensional distance concentration. It extends a known continuum characterization to finite configurations through a perturbation bound, and uses simulations to argue that non-metric MDS tolerates stronger high-dimensional noise than metric MDS. The authors also develop a stochastic implementation of non-metric MDS that computes distances within mini-batches and periodically fits an isotonic transformation. Experiments on five synthetic and real-world datasets compare embedding quality and demonstrate substantial acceleration over the conventional non-metric implementation.

Critical strengths
  1. Useful analysis of a classical embedding objective. The connection between distance concentration and the characteristic geometry of metric MDS provides an informative explanation of its behavior on noisy high-dimensional data. The distinction between preserving absolute distances and preserving their ordering also motivates a useful empirical investigation of non-metric MDS.
  2. A simple implementation with demonstrated computational and empirical benefits. The stochastic implementation substantially accelerates non-metric MDS while achieving stress values comparable to the reference implementation, and avoids storing the full pairwise distance matrix when feature vectors are available. Non-metric MDS also improves several global-quality metrics over classical MDS, with particularly notable distance-correlation gains on the Genomes and MNIST datasets. These results establish that the method can offer benefits beyond merely correcting deficiencies in the metric MDS optimizer.
Critical weaknesses
  1. The practical case for the additional optimization over classical MDS/PCA remains incomplete. The theoretical failure mode concerns metric stress minimization, not classical MDS, and the latter already performs well in several of the paper’s examples. On noisy blobs, the authors state that PCA essentially recovers the original two-dimensional data; on Tasic, classical and non-metric MDS both achieve triplet accuracy of 0.99, while their Pearson correlations are 0.92 and 0.91, respectively. Non-metric MDS improves Tasic’s Spearman correlation from 0.91 to 0.96, but requires 500 epochs and 37 minutes, with no corresponding classical MDS/PCA runtime reported. Thus, acceleration relative to conventional non-metric MDS does not establish a favorable quality–cost trade-off against simpler alternatives. Moreover, the main quality metrics measure agreement with the potentially noisy input distances, which is not equivalent to recovery of the underlying noise-free structure. Comparisons with t-SNE and UMAP on global metrics provide context, but are less decisive because those methods primarily target local structure. The paper needs a clearer characterization of when non-metric optimization provides practically meaningful gains over PCA and other methods targeting global structure.
  2. The central theoretical contribution requires correction and more careful interpretation. Equation (5) defines the continuum stress as the full expectation of the squared distance residual, whereas Appendix D subsequently uses half of this quantity, including in the proof of Lemma 8 and the finite-sample relation. This produces an inconsistency in the stated stability identity and the interpretation of the constants. The argument may be repairable, but the definitions and resulting bounds need to be made consistent. In addition, proximity of the unlabeled embedding distribution to the limiting disk does not by itself establish loss of label or biological information, and the bound concerns global minimizers rather than arbitrary outputs of a nonconvex optimizer. These distinctions should be reflected in the claims about uninformative embeddings and the motivation for the alternative method.
Questions for authors
  1. Under what data conditions does non-metric MDS offer a meaningful advantage over classical MDS/PCA? Could you report embedding quality, end-to-end runtime, and peak memory under the same computational setup, including initialization costs? Quality-versus-time curves would help assess whether the additional optimization is worthwhile.
  2. On the synthetic datasets, do the improvements persist when evaluated against the known noise-free geometry or latent class structure, rather than only the noisy input distances? Please include classical MDS/PCA in the noise-dimensionality robustness analysis.
  3. On Tasic, what useful structure is recovered beyond the PCA embedding, given the equal triplet accuracy and the compression of neural populations? Could global gains and local losses be quantified together, and compared with a relevant method designed to preserve global structure?
  4. Please reconcile the normalization of the continuum stress in Equation (5) with Appendix D and provide the corrected stability identity and perturbation bound. Please also clarify the distinction between distributional proximity, loss of informative structure, and the behavior of locally optimized embeddings.
3 comments

Dear reviewer, many thanks for your review! We address your comments in the following, and hope this will let you reconsider your score!

The practical case for the additional optimization over classical MDS/PCA remains incomplete.

It is true that on noisy blobs and also on Tasic, classical MDS yields similar triplet accuracy to the non-metric MDS. However, on the Genomes, Digits, and MNIST datasets the non-metric MDS does clearly outperform classical MDS (Table 2). On the Genomes dataset the difference is easy to see by eye and can be relevant for interpretation. Also, on Tasic, kkNN accuracy and Spearman correlation between distances are both better in non-metric MDS compared to classical MDS (Tables S3, S5).

Of course classical MDS is much faster (we now added all the runtimes in Table S6). Whether improved metrics are worth additional runtime cost is to be decided in any concrete application. But we do believe that it is interesting that at least we can now discuss the performance of non-metric MDS on Tasic and MNIST! Prior to our paper, this was not possible.

On Tasic, what useful structure is recovered beyond the PCA embedding[?]

As we write in lines 415--417, non-metric MDS embedding makes it obvious that non-neural cells have very large variability and are similarly far away from the neural cells. This is not visible in PCA. We are not claiming that non-metric MDS is strictly better than PCA, but we do claim that it highlights additional meaningful information about the data.

The central theoretical contribution requires correction

Thank you for carefully reading the theory part. You are right: the main text and Appendix C used the full objective S[ρ]=E(∥X−Y∥−1)2S[\rho]=\mathbb E(\|X-Y\|-1)^2 with S⋆=1−π2/12S^\star=1-\pi^2/12, while Appendix D used half of it. We have now adopted the full objective throughout. This matches the average stress, i.e. the standard raw stress divided by n(n−1)/2n(n-1)/2. All our theoretical conclusions still hold with adapted constants.

In addition, proximity of the unlabeled embedding distribution to the limiting disk does not by itself establish loss of label or biological information, and the bound concerns global minimizers rather than arbitrary outputs of a nonconvex optimizer.

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; new Figure S3). 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.

Could you report end-to-end runtime

Added as Table S6. Of course PCA is much faster than our non-metric MDS. Our point is that our implementation is much faster than SMACOF (Table 1).

On the synthetic datasets, do the improvements persist when evaluated against the known noise-free geometry or latent class structure, rather than only the noisy input distances?

Yes -- the kkNN accuracy (of embeddings starting from random initialization) which we use in our robustness experiments on synthetic data does clearly show the advantage of non-metric over metric MDS.

Please include classical MDS/PCA in the noise-dimensionality robustness analysis.

Done, please see updated figure. Here is the updated text:

For reference, classical MDS (equivalently, PCA) was similarly robust (Figure~\ref{fig:robustness}); random matrix theory suggests that the scaling for classical MDS is also $\Theta(D^4 / \sigma^4)$ \citep{baik2005phase}. Note that in the experiments in this section we used random initializations for metric and non-metric MDS, which is why PCA appears to perform better. In practice, we always initialize MDS with classical MDS, and below we will show that non-metric MDS can outperform PCA on real-world data. The main lesson of this section is that non-metric MDS is more robust to high-dimensional noise than metric MDS.

Could global gains and local losses be quantified together, and compared with a relevant method designed to preserve global structure?

We are not sure which relevant methods the reviewer means here. In response to another reviewer, we added PaCMAP to our evaluation. Specifially for non-metric vs classical MDS on Tasic, classical MDS does not outperform the non-metric MDS in terms of local metrics (kkNN accuracy, kkNN recall; see added Tables S4, S5). But in such local metrics t-SNE and UMAP are anyway the best. Our focus in this work is on global metrics.

Dear reviewer, there are only some hours left until the end of the discussion period. We would really appreciate your response! Let us know if you have any remaining concerns.

Thank you for the additional comparisons. My concerns have largely been addressed, and I appreciate the authors' efforts to improve the scalability and evaluation of non-metric MDS.

However, I remain concerned that the claim that non-metric MDS can "strongly outperform other methods in terms of global structure preservation" is overstated. While this may be justified in comparison with metric MDS and local-preserving methods, relevant methods specifically designed to preserve global or diffusion-based structure, such as PHATE and HeatGeo, have not been evaluated.

I would therefore encourage the authors to qualify this claim to reflect the methods actually benchmarked, or provide further comparisons with relevant global-structure-preserving approaches.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.